Master
2021/2022
Discrete Mathematics for Application and Algorithm Development
Type:
Bridging course (Data Science)
Area of studies:
Applied Mathematics and Informatics
Delivered by:
School of Data Analysis and Artificial Intelligence
Where:
Faculty of Computer Science
When:
1 year, 1 module
Mode of studies:
offline
Open to:
students of all HSE University campuses
Master’s programme:
Data Science
Language:
English
ECTS credits:
3
Contact hours:
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 formalize the structure of a given formal language using contextfree grammars.
- Students formalize the structure of a given formal language using regular expressions.
- Students implement algorithms on graphs.
- Students implement algorithms on strings.
- Students know classical predicate calculi.
- Students know classical propositional calculi.
- Students know the notion of graph and basic algorithms on graphs.
- Students use automated parser generators to utilize the aforemented grammars.
Course Contents
- Classical Propositional Logic
- Classical Predicate Logic
- Basic Notions of Graph Theory
- Algorithms on Graphs
- Algorithms on Strings
- Regular Expressions
- Context-Free Grammars and Parsing Algorithms
