Delivered at:: School of Data Analysis and Artificial Intelligence

Course type:: Elective course

When:: 3 year, 3, 4 module

Instructor

Fedyanin, Denis

Full Syllabus

Abstract

The course «Combinatorics, Graphs, and Computational Logic» provides strong ideas to combine logic theories (reasoning, arguments, epistemic logic, proofs), graphs theories (social networks, random graphs, transport, argumentations), and combinatorics theories (enumerations, complexity, probability) for analysis of multiagent behavior datasets. It is a high intense course and it might be recommended for advanced students who are capable to move fast through very different domains. The course contains only ideas of the proofs and many very basic facts from logic, graphs, and combinatorics are omitted assuming that students have already taken any Discrete Math Course. It was done to focus on applications to computer science rather than on the beauty of math proofs.

Learning Objectives

Knowledge of the specific properties of data on multi-agent systems, including social networks.
Ability to use combinatorics to assess the likelihood of data corruption, the presence of data properties, and assess the likelihood of a system's behavior in the future.
The practice of evaluating the complexity of data analysis algorithms using combinatorics, including the algorithms for checking the consistency of datasets and other properties.
Application of logic to check the correctness of algorithms.

Expected Learning Outcomes

Ability to calculate the probability of a formula being satisfied according to the given probabilities of other formulas.
Knowledge about important properties of traffic graphs and the prediction of dynamics.
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 model checking tasks for given sets, the relationship between set algebra and Boolean logic, the complexity of deducing theorems from axioms, completeness concept, connection with data compression.
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
Knowledge about the relationship between probability and combinatorics, basic combinatorial formulas, probability of having a property in the database, social networks models, random graphs, the idea of the proof of connectivity, the concept of hypergraphs.

Course Contents

Introduction to applications of Combinatorics, Graphs, and Logic
Combinatorics and probability of having properties in datasets.
Model-checking problems.
Conditional probabilities and reasoning.
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.

Assessment Elements

Контрольная работа
Контрольная работа
Экзамен

Interim Assessment

2021/2022 4th module
0.3 * Контрольная работа + 0.3 * Контрольная работа + 0.4 * Экзамен

Bibliography

Recommended Core Bibliography

A course in combinatorics, Lint van, J. H., 2004
A first course in graph theory and combinatorics, Cioaba, S. M., 2009
Algorithms, DasGupta, S., 2018
An introduction to mathematical reasoning : numbers, sets and functions, Eccles, P. J., 2013
Arguments and actions in social theory, Preston, P., 2009
Data and evidence in linguistics : a plausible argumentation model, Kertesz, A., 2012
Discrete mathematics : proofs, structures, and applications, Garnier, R., 2010
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
Epistemic logic planning : case-based planning adaptation, using epistemic logic revision for robot's decision making, Maghsoudi, S., 2008
Exponential random graph models for social networks : theory, methods, and applications, , 2013
Graph theory and combinatorial optimization, , 2005
Graph theory and interconnection networks, Hsu, L. H., 2009
Graph theory, combinatorics and algorithms : interdisciplinary applications, , 2005
Handbook of social choice and welfare. Vol.1: ., , 2002
Handbook of social choice and welfare. Vol.2: ., , 2011
How to map arguments in political science, Parsons, C., 2010
Human behaviour and traffic networks, , 2004
Introduction to enumerative combinatorics, Bona, M., 2007
Introduction to graph theory, Voloshin, V. I., 2009
Knowledge and social structure : an introduction to the classical argument in the sociology of knowledge, Hamilton, P., 2015
Knowledge representation and reasoning, Brachman, R. J., 2004
Logic and social choice, Murakami, Y., 2016
Logic in computer science : modelling and reasoning about systems, Huth, M., 2004
Mathematical logic for computer science, Ben-Ari, M., 2012
Mathematical structures for computer science : a modern approach to discrete mathematics, Gersting, J., 2007
Mathematical tools for data mining : set theory, partial orders, combinatorics, Simovici, D. A., 2008
Multiagent systems : algorithmic, game-theoretic, and logical foundations, Shoham, Y., 2009
Propositional and predicate calculus : a model of argument, Goldrei, D., 2005
Random graphs, Bollobas, B., 2001
Rational choice politics. Vol.1: Social choice, equilibrium and electoral systems, , 2009
Reasoning about knowledge, , 2003
Structural proof theory, Negri, S., 2008
Theory of social choice on networks : preference, aggregation, and coordination, Stirling, W. C., 2016
Topics in structural graph theory, , 2013
Верификация моделей программ: Model Checking, Кларк, мл., Э. М., 2002

Recommended Additional Bibliography

Algorithms and complexity, Wilf, H. S., 2002
Analogies and theories : formal models of reasoning, Gilboa, I., 2015
Graphs, networks and algorithms, Jungnickel, D., 2005

Bachelor’s Programme 'Applied Mathematics and Information Science'

Combinatorics, Graphs and Computational Logic