Algoritmuselmélet
A tantárgy angol neve: Theory of Algorithms
Adatlap utolsó módosítása: 2017. január 20.
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
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ó.
Az algoritmusok tervezésével, elemzésével kapcsolatos legfontosabb módszerek, készségek elsajátítása, az alapvető számítási modellek megismerése.
1) Mintaillesztés. Naív algoritmus, Rabin-Karp (ujjlenyomatos) algoritmus. A véges automatás megoldás.
2) Determinisztikus és nemdeterminisztikus véges automaták, ezek ekvivalenciája. A reguláris kifejezés fogalma, kapcsolata a reguláris nyelvekkel, véges automatákkal (az automatából reguláris kifejezés irány legfeljebb vázlatosan).
A véges automata mint lexikális elemzők.
3) Környezetfüggetlen nyelvtanok. Levezetési fák, bal- és jobboldali levezetés. Az egyértelműen levezethető szó, egyértelmű nyelvtan, nyelv fogalma, algoritmikus jelentősége.
4) A (nemdeterminisztikus) veremautomata.
A veremautomaták és a környezetfüggetlen nyelvek kapcsolata (részletesen a nyelvtanból automata irány). Az elemzés feladata (parser).
5) A Turing-gép, mint a legáltalánosabb automata. Church-Turing-tézis. A P, NP, coNP osztályok, kapcsolatuk. A Karp-redukció fogalma, NP-teljesség.
6) Cook-Levin-tétel (vázlatosan), a SAT, 3SAT, 3SZÍN NP-teljessége
7) További NP-teljes nyelvek:MAXFTL, H, H-út, Utazóügynök, 3DH, RH, Partíció, Hátizsák, Részgráfizo (nagyrészt csak az NP-beliség bizonyításával)
Nyitott kérdés: a Gráfizo bonyolultsága.
8) A lineáris és az egészértékű programozás feladata. LP polinom idejű (biz. Nélkül),
IP NP- teljes. Korábbi problémák átfogalmazása egészértékű programozássá.
Elágazás és korlátozás (pl. független pontok, színezés)
9) Dinamikus programozás (pl. Hátizsák, leghosszabb közös részsorozat)
10) Közelítő algoritmusok: utazóügynök probléma így is nehéz, az euklideszi változatára 2-közelítő algoritmus, Ládapakolásra a FirstFit algoritmus 2-közelítésének bizonyítása, Ibarra-Kim-tétel (tetszőlegesen jól lehet közelíteni) kimondva.
11) Összehasonlítás alapú rendezések és elemzésük (buborék, beszúrásos, összefésüléses, gyorsrendezés). Alsó becslés a szükséges összehasonlítások számára.
Nem összehasonlítás alapú rendezések és elemzésük: ládarendezés, radix rendezés.
12) Lineáris és bináris keresés, az utóbbi optimalitása.
Keresőfa fogalma, tulajdonságai, hatékonysága.
13) Egy kiegyensúlyozott keresőfa: a piros-fekete fa fogalma, tulajdonsága.
Egy másik hatékony adatszerkezet: a 2-3 fa, illetve a B-fa fogalma, tulajdonságai, előnyei. Hash.
14) Ismétlés, összefoglalás, tartalék.
Heti 2 óra előadás és heti 2 órás gyakorlat.
A szorgalmi időszakban: A félév folyamán egy nagyzárthelyit íratunk. Az aláírás feltétele a zárthelyi dolgozat sikeres teljesítése.
A vizsgaidőszakban: A vizsgajegyet a zárthelyi eredményéből és az írásbeli vizsgán kapott pontszámból alakítjuk ki olyan módon, hogy abba a zárthelyi 40 százalék erejéig, a vizsgán kapott pontszám 60 százalék erejéig számít bele.
Elővizsga: nincs
Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok, TypoTeX Kiadó,
Csima Judit, Friedl Katalin: Nyelvek és automaták, elektronikus jegyzet
A gyakorlatokon más feladatokat dolgozunk fel, mint a többi kurzuson. Kevesebb bevezető, rutin, gyakorló feladat szerepel és több összetettebb, nehezebb, gondolkodtatóbb feladat lesz.
A zh-n és a vizsgán is lesz egy-egy plusz, nehezebb feladat. A jegyek ponthatárát e nélkül határozzuk meg. A (plusz feladat nélkül is elérhető) jeles feletti teljesítményt a zh-n és a vizsgán is 0-15 plusz ponttal értékeljük. Ezeknek a plusz pontoknak az összege, de maximum 20 adja az IMSC pontot.
A tantárgy témájához csatlakozó, de annál lényegesen összetettebb feladatokkal foglalkozó Algoritmus szakkörön való aktív részvétellel is lehet IMSC pontot szerezni (max 10-et úgy, hogy az összeg ne menjen 20 fölé).
Az IMSC-pontok megszerzése a programban nem résztvevő hallgatók számára is biztosított.