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

Бакалавриат 2024/2025

Статус: Курс обязательный (Программная инженерия)

Направление: 09.03.04. Программная инженерия

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

Когда читается: 1-й курс, 1-4 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для всех кампусов НИУ ВШЭ

Преподаватели: Дашков Евгений Владимирович, Зайцев Александр Владимирович, Киктева Вероника Владимировна, Медведь Никита Юрьевич, Никитина Алина Владимировна, Соколов Павел Павлович, Хрыстик Михаил Андреевич

Язык: русский

Кредиты: 9

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

Авторы

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

Программа дисциплины