Магистратура
2020/2021
Дискретная математика для разработки алгоритмов и программ
Статус:
Курс адаптационный (Науки о данных)
Направление:
01.04.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 1 модуль
Формат изучения:
без онлайн-курса
Прогр. обучения:
Науки о данных
Язык:
английский
Кредиты:
3
Контактные часы:
28
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 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.
