Discrete Mathematics for Application and Algorithm Development
- Understanding of classical propositional logic (in the Hilbert-style and/or resolution calculus).
- Understanding of classical predicate logic.
- Understanding of graphs and algorithms on them (DFS, BFS, Dijkstra's algorithm etc).
- Understanding of algorithms on strings: pattern-matching, maximal common substring, etc.
- Understanding of regular expressions, effective lexical analysis.
- Understanding of context-free grammars and parsing algorithms for them (CYK, LR).
- Students know classical propositional calculi.
- Students know classical predicate calculi.
- Students know the notion of graph and basic algorithms on graphs.
- Students implement algorithms on graphs.
- Students implement algorithms on strings.
- Students formalize the structure of a given formal language using regular expressions.
- Students formalize the structure of a given formal language using contextfree grammars.
- Students use automated parser generators to utilize the aforemented grammars.
- Classical Propositional LogicPropositional formulae. Classical (Boolean) interpretation of propositional formulae. Tautologies and satisfiable formulae. Classical propositional calculus (Hilbert-style derivations). Resolution method.
- Classical Predicate LogicPredicate formulae; quantifiers. Interpretations (models) of predicate logic. Predicate calculus. Completeness and undecidability of classical predicate logic (without proof). Proof search and proof assistants (overview).
- Basic Notions of Graph TheoryDefinition of graph. Special types of graphs. Trees. Using graphs for modelling networks etc. Isomorphism of graphs. Euler graphs.
- Algorithms on GraphsBFS. DFS. Dijkstra's algorithm. Checking whether a graph is a Euler graph. For advanced students: the notion of NP-hardness. NP-hardness of 3-SAT and Hamiltonian path problems
- Algorithms on Strings
- Regular ExpressionsThe notion of regular expression. Regular expressions and finite automata (Kleene's theorem): sketch of proof, examples. Algorithms for matching with regular expressions. Implementation of regular expressions (e.g., in Python).
- Context-Free Grammars and Parsing AlgorithmsContext-free grammars and context-free languages. Parsing with CFG: CYK, LR (overview). The limits of CFG (pumping lemma). Practical parsing using CFG: the Bison/YACC parser generator.
- Homeworks3 assignments during the semester: one written, two programming.
- ExamWritten exam. Preparation time — 180 min. The final assessment is the final exam. It will consist of 7 problems graded equally. No material is allowed for the exam.