| 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 az informatikai szakterület tudásanyagát megalapozó általános és specifikus matematikai, számítástudományi elveket, tényeket, szabályokat, összefüggéseket, és eljárásokat. Az érintett területek: analízis (kalkulus), numerikus analízis, diszkrét matematika, lineáris algebra, operációkutatás, valószínűségszámítás és statisztika, logikai alapok, számításelmélet, algoritmusok tervezése és elemzése, automaták és formális nyelvek, mesterséges intelligencia alapjai. Ismeri és érti az informatikai szakterület legfontosabb általános elméleteit, összefüggéseit, tényanyagát és az ezekhez szükséges felépítő fogalomrendszert, különösen az alábbi területeken: a programozás módszertani alapjai, programozási nyelvek, fordítóprogramok, alkalmazások fejlesztése, programozási környezet; számítógép architektúrák, operációs rendszerek, számítógépes hálózatok, osztott rendszerek, az adatbázisok elméleti alapjai. Képesség: Képes az általános és specifikus matematikai, számítástudományi elveket, tényeket, szabályokat, összefüggéseket alkalmazni informatikai szakterületen. Képes az informatika formális modelljeinek alkalmazására. Képes az informatikai szakterület tudásanyagát alkalmazni algoritmusok tervezésére, elemzésére és implementálására a legfontosabb programozási paradigmák figyelembe vételével. Képes informatikai tudását az elsajátított matematikai, számítástudományi elvek, tények, szabályok, eljárások alapján folyamatosan fejleszteni. Attitűd: Vállalja és hitelesen képviseli informatikai szakterülete szakmai alapelveit. Törekszik a folyamatos szakmai képzésre és általános önképzésre. Autonomia és felelősség: Felelősséget vállal szakmai tevékenységéért. Törekszik a hatékony és minőségi munkavégzésre. | |
| 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. 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. | |