K-INFO
HU
EN
Belépés
Tantárgy » BMEVISZAB03
Régebbi verziók TAD letöltése (PDF)

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 BMEVISZAB03
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 5
Tantárgyfelelős
DR. Friedl Katalin
beosztás: egyetemi docens
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ő.

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

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

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

  2. Cook-Levin-tétel (vázlatosan), a SAT, 3SAT, 3SZÍN NP-teljessége

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

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

  1. Dinamikus programozás (pl. Hátizsák, leghosszabb közös részsorozat)

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

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

  1. Lineáris és bináris keresés, az utóbbi optimalitása.

    Keresőfa fogalma, tulajdonságai, hatékonysága. A piros-fekete fa.

  1. : 2-3 fa, illetve a B-fa fogalma, tulajdonságai, előnyei. Hash

  2. Ismétlés, összefoglalás, tartalék.

 

P { margin-bottom: 0.08in; } A tantárgy célkitűzése a műszaki informatika tanulmányokhoz szükséges és a mérnöki alapműveltséghez tartozó egyes alapvető matematikai ismeretek elsajátítása, azok szemléletmódjának kialakítása. Ezen belül a tantárgy az automaták és formális nyelvek elméletének, adatstruktúrák és algoritmusok elemzésének egyes területeire nyújt bevezetést. A tantárgyat sikeresen teljesítő hallgató képes lesz: (K3)  érteni és alkalmazni a tárgyban előkerülő fogalmakat és ismereteket; (K3)  önállóan megoldani az anyaghoz kapcsolódó gyakorlati feladatokat; (K2)  alkalmazni a tárgyban szereplő algoritmusokat; (K3)  a későbbi tanulmányok során felismerni azokat a helyzeteket, ahol a tárgyban tanult ismeretek szerephez jutnak és sikerrel alkalmazni a tanultakat.

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

P { margin-bottom: 0.08in; } Heti 2 óra előadás és heti 2 órás gyakorlat.

Tanulástámogató anyagok

Online források
P { margin-bottom: 0.08in; }; A tantárgy weboldalán  található leírá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: P { margin-top: 0.07in; margin-bottom: 0.07in; text-align: left; widows: 2; orphans: 2; }P.western { font-size: 12pt; }P.cjk { font-size: 12pt; }P.ctl { font-family: "Times New Roman",serif; font-size: 12pt; } 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: P { margin-bottom: 0.08in; } A félév során az arra kijelölt időpontban pótzárthelyi, valamint a pótlási héten pótpó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.
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.