Bonyolultságelmélet előadás


Az előadás látogatása nem kötelező, azonban a vizsga anyaga minden, ami az előadáson elhangzik. Erősen ajánlott azonban ezt az ottlapot figyelemmel kisérni, itt jelennek meg majd a vizsgaidőpontok, elmaradó órák, egyéb hirdetmények.

Ajánlott Lovász László " Bonyolultságelmélet" c. jegyzete, amely a Jegyzetboltban kapható szokott lenni.


1. előadás: 32 bites szám kitalálása barkochbával, hazudós barkochba. MIN, MAX, MINMAX keresés, ezek optimalitása. Beszúrásos rendezés. Döntési fa, rendezés döntési fán. Beszúrás, egy elem beszúrásához n elemű listába felsőegészrész(log (n+1)) összehasonlítás kell, ennyi azonban elég is. Rendezés beszúrásokkal O(nlog n) összehasonlítással. Rendezéshez legrosszabb esetben log n! A log n! becslései. Átlagosan is kell majdnem ennyi összehasonlítás kell.

2. előadás: Ordó-jelölések. Középső elem megtalálása, a Floyd-Rivest algoritmus. Rendezett sorozatok összefésülése, az összefésülési eljárásunk optimalitása. Rendezés összefésüléssel. A legnagyobb és a második legnagyobb szám megtalalása.