Магистратура
2022/2023
Дискретная математика
Статус:
Курс обязательный
Направление:
01.04.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 1 модуль
Формат изучения:
с онлайн-курсом
Онлайн-часы:
82
Охват аудитории:
для своего кампуса
Преподаватели:
Лопаткин Виктор Евгеньевич
Прогр. обучения:
Магистр по наукам о данных
Язык:
английский
Кредиты:
5
Контактные часы:
8
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
- Use methods of Combinatorics to count objects
- Calculate probabilities of events using definition and properties of probabilities
- Analyze the structure of graphs using parameters
- Apply knowledge in Discrete Mathematics for social network analysis
Expected Learning Outcomes
- Analyze the structure of graphs using parameters: clustering coefficients, diameter etc.
- Apply basic combinatorial methods in programming
- Apply standard operations on sets
- Calculate probabilities of events using definition and properties of probabilities
- Categorize basic combinatorial problems into standard settings
- Categorize combinatorial problems into standard settings
- Combine several combinatorial settings to solve counting problems
- Compare social network graphs (from datasets) with random graphs, and see how the parameters change.
- Develop graph analysis software in Python using NetworkX
- Discover properties and types of graphs, given by geometric (pictorial) representation
- Give examples of graph parameters and their usage in network analysis
- Give examples of graphs used in various application areas
- Give examples of random experiments, outcomes and events
- Practice in using NetworkX for social network analysis
- Recognize operation on events (union, intersection, complement event)
- Use basic methods of combinatorics to count objects
- Use basic properties of binomial coefficients
- Use graph parameters for establishing non-isomorphism of graphs
- Use methods of combinatorics to count objects
- Use standard algorithms for traversing graphs
Course Contents
- Basic Combinatorics
- Advanced Combinatorics
- Discrete Probability
- Introduction to Graphs
- Basic Graph Parameters
- Graphs of Social Networks
Assessment Elements
- pr2 - Ego Network Centers
- pr1 - Clustering
- sga1 - Midterm Quiz
- sga2 - Graphs
- quizzesWeekly quizzes
Interim Assessment
- 2022/2023 1st module0.04 * pr1 - Clustering + 0.76 * quizzes + 0.04 * pr2 - Ego Network Centers + 0.08 * sga2 - Graphs + 0.08 * sga1 - Midterm Quiz
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