A tantárgyleírás hatályossága
Hatályosság kezdete:
2026. March 21.
Hatályosság vége:
—
| Tantárgy neve (magyarul, angolul) |
Algoritmuselmélet
Theory of Algorithms
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Tantárgykód | BMEVISZAA08 | ||||||||||||
| Tantárgyjelleg | — | ||||||||||||
| Képzési szint | — | ||||||||||||
| Kurzustípusok és óraszámok (heti/féléves) |
|
||||||||||||
| Tanulmányi teljesítmény/értékelés típusa | félévközi érdemjegy | ||||||||||||
| Tantárgy kreditértéke | 5 | ||||||||||||
| Tantárgyfelelős |
DR. Katona Gyula
beosztás: egyetemi tanár
elérhetőség:
katona.gyula@vik.bme.hu
|
||||||||||||
| Tantárgyat gondozó oktatási szervezeti egység |
Számítástudományi és Információelméleti Tanszék
|
||||||||||||
| Kar | Villamosmérnöki és Informatikai Kar | ||||||||||||
| Tantárgy weboldala | http://www.cs.bme.hu/algel | ||||||||||||
| Tantárgy elsődleges mintatantervi jellege | — | ||||||||||||
| Közvetlen előkövetelmények – Erős előkövetelmény | nincs | ||||||||||||
| Közvetlen előkövetelmények – Gyenge előkövetelmény | nincs | ||||||||||||
| Közvetlen előkövetelmények – Párhuzamos előkövetelmény | nincs | ||||||||||||
| Közvetlen előkövetelmények – Mérföldkő előkövetelmény | nincs | ||||||||||||
| Közvetlen előkövetelmények – Kizáró feltétel | nincs |
Célkitűzés
Tantárgyprogram
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
(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.
Tanulmányi eredmények
Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:
Tudás
Nincsenek rögzített tanulási eredmények.
Képességek
Nincsenek rögzített tanulási eredmények.
Attitűd
Nincsenek rögzített tanulási eredmények.
Autonómia és felelősség
Nincsenek rögzített tanulási eredmények.
Oktatási módszertan
A tárgyból heti 2 óra előadást és heti 2 óra gyakorlatot tartunk.
Tanulástámogató anyagok
Online források
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
A tantárgy teljesítéséhez ajánlott előzetes ismeretek
Tudás típusú kompetenciák
(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
gráfelmélet, középiskolai matematika
Képesség típusú kompetenciák
(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák
(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)
gráfelmélet, középiskolai matematika
Általános szabályok
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.
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ó.
Teljesítményértékelési módszerek
Szorgalmi időszakban végzett teljesítményértékelések részletes leírása
Nincs megadva részletes értékelés.
Szorgalmi időszakban végzett teljesítményértékelések részaránya
Nincs megadva részarány.
Vizsgaidőszakban végzett teljesítményértékelések részletes leírása
Nincs megadva részletes értékelés.
Vizsgarészek részaránya
Nincs megadva részarány.
Érdemjegy megállapítása
Nincs megadva érdemjegy határ.
Jelenléti és részvételi követelmények
Nincs megadva jelenléti követelmény.
Javítás, ismétlés és pótlás különös szabályai
Nincs megadva.
Rövid leírás
Nincs megadva.
Részletes leírás
IMSc program:
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 pontok:
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.
Ajánlott tantárgyak
Nincs megadva.
A tantárgy elvégzéséhez szükséges tanulmányi munka
Nincs megadva munkaidő bontás.
Tantárgykövetelmények hatályossága
Tantárgykövetelmények hatályosságának kezdete:
—
Tantárgykövetelmények hatályosságának vége:
—
Tantervi elhelyezés
Nincsenek rögzített tantervi elhelyezések ehhez a tárgyverzióhoz.