Algoritmuselmélet

A tantárgy angol neve: Theory of Algorithms

Adatlap utolsó módosítása: 2017. január 20.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar
Mérnök informatikus szak, BSc képzés
Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZAB01 4 2/2/0/v 4  
3. A tantárgyfelelős személy és tanszék Dr. Friedl Katalin, Számítástudományi és Információelméleti Tanszék
A tantárgy tanszéki weboldala http://cs.bme.hu/algel
4. A tantárgy előadója

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

egyetemi docens

Számítástudományi és Információelméleti Tanszék

Dr. Katona Gyula

egyetemi docens

Számítástudományi és Információelméleti Tanszék

6. Előtanulmányi rend
Kötelező:
(TárgyEredmény( "BMEVISZAA01" , "aláírás" , _ ) = -1
VAGY TárgyEredmény( "BMEVISZAA04" , "aláírás" , _ ) = -1)

ÉS
NEM ( TárgyEredmény( "BMEVISZA213" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZA213", "FELVETEL", AktualisFelev()) > 0
VAGY
TárgyEredmény( "BMEVISZAB03" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZAB03", "FELVETEL", AktualisFelev()) > 0
VAGY
TárgyEredmény( "BMEVISZAB03" , "aláírás" , _ ) = -1)

A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

A kötelező előtanulmányi rendek grafikus formában itt láthatók.

7. A tantárgy célkitűzése

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.

8. A tantárgy részletes tematikája

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.

9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

Heti 2 óra előadás és heti 2 órás gyakorlat.

10. Követelmények

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

11. Pótlási lehetőségek A félév során az arra kijelölt időpontban, valamint a pótlási héten pótzárthelyi írására van lehetőség.
12. Konzultációs lehetőségek Igény szerint.
13. Jegyzet, tankönyv, felhasználható irodalom

Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok, TypoTeX Kiadó,

Csima Judit, Friedl Katalin: Nyelvek és automaták, elektronikus jegyzet

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
Kontakt óra56
Félévközi készülés órákra28
Felkészülés zárthelyire10
Házi feladat elkészítése 
Kijelölt írásos tananyag elsajátítása 
Vizsgafelkészülés26
Összesen120
15. A tantárgy tematikáját kidolgozta

Név:

Beosztás:

Tanszék, Int.:

Dr. Friedl Katalin

egyetemi docens

Számítástudományi és Információelméleti Tanszék

IMSc tematika és módszer

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.

IMSc pontozás

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.