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

Дискретная математика (углубленный курс)

Статус: Курс по выбору (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

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

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

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

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

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

Преподаватели: Лукьяненко Никита Сергеевич, Максаев Артем Максимович, Промыслов Валентин Валерьевич, Сысоева Любовь Николаевна

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

Кредиты: 6

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

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

Аннотация

Дискретная математика-1 — базовый вводный курс, прививающий студентам азы математической культуры, нужные для последующего изучения как математических дисциплин, так и компьютерных наук. Курс знакомит с такими фудндаментальными понятиями как множества, алгебра логики, функции и отображения, булевы функции, отношения и графы. Они являются фундаментом как для изучения математики и для структур данных в программировании. Разделы введение в теорию чисел и мощность множеств готовит студентов к изучению алгебры и последующему изучению вычислимых функций в рамках курса дискретная математика-2.

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

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

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

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

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

• Домашнее задание 1
  В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и итоговой оценок. При выставлении итоговой и промежуточных оценок используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3, 5,48 – до 5, 5,54 – до 6, 7,12 – до 8.
• Домашнее задание 2
  В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и итоговой оценок. При выставлении итоговой и промежуточных оценок используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3, 5,48 – до 5, 5,54 – до 6, 7,12 – до 8.
• Домашнее задание 3
  В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и итоговой оценок. При выставлении итоговой и промежуточных оценок используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3, 5,48 – до 5, 5,54 – до 6, 7,12 – до 8.
• Коллоквиум 1
• Коллоквиум 2
• Промежуточный экзамен
  В письменной форме после второго модуля.
• Итоговый экзамен
  Для пилотного потока: Письменный экзамен. Студенты пишут на бумаге. В конце экзамена отправляют скан/фото работы. В течение экзамена за ними ведется наблюдение через zoom. Можно пользоваться распечатанными или заранее скачанными материалами. Во время экзамена преподаватель может попросить студента включить звук или поделиться экраном. Допускается два разрыва связи по пять минут. Если лимит превышен, вторая попытка через неделю, формат будет изменен на устный. Для основного потока: Экзамен проводится в форме теста на компьютере с применением проткоринга. Студенты получают задания в Moodle. Вариант с формами трёх типов: 1) вопросы с множественным выбором вариантов ответа (checkbox); 2) формы ввода текста; 3) форма для сканов/фото решений объёмных задач (одна). То есть в итоге студенты должны будут отправить не один файл с решениями, а форму.

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

• 2022/2023 учебный год 2 модуль
  0.4 * Коллоквиум 1 + 0.15 * Домашнее задание 1 + 0.15 * Домашнее задание 2 + 0.3 * Домашнее задание 3
• 2022/2023 учебный год 3 модуль
  0.083 * Домашнее задание 1 + 0.084 * Домашнее задание 3 + 0.3 * Итоговый экзамен + 0.15 * Промежуточный экзамен + 0.15 * Коллоквиум 1 + 0.15 * Коллоквиум 2 + 0.083 * Домашнее задание 2