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ó    

    Algoritmusok és adatszerkezetek hatékony implementálása C nyelven

    A tantárgy angol neve: Algorithms, Data Structures and their Efficient Implementation in C Language

    Adatlap utolsó módosítása: 2023. július 6.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar
    Villamosmérnöki szak   
    BSc. és MSc képzés            
    Szabadon választható   

    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VIHIAV10   0/2/0/f 2  
    3. A tantárgyfelelős személy és tanszék dr. Zsóka Zoltán,
    4. A tantárgy előadója Vitéz András    óraadó    Hálózati Rendszerek és Szolgáltatások Tsz.
    Dr. Zsóka Zoltán    docens    Hálózati Rendszerek és Szolgáltatások Tsz.
    5. A tantárgy az alábbi témakörök ismeretére épít Alapszintű strukturált programozás, C programozási nyelv ismerete
    6. Előtanulmányi rend
    Kötelező:
    NEM
    (Training.Code=("5N-A8")
    VAGY
    Training.Code=("5N-M8"))

    A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

    A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

    Ajánlott:
    A tárgyat csak azoknak célszerű felvenni, akik korábban már hallgatták a következő tárgyat:
    villamosmérnök alapszakon (BSc) a VIHIA106 Programozás alapjai I., vagy VIHIAA01 A programozás alapjai 1.
    7. A tantárgy célkitűzése A tantárgy célkitűzése, hogy a hallgatók a programozási ismereteiket olyan megoldásokkal, módszerekkel bővítsék ki, melyek a képzés programozási törzsanyagában nem szerepelnek, de a hatékony programok írását lehetővé teszik. Ennek során elsajátítják egyes hatékony, illetve gyakran használt algoritmusok és adatszerkezetek megvalósítási lépéseit a C nyelv lehetőségeit felhasználva és kihasználva. Az elsajátítandó módszereket a mérnöki gyakorlatban sűrűn előforduló kritikus problémákon próbáljuk ki.
    8. A tantárgy részletes tematikája 1.   A strukturált programozás tétele a gyakorlatban, a backtrack algoritmus implementálása

    2.    Rekurzió vs. ciklus: előnyök – hátrányok, rekurzív algoritmusok átalakítása ciklusokká, rekurzív adatszerkezetek

    3.    Eseményvezérelt modell megvalósítása függvénypointerekkel. Alapszintű diszkrét idejű szimuláció.

    4.    K-ágú fák alkalmazása tudás reprezentációra, szakértő rendszerek, egyszerű tanulóalgoritmus megvalósítása bináris fa használatával.

    5.    Fájlok kezelése az operációs rendszerben. Dinamikus adatszerkezetek mentése és felépítése fájlba, illetve fájlból.

    6.    Kiegyensúlyozott bináris fák, AVL és piros-fekete fák megvalósítása és karbantartása. Kupac adatszerkezet.

    7.    Helyben rendező algoritmusok összehasonítása, osztályozása, szoftver mérési eredmények vizualizálása


    8.    Szélességi keresés, a legrövidebb út problémája; elárasztásos algoritmus implementálása várakozási sorral, Dijsktra algoritmusa kupaccal megvalósítva

    9.     Típusok hatékony felhasználása lineáris algebrai algoritmusokban, mellékhatások kihasználása.
    10.    Magasszintű nyelvek verem használata; a párhuzamos programozás lehetőségének megteremtése

    11.    Tartalék előadás: Tesztelési adatsorok szisztematikus tervezése.

    12.    A hallgatók által házi feladatként elkészített programok prezentációja, kódelemzés, a megoldások megvitatása – 1. alkalom

    13.    u.a. – 2. alkalom

    14.    u.a. – 3. alkalom
    Ha a félév során 2 alkalommal marad el a foglalkozás, akkor a prezentációk bemutatására órarenden kívüli alkalmat biztosítunk.
    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) A kétórás foglalkozások első részében elméleti szinten ismertetjük a problémákat és a megoldási módszereket, majd ezeket az ismereteket konkrét problémákra alkalmazzuk.
    10. Követelmények A gyakorlatok látogatása (a TVSZ értelmében) kötelező. A jelenlétet minden alkalommal ellenőrizzük, 30%-ot meghaladó hiányzás esetén a tantárgyból az elégtelentől eltérő jegy sem kreditpont nem szerezhető.

    a.    A szorgalmi időszakban:
    (1) Egy nagy házi feladat, ami a tanultak alkalmazása egy a való életből vett problémára. Az elkészült munkát a tárgy hallgatóságának személyes prezentáció formájában be kell mutatni. A bemutatás feltétele, a házi feladat beadása az utolsó órarendi órát megelőző napon 12 óráig. A nagy házi feladat értékelése 0 - 58 pont.
    A nagy házi feladat elfogadható szintű megoldása elégtelentől eltérő jegy megszerzésének feltétele (legalább  20 pont).
    (2) Két kis házi feladat a tanultakhoz kapcsolódó összehasonlító szoftver kísérlet dokumentálása, értékelése egyenként 0 - 21 pont
    Az elégtelentől eltérő jegy megszerzéséhez a hallgatónak legalább az egyik kis házi feladatot teljesen meg kell oldania (21 pont).
    A házi feladatokkal összesen 100 pont érhető el.
    A félévközi jegy ponthatárai:
    40 pontig elégtelen
    41 ponttól elégséges
    56 ponttól közepes
    71 ponttól jó
    86 ponttól jeles.
    11. Pótlási lehetőségek A házi feladatok késedelmes beadására, a pótlások hetének utolsó előtti munkanapján 10 óráig van lehetőség.
    A késedelmesen beadott feladatok prezentálására nincs lehetőség, de a prezentáció hiányában is elérhető az elfogadáshoz minimálisan szükséges pontszám.
    12. Konzultációs lehetőségek Igény szerint előadóval egyeztetve.
    13. Jegyzet, tankönyv, felhasználható irodalom
      •    N. Wirth: Algoritmusok + Adatstruktúrák = Programok, Műszaki Könyvkiadó, 1982
      •    Benkő Tiborné, Dr. Poppe András: Együtt könnyebb a programozás – C, Computer Books, 2006
      •    Nemes Mihály: Sebesség a számítástechnikában, Szieben és Tsa, 1995
      •    Wayne Amsbury: Data Structures from Arrays to Priority Queues, Wadsworth Publishing, 1985
      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  6
      Felkészülés zárthelyire 
      Házi feladat elkészítése 26
      Kijelölt írásos tananyag elsajátítása  -
      Vizsgafelkészülés  -
      Összesen 60
      15. A tantárgy tematikáját kidolgozta Vitéz András    adjunktus    Hálózati Rendszerek és Szolgáltatások Tsz.
      Dr. Zsóka Zoltán    docens    Hálózati Rendszerek és Szolgáltatások Tsz.