• 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
    В измененных в 2021 г. правилах оценивания не используется. Остается из-за невозможности удалить элемент контроля из списка.
  • неблокирующий Коллоквиум 1
  • неблокирующий Коллоквиум 2
  • неблокирующий Промежуточный экзамен
    В письменной форме после второго модуля. Предполагается очная форма сдачи экзамена. При невозможности проведения очного экзамена проводится дистанционный экзамен по правилам, которые дополнительно сообщаются студентам.
  • неблокирующий Итоговый экзамен
    В письменной форме после третьего модуля. Предполагается очная форма сдачи экзамена. При невозможности проведения очного экзамена проводится дистанционный экзамен по правилам, которые дополнительно сообщаются студентам.
Промежуточная аттестация

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

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

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

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

  • 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