Магистратура
2020/2021
Дискретная математика
Статус:
Курс обязательный (Магистр по наукам о данных)
Направление:
01.04.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 1 семестр
Формат изучения:
без онлайн-курса
Преподаватели:
Промыслов Валентин Валерьевич
Прогр. обучения:
Магистр по наукам о данных
Язык:
английский
Кредиты:
5
Контактные часы:
90
Course Syllabus
Abstract
This course encompasses various topics in discrete mathematics that are relevant for data analysis. We will begin with a brief introduction to combinatorics, a branch of mathematics concerned with counting. Familiarity with this topic is critical for anyone who wants to work in data analysis or computer science. We will learn how to put our new knowledge into practice, for example, we will count the number of features in a dataset and estimate the time required for a Python program to run. Next, we will use our knowledge of combinatorics to study the Basic Probability Theory. Probability is the cornerstone of data analysis, and we will consider it in much more detail later. However, this section will allow you to get a taste of the probability theory and learn important information which will be essential for the Algorithms and Data Structures course. Finally, we will study a combinatorial structure that remains most relevant for data analysis, namely graphs. Graphs can be found everywhere around us, and we will provide you with numerous examples proving this statement. In this course, we will focus on social network graphs. You will learn the most important notions of the graph theory, have a look at how social network graphs work and study their basic properties. At the end of the course, you will be expected to complete a project related to social graphs. Topics: ● Basic combinatorics ● Advanced combinatorics ● Discrete probability ● Introduction to graphs ● Basic graph parameters ● Social graphs
Learning Objectives
- Apply basic knowledge in discrete mathematics to problems in data sceince
- Solve problems in discrete mathematics
Expected Learning Outcomes
- Use basic methods of combinatorics to count objects
- Apply standard operations on sets
- Categorize basic combinatorial problems into standard settings
- Apply basic combinatorial methods in programming
- Combine several combinatorial settings to solve counting problems
- Categorize combinatorial problems into standard settings
- Use methods of combinatorics to count objects
- Use basic properties of binomial coefficients
- Give examples of random experiments, outcomes and events
- Calculate probabilities of events using definition and properties of probabilities
- Recognize operation on events (union, intersection, complement event)
- Give examples of graphs used in various application areas
- Use standard algorithms for traversing graphs
- Discover properties and types of graphs, given by geometric (pictorial) representation
- Give examples of graph parameters and their usage in network analysis
- Use graph parameters for establishing non-isomorphism of graphs
- Analyze the structure of graphs using parameters: clustering coefficients, diameter etc.
- Develop graph analysis software in Python using NetworkX
- Compare social network graphs (from datasets) with random graphs, and see how the parameters change.
- Practice in using NetworkX for social network analysis
Course Contents
- Basic CombinatoricsSuppose we need to count certain objects. Can we do anything better than just list all the objects? Do we need to create a list of all our data entries to check whether we have enough data to teach our ML model? Is there a way to tell whether our algorithm will run in a reasonable time before implementing and actually running it? All these questions are addressed by a mathematical field called Combinatorics. In this module we will give an introduction to this field that will help us to answer basic versions of the above questions.
- Advanced CombinatoricsIn the first week we have already considered most of the standard settings in Combinatorics, that allow us to address many counting problems. However, successful application of this knowledge on practice requires considerable experience in this kind of problems. The goal of this module is twofold. First, we study extensively more advanced combinatorial settings. We discuss in more detail binomial coefficients. Also, we address one more standard setting, combinations with repetitions. The second goal of the course is to practice counting. We will gain some experience in this by discussing various problems in Combinatorics.
- Discrete ProbabilityProbability theory is a mathematical foundation of Statistics, the core of Data Science. During this week we study discrete probability, the first chapter of the probability theory, closely related to combinatorics. We discuss random experiments, their outcomes and events, introduce the notion of probability and some basic rules that follow immediately from the combinatorial results studied before. We also study simple probabilistic models like coin-tossing that will be used later.
- Introduction to GraphsGraphs represent objects and relations between them in a compact geometric form. Objects are represented by vertices of a graph and relations correspond to edges. Applications of graphs include geoinformational systems (vertices are cities, edges are roads), social network analysis (people and friendship relations), chemistry (graphs of molecular structure), computer network topology, and many more. During this week, we introduce basic notions of graph theory and discuss basic algorithms on graphs.
- Basic Graph ParametersGraph parameters, also called graph properties and graph invariants, are values (usually numerical), which are calculated for a given graph and depend only on its abstract structure (not, say, on a particular way of drawing the graph on a plane). Graph parameters are useful in data science, since they reduce a big amount of data (the graph) to a small one (the parameter), while conveying important information about the graph. We discuss some of the basic graph parameters in this module.
- Graphs of Social NetworksIn this final part of the course we discuss a Python library for working with graphs, called NetworkX. In NetworkX, one can create and modify graphs, compute graph parameters, visualize graphs, etc. We shall show how NetworkX is used to operate on graphs coming from a real-world dataset.
Interim Assessment
- Interim assessment (1 semester)The results of all tests are add up. THe following list defines the translation of the fraction of solved test to grades. For 10 at least 90%, for 9 at least 85%, for 8 at least 80%, for 7 at least 75%, for 6 at least 70%, for 5 at least 65%, for 4 at least 60$, for 3 at least 40%, for 2 at least 20%.
Bibliography
Recommended Core Bibliography
- Lovász, L., Pelikán, J., & Vsztergombi, K. (2003). Discrete Mathematics : Elementary and Beyond. New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=108108
Recommended Additional Bibliography
- Conradie, W., & Goranko, V. (2015). Logic and Discrete Mathematics : A Concise Introduction, Solutions Manual. Chichester, West Sussex: Wiley. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=987020