Бакалавриат
2022/2023
Дискретная математика 2
Статус:
Курс обязательный (Прикладной анализ данных)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
2-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Преподаватели:
Данилов Борис Радиславович,
Трофимова Анастасия Алексеевна
Язык:
английский
Кредиты:
5
Контактные часы:
60
Course Syllabus
Abstract
The course is a natural follow up of the course Discrete Mathematics. This course covers topics that are not covered in traditional courses of calculus, algebra and linear algebra, but are part of the basic mathematic culture. The course provides theoretical foundations for courses of a more applied nature: programming, algorithms and data structures, data analysis, discrete optimization.
Learning Objectives
- After finishing this course students will be prepared to read more specialized literature on graphs and Boolean functions.
- Students will learn and analyze several important algorithms on graphs and Boolean functions.
- Students will be able to recognize hard computational problems and justify the use of heuristic and brute force algorithms for such problems.
Expected Learning Outcomes
- Will master the Quine-McCluskey method of DNF minimization.
- Will know basic algorithms of searching shortest spanning trees.
- Will know the Ford-Fulkerson’s algorithm of finding the maximum flow.
- Will be able to establish equivalence of Boolean formulas.
- Will be able to establish completeness of sets of Boolean functions.
- Will be able to prove for some problems that they are computationally hard in some sense (NP-complete, NP-hard, etc.)
Course Contents
- Graph theory
- Boolean algebra
- The problem of DNF minimization and associated algorithmic obstacles
- The theory of complexity and P versus NP problem
Assessment Elements
- Homework assignmentsHomework problems are assigned on a weekly basis on practical lesson (seminar) starting with the first seminar, but excluding the last seminar of the course. Each homework assignment usually contains from 5 to 12 exercises of varying complexity, often consisting of two parts: the compulsory part with “ordinary” exercises and a bonus part with “starred” exercises (the bonus part may stay out). Each student is expected to solve problems individually. Solutions must be performed in hand-written form on a piece of paper and contain the full name of the student, his group number, and the list of solved problems written in clear and recognizable manner. Each problem in homework must contain 1) it's respective number in the assignment; 1) the solution; and 3) the answer explicitly given after the written word «answer». When several answers are given for a task the inspector may choose any of the specified answers to score the task. When problem is not supposed to have an answer (exercises to prove facts) then the complete proof should be provided. Each step in the solution of a task must be supported by a mathematical argument, unfounded statements may lead to lowering the score up to zero points for the task. Only statements and theorems provided on lectures or seminars can be used without a proof. The correct answer for the task without provided solution is scored with zero points. These rules also apply for the quizzes and written tests (midterm written test and final written test).
- Quizzes (control works)Quizzes are small control works that contain 1 or 2 exercises for 10-15 minutes that are held on practical lessons (seminars). The form of a quiz is a written test. Students can’t use any materials during the quiz. Rules for submitted solutions follow the rules described for the homework assignments, except that solutions for quiz exercises can be given in short form and the exercise itself can be sometimes assessed based on the answer only.
- Midterm testThe planned form of the midterm written test is the offline written test at the start of the second module. In the case of aggravating of epidemiologic state the midterm written test may be carried out online, in which case the rules and the form of the test are announced separately and may or may not match the rules announced for the offline form of the test. No resort to any materials is allowed during the test. Rules for submitted solutions also follow the rules described for the homework assignments.
- Final test (exam)The planned form of the final written test is the offline written exam which is conducted in session period. In the case of aggravating of epidemiologic state the final written test may be carried out online, in which case the rules and the form of the test are announced separately and may or may not match the rules announced for the offline form of the test. No resort to any materials is allowed during the test. Rules for submitted solutions also follow the rules described for the homework assignments
Interim Assessment
- 2022/2023 2nd moduleGrades <HA>, <QZ>, <MT>, <FT> for interim assessment activities are rational numbers between 0 and 20. The grade of the course is rounded exactly once after calculating the value by the formula given below. The value rounds to the nearest integer, tie-values are rounded up (for instance, 3.5 rounds to 4). The grade <CG> for the course is determined by the formula: <CG> = min(10, round( 0.25 * <HA> + 0.15 * <QZ> + 0.3 * <MT> + 0.3 * <FT>))
Bibliography
Recommended Core Bibliography
- Bernhard Korte, Jens Vygen. Combinatorial Optimization. Theory and Algorithms. Fifth edition. Springer-Verlag, Berlin Heidelberg, 2012.
- Graph theory, Bondy, J. A., 2008
- J. A. Bondy, & U. S. R. Murty. (1976). Graph theory with applications. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.CB6871BA
Recommended Additional Bibliography
- Лекции по теории графов : учеб. пособие, Емеличев, В. А., 2009