Kurzus nemzetközi vendég- és részidős hallgatóknak

Kar
Informatikai Kar
Szervezet
IK Algoritmusok és Alkalmazásaik Tanszék
Kód
IP-18fSZEA2G
Cím
A számításelmélet alapjai II. Gy
Tervezett félév
Őszi
ECTS
3
Nyelv
en
Oktatás célja
a) tudása - 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. b) képességei - 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 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. - Képes az informatika formális modelljeinek alkalmazására.
Tantárgy tartalma
A számítástudomány rövid története. A Turing-gép, mint algoritmus modell.  Church-Turing-tézis. A nulladrendû és elsõrendû logika alapfogalmai. Sorozatok aszimptotikus növekedése. Többszalagos, nemdeterminsztikus, off-line és szófüggvényeket kiszámító Turing-gépek. Példák eldönthetetlen és nem rekurzívan felsorolható nyelvekre, eldönthetetlenség bizonyítása visszavezetéssel. CF nyelvtanokkal, elsõrendû logikával kapcsolatos  eldönthetetlen kérdések. Az algoritmikus és a Chomsky nyelvosztályok kapcsolata. A P, NP, coNP osztályok, kapcsolatuk. P=?NP. A polinom idejû (Karp-) visszavezetés fogalma, NP-teljesség. NP-teljes problémák: SAT és különbözõ változatai, gráfelméleti problémák, Hamilton út és változatai, utazóügynök probléma, hátizsák probléma, ládapakolás. A tárbonyolultság fogalma, elérhetõségi módszer, Savitch tétele, hierarchia tétel. Kitekintés egyéb bonyolultsági osztályokra.
Számonkérés és értékelés
A hallgatóknak teljesíteniük kell a kurzus tanára által a félév elején ismertetett követelményeket, mely általában tartalmaz 2 sikeres zárthelyi dolgozatot és egy rendszeres részvételre vonatkozó feltételt. Ötfokozatú értékelés.
Irodalomjegyzék
Gazdag Zsolt: Bevezetés a számításelméletbe, ELTE Digitális Intézményi Tudástár, 2015. Ésik Zoltán: A számítástudomány alapjai, Typotex, 2011. Rónyai L. Ivanyos G., Szabó R. Algoritmusok, Typotex, 1999. Lovász L.: Algoritmusok bonyolultsága, Typotex, 2014. Pásztorné Varga K., Várterész M.: A matematikai logika alkalmazásszemléletû tárgyalása, 2003. M. Ben-Ari: Mathematical Logic for Computer Science, 3rd ed., Springer, 2012. J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation, 3rd ed. Pearson Education Ltd., 2014. M.R. Garey, D.S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979. Michael Sipser: Introduction to the Theory of Computation, 3rd ed., Cengage Learning, 2013. A. Salomaa, G. Rozenberg (eds.): The Handbook of Formal Languages I., II. , Springer Publishing Company, 1997.

Kurzus szakjai

Név (kód) Nyelv Szint Kötelező Tanév ...
Erasmus program keretében (IK-ERASMUS-NXXX) en Kötelező
programtervező informatikus - F (ELTE-K7473-S-N-10-ENG) en 6 Kötelező 3/3
Vissza