Algoritmuselmélet

Theory of Algorithms

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

BMEVISZAB01

Tantárgyjelleg

—

Képzési szint

—

Kurzustípusok és óraszámok (heti/féléves)

Kurzustípus	elmélet	gyakorlat	laboratóriumi gyakorlat
óraszám (heti)	2	2	0
jelleg (kapcsolt/önálló)	—	kapcsolt	—

Tanulmányi teljesítmény/értékelés típusa

vizsga

Tantárgy kreditértéke

Tantárgyfelelős

DR. Friedl Katalin

beosztás: egyetemi docens

elérhetőség: friedl.katalin@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://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) 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.

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.

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

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

Tanulástámogató anyagok

Online források

Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok,; TypoTeX Kiadó,; Csima Judit, Friedl Katalin: Nyelvek és automaták,; elektronikus jegyzet

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)

nincs

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)

nincs

Általános szabályok

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

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: P { margin-bottom: 0.08in; } 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: P { margin-bottom: 0.08in; } 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.

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.