Bachelor 2024/2025

Combinatorics, Graphs and Logic

Type: Compulsory course (Applied Mathematics and Information Science)

Area of studies: Applied Mathematics and Information Science

Delivered by: School of Data Analysis and Artificial Intelligence

Where: Faculty of Computer Science

When: 3 year, 3, 4 module

Mode of studies: offline

Open to: students of one campus

Instructors: Denis Fedyanin

Language: English

ECTS credits: 6

Course Syllabus

Abstract

«Combinatorics, Graphs and Boolean Logic» class covers more complicated sections of discrete mathematics. The combinatorics chapter is devoted to in-depth combinatorics, recursive sequences and the group action on the sets. The graph chapter covers theoretical foundations of algebric graph theory, algorithms on graphs and their applications. Computational Logic chapter covers modern methods for closed classes of Boolean logic, propositional calculus, predicate logic, and properties of classes to have a system of identities, as well as Prolog and Resolution Method. Cryptography applications is not included for the purpose to not interfere with parallel courses. As a result, the CGCL greatly advances students’ knowledge in the fields of modern discrete mathematics theory and applications, preparing our students to professional work in research projects and IT-industry. So, despite its theoretical content, the class has got many applications in the theory of algorithms, borrowing many math/IT concepts. This course may be useful for collaboration with the following disciplines: - Information theory - Ordered sets and lattices - Applied Graph Theory - Computer Algebra - Semantic Web The importance of discrete mathematics has increased significantly since last 50 years, although there are few full handbooks of modern methods in its areas. The purpose of the course CGCL is to provide systematic review of certain fields of discrete mathematics for computer scientists, mathematicians, and others, such as students, physical and social scientists, who need information about discrete mathematics. The scope of material includes the many areas generally considered to be parts of discrete mathematics, focusing on the information considered essential to its application in computer science and engineering. Some of the fundamental topic areas covered includes: - combinatorial designs - recurrence relations - generating functions - computational geometry - graph theory - enumeration trees - abstract algebra - logic and set theory - data structures and algorithms - discrete optimization