| Tantárgy neve: Adatstruktúrák és algoritmusok |
Tantárgy Neptun kódja: Nappali: GEMAK121-B Tárgyfelelős intézet: MAT - Matematikai Intézet |
| Tantárgyelem: A | |
| Tárgyfelelős: Dr. Házy Attila - egyetemi docens | |
| Közreműködő oktató(k): | |
| Javasolt félév: 2 | Előfeltétel:GEMAN102-B vagy GEMAN112-B |
| Óraszám/hét: Előadás (nappali): 2 Gyakorlat (nappali): 2 | Számonkérés módja: kollokvium |
| Kreditpont: 5 | Munkarend: Nappali |
| Tantárgy feladata és célja: A matematikai alapok elméleti kiterjesztése, modellek és algoritmusok fejlesztése, használata Tudás: Ismeri és érti az analízis, valószínűségszámítás, lineáris algebra, operációkutatás, statisztika, illetve a számítástudomány alapvető fogalmait és összefüggéseit, valamint az alkalmazási területekhez kapcsolódó rutinszerű problémák formális modelljeit. Ismeri a programozással összefüggésben az alapvető programozási struktúrákat, a szoftverfejlesztés módszertanát és a fontosabb programozási környezeteket. Képesség: Képes az üzleti és informatikai szakemberekkel együttműködve, a leghatékonyabb IT-megoldások felhasználásával gazdasági problémák megoldási változatainak elkészítésére, informatikai támogatás, fejlesztés kezdeményezésére, végrehajtására. Attitűd: Fontosnak tartja az informatikai szakmai eredmények közvetítését szakmai és az alkalmazási területe egyéb képviselői számára. Törekszik a folyamatos szakmai képzésre és általános önképzésre. Autonomia és felelősség: Feladatvégzéskor szakmai szempontok érvényesítése mellett önálló véleménye van az informatikai rendszerek gazdasági, társadalmi, és biztonsági hatásaival, vonzataival kapcsolatosan. | |
| Tárgy tematikus leírása: Absztrakt adattípusok, reprezentálásuk absztrakt adatszerkezetekkel. Az absztrakt adatszerkezetek ábrázolásának módszerei, a dinamikus memóriagazdálkodás. Elemi adatszerkezetek (tömb, verem, sor, lista) és tipikus alkalmazásaik. Elemi gráfelméleti bevezető. A fa szerkezet és legfontosabb tulajdonságai, műveletei. Gyökeres fák, kupac. Kupacrendezés. Optimumfeladatok fákon. Rendezési algoritmusok. (Buborék, tournament, heap, összefuttatás, gyorsrendezés, Beillesztéses, Shell, radix, külső rendezők, rendezések párhuzamosítása, Batcher). Keresési technikák. (keresési algoritmusok, hasító táblázatok, optimális keresőfák). Szelekciós módszerek (maximum, párhuzamos min-max, k. elem, medián). Technikák algoritmusok gyorsítására (oszd meg és uralkodj, dinamikus programozás, randomizálás). Feladatok algoritmikus megoldhatósága. Turing gépek. P és NP feladatosztályok kapcsolata. P és NP feladatok. Számelméleti algoritmusok, titkosítások | |
| Félévközi számonkérés módja és az aláírás megszerzésének feltétele (Nappali): 2 db zárthelyi dolgozat legalább elégséges szintű megírása. Az elégséges szint a pontok 50%-át jelenti. | |
| Félévközi számonkérés módja és az aláírás megszerzésének feltétele (Levelező): | |
| Gyakorlati jegy / kollokvium teljesítésének módja, értékelése (Nappali): Az írásbeli vizsga elméleti kérdéseket és gyakorlati feladatokat tartalmaz. Mindkét rész jeggyel zárul és 50-50%-ban kerül be a végleges vizsgajegybe, ha egyikük sem elégtelen, egyébként a vizsgajegy elégtelen. Vizsga zh. összetétele: Az elméleti kifejtendő kérdést adunk, kérdésenként 2 pont adható a helyes válaszra. A gyakorlati feladatok 4 pontot érnek. Ha mind az elméleti, mind a számolásos rész legalább elégséges, akkor a vizsgajegy a két jegy számtani átlaga felfelé kerekítve, ha nem egész számnak adódna az átlag. Egyéb esetben a vizsgajegy elégtelen. | |
| Gyakorlati jegy / kollokvium teljesítésének módja, értékelése (Levelező): | |
| Kötelező irodalom: 1. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. : Algoritmusok, Scolar Kiadó, Budapest, 2003 2. Nagy Ferenc, Házy Attila: Adatstruktúrák és algoritmusok (elektronikus jegyzet) 3. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. : Introduction to Algorithms, Third Edition, MIT Press, Cambridge, Massachusetts, USA 4. 5. | |
| Ajánlott irodalom: 1.A. Aho, J. Hopcroft, J. Ullmann: Számítógép algoritmusok tervezése és analízise, Budapest, 1982. 2. D. Knuth: A programozás művészete, Budapest, 19884 3. 4. 5. | |