| Tantárgy neve: Algoritmusok és vizsgálatuk |
Tantárgy Neptun kódja: Nappali: GEMAK121M 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: 1 | Előfeltétel: |
| Óraszám/hét: Előadás (nappali): 3 Gyakorlat (nappali): 1 | Számonkérés módja: kollokvium |
| Kreditpont: 5 | Munkarend: Nappali |
| Tantárgy feladata és célja: A mérnök informatikus mesterszak elméleti alapozása, modellek és algoritmusok fejlesztése, vizsgálata, használata Tudás: Érti az informatikai alkalmazások fejlesztéshez szükséges természettudományos és mérnöki módszerek elvét. Az informatikai szakmán belül, a specializációtól függően mélyebb elméleti és gyakorlati ismeretekkel rendelkezik az alábbiak közül egy vagy néhány területen: szoftvertervezés, rendszerszimuláció és -modellezés, kommunikációs hálózatok, mobil- és erőforrás-korlátos alkalmazások, számítógépes grafika és képfeldolgozás, kritikus és beágyazott rendszerek, médiainformatika, IT-biztonság, párhuzamos rendszerek, intelligens rendszerek, számításelmélet, adatbázisok. Képesség: Képes törvényszerűségeket, összefüggéseket feltárni és megérteni. A megszerzett tudást képes alkalmazni és a gyakorlatban hasznosítani. Képes problémamegoldó technikákat használni a szoftver- és alkalmazásfejlesztés során. Attitűd: Nyitott és elkötelezett az önművelésre, önfejlesztésre, az egyéni tudás, ismeret elmélyítésére, bővítésére a természettudományok, a mérnöki és informatikai tudományok területén. Munkája során vizsgálja a kutatási, fejlesztési és innovációs célok kitűzésének lehetőségét és törekszik azok megvalósítására. Autonomia és felelősség: Önállóan tölt be informatikai munkakört, amelyben a teljes folyamatot kezében tartva, szakmailag felelős módon dolgozik. | |
| Tárgy tematikus leírása: Rekurzív függvények és algoritmusok. Parciálisan rekurzív függvények, algoritmusok, kiszámíthatóság. A Turing gép fogalma, működése, idő- és tárigénye. Algoritmikus eldönthetőség. Szimuláció fogalma, szimulációs tételek. Gödel tétel. Rekurzív és rekurzívan felsorolható nyelvek, rekurzív illetve parciálisan rekurzív függvények. Példák rekurzivitásra. Az R, Re, coR, coRE nyelvosztályok és ezek kapcsolata. Nevezetes nyelvek és bonyolultságuk. Idő és tárkapacitásos- univerzális Turing-gépek fogalma, Church-Turing tézis, a Turing kiszámíthatóság A regisztergépek programjai, kiszámítási sorozatok. Felsorolható rekurzív halmazok. Idő-tár tétel, nevezetes nyelvek (P, PSPACE, EXPTIME). Nemdeterminisztikus Turing-gépek, az NP- és coNP-nyelvosztály, tanú tétel. A P és NP osztályok kapcsolata. Példák NP és coNP-beli nyelvekre. NP teljes problémák, Karp redukció, Cook-Levin tétel. Kolmogorov bonyolultság és alkalmazásai. Bonyolultsági osztályok. Algoritmustervezési módszerek. Közelítő és randomizált algoritmusok, az RP-nyelvosztály, prímtesztelés | |
| 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): A kollokvium írásbeli, amely elméleti kérdéseket (definíciók, tételek) tartalmaznak, valamint egy gyakorlati példát. Az elégséges szinthez a pontok 50%-át kell elérni. A közepeshez 65%, a jóhoz 75%, a jeleshez 85%-ot kell teljesíteni. | |
| Gyakorlati jegy / kollokvium teljesítésének módja, értékelése (Levelező): | |
| Kötelező irodalom: 1. Lovász L.: Computation complexity. ftp://ftp.cs.yale.edu/pub/lovasz.pub 2. Lovász L.: Algoritmusok bonyolultsága. Budapest, Tankönyvkiadó, 1990 3. Manyin, J. I.: Bevezetés a kiszámíthatóság matematikai elméletébe. Műszaki Könyvkiadó, 1985 4. 5. | |
| Ajánlott irodalom: 1. Trahtenbrot, B. A.: Algoritmusok és absztrakt automaták. Műszaki Könyvkiadó, 1987. 2. Papadimitriou, H.: Számítási bonyolultság. Egyetemi tankönyv, Novadat, 1999. 3. Aurello, G.: Algoritmusok és rekurzív függvények bonyolultságelmélete. Műszaki Könyvkiadó, 1984. 4. 5. | |