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.