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

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

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

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

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

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

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

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

Охват аудитории: для своего кампуса

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

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

Кредиты: 9

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

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

Аннотация

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

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

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

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

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

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

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

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

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

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

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

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

Авторы

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

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