Delivered at:: Big Data and Information Retrieval School

Course type:: Compulsory course

When:: 1 year, 1-4 module

Instructors

Dashkov, Evgeny V.

Zaitsev, Alexander

Zapryagaev, Alexander

Игнатьев Николай Эдуардович

Kikteva, Veronika

Medved, Nikita

Nikitina, Alina V.

Хрыстик Михаил Андреевич

Дополнительные материалы в LMS Задать вопрос

Аннотация

Курс знакомит слушателя с основами разделов математики, необходимых для разработки и анализа алгоритмов, но остающихся за рамками традиционных вводных математических курсов. Среди рассматриваемых тем: арифметика остатков, формализм множеств и отношений, частичные порядки, графы, булевы функции и схемы, элементы комбинаторики, формальной логики, теории алгоритмов, функционального программирования. Поскольку курс адресован вчерашним школьникам, особое внимание уделяется строгости математических рассуждений: знакомству с логико-математическим языком, простейшим приемам доказательств, понятиям индукции и рекурсии и пр.

Цель освоения дисциплины

Формирование понимания студентами ключевых положений информатики, математической логики и теории алгоритмов, необходимых для практического использования на последующих этапах обучения и в профессиональной сфере деятельности будущего специалиста.
Изучение логических основ информатики и основных концепций, которые позволяют студентам получить базовое представление об эффективных способах разработки программного обеспечения.
Формировании у студентов компетенций, связанных с базовыми понятиями, которые составляют основу программирования, и позволяют сделать процесс проектирования программ и программирования более легким и эффективным.
Формирование у студентов навыков логического и алгоритмического мышления при реализации решения поставленной задачи в виде программы.

Планируемые результаты обучения

Овладение навыками представления несложных понятий на языке логики предикатов.
Развитие навыков решения элементарных задач арифметики целых чисел.
Формирование аксиоматического представления о множествах; развитие навыка доказывания и использования тождеств алгебры множеств и алгебры бинарных отношений.
Развитие навыка решения задач о сравнении множеств по мощности.
Развитие навыка решения стандартных комбинаторных задач на основе теоретико-множественного формализма.
Формирование понятия об отношениях порядка и эквивалентности; навык решения задач о них в абстрактной постановке; знакомство с началами экстремальной комбинаторики.
Развитие навыков формализации и решения различных задач на языка теории графов; знакомство с основами экстремальной комбинаторики.
Знакомство с дискретными вариантами основных понятий анализа; развитие навыков решения линейных рекуррентных соотношений, простых разностных уравнений и вычисления частичных сумм последовательностей.
Развитие навыка решения комбинаторных задач с помощью производящих функций.
Формирование понимания рекурсии и индукции как базовых идей дискретной математики и информатики; развитие навыков индуктивных доказательств в различных ситуациях.

Содержание учебной дисциплины

Язык математики
Индукция и рекурсия
Основы арифметики
Основы теории множеств
Мощность множеств
Начала комбинаторики
Порядки и эквивалентости
Основы теории графов
Конечные разности и рекурренты
Производящие функции

Элементы контроля

Э 2
Письменная экзаменационная работа проводится в сессию после модуля 2.
КР 3
Письменная контрольная работа проводится в конце модуля 3.
Э 4
Письменная экзаменационная работа проводится в сессию после модуля 4.
КР 2
Письменная контрольная работа проводится в конце модуля 2.
ДЗ 2
Домашнее задание в модулях 1 и 2 выдается частями, каждую из которых следует сдавать в установленные сроки. Преподаватель вправе потребовать от любого студента "защитить" (т.е. изложить устно, отвечая на возникающие при этом вопросы) решение любой из зачтенных этому студенту задач ДЗ. В случае неуспешной защиты, баллы за соответствующую часть ДЗ могут быть снижены, в т.ч. до нуля. Некоторые задачи отмечены как задачи "повышенной сложности"; остальные считаются "обыкновенными".
ДЗ 4
Домашнее задание в модулях 3 и 4 выдается частями, каждую из которых следует сдавать в установленные сроки. Преподаватель вправе потребовать от любого студента "защитить" (т.е. изложить устно, отвечая на возникающие при этом вопросы) решение любой из зачтенных этому студенту задач ДЗ. В случае неуспешной защиты, баллы за соответствующую часть ДЗ могут быть снижены, в т.ч. до нуля. Некоторые задачи отмечены как задачи "повышенной сложности"; остальные считаются "обыкновенными".
КР 4
Письменная контрольная работа проводится в конце модуля 4.
КР 1
Письменная контрольная работа проводится в конце модуля 1.

Промежуточная аттестация

2025/2026 2nd module
0.09 * ДЗ 2 + 0.7 * Э 2 + 0.105 * КР 2 + 0.105 * КР 1
2025/2026 4th module
0.09 * ДЗ 4 + 0.7 * Э 4 + 0.105 * КР 4 + 0.105 * КР 3

Список литературы

Авторы

Оруджева Альбина Александровна
Волкова Вера Константиновна
Дашков Евгений Владимирович
Сысоева Алевтина Александровна

Bachelor’s Programme 'Software Engineering'

Contacts

Accredited by the Engineering Commission of ABET

Discrete Mathematics