Бакалавриат
2025/2026
Дискретная математика
Статус:
Курс обязательный (Прикладной анализ данных)
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 1-3 модуль
Охват аудитории:
для своего кампуса
Язык:
английский
Контактные часы:
102
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.
- The student is able to formalize simple mathematical and real-world ideas with logical connectives and quantifiers and to comprehend such formalizations.
- The student is able to solve simple problems in integer arithmetic applying classical results and concepts.
- The student is able to produce rigorous axiom-based proofs for easy set existence problems; the student is able to prove set algebra equivalence.
- The student is able to reason about equations in binary relation algebra.
- The student is able to compare sets by cardinality (in easy situations).
- The student is able to solve standard combinatorial problems and to produce double counting proofs.
- The student is able to apply order and equivalence formalism to various problems and to solve such problems in abstract setting.
- The student is able to apply generating functions to combinatorial problems.
Course Contents
- The language of mathematics
- The basics of arithmetic
- Set theory elements
- Binary relations
- Set cardinality
- Basics of combinatorics
- Orders and equivalences
- Generating functions
Assessment Elements
- HW_AThe homework includes 2 problem sets in Module 1. The deadlines are announced on giving each set. Every problem set consists of about 10 - 15 problems. These sets may be subdivided further for students’ convenience.
- Exam1A written examination is held past Module 1. Students may not consult any sources during the exam. The examination takes about 120 minutes. An integer weight is assigned to every problem.
- HW_BThe homework includes 7 problem sets in Modules 2 and 3. The deadlines are announced on giving each set. Every problem set consists of about 10 – 15 problems. These sets may be subdivided further for students’ convenience.
- ColloqAn oral colloquium is held at the beginning of Module 3. Each student is given two questions concerning statements and definitions as well as one question requiring a proof. After no less than 45 minutes of preparation (when using any literature is allowed), the student is required to answer ‘from scratch’, that is, with no recourse to any materials. The examiner may pose additional questions as he sees fit.
- Exam2A written examination is held past Module 3. Students may not consult any sources during the exam. The examination takes about 120 minutes. An integer weight is assigned to every problem.
- BonusA variety of ‘bonus activities’ (like quizzes, etc.).
- HW_Test_BIn Modules 2 and 3, just about 25% of the homework problems are chosen to be graded. The remaining homework problems comprise the base for two written tests (one per module) aimed at assessing students' ability to solve problems they know well in advance but in a controlled, AI-free environment. Each test takes about 80 minutes and contains 6 -- 8 problems from the homework problem sets or very similar to those.
Interim Assessment
- 2025/2026 1st module0.5 * Exam1 + 0.5 * HW_A
- 2025/2026 3rd module0.06 * Bonus + 0.295 * Colloq + 0.35 * Exam2 + 0.085 * HW_B + 0.21 * HW_Test_B
Bibliography
Recommended Core Bibliography
- Discrete mathematics, Biggs, N. L., 2004
- Extremal combinatorics : with applications in computer science, Jukna, S., 2011
- Generatingfunctionology, Wilf, H. S., 1990
- Introduction to enumerative combinatorics, Bona, M., 2007
- Ordered sets, Harzheim, E., 2005
- Sets, functions and logic : basic concepts of university mathematics, Devlin, K. J., 1981
- Алгебра и теория чисел : сборник задач для математических школ, Алфутова, Н. Б., 2002
- Задачи по теории множеств, математической логике и теории алгоритмов, Лавров, И. А., 2004
- Комбинаторика, Виленкин, Н. Я., 2006
- Лекции о производящих функциях, Ландо, С. К., 2007
- Математическая индукция, Шень, А., 2007
- Математическая логика, Клини, С. К., 1973
- Основы теории чисел : учебник для вузов, Виноградов, И. М., 1972
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