Algorithms and Their Complexity lec. (MSc)
Tanszék: Halmazelmélet és Matematikai Logika Tanszék
Tematika:
Dinamikus programozás, példák. Algoritmusok javításokkal, folyamok, Dinic algoritmusa. Algoritmusok amortizált analízise, példák. Adatstruktúrák, Fibonacci-kupacok. Adattömörítés, LZW algoritmus. Prím tesztelés, AKS algoritmus. Turing-gépek, nem-determiniumus. Tér és idő bonyolultság. Bonyolultsági osztályok: L, NL, P, NP, PSPACE és kapcsolatuk. Redukciók és teljesség. NP-teljes problémák. Véletlen algoritmusok és bonyolultsági osztályaik.
Előfeltétel: nincs.
Helyettesítő tárgyak: nincsenek.
Előadás:
Kurzuskód: MMNKEN11E Kredit: 6 Óraszám: 2 hetente