Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással
    vissza a tantárgylistához   nyomtatható verzió    

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

    A tantárgy angol neve: Algorithmic Problem Solving Laboratory

    Adatlap utolsó módosítása: 2024. január 3.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar     		Mérnökinformatikus, BSc

    Információs rendszerek specializáció, SZIT ágazat főtárgy
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZAC02 6 0/0/2/f 3  
    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 óra28
    Félévközi készülés órákra28
    Felkészülés zárthelyire
    Házi feladat elkészítése34
    Kijelölt írásos tananyag elsajátítása
    Vizsgafelkészülés
    Összesen90
    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.