diszkrét matematika

Magyar

Kiejtés

• IPA: [ ˈdiskreːtmɒtɛmɒtikɒ]

Főnév

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.

Alapfogalmak

Halmazelélet

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

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

Logika

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

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

Kombinatorika

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. $P(n)=n!$
• Kombinációk: Az elemek sorrend nélküli kiválasztása. $C(n,k)={\frac {n!}{k!(n-k)!}}$
• Binomiális tétel: $(a+b)^{n}=\sum _{k=0}^{n}C(n,k)a^{n-k}b^{k}$

Gráfelmélet

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

• Gráf: $G=(V,E)$, ahol $V$ a csúcsok halmaza, $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.

Algoritmusok

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

Fontos tételek

Pigeonhole-elv

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

Ramsey-tétel

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.

Alkalmazások

• 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.

Fordítások

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

További információk

• 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)