Combinatorics, Graphs and Computational Logic
- To fill the gaps in modern problems of Discrete mathematics.
- To learn practical problem-solving skills, which can be later applied in algorithmic theory.
- To develop fundamental knowledge of combinatorics and complexity.
- To develop practical skills needed in modern logic.
- To give practical knowledge, which is needed in many courses theoretical informatics.
- Students know basic concepts in combinatorics and group algebra, social network analysis, first-order logic and knowledge bases.
- Students use combinatorial statements interpreted in generating functions of regular sets, use library Igraph for analyzing graphs in R programming environment, use Prolog for querying knowledge bases.
- Students analyze combinatorial problems, extract and interpret descriptive statistics from social networks, apply resolution techniques for finding the answer for first-order query.
- Sets, relations, functions, simplest combinatorial formulas
- Euler formula for intersecting sets, Newton binomial, asymptotic combinatorial identities
- Linear recurrent sequences and regular generating functions
- Group action on finite sets
- Graphs and trees, basic theorems on graphs and coloring of graph
- Boolean logic and completeness of functional systems
- Predicate logic, basic notions, prefix form
- Normal forms, complexity for Boolean functions realizations by schemes and formulas
- Basis and finite total equivalence systems for closed classes of Boolean logic
- Class worksTwo class works. <br />Written work during 120 minutes.
- ExamSpeaking exam with preparation time about 60 minutes.
- Garnier, R., Taylor, J. Discrete mathematics: proofs, structures and applications. – CRC press, 2009. – 847 pp.
- Colbourn, Charles, Dinitz, Jeffrey. Handbook of Combinatorial Designs, Second Edition (Discrete Mathematics and Its Applications). – 2007. – 1016 pp.