Online algoritmusok

Szorgalmi: feladat

Teljesítés feltétele (nappali 2011)

Két darab 50 pontos ZH-ból összesen 40 pont elérése.
Kollokvium: szóbeli vizsga, ahol 100 pont érhető el. Legalább 50 pontot el kell érni.
Összesen legalább 100 pontot kell elérni.
Osztályzat: 0-100 (1), 101-125 (2), 126-150 (3), 151-175 (4), 176-200 (5).

Teljesítés feltétele (levelező 2012)

ZH nincs a gyakorlati számonkérés a kollokviumba van építve
Kollokvium: Három részből áll. Az első részben feladatokat kell megoldani, 100 pont szerezhető és minimum 40-et el kell érni. A második rész az egyszerűbb kérdésekből szerezhető 70 pont, amiből minimum 40 pontot el kell érni. Végűl a harmadik rész egy bonyolultabb tétel bizonyítással, ami 30 pontot érhet.
Osztályzat: 0-100 (1), 101-125 (2), 126-150 (3), 151-175 (4), 176-200 (5).

Eredmények

Tematika

Tematika On-line problémáról beszélünk abban az esetben ha az inputot csak részenként ismerjük meg, és az algoritmusnak az aktuális döntéseket az input eddig megismert részei alapján a további részekre vonatkozó információk nélkül kell meghoznia. Az on-line modelleknek sok alkalmazása található az elméleti számítástudomány, az operációkutatás és a közgazdaságtan területein. A kurzus fő célja az on-line algoritmusok elemzésénél használt technikák módszerek (elsősorban a versenyképességi analízis) bemutatása. A módszereket néhány klasszikusabb területen (1990-es évek) és néhány újabb eredményen (2000-es évek) keresztül mutatjuk be. A tárgyalt témák

Bevezetés, alapfogalmak, síbérlés
memóriakezelés (paging) probléma, bélyegző algoritmusok,
véletlenített on-line algoritmusok, lapozás, síbérlés
ütemezési feladatok, lista modell, idő modell,
ládapakolás és általánosításai, súlyfüggvénytechnika, alsó korlátok (IP módszer)
lista karbantartás
k-szerver probléma, alsó korlát, algoritmus a fákra, munkafüggvény algoritmus
online algoritmusok a számítógépes hálozatok témakörében
a versenyképességi analízis általánosításai, egyéb módszerek

Oktatási segédanyagok

Levelezős kérdés és tételsor (ugyanaz, mint 2011-ben)

kérdéssor
tételsor
Levelező hallgatóknál az első, gyakorlati részben végrehajtás konkrét inputon lehet: k-szerver feladat algoritmusai (EGYENSÚLY, DUPLA LEFEDŐ), Intervallum algoritmus az idő ütemezési modellben, NFS_r algoritmus a sávpakolásra, ébresztő algoritmus a nyugtázásra, HÁZIÚR algoritmus weblapletöltésnél. Ezekből három feladat lesz 50 pontért. Továbbá lesz két bizonyítás is 50 pontért, az egyik egy véletlenített síbérlési algoritmusra.