BME VIK - Algoritmuselmélet

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ő:

((EgyenCsoportTagja("INFO - 2022 - MINTATANTERV HALLGATÓI") VAGY

EgyenCsoportTagja("INFO - 2022ENG - MINTATANTERV HALLGATÓI"))

ÉS

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

ÉS

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

ÉS

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

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 óra	56
Félévközi készülés órákra	28
Felkészülés zárthelyire	24
Házi feladat elkészítése	28
Kijelölt írásos tananyag elsajátítása	14
Vizsgafelkészülés
Összesen	150

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.