Belépés címtáras azonosítással
magyar nyelvű adatlap
angol nyelvű adatlap
Algoritmusok és bonyolultságuk
A tantárgy angol neve: Algorithms and Complexity
Adatlap utolsó módosítása: 2014. október 3.
Mérnökinformatikus szak, MSc képzés
Számításelmélet mellékspecializáció
Név:
Beosztás:
Tanszék, Int.:
Dr. Csima Judit
egyetemi docens
Számítástudományi és Információelméleti Tanszék
Dr. Friedl Katalin
Dr. Katona Gyula
Alapvető algoritmikus technikák
A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.
A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.
Ezt a tárgyat nem vehetik fel, akik a korábbi változatot (VISZM143) vagy a VISZM031 kódú “ Algoritmusok és bonyolultságuk – matematikusoknak” című tárgyat teljesítették.
A tantárgy célja az algoritmikus gondolkodás továbbfejlesztése, további módszerek, technikák megismerése. A hallgatók betekintést kapnak a témakör modern irányzataiba, az új és jövőbeli eszközök (párhuzamos számítások, kvantumszámítógépek) által megoldható kérdésekre, felvetett problémákra. Cél, hogy mindenki egy általa választott témakört önállóan is feldolgozzon.
1) A várható témakörök, előadások megbeszélése. Interaktív bizonyítások: az NP kiterjesztése interaktív algoritmusok segítségével. Interakció egy erős és egy gyenge fél között, az AM és az IP nyelvosztály. PCP (Probabilistically checkable proofs)
2) Kommunikációs bonyolultság: hogyan lehet együttműködve számolni minimális információcserével. Kapcsolata a függvény mátrixával (mátrix felbontás, rang). Nemdeterminisztikus bonyolultság, és kapcsolata a determinisztikus bonyolultsággal. Példák véletlent használó protokollokra, hatékonyságuk.
3) Geometriai algoritmusok a síkban: Fordulási irány megállapítása osztás nélkül. Hatékony algoritmusok a konvex burok meghatározására. A legközelebbi pontpár megtalálása.
4) A keresés és rendezési algoritmusok továbbfejlesztése: Listában a középső (k-adik) elem megtalálása összehasonlításokkal. Algoritmus a listabeli elemek nagyság szerinti sorszámának meghatározására (rang számolása). Intervallumok hatékony tárolása.
5) Mintaillesztés: KMP-algoritmus, Boyer-Moore- algoritmus. Mintaillesztő automata. Mintaillesztés hibák esetén. A szerkesztési távolság és annak meghatározása dinamikus programozással.
6) Párhuzamos algoritmusok: A PRAM-modell különböző változatai, egyszerű függvények hatékony számolása az eltérő modellekben. Bináris fa alapú algoritmusok. A processzorszám csökkentése: Brent-elv.
7) Párhuzamos algoritmus a rendezési feladatra (Batcher). A prefix-számítás eljárása és ennek alkalmazásai. A rang meghatározása párhuzamosan.
8) Elosztott algoritmusok: az elméleti modell. Algoritmusok a gyűrűben való vezetőválasztásra szinkron és aszinkron esetben. Általánosítás tetszőleges gráfra. Alsó becslés az üzenetek számára. Az egyezségre jutás feladata.
9) Elosztott algoritmusok hibákkal. A vonalhiba esete. Algoritmus processzorok leállási hibája esetén. Rosszindulatú (bizánci) hibák kezelése. Felső becslések az egyezséget még lehetővé tevő hibák számára.
10) Hálózati topológiák gráfelméleti szempontból: rács, CCC, pillangó, Benes-hálózat gráfelméleti tulajdonságai (legrövidebb utak, átmérő, vágások, összefüggőségi szám) egymásba ágyazhatóságuk, algoritmikus szempontok.
11) Véletlen gráfok: Különböző modellek, ezek alaptulajdonságai (fokszámok, utak, összefüggőség). A véletlen gráfok, mint hálózati modellek.
12) Paraméteres bonyolultság: NP-nehéz, de paraméteresen megoldható feladatok. Keresőfa mélységének korlátozása. A gráfminor tétel és következményei. Kernelizációs módzserek. W[1]-teljesség.
13) On-line algoritmusok: modell, hatékonyság mérése, listaelérési feladat. Egyszerű, sokat használt ütemező algoritmusok és elemzésük.
14) Kvantumszámítás: elméleti modell, lineáris algebrai eszköztár. Egyszerű algoritmusok (teleportálás, Deutsch-Józsa). A Fourier-transzformáció haszna. Prímfelbontás. Titkosítás kvantumeszközök esetén.
A tananyagot részben szeminárium-szerűen, hallgatók által tartott órákkal dolgozzuk fel. A témák sorrendje, és az érdeklődéstől függően a pontos köre is évről évre változhat valamennyit. Az aktuális menetrendet az első órán megbeszéljük.
aktív részvétel az órákon, valamint előadás, beszámoló tartása.
A vizsgaidőszakban: nincs
Elővizsga:
Előzetes egyeztetés szerint.
T. Corman, C. Leiserson, R. Rivest, C. Stein: Új algoritmusok, Scolar Kiadó, 2003.
H. Attiya: Distributed Computing lecture notes
J. Flum, M. Grohe: Parameterized Complexity Theory, Springer 2006.
A. Gibbons, W. Rytter: Efficient Parallel Algorithms, Cambridge University Press, 1988.
