Lectures:
- Basics of propositional and predicate logic.
- Analysis of sentences of a natural language in the language of propositional and predicate logic.
- Deduction of consequences. Set theoretical / semantic proofs.
- Basics of resolution method.
- Formal languages - basic notions (an alphabet, a word, a language). Operations
on languages. Finite automata.
- Construction of finite automata. Nondeterinistic finite automata.
- Transformation of nondeterministic finite automata to deterministic.
Regular expressions.
- Context-free grammar and languages.
- Algorithmic problems. Models of computation (Turing machines and RAM machines).
- Asymptotic notation. Complexity of algorithms.
- Complexity of problems. Complexity classes. Reductions between problems. NP-complete
problems.
- Algorithmically undecidable problems.
Tutorials:
- Recalling of basics of the set theory, relations, functions and the graph theory.
- Propositional and predicate logic.
- Analysis of sentences of a natural language in the language of propositional and predicate logic.
- Deduction of consequences. Set theoretical / semantic proofs.
- Resolution method.
- Operations with languages.
- Construction of finite automata.
- Transformation of nondeterministic automata to deterministic.
- Regular expressions.
- Context-free grammars.
- Turing machines and RAM machines.
- Asymptotic notation. Complexity of algorithms.
- Complexity of problems. Complexity classes.
- Basics of propositional and predicate logic.
- Analysis of sentences of a natural language in the language of propositional and predicate logic.
- Deduction of consequences. Set theoretical / semantic proofs.
- Basics of resolution method.
- Formal languages - basic notions (an alphabet, a word, a language). Operations
on languages. Finite automata.
- Construction of finite automata. Nondeterinistic finite automata.
- Transformation of nondeterministic finite automata to deterministic.
Regular expressions.
- Context-free grammar and languages.
- Algorithmic problems. Models of computation (Turing machines and RAM machines).
- Asymptotic notation. Complexity of algorithms.
- Complexity of problems. Complexity classes. Reductions between problems. NP-complete
problems.
- Algorithmically undecidable problems.
Tutorials:
- Recalling of basics of the set theory, relations, functions and the graph theory.
- Propositional and predicate logic.
- Analysis of sentences of a natural language in the language of propositional and predicate logic.
- Deduction of consequences. Set theoretical / semantic proofs.
- Resolution method.
- Operations with languages.
- Construction of finite automata.
- Transformation of nondeterministic automata to deterministic.
- Regular expressions.
- Context-free grammars.
- Turing machines and RAM machines.
- Asymptotic notation. Complexity of algorithms.
- Complexity of problems. Complexity classes.