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

Discrete Mathematics for Application and Algorithm Development

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

Instructor

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

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

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

  • Interim assessment (1 module)
    0.5 * Exam + 0.5 * Homeworks
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.