Információk
Kurzuskódok, időpontok, terem
IB304g-14: hétfő 12-13, Irinyi 214
IB304g-15: hétfő 13-14, Irinyi 214
IB304g-16: hétfő 14-15, Irinyi 214
Követelmények
Az évközi számonkérések során elérhető maximális pontszám 100 pont.
A gyakorlaton lesz 9 rövid írásbeli dolgozat (kis ZH) a 3., 4., 5., 6., 8., 9., 10., 11., 13. gyakorlatokon. Elérhető maximális pontszám: 4 pont/dolgozat. Teljesítendő minimális összpontszám: 20 pont. Ezen kívül lesz két írásbeli dolgozat (nagy ZH) a 7. és 12. gyakorlaton. Elérhető maximális pontszám: 32/dolgozat. Teljesítendő minimális összpontszám: 24 pont a két dolgozatból összesen.
Aki igazolt hiányzás miatt valamelyik nagy ZH-t nem tudja megírni, az a következő gyakorlaton ezt pótolhatja. Aki a 2 nagy ZH-ból nem éri el a minimális 24 pontot, vagy összesen nincs 51 pontja, az az utolsó előadás alatt dolgozatot írhat az egész éves anyagból, melynek sikeres teljesítése esetén a nagy ZH-s pontszámait 32-re cseréli.
Ponthatárok
- 86-100 jeles
- 76-85 jó
- 66-75 közepes
- 51-65 elégséges
- 0-50 elégtelen
Hasznos linkek
Az előadó honlapja: http://www.inf.u-szeged.hu/~cimreh/
Az elődasás és gyakorlat anyaga: www.inf.u-szeged.hu/~cimreh/alg.htm és /pub/alg/I.
Feladatgyűjtemény: www.inf.u-szeged.hu/~cimreh/feladatgyujt.pdf
Tematika
-
Szeptember 1.
Teljesítés feltételei, az algoritmus fogalma, egyszerű példák
-
Szeptember 8.
Aszimptotikus jelölések, bináris keresés rendzett sorozatban, kiválasztó rendezés, buborékrendezés
-
Szeptember 15.
Rekurziók - dinamikus programozás; Kis ZH: beszúró rendezés, partíciószámot kiszámoló algoritmus + rekurziós fa, gyorsrendezés + felosztHoare, gyorsrendezés + felosztLomuto
-
Szeptember 22.
További példák rekurziókra; Kis ZH: Partíció négyzetes táblázatkitöltéssel, mátrixszorzás (+KIIR), leghosszabb közös részsorozat (+KIIR) és végrehajtás is lehet: 2 sztring esetén a legkisebb közös részsorozat meghatározása
-
Szeptember 29.
Absztrakt adatszerkezetek, fák; Kis ZH: Hátizsák feladat+KIIR, definíciók: lánc, körlánc, kétirányú lánc; kupac adatszerkezet definíciója
-
Október 6.
Fák, gyakorló feladatok az 1. nagy ZH-ra; Kis ZH: Kupacrendezés algoritmus, rekurzív preorder bejárás algoritmusa, preorder bejárás veremmel algoritmus, szintszerinti bejárás algoritmus
-
Október 13.
1. Nagy ZH
-
Október 20.
Mohó algoritmusok; Kis ZH: Eseményválasztás algoritmusa, Huffman kód algoritmusa + végrehajtás + optimális fa felépítése
-
Október 27.
Gráfok, Szélességi/mélységi kereséssel megoldható problémák; Kis ZH: Szélességi keresés algoritmus + végrehajtás, mélységi keresés algoritmus, az erősen összefüggő komponenskeresés elvi algoritmusa
-
November 3.
Szélességi/mélységi kereséssel megoldható feladatok; Kis ZH: Dijskstra algoritmus, Ford Bellman algoritmus, Floyd Warshall algoritmus, Kruskal algoritmus
-
November 10.
Topologikus rendezés, erősen összefüggő komponensek, alkalmazások; Kis ZH: Prim algoritmus, Ford-Fulkerson algoritmus, stabil párosítások és leánykérő algoritmus
-
November 17.
2. Nagy Zh: mohó algoritmusok, gráfelméleti alapfogalmak, szélességi/mélységi keresés, Dijkstra-algoritmus, erősen összefüggő komponensek, toplogikus rendezés
Szorgalmi feladat (beadható december 1-ig)