• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2024/2025

Дискретная математика 2

Статус: Курс обязательный (Прикладной анализ данных)
Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 2-й курс, 1, 2 модуль
Формат изучения: без онлайн-курса
Охват аудитории: для своего кампуса
Язык: английский
Кредиты: 4

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

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

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

Course Contents

  • Graph theory
  • Boolean algebra
  • DNF minimization and associated algorithmic obstacles
  • Complexity and hard algorithmic problems, the problem P = NP
Assessment Elements

Assessment Elements

  • non-blocking Midterm control work <MT>
  • non-blocking Examination control work <FT>
  • non-blocking Homework assignments <HA>
  • non-blocking Quizes <QZ>
Interim Assessment

Interim Assessment

  • 2024/2025 2nd module
    = min(10, round( 0.23 * + 0.15 * + 0.23 * + 0.39 * ))
Bibliography

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

Authors

  • Абдулхакимов Мухиддин Мураджанович
  • DANILOV BORIS RADISLAVOVICH