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

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

Язык: русский
Кредиты: 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)
Список литературы

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

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

  • Дискретная математика. Формально - логические системы и языки, Авдошин, С. М., 2018

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

  • Дискретная математика для инженера, Кузнецов, О. П., 2004
  • Математическая логика : учеб. пособие для вузов, Колмогоров, А. Н., 2005
  • Математические основы информатики: элективный курс : учеб. пособие, Андреева, Е. В., 2007