Algoritmusok és adatszerkezetek I. Gyakorlat

Információk

Kurzuskódok, időpontok, terem

IB304g-15: hétfő 16-17, Irinyi 214

IB304g-16: hétfő 17-18, Irinyi 214

IB304g-17: kedd 11-12, Irinyi 214

Követelmények

Az évközi számonkérések során elérhető maximális pontszám 100 pont. Teljesítendő minimális pontszám: 40 pont.

A gyakorlaton lesz 9 rövid írásbeli dolgozat (kis ZH) a 3., 4., 5., 6., 8., 9., 10., 11., 13. gyakorlaton. Elérhető maximális pontszám: 4 pont/dolgozat. Teljesítendő minimális összpontszám: 16 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. Az I304 kódú tárgy esetén teljesítendő egy további feladat.

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, az a vizsgaidőszak 1. hetében javító dolgozatot írhat. A hallgató csak akkor jelentkezhet a kollokviumra, ha a javító dolgozattal megszerezhető maximális 40 pontból legalább 20 pontot teljesít. Fontos, hogy a javító dolgozaton szerzett pont NEM számít be az összpontszámba.

A kollokviumon szintén 100 pont szerezhető (az előadó ismerteti az első előadáson).

Ponthatárok

• 175-200 jeles
• 150-174 jó
• 125-149 közepes
• 100-124 elégséges
• 0-99 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 3-4.

  Teljesítés feltételei, algoritmus fogalma, egyszerű példák

• Szeptember 10-11.

  Aszimptotikus jelölések, bináris keresés rendzett sorozatban, kiválasztó rendezés, buborékrendezés

• Szeptember 17-18.

  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 24-25.

  További példák rekurziókra; Kis ZH: Partíció rekurziómemorizálással, partíció négyzetes táblázatkitöltéssel, mátrixszorzás (+KIIR), leghosszabb közös részsorozat (+KIIR) /végrehajtás nem lesz/

• Október 1-2.

  Absztrakt adatszerkezetek, fák; Kis ZH: Hátizsák feladat+KIIR, hátizsákfeladat végrehajtása, definíciók: lánc, körlánc, kétirányú lánc, fa algebrai definíciója

• Október 8-9.

  Fák, gyakorló feladatok; Kis ZH: Kupacrendezés algoritmus (+ MAXIMUM-KUPACOL), kupacrendezés végrehajtása, rekurzív preorder bejárás algoritmusa, preorder bejárás veremmel algoritmus, szintszerinti bejárás algoritmus

• Október 15-16.

  Nagy ZH: készüléshez: feladatgyűjtemény 4. (rekurzíók) 6. (elsőfiú-testvér ábrázolás esetén, ami ugyanaz gyakorlatilag ami órán volt) 7. fejezet (a megfelelő táblázatkitöltésekkel együtt, 4. órán néztünk rá példákat), továbbá minden amiről az eddigi gyakrolatokon szó volt

• Október 22-23.

  Nemzeti ünnep

• Október 29-30.

  Az 1. nagy ZH néhány feladata, mohó algoritmusok; Kis ZH: Eseményválasztás algoritmusa, Huffman kód algoritmusa + végrehajtás + optimális fa felépítése

• November 5-6.

  Gráfok; Kis ZH: Szélességi keresés algoritmus + végrehajtás, mélységi keresés algoritmus + végrehajtás

• November 12-13.

  Szélességi/mélységi kereséssel megoldható feladatok; Kis ZH: Zárójelezési tétel kimondása, a topologikus rendezés elvi algoritmusa, az erősen összefüggő komponenskeresés elvi algoritmusa, erősen összefüggő komponensek definíciója + meghatározásuk egy megadott gráfban

• November 19-20.

  Topologikus rendezés, gráfok összefüggősége; Kis ZH: Dijkstra, Ford Bellman, Floyd Warshall, Kruskal algoritmusok (mindenhol pszeudokód + tudjuk, hogy mire használható)

• November 26-27.

  Nagy ZH. Készüléshez: feladatgyűjtemény 8. (mohó algoritmusok), 10. (gráfok és ábrázolásaik), 11. (szélességi és mélységi keresés alkalmazásai), 12. (gráfok összefüggősége), ezen kívül minden, amit az 1. nagy ZH óta a gyakorlatokon vettünk

• Szorgalmi (beadási határidő: dec. 3-4.)

  3 plusz pontért az utolsó heti gyakorlatig a következő feladatot lehet beadni: szorgalmi. A megoldást emailben, részletesen leírva, esetleg ábrával kiegészítve küldjétek el.

• December 3-4.

  Az 2. nagy ZH megbeszélése; Kis ZH: lineáris időben kiválasztó algoritmus, beszúrás algoritmusa bináris keresőfába, törlés algoritmusa bináris keresőfából, törlés végrehajtása adott bináris keresőfában

Eredmények

Az eredményeket IDE kattintva nézhetitek meg. (Utolsó frissítés: 2012.11.28. 14:00)