| 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 Előadás (levelező): 16 | 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 az informatikai szakterületének műveléséhez szükséges természettudományi elveket és módszereket (matematika, fizika, egyéb természettudományok). Ismeri az informatikai rendszerek hardver és szoftver elemeinek működését, megvalósításuk technológiáját, működtetéséből származó feladatok megoldásának mikéntjét, valamint informatikai és egyéb műszaki rendszerek összekapcsolásának lehetőségeit. Ismeri a főbb programozási paradigmákat, programnyelveket, fejlesztési eszközöket. Tudása kiterjed az információs rendszerek modellezésére, adatbázis alapú rendszerek kialakítására, számítógépes hálózatok felépítésére, működésére és implementációjára, felhasználói interfészek és grafikus alkalmazások megvalósítására, intelligens rendszerek jellemzőire, a mobil alkalmazásfejlesztés sajátosságaira, a korszerű, általános célú operációs rendszerek menedzselésére, és az IT biztonság szempontjaira. Képesség: Felhasználja az informatikai szakterületének műveléséhez szükséges természettudományi elveket és módszereket (matematika, fizika, egyéb természettudományok) az informatikai rendszerek kialakítását célzó mérnöki munkájában. Képes szakterületén elemzési, specifikációs, tervezési, fejlesztési és üzemeltetési feladatok ellátására, alkalmazza a fejlesztési módszertanokat, hibakeresési, tesztelési és minőségbiztosítási eljárásokat. Attitűd: Hitelesen képviseli a mérnöki és informatikai szakterületek szakmai alapelveit. Nyitott az új módszerek, programozási nyelvek, eljárások megismerésére és azok készség szintű elsajátítására. Autonomia és felelősség: Felelősséget érez az önálló és csoportban végzett informatikai rendszerelemzői, -fejlesztői és -üzemeltetési tevékenységéért. | |
| 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ő): 2 db zárthelyi dolgozat legalább elégséges szintű megírása. Az elégséges szint a pontok 50%-át jelenti. | |
| 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ő): 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. | |
| 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. | |