Kurzus nemzetközi vendég- és részidős hallgatóknak
- Kar
- Természettudományi Kar
- Szervezet
- TTK Számítógéptudományi Tanszék
- Kód
- dimate1u0um17gm
- Cím
- Diszkrét matematika 1 (gy)
- Tervezett félév
- Őszi
- Meghirdetve
- 2024/25/1
- ECTS
- 3
- Nyelv
- en
- Oktatás célja
- Tudás: a diszkrét matematika főbb fogalmainak elsajátítása Képesség: a tanult algoritmusokat összetett feladatok megoldására is használni tudja Attitűd: igény az alkalmazott matematikai tudás gyarapítására, új alkalmazott matematikai ismeretek megszerzésére, kompetenciák elsajátítására, kifejlesztésére. Törekvés a matematikai ismereteinek minél szélesebb körű alkalmazására Autonómia és felelősség: a diszkrét matematika témakörében elsajátított alapvető ismeretei felhasználásával képes önállóan megválasztani az alkalmazási problémák megoldására alkalmazható módszereket
- Tantárgy tartalma
- Gráfelmélet: gráfok és hipergráfok színezései. Párosításelmélet. Többszörös összefüggőség. Erősen reguláris gráfok, az egészségi feltétel és alkalmazásai. Blokkrendszerek. Véges testek, hibajavító kódok, perfekt kódok. Extremális gráfok, Bondy-Simonovits tétel. Regularitási lemma. Síkbarajzolhatóság, Kuratowski tétel, gráfok lerajzolása felületeken, minorok, Robertson-Seymour elmélet. Leszámláló kombinatorika alapvető kérdései: generátorfüggvények, inverziós formulák részben rendezett halmazokon, rekurziók. Mechanikus összegzés. Klasszikus gráfelméleti leszámlálások, fák, feszítő fák száma. Véletlen módszerek, várható érték módszer. Véletlen gráfok. Testek alkalmazásai: a lineáris algebrai módszer. Kombinatorikus Nullstellensatz
- Számonkérés és értékelés
- gyakorlati jegy
- Ajánlott irodalom
- J. H. van Lint, R.J. Wilson, A course in combinatorics, Cambridge Univ. Press, 1992; 2001. Lovász L.: Kombinatorikai problémák és feladatok, Typotex. Hajnal P.: Gráfelmélet, Polygon, Szeged. R. L. Graham, D. E. Knuth, O. Patashnik, Konkrét matematika, Műszaki Kiadó 1998.