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

Бакалавриат 2022/2023

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

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

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

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

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

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

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

Преподаватели: Дашков Евгений Владимирович, Запрягаев Александр Александрович, Лукьяненко Никита Сергеевич, Медведь Никита Юрьевич, Морозенко Владимир Викторович, Правдивец Николай Александрович, Рустамханова Гульшат Ильдаровна, Хрыстик Михаил Андреевич, Хузиева Алина Эдуардовна, Шварц Дмитрий Александрович

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

Кредиты: 10

Контактные часы: 140

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

Аннотация

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

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

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

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

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

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

Дифференциальное исчисление булевых функций.
Критерий Поста.
Конечные автоматы.
Формальные аксиоматические системы.
Неклассические логики.
«Введение в логику» (Introduction to Logic).
Формализация понятия алгоритма.
Нормальный алгоритм Маркова.
Рекурсивные функции.
Меры сложности алгоритмов.
Основы теории информации.
Системы счисления.
Форматы представления информации в компьютере.
Вычислительная погрешность.
Функции и отношения.
Основы теории графов.
Фундаментальные системы циклов и разрезов (коциклов).
Алгоритмы на графах.
Двудольные графы.
Планарные графы.
Раскраска графов.
Потоки в сетях.
«Математика для компьютерных наук» (Mathematics for Computer Science, 6.042J / 18.062J).
Универсальные алгебры.
Матроиды.

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

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

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

2022/2023 учебный год 2 модуль
НК1' = 10 * min (1, 0.35 * КР1 + 0.35 * КР2 + 0.3 * ДЗ1)
2022/2023 учебный год 4 модуль
НК2' = 10 * min (1, 0.35 * КР3 + 0.35 * КР4 + 0.3 * ДЗ2)

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

Авторы

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

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