A tantárgy az alábbi témakörök ismeretére épít:
Algebra, lineáris algebra.
A tantárgy szerepe a képzés céljának megvalósításában:
TTK Matematikus és Alkalmazott matematikus MSc képzések kötelezően választható törzstárgya
A tantárgy részletes tematikája magyarul és angolul:
Induktív adattípusok, rekurzív függvények, lambda-kalkulus, Curry-Howard-Lambek-izomorfizmus. Algoritmikus bizonyításkeresés a különböző rendű logikákban. Bonyolultságelméleti eredmények. A logika számítástudományban alkalmazott Kripke- és algebrai szemantikái.
Az algoritmus fogalmának formális modellje: különböző Turing-gépek és egyenértékűségük, Church-Turing-tézis. Rekurzív és rekurzívan felsorolható nyelvek osztálya, zártsági tulajdonságaik, nevezetes nem rekurzív, illetve nem rekurzívan felsorolható nyelvek. Bonyolultságelméleti alapfogalmak, nevezetes idő és tárosztályok. Kolmogorov-bonyolultság.
Inductive data types, recursive functions, lambda calculus, Curry-Howard-Lambek isomorphism. Algorithmic proof search in various order logics. Complexity results. Kripke and algebraic semantics of logic in computer science.
Formal model of algorithms: some Turing machines and their equivalences, Church-Turing thesis. The class of recursively enumerable languages, their closure properties, notable non-recursive and non-recursively enumerable languages. Basic concepts in complexity theory, notable time and space complexity classes. Kolmogorov complexity.
Követelmények szorgalmi időszakban:
Két zárthelyi dolgozat teljesítése és házi feladok elkészítése.
Pótlási lehetőségek:
A TVSz előírásai szerint.
Konzultációs lehetőségek:
Jegyzet, tankönyv, felhasználható irodalom:
Lambek, J., Scott, P.: Introduction to Higher Order Categorical Logic. Cambridge Univ. Press, 1994.
Sørensen, M., Urzyczyn, P.: Lectures on the Curry-Howard Isomorphism. Elsevier, 2006.
Sipser, M.: Introduction to the Theory of Computation. Boston, Course Technology, 2020.
Cormen, T., et al.: Introduction to Algorithms. Cambridge, Massachusett, The Mit Press, 2001.
Nyomtatóbarát változat
