Algoritmikus problémák megoldása laboratórium

Algorithmic Problem Solving Laboratory

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)

Algoritmikus problémák megoldása laboratórium

Algorithmic Problem Solving Laboratory

Tantárgykód

BMEVISZAC02

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

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

félévközi érdemjegy

Tantárgy kreditértéke

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://cs.bme.hu/alglab

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

Korábban megismert algoritmusok, adatstruktúrák felhasználása, játékelmélet algoritmusok szimulálása.

(K2) alkalmazni a tárgyban szereplő algoritmusokat

(K3) önállóan megoldani az anyaghoz kapcsolódó gyakorlati feladatokat

(K4) problémaelemzés, megoldási alternatívák felállítása, összevetése, választás, indoklás

1. Ismerkedés szimulációs szoftvarekkel (Abed, Evoplex, Gambit), Nash-egyensúly számítása, Shapley-érték számítás, Shapley-Shubik hatalmi index, Banzhaf index számítása.

2. Igazságos osztozkodást (fair division) megvalósító protokollok, igazságos költség megosztási (cost sharing) protokollok

3. Allokációs és párosító mechanizmusokkal kapcsolatos algoritmusok: felső korcsere (top trading cycles, TTC), leánykérő algoritmus stabil párosításra

4-7. Összetett algoritmus elméleti, adatstruktúra vagy gráfelméleti ismereteket igénylő egyéni feladat valamely versenyfeladatokat kínáló oldalról (ACM, Codeforces, CodeChef, AtCoder, Topcoder, Codejam)

A hallgatók a Bevezetés a számítástudományba, Algoritmuselmélet és a specializáció főtárgy (Algoritmikus játékelmélet) tárgyakban számos algoritmussal megismerkedtek már. De ezekben a tárgyakban csak nagyon kevés szó esett az implementálás részleteiről, illetve az algoritmusok alkalmazásairól. Ezen a laboron egyrészt az implementálás magasabb szintű részleteivel foglalkozunk. Másrészt olyan gyakorlatibb feladatokkal foglalkozunk, ahol a feladat leírásából elsőre nem látszik könnyen, hogy milyen algoritmust is kell használni. Ilyenkor az is előfordul, hogy nem egyszerűen egy ismert algoritmust kell felhasználni, hanem valahogyan módosítani kell azt, esetleg több algoritmust is kell kombinálni. A legtöbb programozási versenyen (pl. ACM) ilyen típusú feladatokat kell megoldani. A játékelmélet részben pedig az ott megismert többszereplős játékok szimulációjával mélyítjük el a tudást.

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áratlan heteken jelenléti oktatásban megismertetjük a hallgatókat a soron következő feladattal, áttekintjük a szükséges előismereteket, a hallgatók megoldási javaslatokat tesznek. Ezután a hallgatók önállóan dolgoznak a megoldáson. Páros heteken az időközben felmerült kérdéseket személyes vagy online konzultáció keretében tisztázzuk.

Tanulástámogató anyagok

Online források

Rónyai Lajos, Ivanyos Gábor, Szabó Réka: Algoritmusok, TypoTeX Kiadó ; Végh László, Király Tamás, Pap Júlia: Játékelmélet jegyzet http://tkiraly.web.elte.hu/students/jatekelmelet_jegyzet.pdf ; Stephen G. Kochan: Programfejlesztés C nyelven. (Kiskapu, 2008.) ; Pohl László: A programozás alapjai, https://infoc.eet.bme.hu/jegyzet/c_jegyzet.pdf

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)

Algoritmuselmélet, Algoritmikus játékelmélet, Programozás alapjai 1

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)

Algoritmuselmélet, Algoritmikus játékelmélet, Programozás alapjai 1

Általános szabályok

Követelmények: A laborok teljesítéséhez a laborok során aktív közreműködés és a feladat megoldásának megfelelő szintű dokumentálása szükséges. A laborhoz tartozó feladatkiírásban meghatározott beadandó anyagokat (pl. algoritmus vázlatot, programlistákat) az adott labort követő egy héten belül el kell juttatni a laborvezetőhöz az általa kért módon. Minden labort külön jeggyel értékelünk. Az el nem végzett labor jegye elégtelen. A félévközi jegy a laborokon szerzett 7 jegy átlaga. A félévközi jegy megszerzéséhez legalább 6 labort legalább elégséges jeggyel kell teljesíteni. Pótlási lehetőségek: A pótlási időszakban egy labor pótolható. Erre legkésőbb a szorgalmi időszak utolsó napjáig jelentkezni kell a tárgyfelelősnél. A beadandó anyagokat a pótlást követő 2 napon belül el kell juttatni a laborvezetőhöz az általa megadott módon.

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 labor feladatok értékelése a beadott algoritmusok, programok helyessége és hatékonysága szerint történik. A jeles eredmény eléréséhez meghatározott hatékonyságot várunk el. Az IMSC hallgatóktól jobb, ötletesebb vagy általánosabb megoldásokat várunk el. IMSc pontok: Minden laborfeladat esetén a jeles eredmény elérésez szükségesnél jobb algoritmussal laboronként 5 IMSC pont szerezhető. A kurzuson szerezhető összes IMSC pont a feladatonként szerzett pontok összege, de legfeljebb 15.

Ajánlott tantárgyak

Algoritmuselmélet, Programozás alapjai 1 , Algoritmikus játékelmélet

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.