• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2021/2022

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

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Статус: Курс обязательный (Прикладная математика и информатика)
Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 1-й курс, 1-3 модуль
Формат изучения: без онлайн-курса
Охват аудитории: для всех кампусов НИУ ВШЭ
Язык: русский
Кредиты: 7

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

Аннотация

Дискретная математика-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) форма для сканов/фото решений объёмных задач (одна). То есть в итоге студенты должны будут отправить не один файл с решениями, а форму.
Промежуточная аттестация

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

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

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

Рекомендуемая основная литература

  • Lovász, L., Pelikán, J., & Vsztergombi, K. (2003). Discrete Mathematics : Elementary and Beyond. New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=108108
  • Верещагин Н.К., Шень А. - Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Московский центр непрерывного математического образования - 2008 - ISBN: 978-5-94057-321-0 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9306
  • Верещагин Н.К., Шень А. - Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления - Московский центр непрерывного математического образования - 2008 - ISBN: 978-5-94057-322-7 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9307

Рекомендуемая дополнительная литература

  • Дискретная математика. Углубленный курс: Учебник / Соболева Т.С.; Под ред. Чечкина А.В. - М.:КУРС, НИЦ ИНФРА-М, 2017. - 278 с.: - (Бакалавриат) - Режим доступа: http://znanium.com/catalog/product/851215