Tárgykód: IP-08abctAA2
Célkitűzés:
A kurzus célja a gyakorlatban leginkább használat egyszerű algoritmusok és adatszerkezetek elsajátítása, különös figyelemmel hatékonyságuk vizsgálatára, illetve az algoritmustervező készség fejlesztése. A hallgatók a tervezés és ábrázolás különböző, nyelvfüggetlen szintjeivel ismerkedhetnek meg, amelynek köszönhetően absztrakciós képességeik is javulnak.
A két féléves tantárgy második félévében a hallgatók további alapvető, gyakorta használt algoritmusokat sajátíthatnak el, a szemeszter nagy részében gráfokkal kapcsolatosan.
Előfeltétel:
- Algoritmusok és adatszerkezetek I (IP-08abctAA1, erős).
Szükséges előismeretek:
- Procedurális programozás, programozási tételek.
- Típusoritentált programozás, típuskonstrukciók.
- Adatszerkezetek reprezentációs módjai.
- Algoritmusok műveletigénye.
- Alapvető adatszerkezetek (verem, sor, fák) és műveleteik.
- Összehasonlító rendezések.
Gyakorlati tematika:
1) Rendezés lineáris időben.
2) Hash-elés, hash-táblák.
3) Gráfok ábrázolása, egyszerű gráfos algoritmusok.
4) Gráfok szélességi bejárása, legrövidebb utak gráfokban (Dijkstra).
5) Minimális költségű feszítőfák (Prím).
6) 1. zárthelyi dolgozat.
7) Legrövidebb utak (Bellman-Ford, Floyd) .
8) Gráfok tranzitív lezárása (Warshall). Mélységi bejárás.
9) Topológikus rendezés, erősen összefüggő komponensek.
10) Adattömörítés (Huffman-kód, LZW).
11) Mintaillesztés (Brute Force, Knuth-Morris-Pratt).
12) 2. zárthelyi dolgozat.
13) Mintaillesztés (Quick Search, Rabin-Karp).
Számonkérés:
A tárgyból a hallgatók vizsgajegyet, valamint gyakorlati jegyet kapnak.
A vizsgajegyet írásbeli vizsga keretén belül szerezhetik meg, amely a félév elméleti és gyakorlati ismereteit is magában foglalja.
A gyakorlati jegyhez a félév során a hallgatóknak két zárthelyi dolgozatot kell teljesíteniük, valamint lehetőségük van beadandó feladat elkészítésére javítás céljából.
- Zárthelyik: A három zárthelyi dolgozatból kettő a félév során teljesíthető, az azt megelőző gyakorlatok anyagából. A hallgatónak továbbá lehetősége van, hogy egyik zárthelyijét javítsa, illetve pótolja egy pótzárthelyi keretében a félév végén.
- Feladatok: A félév során (a szorgalmi időszakban) bármikor beadható programozási feladat, amelyet a hallgató tetszőlegesen választhat ki a feladatlistából. Egy hallgató több feladatot is beadhat, de maximum 20 pontot szerezhet általuk.
Értékelés:
A gyakorlati jegy a két zárthelyi eredménye alapján kerül kiszámolásra, továbbá javítható a kiírt házi feladatok beadásával. Így összesen a zárthelyiken 120 pont, a házi feladatokkal további 20 pont szerezhető, a osztályzat a pontszám huszadának alsó egészrésze.
Az átmenő gyakorlati jegy feltétele, hogy a hallgató mindkét zárthelyit legalább 20 pontosra teljesítse. Aki nem teljesíti az előírt pontszámokat, elégtelen gyakorlati jegyet kap, amit utóvizsga keretében javíthat egy újabb zárthelyi dolgozat megírásával (a teljes félév anyagából).
