Grafelmelet es algoritmusok

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. az ETR-t.
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 az ETR oldalakon lehet.

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.

Ajánlott irodalom:

A fő forrás:

Volt:

32 bites szám kitalálása barkochbával, ennek optimalitása. n bites szám kitalálása barkochbával, ennek optimalitása.(Illusztráció: játék a géppel, Alexander Bogomolny). Hazug barkochba. MAX, MIN, (MAX,MIN) megkeresése páronkénti összehasonlításokkal. A legjobb és a legrosszabb játékos kitalálásának optimalitása: a kavicsos konstrukció.

A legjobb és a második legjobb teniszjátékos kiválasztása.

Rendezés kitalálása barkochbával.

Ordó-jelölések. Rendezéshez legrosszabb esetben log n! összehasonlítás kell. log n! becslései . 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(n log n) összehasonlítással. Összefésüléses rendezés. Két n hosszú sorozat 2n-1 összehasonlítással összefésülhető, es ez optimális is. Rendezés összefésüléssel.

Középső elem megtalálása, a Floyd-Rivest algoritmus

Karacuba-Ofman algoritmus két nagy szám szorzatára. Strassen mátrix-szorzása. (illusztráció: Kirk Pruhs appletje a Karacuba-Ofman polinomszorzásra)

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 es tömbön. A kupac fogalma; DELETE_MIN, INSERT.

Williams és Floyd kupac-rendezése O(n log n) művelettel. Gráfok ábrázolása.

Gráfalgoritmusok: Szélességi gráf-bejárás, ezzel komponensek meghatározása, összefüggőség-vizsgálat, feszítő-erdő megadása.

Egy gráfnak exponenciálisan sok feszítőfája is lehet. Minimális költségű feszítőfa keresése, Prim algoritmusa, kupac-implementáció.

Dijkstra algoritmusa szemléletesen: golyók és fonalak. Dijkstra algoritmusa egy pontból kiinduló minimális költségű utak kiszámítására, kupac implementáció.

Lesz: