| Tantárgy neve: Algoritmusok és vizsgálatuk |
Tantárgy Neptun kódja: Nappali: GEMAK234-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: 5 | Előfeltétel:GEMAK121-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: 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. | |