Бакалавриат
2021/2022
Дискретная математика
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Статус:
Курс обязательный
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 1-3 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Преподаватели:
Данилов Борис Радиславович,
Дашков Евгений Владимирович,
Трофимова Анастасия Алексеевна
Язык:
английский
Кредиты:
7
Контактные часы:
104
Course Syllabus
Abstract
The course encompasses many topics important for both computer scientists and practitioners from their earliest stages, which are not covered by more traditional basic courses like Calculus. These come from different branches of mathematics such as logic, combinatorics, probability theory etc. Pre-requisites: High school elementary algebra.
Learning Objectives
- To prepare students for studying the subsequent courses which use the set-theoretic, combinatorial, graph or probability formalism.
- To teach students how to identify a typical problem of Discrete Mathematics in a problem given, either applied or theoretical.
Expected Learning Outcomes
- Students will develop skills in formalizing and solving applied problems using the methods of Discrete Mathematics.
- Students will gain an understanding of propositional and predicate logic.
- Students will gain an understanding of several major theorems in discrete mathematics (Euler's theorem, Fermat's little theorem, Chinese remainder theorem).
- Students will gain an understanding of the set theory.
- Students will master basic concepts and methods of Discrete Mathematics as far as these are necessary for studying more advanced courses and for the future professional life.
Course Contents
- Propositional and predicate logic (an informal treatment). Structural induction and recursion for strings (an informal case study).
- Main set-theoretic constructions. Algebra of sets. Cartesian product.
- Induction principle. Fundamental theorem of arithmetic. Euclidean algorithm. Continued fractions. Modular arithmetic. Linear congruences and Diophantine equations. Chinese remainder theorem. Fermat's little theorem, Euler’s theorem.
- Algebra of binary relations. Image of set. Special binary relations. Functions, bijections. Set equivalence. Indicator functions. Cantor’s theorem. Cantor–Schröder–Bernstein theorem. Cardinalities of sets \N^2, \Z, \Q, \R^2, \N^\N, \R^\N.
- Pigeonhole principle. Finite and countable sets. Countable union of countable sets. Rules of sum and product. Number of functions, injections, bijections. Number of subsets, binomial coefficients and their properties. Binomial and multinomial theorems. Multisets. Inclusion–exclusion principle with applications (surjections, derangements, Euler’s totient function).
- Special binary relations. Orderings. Order isomorphism. Lattices; chains and antichains. Equivalences and partitions. Counting chains and partitions for finite sets (Dilworth's theorem etc.).
- Finite differences and sums. Linear recurrences.
- Generating functions and their combinatorial applications.
- Classical probability model. Conditional probability, Bayes’ theorem. Random variable. Expectation and variance. Some inequalities. Combinatorial applications.
- Boolean functions and circuits. Clones. Functional completeness. Counting functions of various classes.
Assessment Elements
- Final examA final written exam with open questions.The exam may be carried out online via distance learning platforms. Экзамен письменный. Экзамен проходит с прокторингом через Zoom в системе Moodle. Студенты получают задание, решают на бумаге, в конце загружают фотографии/сканы решений. Экзамен длится 2 астрономических часа. Во время экзамена разрешается пользоваться конспектами курса и любой литературой, но не советоваться с кем-либо. Если у студента случился обрыв связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена.
- Homework
- ColloquiumThe grade for the colloquium will be included into the cumulative grade.
- Cumulative Grade
- Test
- Bonus points
Interim Assessment
- 2021/2022 3rd moduleIntermediate grade-2 = (1/3) test-1 + (1/3) colloquium-2 + (1/3) homework-2. Cumulative grade-3 = (3/10) test-1 + (3/10) colloquium-2 + (4/10) homework-3. Final grade = min(10, (7/10) cumulative grade + (3/10) final exam + (1/10) bonus points).
Bibliography
Recommended Core Bibliography
- Discrete mathematics, Biggs, N. L., 2004
Recommended Additional 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