BSc Matematika Alapszak
Tantárgyleírás
2017.
Tantárgyleírás
2017.
Algoritmusok tervezése és elemzése1
- Óraszám (ea+gy): 2 + 2
- Specializáció: alk. mat.
- Kredit (ea+gy): 3 + 2
- Számonkérés: kollokvium + gyak. jegy
- Tárgykód (ea, gy): algter1a0_m17ea, algter1a0_m17ga
- Ajánlott félév: 4
- Státusz: kötelező
Óraszám
ea(+k) + gy(+k) |
Kredit
ea + gy |
Számonkérés | Specializáció | Tárgykód
ea/gy |
Ajánlott
félév |
Státusz |
---|---|---|---|---|---|---|
2 + 2 | 3 + 2 | kollokvium + gyak. jegy |
alk. mat. | algter1a0_m17ea algter1a0_m17ga |
4 | kötelező |
Tantárgyfelelős
Erős | Gyenge | előfeltételek |
---|---|---|
Gyakorlat | ||
Erős:
Matematika kritériumtárgyG
(bevmat1x0_m17ga)
| ||
Előadás | ||
Gyenge:
a gyakorlat
|
Megjegyzések
- A programozási alapismeretek (prgism1x0_m17va) előzetes elvégzése ajánlott.
A tematikát kidolgozta:
Szükséges előismeretek
Programozási alapismeretek.
Irodalom
- Cormen, Leiserson, Rivest, Stein: Új algoritmusok. Scolar, 2003.
- Rónyai L., Ivanyos G., Szabó R.: Algoritmusok. TypoTex, 2005.
Ajánlott:
- D. E. Knuth: A számítógép-programozás művészete, I. és III. Műszaki Könyvkiadó, 1987.
- S. Lipschutz: Adatszerkezetek. Panem-McGraw-Hill, 1993.
- N. Wirth: Algoritmusok + Adatstruktúrák = Programok. Műszaki Könyvkiadó, 1982.
- A. Aho, J. Hopcroft, J. Ullman: Számítógép-algoritmusok tervezése és analízise. Műszaki Könyvkiadó, 1982.
- Iványi Antal: Informatikai algoritmusok I-II. 2004, 2005.
- Tematikák, segédanyagok letölthetők a http://aszt.inf.elte.hu/~hunlaci/ és http://people.inf.elte.hu/fekete/ címekről.
Tematika
- Feladatok algoritmikus megoldhatósága, az idő- és tárbonyolultság, az „ordó matematikája”, nagyságrendek.
- A programozás absztrakt alapfogalmai: állapottér, feladat, program, megoldás. Program-konstrukciós módszerek, programhelyesség bizonyítás. Programozási tételek.
- Az adattípus absztrakciós szintjei: absztrakt adattípus (ADT), absztrakt adatszerkezetek (ADS), ábrázolási módszerek (aritmetikai, láncolt). Egyszerű adattípusok: tömb, verem, sor, elsőbbségi sor, listák, fák, és tipikus alkalmazásaik.
- Kiválasztások: maximum, szimultán minimum és maximum kiválasztás, a k-adik legkisebb elem kiválasztása lineáris időben. Alsókorlát-elemzés a „csalafinta válaszoló” módszerével.
- Az összehasonlításos rendezések alsókorlát-elemzése a legkedvezőtlenebb és az átlagos esetben. Rendezési módszerek osztályozása. A maximumot kiválasztó rendezések alapalgoritmusa és gyorsítás lehetősége tournament és heap felhasználásával. Az egy elemet a helyére vivő rendezők, quick-sort, rendező-fák (bináris rendező-fa, kiegyensúlyozott bináris rendező-fa). Az egyszerű beillesztés és a fogyó növekményű rendezés (Shell-módszer). Csere rendezések, adat-független csere-rendezések, szemléltetésük rendező hálózatokkal (buborék, piramis, Batcher). Az összefuttatásos rendezés tömbökben, illetve külső rendezőként.
- Keresési módszerek asszociatív adatszerkezeteken 1, visszavezetéses technikák (lineáris keresés, logaritmikus (bináris) keresés, keresőfák, optimális keresőfa, AVL-fa, B-fák).