• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Магистерская программа «Науки о данных (Data Science)»

Discrete Mathematics for Application and Algorithm Development

2021/2022
Учебный год
ENG
Обучение ведется на английском языке
3
Кредиты
Статус:
Курс адаптационный
Когда читается:
1-й курс, 1 модуль

Преподаватели

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

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

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

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
Assessment Elements

Assessment Elements

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

  • 2021/2022 1st module
    0.5 * Homeworks + 0.5 * Exam
Bibliography

Bibliography

Recommended Core Bibliography

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

Recommended Additional Bibliography

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms (3rd edition). – MIT Press, 2009. – 1292 pp.