Kupacépítés. Középső elem keresése. Gyorsrendezés és elemzése.
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.
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.
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.
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.
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.
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.
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.
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.
Irving algoritmusának a vége.
Hálózati kódok.
A lineáris hálózati kódok alaptétele.
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.
Beck-Fiala tétel algoritmikusan.
Fix paraméterrel megoldható feladatok. Steiner fa FPT dinamikus programozással.
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).
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.