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