Algoritmuselmélet

A tantárgy angol neve: Theory of Algorithms

Adatlap utolsó módosítása: 2022. augusztus 24.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

Mérnökinformatikus BSC

kötelező tárgy 
Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
VISZAA08 2 2/2/0/f 5  
3. A tantárgyfelelős személy és tanszék Dr. Katona Gyula,
A tantárgy tanszéki weboldala http://www.cs.bme.hu/algel
4. A tantárgy előadója
dr. Csima Judit egyetemi docens SZIT 
dr. Friedl Katalin egyetemi docens 
dr. Katona Gyula egyetemi docens SZIT  
dr. Kaszanitzky Viktória, egyetemi docens SZIT
dr. Sali Attila, egyetemi docens SZIT 

 
5. A tantárgy az alábbi témakörök ismeretére épít gráfelmélet, középiskolai matematika 
6. Előtanulmányi rend
Kötelező:

(TárgyTeljesítve_Képzésen("BMEVISZAA04") VAGY
TárgyTeljesítve_Képzésen("BMEVISZAA01") VAGY
Felvetel("BMEVISZAA04") )


ÉS

NEM ( TárgyTeljesítve_Képzésen("BMEVISZAB03") )

ÉS

( Kepzes("5N-A8") VAGY
Kepzes("5NAA8"))

VAGY EgyenCsoportTagja("Kreditpótlás_2023/24/2 ")

VAGY
(Kepzes("9N-AM06")ÉS
TargyEredmeny("BMEVISZA025" , "jegy" , _ ) >= 2 ÉS
TargyEredmeny("BMETE91AM43" , "jegy" , _ ) >= 2 ÉS
(TargyEredmeny("BMETE91AM57" , "jegy" , _ ) >= 2 VAGY
TargyEredmeny("BMETE91AM57", "FELVETEL", AktualisFelev()) > 0))

VAGY

(Kepzes("9NAAM17")ÉS
TargyEredmeny("BMEVISZA025" , "jegy" , _ ) >= 2 ÉS
TargyEredmeny("BMETE91AM43" , "jegy" , _ ) >= 2 ÉS
(TargyEredmeny("BMETE91AM57" , "jegy" , _ ) >= 2 VAGY
TargyEredmeny("BMETE91AM57", "FELVETEL", AktualisFelev()) > 0))

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ó.

7. A tantárgy célkitűzése
(K1) Ismeret szint: 
a témakör fogalmainak felidézése, felsorolása, felületes bemutatása. 

(K2) Megértés szint: 
magyarázatok, összefüggések ismerete, esetek felismerése, besorolása. 

(K3) Alkalmazás szint: 
problémamegoldás ismeretek alkalmazásával, példák, feladatok önálló megoldása. 

(K4) Konstrukciós szint: 
problémaelemzés, megoldási alternatívák felállítása, összevetése, választás, indoklás. 
8. A tantárgy részletes tematikája
1. Minimum, maximum keresés n-1 lépésben, kiválasztásos rendezés, függvények nagyságrendje, Ordo jelölés, egyszerű rekurziós egyenletek megoldása, összefésüléses rendezés. 
 
2. Ö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. 
 
3. Gráfok megadása mátrixszal, illetve éllistával, alapműveletek lépésszáma gráfokban, mélységi keresés, irányított-körmentes gráfok (DAG), ezek felismerése, 
 
4. Topologikus sorrend meghatározása, legrövidebb és leghosszabb út DAGban 
 
5. Dinamikus programozás, hátizsák feladat, maximális összegű intervallum 
 
6. A Dijkstra-algoritmus és helyességének bizonyítása 
 
7. Adatszerkezetek: bináris fa és bejárásai, kupac, Dijsktra algoritmus kupaccal 

8. Bináris keresőfa, piros-fekete fa, 2-3-fa, B-fa 
 
9. Vödrös hashelés, hashelés nyitott címzéssel 
 
10. Kruskal implementációs részletei, lépésszáma, Prim-algoritmus 
 
11. Eldöntési problémák, hatékony tanúsítvány, a P, NP, coNP problémaosztályok definíciói és kapcsolatuk 

12.A Karp-redukció és tulajdonságai, NP-teljesség, példák NP-teljes problémákra 
 
13. Közelítő algoritmusok, epszilon közelítés, ládapakolás, FirstFit algoritmus, FirstFitDecreasing algoritmus, utazóügynök probléma: általában és az euklideszi változat, elágazás-és-korlátozás  
 
9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) A tárgyból heti 2 óra előadást és heti 2 óra gyakorlatot tartunk.
10. Követelmények
A félév során 2 zárthelyit iratunk. A félév teljesítésének feltétele: mindkét zárthelyin legalább 40 %-os teljesítmény. A végső jegy (teljesítés esetén) a  zárthelyik átlagából adódik. 

11. Pótlási lehetőségek
A szorgalmi időszak során minden zárthelyi dolgozathoz lesz pótlási (javítási) lehetőség. 
 
A pótlási héten egyetlen alkalom lesz, amikor egy tetszőleges zh dolgozat pótolható.  
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ó 
Thomas H. Cormen,  Charles E. Leiserson , Ronald L. Rivest,  Clifford Stein: Új algoritmusok Scolar Kiadó, 2003 
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árthelyire24
Házi feladat elkészítése28
Kijelölt írásos tananyag elsajátítása14
Vizsgafelkészülés
Összesen150
15. A tantárgy tematikáját kidolgozta
dr. Csima Judit egyetemi docens SZIT 
dr. Friedl Katalin egyetemi docens SZIT
dr. Katona Gyula egyetemi docens SZIT 

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 2 zárthelyin 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 zárthelyiken plusz ponttal értékeljük. Ezeknek a plusz pontoknak az összege, de maximum 25 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 25 fölé). 
 
Az IMSC-pontok megszerzése a programban nem résztvevő hallgatók számára is biztosított.