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-18fSZEA2E

Cím

A számításelmélet alapjai II. Ea

Tervezett félév

Őszi

Meghirdetve

2024/25/1, 2024/25/2

ECTS

2

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

kollokvium (5)

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