• A
• A
• A
• ABC
• ABC
• ABC
• А
• А
• А
• А
• А
Regular version of the site

Discrete Mathematics for Application and Algorithm Development

2019/2020
ENG
Instruction in English
3
ECTS credits
Course type:
Bridging course
When:
1 year, 1 module

Course Syllabus

Abstract

This course includes the basics of mathematical logic, graph theory, combinatorics, and formal language theory. The emphasis is put upon the algorithmic side: mathematical results act as a support for effecient algorithms operating on graphs, strings, and, finally, parsing algorithms for regular expressions and contextfree grammars. The course is actually twofold: besides usual «chalk-and-blackboard» mathematical part, it also includes a practical one, i.e., implementing the algorithms discussed in the course. The students are supposed and encouraged to (but not restricted to) use the Python language. For the last part, parsing algorithms, PyBison is also welcome.

Learning Objectives

• 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).

Expected Learning Outcomes

• 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.

Course Contents

• Classical Propositional Logic
Propositional formulae. Classical (Boolean) interpretation of propositional formulae. Tautologies and satisfiable formulae. Classical propositional calculus (Hilbert-style derivations). Resolution method.
• Classical Predicate Logic
Predicate 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 Theory
Definition of graph. Special types of graphs. Trees. Using graphs for modelling networks etc. Isomorphism of graphs. Euler graphs.
• Algorithms on Graphs
BFS. 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 Expressions
The 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 Algorithms
Context-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.

Assessment Elements

• Homeworks
3 assignments during the semester: one written, two programming.
• Exam
Written 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.

Interim Assessment

• Interim assessment (1 module)
0.5 * Exam + 0.5 * Homeworks

Recommended Core Bibliography

• Chiswell, I., Hodges, W. Mathematical logic. – Oxford University Press, 2007. – 250 pp.