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: 2014. január 27.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar
    Mérnök informatikus szak
    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, Hálózati Rendszerek és Szolgáltatások Tanszék
    4. A tantárgy előadója 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.
    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 rendek grafikus formában itt láthatók.

    Ajánlott:

    A tárgyat csak azok vehetik fel, akik korábban már hallgatták a következő tárgyat:

    villmosmérnök szakon a VIHIA106 Programozás alapjai I., vagy

    mérnök informatikus szakon a VIEEA100 A programozás alapjai I.

    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. Strukturálatlan algoritmusok strukturálttá tétele.
    Visszalépéses algoritmus, backtrack.

    2.    Rekurzív módszerek átalakítása.

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

    4.    Egyszerű tanulóalgoritmus megvalósítása.

    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 fák, AVL fák megvalósítása. Kupac adatszerkezet.

    7.    Kupacrendezés, rendezések hatékonyságának növelése, shell algoritmus


    8.    Mellékhatások kihasználása. Típusok hatékony felhasználása.

    9.    Memóriakezelés és címzés az operációs rendszerben. Dinamikus adatszerkezetek és tömbök használata.

    10.    Memóriakezelés, függvényhívás és indirekció hatása a futásidőre.

    11.    Tesztelési adatsorok tervezése.

    12.    A program felélesztése, fordítás, linkelés, make (build) funkció. Hibakeresés.

    13.    Pótelőadás, hallgatói prezentációk: érdekes házi feladatok bemutatása.

    14.    Hallgatói prezentációk: érdekes házi feladatok bemutatása.

    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) A kétórás foglalkozások első felé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 sem aláírás sem kreditpont nem szerezhető.
    a. A szorgalmi időszakban:
    (1) két kisebb terjedelmű házi feladat a tanult elvek elsajátításának gyakorlati demonstrálására, kontroll kísérlet a kézenfekvő megoldáshoz képesti javulás mérésére
    Legalább az egyik feladat elfogadható szintű megoldása az aláírás megszerzésének feltétele.

    Értékelés:  mindkettő 0 – 26 pontig  
    (2) egy nagyobb terjedelmű összetett házi feladat valamely vizsgált elv alkalmazásával. A különösen érdekes megoldásokat az utolsó foglalkozáson a csoportnak be lehet mutatni.
    A feladat elfogadható szintű megoldása az aláírás megszerzésének feltétele.
    Értékelés: 0 – 48 pontig
    A félévi jegy ponthatárai:
    50 ponttól elégséges
    61 ponttól közepes
    72 ponttól jó
    83 ponttól jeles

    11. Pótlási lehetőségek A házi feladat késedelmes beadására, a pótlások hetének péntek 11 óráig van lehetőség.
    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 14
      Felkészülés zárthelyire 
      Házi feladat elkészítése 18
      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.