Diszkrét matematika

1. Sablon: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 ($\wedge$)
  • Vagy ($\vee$)
  • Negáció ($\mathrm{\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.

Sablon:-ford-

• Sablon:En: Sablon:T
• Sablon:Fr: Sablon:T
• Sablon:De: Sablon:T
• Sablon:Ru: Sablon:T