Algoritmuselmélet

Törzsanyag előadás Matematikus és Alkalmazott Matematikus MSc hallgatóknak

2019 ősz

Előadó: Király Zoltán

Kedd 12:15-13:45, D.0.312.


Csak a hallgatóimnak / Only for my students


Hirdetmények


Ajánlott irodalom


1. előadás (IX. 10.)

Kupacépítés. Középső elem keresése. Gyorsrendezés és elemzése.


2. előadás (IX. 17.)

Leszámláló és számjegyes (radix) rendezés.
Számolás nagy számokkal, hatványozás. mod m számítások. Euklideszi algoritmus, kiterjesztett Euklideszi algoritmus, mod m osztás, kínai maradék-tétel. Alkalmazásuk a prímtesztelésben és az RSA titkosírásban.


3. előadás (IX. 24.)

Karacuba szorzási módszere (gyakorlaton).
Polinom szorzás, diszkrét Fourier-transzformáció. Gyors Fourier-transzformáció.
Két n bites szám szorzása O(n\log^3 n) bitművelettel.
Schönhage-Strassen szorzás.


4. előadás (X. 1.)

Dinamikus programozás: Fibonacci számok, hátizsák feladat.
Optimális bináris keresőfa megtalálása.
Adattömörítés: Huffman-kód és Lempel-Ziv tömörítési eljárása (gyakorlaton).
Gráfok tárolása.


5. előadás (X. 8.)

Szélességi keresés lépésszáma, komponensek és legrövidebb utak meghatározása.
Szélességi keresés alkalmazásai. Mélységi keresés és alkalmazásai. (Gyakorlaton).
Alsó becslések összefüggőség eldöntésére.

Legrövidebb utak keresése, Dijkstra algoritmusa. Futási idő. Dijkstra kül. kupacokkal, KULCS-CSÖK, d-edfokú kupac.
Prim alg.
Dijkstra alkalmazásai: 1. legbiztonságosabb út, 2. legszélesebb út. 3. legrövidebb utak közül legszélesebb. 4. idő-függő legrövidebb út.


6. előadás (X. 15.)

Bellman-Ford módszer legrövidebb utak keresésére, Bellman-Ford elemzése, javítása. Negatív kör visszakeresése.

Legövidebb út konzervatív irányítatlan gráfban (vázlatosan).
Megengedett potenciál. Johnson algoritmusa legrövidebb út keresésére minden pontpár között.
Gyakorlaton: Floyd algoritmusa.
Min. átlagú kör (Karp).
Suurballe algoritmusa legrövidebb útpár keresésére egy célcsúcsra.


7. előadás (X. 22.)

Suurballe és Tarjan algoritmusa: legrövidebb útpár egy forrásból minden célcsúcsra. Az utak visszakeresése, Suurballe és Tarjan algoritmusának jósága, megvalósítása hatékonyan. Az algoritmus lépésszámelemzése.


8. előadás (XI. 5.)

ST-alg. elemzésének legvége.

Hopcroft és Karp algoritmusa.
Folyamok, Dinic alg. Diszjunkt utak.
Többtermékes folyamok.
Japán tétel. NP-teljességi állítások. Vágásfeltétel.


9. előadás (XI. 12.)

Hu és Rothschild-Whinston tételei.

Stabil házasítás páros gráfban.
Stabil házasítás és az egyetemi felvételi rendszer.
Stabil szobatárs probléma: Irving algoritmusa nem páros gráfban teljes stabil párosítás keresésére.


10. előadás (XI. 19.)

Irving algoritmusának a vége.

Hálózati kódok. A lineáris hálózati kódok alaptétele.


11. előadás (XI. 26.)

Közelítő algoritmusok. Alapdefiníciók, példák. Approximációs sémák: PTAS, EPTAS és FPTAS.
Közelíthetetlenség, APX, APX-teljesség.
Gyakorlaton: TSP, Metrikus TSP, 3/2 közelítés metrikus TSP-re, Ládapakolás.

Ibarra-Kim FPTAS hátizsákra.
Max stabil párosítás (csak arra az esetre, ha döntetlenek egy oldalon vannak).
Halmazfedés, súlyozott lefogó csúcshalmaz. LP relaxáció (halmazfedés).
Egészségi hézag, randomizált/iteratív kerekítés.
Beck-Fiala tétel.


12. előadás (XII. 3.)

Beck-Fiala tétel algoritmikusan.

Fix paraméterrel megoldható feladatok. Steiner fa FPT dinamikus programozással.
Két alap-megoldás lefogó csúcshalmazra. Javított döntési fa.

Kernel-tétel (kimondva).
W[1]-teljesség.

Korona-redukció, jobb kernel (3k csúcsú). (A jegyzetben tanácsolt elolvasni a 2k csúcsú kernel készítéséről szóló részt is).


13. előadás (XII. 10.)

Párhuzamos számítások: modellek, Brent 1. tétele, minimum loglog n-ben.
Rendező hálózatok, összefésülő rendezés (gyakorlaton).
Összeadás, szorzás, Brent 2. tétele.
Összefüggőség, mátrix-szorzások és alkalmazásaik.