Az ezen oldalon levő tematikából kap
mindenki két tételt, távolabb levő helyekről.
A sikeres vizsga feltételei:
A két kiadott tétel alapos ismerete, különösen:
A definíciók és a tételek pontos ismerete,
A tétel bizonyításában lényeges eredmény elérése a kettes, a
bizonyítás lényegében történő befejezése nagyobb hiánnyal
a hármas, apró hiánnyal a négyes, hiánytalanul az ötös
szinthez.
Hiányosság a definíciókban illetve a tételek kimondásában nem megengedett (azaz rögtön elégtelen a hibás definíció illetve állítás kimondása).
Vizsgaidőpontok: Ld. a Neptunt.
Minden vizsga a Déli tömb 3-614-es
szoba környékén lesz, a szoba ajtaja melletti táblára lesz
kirakva a vizsga reggelén a vizsga helye. A vizsgára jelentkezni illetve törölni
magad a Neptunban lehet.
A vizsgák 9:30-kor kezdődnek.
A vizsga anyaga minden, ami az
előadáson elhangzik. Az ajánlott irodalomban minden elhangzott
tétel megtalálható, sokszor azonban más, hosszabb, bonyolultabb
bizonyítással. Vizsgán természetesen akármilyen helyes bizonyítást
elfogadok.
Cormen, Leiserson, Rivest: Algoritmusok, vagy az Új Algoritmusok c. könyve
Gács-Lovász: Algoritmusok Katona-Recski-Szabó: A Számítástudomány alapjai Aho-Hopcroft-Ullman: Számítógépalgoritmusok tervezése és analízise Knuth: A számítógépprogramozás művészete Lawler: Kombinatorikus Optimalizálás: Hálózatok és matroidok Rónyai, Ivanyos, Szabó: Algoritmusok jegyzet (BME jegyzete)
Dinamikus programozás: maximális intervallum-összeg lineáris időben. Egy 0-1 mátrixban a legnagyobb egybefüggő, négyzet alakú, csupa-1-es részmátrix megtalálása lineáris időben.Mátrix-szorzás optimális zárójelezése, a naiv algoritmus és a dinamikus programmal elérhető lépésszám összehasonlítása.
A
hátizsák-probléma, megoldása dinamikus programmal. Apró
értékek esetén az algoritmus polinomiális. Ibarra és Kim skalázási eljárása.
Adatok tárolása: láncolt lista és tömb. Beszúrásos rendezés láncolt listán és tömbön. A kupac fogalma; DELETE_MIN, INSERT.