Teaching / Oktatás

A számítástudomány alapjai (BME villamosmérnök alapképzés, Hatvan)

Az 1. ZH-t október 15-én, szombaton írjuk, anyaga az 1-5. héten vett témakörök.

A 2. ZH-t november 26-án, szombaton írjuk, anyaga a 6-11. héten vett témakörök.

• 1. hét
  • EA: Permutációk, variációk, kombinációk, mind ismétléssel és ismétlés nélkül. Kiszámításuk, példák. A binomiális tétel és bizonyítása.
  • GY: 2, 3, 10, 12, 13, 19, 20
  • Jegyzet: 15-19.o., 1.2.1 fejezet. Megjegyzés 1.25/1,2,3 kell, Következmény 1.30 nem kell.
  • HF: 14, 21
• 2. hét
  • EA: Gráfelméleti alapfogalmak. Gráfok fokszámösszege bizonyítással, fák egyszerűbb tulajdonságai. Minimális költségű feszítőfa: Kruskal algoritmus és a helyességének bizonyítása.
  • GY: 3, 6, 7, 14, 16, 20, 22
  • Jegyzet: 62-67.o., 3.1, 3.2.1 és 3.2.3 fejezetek. Tétel 3.13, Állítás 3.18, Def 3.19, Köv 3.30, Def. 3.32, Alk 3.46 nem kell. Állítás 3.29-hez csak vázlatos bizonyítás (egy-két mondat) kell. A normális fát (Def 3.47) el kell tudni mesélni, informálisan, ahogy a jegyzetben is szerepel. Alk. 3.48. matematikai ötlete (áramforrás = magas költség, feszültségforrás = alacsony költség) kell.
  • HF: 9 vagy 12, szabad választás szerint
• 3. hét
  • EA: Legszélesebb út keresése irányítatlan gráfban. Legrövidebb utak keresése, BFS. Dijkstra, Ford és Floyd algoritmusok.
  • GY: 3. feladatsor: 1, 8, 9, 10. 4. feladatsor: 1, 3, 6.
  • Jegyzet: 82-90. o., 3.4 fejezet, a 3.70 Tétel bizonyításának végéig.
  • HF: 3\4 vagy 4\2, szabad választás szerint
• 4. hét
  • EA: Mélységi keresés, irányított körök keresése, PERT-módszer és helyességének bizonyítása.
  • GY: 5. feladatsor: 3, 5, 6, 8. 6. feladatsor:1.
  • Jegyzet: 94-99.o., a 3.4.3 fejezet.
  • HF: 5\7 vagy 6\1 második gráfja vagy 6\3.
• 5. hét
  • EA: Euler-séta és körséta, létezésének szükséges és elégséges feltétele (összefüggő gráf esetén). Hamilton-kör és út fogalma. Szükséges, illetve elégséges feltételek Hamilton-kör létezésére: Dirac és Ore tételei ill. komponensszám pontelhagyások esetén.
  • GY: 6. feladatsor:
  • Jegyzet: 75-82.o., a 3.3 fejezet.
  • HF: a ZH-ra való tekintettel nincs
• 6. hét
  • EA: Gráfok színezése, klikkméret és kromatikus szám viszonya. Páros gráf fogalma. Páros gráf alternatív definíciója (minden köre páros) és bizonyítása.
  • GY: ZH miatt elmaradt
  • Jegyzet: 128-130.o., a 3.7 fejezet eleje. 3.150 és 3.151. nem kell, 3.152 bizonyítás nélkül volt. 110-111.o., a 3.5.2 fejezet eleje a 3.102. Def-ig.
  • HF: az elmaradt gyakra való tekintettel nincs
• 7. hét
  • EA: Párosítások, Hall-tétel bizonyítással, algoritmus maximális párosítás keresésére páros gráfban. Független/lefogó pont-/élhalmazok, Kőnig és Gallai tételei bizonyítással.
  • GY: 7. feladatsor: 1, 4, 5. 8. feladatsor: 1, 2, 4, 6.
  • Jegyzet: 111-117. o., a 3.5.2 fejezet maradéka a 3.114-gyel bezáróan. Vigyázat! A jegyzetben kicsit más bizonyítás olvasható, mint amit órán vettünk. Mindkét bizonyítás megfelelő vizsgafelkészüléshez, csak ne keverjük őket.
  • HF: 8/9 vagy 8/11.
• 8. hét
  • EA: Hálózati folyamok, Ford-Fulkerson tétel, algoritmus maximális folyam keresése, egészértékűségi lemma. Többtermelős, többfogyasztós hálózatok, csúcskapacitások és irányítatlan élek visszavezetése szokásos hálózatra.
  • GY: 7. feladatsor: 13, 14, 18.
  • Jegyzet: 99-105. o., a 3.5. fejezet, a 3.5.1-ig (az már nem).
  • HF: 13/2 vagy 21.
• 9. hét
  • EA: Síkbarajzolhatóság, gömbre rajzolhatóság. Az Euler-féle poliédertétel és következményei egyszerű, síkbarajzolható gráfokra. Kuratowski gráfok, topologikus izomorfia, Kuratowski tétele. Síkbarajzolt gráf duálisa. Elvágó él, vágás. A duális gráf tulajdonságai (élszám, csúcsszám, összefüggőség, kör-vágás dualitás). Síkgráfok kromatikus száma, ötszíntétel bizonyítással.
  • GY: 9/16, 18, 19, 22
  • Jegyzet: 118-124. o., a 3.135. Tétel bizonyításával bezáróan. 132-134. o., a 3.163. Tétel bizonyításával bezáróan.
  • HF: 9/25 vagy 9/26
• 10. hét
  • EA: Oszthatóság, maradékos osztás. Euklideszi algoritmus, prímek, számelmélet alaptétele, osztók száma. Tételek a prímek eloszlásáról. Kongruenciák, maradékrendszerek, lineáris kongruenciák megoldása.
  • GY: 10/9, 17, 11/2 (más számokkal).
  • Jegyzet: 142-149.o. A 4.13-as következmény nem kell, a 4.23. tételt a 11. előadáson vettük.
  • HF: óratorlódás miatt nincsen
• 11. hét (A 10. hét szombatján megtartva)
  • EA: Kongruenciák, maradékrendszerek, lineáris kongruenciák megoldása két módszerrel (ekvivalens átalakítások és euklideszi algoritmus).
  • GY: 11/11, 11/12.
  • Jegyzet: 150-151 és 155-157.o. A 4.3 fejezetet egyáltalán nem vettük.
  • HF: zh előtt közvetlenül nincsen
• 12. hét
  • EA: Algoritmusok bonyolultsága (input mérete, algoritmus lépésszáma az inputméret függvényében, polinomidejű algoritmus), döntési problémák.
  • GY: ZH volt
  • Jegyzet: 189-193.o. 6.4.1. fejezetben szereplő példákból csak az összeadást kell részletesen tudni.
  • HF: ZH volt
• 13. hét
  • EA: P, NP, co-NP bonyolultsági osztályok fogalma, feltételezett viszonyuk, példa ilyen problémákra. Polinomiális visszavezethetőség (Karp-redukció), NP-teljesség, Cook-Levin tétel, nevezetes NP-teljes problémák: SAT, HAM, 3-SZÍN, k-SZÍN, MAXFTN, MAXKLIKK.
  • GY: SAT, HAM, 3-SZÍN, k-SZÍN, MAXFTN, MAXKLIKK visszavezetések
  • Jegyzet: 194-200.o
  • HF: nincs
• 14. hét
  • EA: Számelméleti algoritmusok: alapműveletek, (modulo m) hatványozás és az euklideszi algoritmus lépésszáma. Prímtesztelés, Fermat-teszt. Nyilvános kulcsú titkosírás, digitális aláírás. Az RSA titkosítási módszer.
  • GY:
  • Jegyzet: 202-208.o.
  • HF: nincs