Algoritmusok és bonyolultságuk

Algorithms and Complexity

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)

Algoritmusok és bonyolultságuk

Algorithms and Complexity

Tantárgykód

BMEVISZM031

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)	3	1	0
jelleg (kapcsolt/önálló)	—	kapcsolt	—

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

félévközi érdemjegy

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/algbony

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

• A kódoláselmélet algoritmikus kérdései
• Geometriai algoritmusok (legközelebbi pontpár, konvex burok meghatározása)
• Párhuzamos algoritmusok (PRAM modellek, egyszerű függvények kiszámítása az eltérő modellekben, Brent-elv, párhuzamos rendezés, prefix számítások)
• Elosztott algoritmusok (a vezetőválasztás algoritmusai, egyezségre jutás, illetve ennek lehetetlensége különböző típusú hibák esetén: vonalhiba, leállási hiba, bizánci hiba)
• Interaktív bizonyítások (az NP kiterjesztése interaktív algoritmusok segítségével, interakció egy erős és egy gyenge fél között, az AM és az IP nyelvosztály, jellemző példák, IP=PSPACE, a PCP elmélet kapcsolata a közel optimális megoldás megtalálhatóságával)
• On-line algoritmusok (modell, hatékonyság mérése, listaelérési feladat, ütemezési problémák)
• Paraméteres bonyolultság (NP-nehéz, de paraméteresen megoldható feladatok, korlátos mélységű keresőfák, a gráfminor tétel és következményei, W[1]-teljesség)
• A kvantumalgoritmusok alapjai (számítási modell, lépés mint unitér transzformáció, illetve vetítés, no-cloning tétel, egyszerű algoritmusok, prímfaktorizáció, keresés, kvantumszámítás és titkosítás)

A gyakorlaton az előadás anyagához kapcsolódó feladatokat oldunk meg, melyek az ismertetett algoritmusok, módszerek jobb megértését teszik lehetővé és rávilágítanak bizonyos alkalmazási lehetőségekre.

A tantárgy célja az algoritmikus gondolkodás továbbfejlesztése, a BSc-hez képest további módszerek, technikák megismerése. A hallgatók betekintést kapnak a témakör modern irányzataiba, az új és jövőbeli eszközök (párhuzamos számítások, kvantumszámítógépek) által megoldható kérdésekre, felvetett problémákra.

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

előadás + gyakorlat

Tanulástámogató anyagok

Online források

T. Corman, C. Leiserson, R. Rivest, C. Stein: Új algoritmusok, Scolar Kiadó, 2003.; H. Attiya: Distributed Computing (lecture notes); J. Flum, M. Grohe: Parameterized Complexity Theory, Springer 2006.

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)

Alapvető algoritmikus technikák

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)

Alapvető algoritmikus technikák

Általános szabályok

Követelmények: • Szorgalmi időszakban: 5 kiszárthelyi (10-15 perces) és 1 zárthelyi dolgozat. A 3 legjobb kis zh adja a jegy 40%-át, a zárthelyi dolgozat a 60%-át. • Vizsgaidőszakban: - Pótlási lehetőségek: A kis zh-k nem pótolhatóak. A zárthelyi dolgozathoz egy pótlási lehetőség lesz a szorgalmi időszakban és egy a pótlási héten.

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

Nincs megadva.

Ajánlott tantárgyak

Ezt a tárgyat nem vehetik fel, akik a VISZM143 kódú “ Algoritmusok és bonyolultságuk – informatikusoknak” című tárgyat teljesítették.

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.