BME VIK - Algoritmikus problémák megoldása laboratórium

3. A tantárgyfelelős személy és tanszék Dr. Katona Gyula,

A tantárgy tanszéki weboldala http://cs.bme.hu/alglab

4. A tantárgy előadója

dr. Katona Gyula egyetemi docens SZIT

dr. Csima Judit egyetemi docens SZIT

dr. Friedl Katalin egyetemi docens

Kabódi László egyetemi tanársegéd

5. A tantárgy az alábbi témakörök ismeretére épít Algoritmuselmélet, Algoritmikus játékelmélet, Programozás alapjai 1

6. Előtanulmányi rend

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

7. A tantárgy célkitűzése 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.

8. A tantárgy részletes tematikája

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)

9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

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.

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

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

12. Konzultációs lehetőségek Igény szerint.

13. Jegyzet, tankönyv, felhasználható irodalom

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

14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka

Kontakt óra	28
Félévközi készülés órákra	28
Felkészülés zárthelyire
Házi feladat elkészítése	34
Kijelölt írásos tananyag elsajátítása
Vizsgafelkészülés
Összesen	90

15. A tantárgy tematikáját kidolgozta Dr. Katona Gyula egyetemi docens, SZIT

IMSc tematika és módszer 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 pontozás 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.