Certification Programme description: Theoretical introduction; Finite State Machines (FSMs): introduction to FSMs, examples of FSMs, operations on regular languages, introduction to nondeterministic FSMs, formal definition of nondeterministic FSMs, equivalence of deterministic and nondeterministic FSMs; Regular languages: closure of regular operations, regular expressions, equivalence of regular expressions and regular languages, pumping lemma for regular languages, summary of regular languages; Context free grammars and languages (CFGs and CFLs): introduction to CFGs and CFLs, examples of CFGs, kinds of CFLs, facts about CFLs; Context Sensitive Languages: Chomsky normal form, Chomsky hierarchy and context sensitive languages, pumping lemma for CFLs; Pushdown Automata (PDA): introduction to PDAs, Equivalence of CFGs and PDAs, conclusions from equivalence of CFGs and PDAs; Turing machines (TMs): introduction to TMs, TM examples, definition of TMs and related language classes, the Church-Turing thesis, TM programming techniques, multitape TMs, nondeterminism in TMs, TMs as problem solvers, enumerators; Decidability: decidability and decidable problems, more decidable problems For DFAs, problems concerning CFLs, universal TM, infinity - countable and uncountable, languages that are not Turing recognizable, undecidability of the halting problem, language that is not Turing recognizable, reducibility - a technique for proving undecidability, halting problem - a proof by reduction, computable functions, equivalence of TMs, reducing one language to another, the post correspondence problem, undecidability of the PCP, linear bound automata; Recursion: program that prints itself, TM that writes a description of itself, recursion theorem, results from the recursion theorem, the fixed point theorem; Logic: first-order predicate logic - overview, truth (meaning and proof), true statements and provable statements, Godel`s incompleteness theorem; Complexity: time complexity and big-O notation, computing an algorithm`s runtime, time complexity with different computational models, time complexity classes P and NP, definition of NP and polynomial verifiability, NP-completeness, proof that SAT is NP complete, space complexity classes
Certification Programme version/revision: EITC/IS/CCTFv1r1)Earned ECTS credits: 2
