Бакалавриат
2022/2023
Комбинаторика, графы и булева логика
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
3-й курс, 3, 4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Язык:
английский
Кредиты:
6
Контактные часы:
80
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
Learning Objectives
- To fill the gaps in modern problems of Discrete mathematics.
- To develop fundamental knowledge of combinatorics and complexity.
- To give practical knowledge, which is needed in many courses theoretical informatics.
Expected Learning Outcomes
- Knowledge about logic in programming, checking the correctness of programs, elements of proof theory.
- Knowledge about modal and epistemic logic, Binary Decision Tree as a partial solution to the complexity curse, making decisions in multi-agent systems, the complexity of manipulation in Social Choice problems. o Shapley vector and corporate game theory.
- Knowledge about polysemy in linguistics and combinatorics, graphs of abstract argumentation - open problem argument extraction, properties of graphs of abstract argumentation, the problem of propagating arguments on graphs.
- Knowledge about properties of multiagent systems datasets, properties of social media data, social media metrics, text datasets of social networks, equilibrium in social systems, game theory, behavior prediction, search for anomalies in datasets
- Knowledge about the application of group theory in data analysis, Poya's theorem (without proof), indistinguishability in logic, common knowledge of robots, enumerations for graphs, the complexity of some famous algorithms.
- Knowledge about the inconsistency and incompleteness of data, evaluation of the probability of the truth of the formula (as a response to a binary query to the database) with incomplete or conflicting information, difficulty performing an assessment of inconsistency, relationship with modal logic, and classification of requests
Course Contents
- Introduction to applications of Combinatorics, Graphs, and Logic
- Combinatorics and probability of having properties in datasets.
- The enumeration in datasets and estimation of datasets sizes.
- Complexity in social choice problems, cooperative decision making, and epistemic logic.
- Important properties of traffic graphs and prediction of dynamics.
- Inconsistency and incompleteness of data.
- Combinatorics and logic in argumentation graphs and linguistics.
- Logic in programming and automatic proofs.
- Model-checking problems.
- Conditional probabilities and reasoning.
Bibliography
Recommended Core Bibliography
- A first course in graph theory and combinatorics, Cioaba, S. M., 2009
Recommended Additional Bibliography
- Enumerative combinatorics. Vol.1: ., Stanley, R. P., 2012
- Enumerative combinatorics. Vol.2: ., Stanley, R. P., 2004
- Epistemic logic for AI and computer science, Meyer, J.-J. C., 2004
- Exponential random graph models for social networks : theory, methods, and applications, , 2013
- Introduction to enumerative combinatorics, Bona, M., 2007