Бакалавриат
2019/2020
Комбинаторика, графы и вычислительная логика
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
3-й курс, 3, 4 модуль
Формат изучения:
без онлайн-курса
Преподаватели:
Гольденгорин Борис Исаакович,
Тюрюмина Элла Яковлевна
Язык:
английский
Кредиты:
6
Контактные часы:
80
Course Syllabus
Abstract
«Combinatorics, Graphs and Computational 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
Learning Objectives
- 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.
Expected Learning Outcomes
- 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.
Course Contents
- 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
Assessment Elements
- Class worksTwo class works. <br />Written work during 120 minutes.
- ExamSpeaking exam with preparation time about 60 minutes. Экзамен в письменной форме. За 15 минут до начала студенты заходят на групповую почту. Преподаватель высылает им задание. Студенты пишут на бумаге, в течение 5-ти минут после окончания экзамена, высылают скан/фото работы на почту преподавателя. При наличии технических проблем, студент должен позвонить преподавателю.
Bibliography
Recommended Core Bibliography
- Garnier, R., Taylor, J. Discrete mathematics: proofs, structures and applications. – CRC press, 2009. – 847 pp.
Recommended Additional Bibliography
- Colbourn, Charles, Dinitz, Jeffrey. Handbook of Combinatorial Designs, Second Edition (Discrete Mathematics and Its Applications). – 2007. – 1016 pp.