diszkrét matematika

• IPA:

diszkrét matematika

1. (matematika) A diszkrét szó a matematikában a folytonos ellentéte. Olyan dolgok diszkrétek, amelyek nincsenek egymáshoz tetszőlegesen közel, hanem „hézagok” vannak közöttük. Például a valós számok folytonosan töltik ki a számegyenest, ellenben az egész számok diszkréten helyezkednek el. A diszkrét matematikához szokták sorolni a kombinatorikát és gráfelméletet.

A diszkrét matematika a matematika egy olyan területe, amely az olyan struktúraival foglalkozik, amelyek nem folytonosak. Ide tartoznak a halmazelélet, gráfelmélet, kombinatorika, logika és algoritmusok.

A halmazelélet a matematika alapjait képezi, és halmazokkal, azok műveleteivel foglalkozik.

• Halmaz: Egy objektumokból álló csoport, például ${\displaystyle A=\{1,2,3\}}$.
• Műveletek:
  • Unio: ${\displaystyle A\cup B}$
  • Metszet: ${\displaystyle A\cap B}$
  • Különbség: ${\displaystyle A\setminus B}$
  • Komplementer: ${\displaystyle A^{c}}$

A logika a formális érvelés szabályaival foglalkozik.

• Logikai műveletek:
  • És (${\displaystyle \land }$)
  • Vagy (${\displaystyle \lor }$)
  • Negáció (${\displaystyle \neg }$)
• Igazságtáblák: Az és és vagy műveletek kombinációinak igazságértékét mutatják.

A kombinatorika a halmazok részelemeivel és azok kombinációival foglalkozik.

• Permutációk: Az elemek sorrendjének összes lehetséges variációja. ${\displaystyle P(n)=n!}$
• Kombinációk: Az elemek sorrend nélküli kiválasztása. ${\displaystyle C(n,k)={\frac {n!}{k!(n-k)!}}}$
• Binomiális tétel: ${\displaystyle (a+b)^{n}=\sum _{k=0}^{n}C(n,k)a^{n-k}b^{k}}$

A gráfelmélet a csúcsokból és élekből álló struktúrákkal foglalkozik.

• Gráf: ${\displaystyle G=(V,E)}$, ahol ${\displaystyle V}$ a csúcsok halmaza, ${\displaystyle E}$ pedig az élek halmaza.
• Gráf típusai:
  • Irányított gráf
  • Irányítatlan gráf
  • Súlyozott gráf
• Euler-kör: Egy olyan kör, amely minden élet pontosan egyszer tartalmaz.
• Hamilton-kör: Egy olyan kör, amely minden csúcspontot pontosan egyszer tartalmaz.

Az algoritmus egy lépésről lépésre történő utasításhalmaz, amely egy adott probléma megoldására szolgál.

• Időbonyolultság: Egy algoritmus futási idejének mérése a bemenet méretének függvényében.
• Térbonyolultság: Az algoritmus által használt memória mérése.
• Híres algoritmusok:
  • Dijkstra algoritmus: legrövidebb út keresése
  • Prím algoritmus: minimális feszítő fa keresése

Ha ${\displaystyle n}$ tárgyat ${\displaystyle k}$ rekeszbe helyezünk és ${\displaystyle n>k}$, akkor legalább egy rekeszbe több mint egy tárgy kerül.

A Ramsey-tétel szerint egy elég nagy gráfban mindig találhatóak bizonyos észerű módon definiált struktúrák, például teljes algráfok.

• Számítástechnika: adatszerkezetek, titkosítási algoritmusok.
• Hálózatelmélet: Internet protokollok, szociális hálózatok elemzése.
• Kódelmélet: hibajavító kódok tervezése.
• Kombinatorikus optimalizálás: pl. utazó ügynök probléma.

• angol: discrete mathematics (en)
• francia: mathématiques discrètes (fr)
• német: diskrete Mathematik (de)
• orosz: дискретная математика (ru) (diskretnaja matematika)

• diszkrét matematika - Értelmező szótár (MEK)
• diszkrét matematika - Etimológiai szótár (UMIL)
• diszkrét matematika - Szótár.net (hu-hu)
• diszkrét matematika - DeepL (hu-de)
• diszkrét matematika - Яндекс (hu-ru)
• diszkrét matematika - Google (hu-en)
• diszkrét matematika - Helyesírási szótár (MTA)
• diszkrét matematika - Wikidata
• diszkrét matematika - Wikipédia (magyar)