ADATSZERKEZETEK
tárgy
2009/10 tanév 2. félév
(
)
tematika
áLTALÁNOS KÉRDÉSEK
Az Adatszerkezetek 2 féléves tárgy, mindkét félévben kollokvium és gyakorlati jegy van.
Követelmények az aláírásért:
· a papíros zárthelyi (?) megírása,
· beadandó (.) feladat érdemi megoldása és beadása,
· a (:) gépes zárthelyi megírása,
· rendszeres gyakorlatra járás (a vizsgaszabályzatban rögzítettek szerint[1]).
Követelmények a legalább kettes
gyakorlati jegyért:
· a papíros zárthelyi legalább 2,
· a beadandó feladat legalább 2,
· a gépes zárthelyi legalább 2.
A gyakorlati jegybe a zárthelyik, beadandók és a házi feladat(ok) eredményei mellett a gyakorlaton való részvétel minősége is beleszámít.
Ha a(z „elméleti” és géptermi) zárthelyi valamelyikét nem írta meg legalább elégségesre, akkor a pótzárthelyi(ke)t meg kell írnia!
A beadandóval szemben támasztott feltétel, hogy
1. a program legyen képes rövid (2-3 oldalnyi!) nyitó tájékoztató megjelenítésére,
2. mivel a megoldáshoz néhány „komplex” adatszerkezetre (gráfra, absztrakt sorozatra stb.-re) van szükség, ezért ezt (ezeket) önálló modulban (unit-ban, include-állományban), elkülönítve kell megvalósítani. Azaz a program algoritmusa is és a kódja is legalább két-két független programegységet alkot.
3. a program helyes működésének dokumentálásához szükséges jónéhány (fekete doboz tesztelésnek megfelelően, legalább 5) elvileg különböző tesztadatsor, fájlokban. Ezeket az exe mellett kell elhelyezni az anyagban; nélkülük nem értékelhető a program!
A beadandó feladat beadásáról (N):
1. a meghatározott formai feltételeknek eleget nem tevő dolgozatokat nem értékeljük (azt újra be kell adni helyesen; azonban a határidő nem módosul);
2. a beadás elektronikusan történik a gyakorlatvezetőnek (moodle rendszerén keresztül), a dokumentációt[2] ettől függetlenül papíron is beadhatja (ami azonban nem helyettesíti az elektronikus beadást!), ekkor kaphat részletes értékelést munkájáról;
3. a beadási határidő: 2010.05.02. vasárnap éjfél;
4. késedelmes beadás esetén a jegyet hetente 1 jeggyel csökkentjük (legfeljebb 3 hetes késéssel fogadjuk el a beadandót).
5. A részletes értékelést l.: ADTBeaErt.pdf.
részletes tematika
A tematikában elsősorban az alábbi, papíros alapú irodalmakra építünk és hivatkozunk:
1. Módszeres programozás – Programozási bevezető (μlógia 18),
2. Módszeres programozás – Adattípusok (μlógia 34),
3. Módszeres programozás – A programkészítés
technológiája (μlógia 21),
4. Adatszerkezetek példatár (μlógia 45),
5. Módszeres programozás – Gráfok,
gráfalgoritmusok (μlógia
38).
a
további kommunikációhoz
az ETR kurzus-mail szolgáltatását fogom
használni!
|
Sorszám/ |
Előadás |
Gyakorlat |
|
1. |
Regisztrációs hét |
|
|
2. |
Gráfok 1.: Gráfalkalmazási példák, gráfábrázolások. |
Gráfábrázolások: Konverziós
műveletek a csúcsmátrixos és a további ábrázolások között. |
|
3. |
Gráfok 2.: A gráf mint típuskonstrukciós eszköz. |
Gráfábrázolások: „Statikus”
gráf modul csúcsmátrixos megvalósítása. |
|
4. |
Gráfok 3.: Gráfbejárási algoritmusok. Útkeresések. |
Bejárások: Szélességi
bejárás és alkalmazása. |
|
5. |
Gráfok 4.: Gráfösszefüggőség-vizsgálat. Feszítőfák. Hálózati
folyamok. |
Bejárások: Mélységi
bejárás és alkalmazása. |
|
6. |
Mohó algoritmusok
1.: Bevezetés, egy iskolapélda, első alkalmazási
példa |
Összefüggőség-vizsgálat. |
|
7. |
Mohó algoritmusok 2.: További alkalmazási példák. Dinamikus programozás 1.: Bevezetés, egy iskolapélda, első alkalmazási példa. |
Feszítőfák/Hálózati folyamok. |
|
8. |
Dinamikus
programozás 2.: További alkalmazási példák. .Az önálló feladatok kiosztása. |
Mohóalgoritmusok: alkalmazások. |
|
9. |
Tavaszi szünet (03.31.-04.06.) |
|
|
10. |
? Papíros zárthelyi – Téma: gráfok |
Dinamikus programozás: alkalmazások. |
|
11. |
Geometriai
algoritmusok: Bevezetés, a geometriai operációk „nyelve”, alkalmazási
példák. |
Geometriai algoritmusok: a „geometria” típus megvalósítása |
|
12. |
Kombinatorikai
algoritmusok: „Klasszikus” és véletlen kombinatorikai algoritmusok. |
Geometriai algoritmusok: alkalmazások. |
|
13. |
: Géptermi
zárthelyi: 8-11 (KisLovi) . Az önálló feladat beadása: 05.02. éjfél |
Kombinatorikai algoritmusok: klasszikus alkalmazások. |
|
14. |
Rendezések. „Rendezéselmélet”, Hatékonyrendezések: Shell, Radix,… |
Kombinatorikai algoritmusok: véletlen alkalmazások. |
|
15. |
?
Pót papíros Vizsga-zárthelyi 10-12 (KisLovi) |
: pót gépes
zárthelyi: 05.18. (kedd) |
Gyakorlati
jegy UV: 2010.05.25.
(kedd) 10-12 (KisLovi)
Tudnivalók:
· Egy komplex feladat megoldása papíron és számítógépen.
· Minden saját, papíralapú és elektronikus anyag használható.
Vizsga[3]:
2010.05.27. csütörtök
10-12 (KisLovi)
Utóvizsga: 2010.06.10. csütörtök
10-12 (KisLovi)
Vizsgatételek:
|
# |
Tétel |
|
1. |
Gráfok 1.: A gráf típuskonstrukció, ábrázolások. |
|
2. |
Gráfok 2.: gráfbejárások; útkeresések. |
|
3. |
Gráfok 3.: összefüggőség-vizsgálat; feszítőfák; hálózati folyamok. |
|
4. |
Mohó algoritmusok – elvek, mintapéldák. |
|
5. |
Dinamikus programozás – elvek, mintapéldák. |
|
6. |
Geometriai algoritmusok. |
|
7. |
Kombinatorikai algoritmusok. |
|
8. |
|
A
tárgy 1. félévének tematikája:
http://people.inf.elte.hu/szlavi/Adatszerk/Adatszerk_1felev.htm.
A
tárgy 1. félévének „hivatalos” weblapja:
http://adatszerk1.elte.hu/?%C3%81ltal%C3%A1nos_inform%C3%A1ci%C3%B3k
(még feltöltés alatt).
A
tárgy 2. félévének „hivatalos” weblapja:
http://adatszerk2.elte.hu/?%C3%81ltal%C3%A1nos_inform%C3%A1ci%C3%B3k
(még feltöltés alatt).