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