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

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

Статус: Курс обязательный (Программная инженерия)
Направление: 09.03.04. Программная инженерия
Когда читается: 1-й курс, 1-4 модуль
Формат изучения: Blended
Язык: русский
Кредиты: 8

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

Аннотация

Тематически дисциплина состоит их 6 частей. Первая часть посвящена математической логике и изучается в первом модуле. Здесь будут рассмотрены основные сведения из формально-логических систем. Вторая часть посвящена формализации понятия алгоритма и изучается во втором модуле. Здесь будут рассмотрены такие алгоритмические системы, как машины Тьюринга и Поста, нормальный алгоритм Маркова, частично-рекурсивные функции, а также меры сложности алгоритмов. Третья часть – самостоятельное прохождение семестрового (параллельно с тематикой первого и второго модулей) массового открытого онлайн-курса (Coursera) «Введение в логику» (Introduction to Logic). Успешное прохождение курса «Введение в логику» демонстрирует владение англоязычной терминологией в рамках дисциплины и способность к самостоятельному изучению материала на английском языке. Четвертая часть изучается в третьем модуле и посвящена в основном алгоритмическим задачам теории графов. Пятая часть посвящена основам комбинаторики, модулярной алгебре, криптографии и кодированию и изучается в четвертом модуле. Шестая часть – самостоятельное прохождение семестрового (параллельно с тематикой третьего и четвертого модулей) открытого курса (MIT OpenCourseware) «Математика для компьютерных наук» (Mathematics for Computer Science, 6.042J / 18.062J). Успешное прохождение курса «Математика для компьютерных наук» демонстрирует владение англоязычной терминологией в рамках дисциплины и способность к самостоятельному изучению материала на английском языке.
Цель освоения дисциплины

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

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

Результаты освоения дисциплины

  • Выполнение компьютерного теста за первый модуль
  • Выполнение англоязычного компьютерного теста за первый семестр
  • Выполнение компьютерного теста за второй модуль
  • Выполнение компьютерного теста за третий модуль
  • Выполнение англоязычного компьютерного теста за второй семестр
  • Выполнение компьютерного теста за четвертый модуль
Содержание учебной дисциплины

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

  • Основные понятия математической логики.
    Высказывание. Логические связки. Силлогизм. Законы Аристотеля. Закон Лейбница. Логика высказываний. Пропозициональные переменные. Формулы логики высказываний. Равносильность формул. Тавтология. Противоречие. Выполнимость. Опровержимость. Алгебра высказываний. Булева функция. Существенные и несущественные переменные. Таблицы истинности. Множество. Предикат. Свойство. Кванторы. Законы де Моргана. Законы булевой алгебры. Абстрактные алгебры с одной и двумя операциями. Изоморфизмы алгебр. Классический принцип двойственности. Булева алгебра. Алгебра Кантора. Законы поглощения. Законы Порецкого. Законы склеивания. Компьютерное представление конечных множеств. Дизъюнктивное и конъюнктивное разложение Шеннона. Синтез логических формул. Предельные разложения Шеннона. Канонические формы. Совершенная дизъюнктивная нормальная форма СДНФ. Совершенная конъюнктивная нормальная форма СКНФ.
  • Дифференциальное исчисление булевых функций.
    Ортогональность. Разложения Рида. Полиномы Жегалкина. Логические уравнения. Теоретико-множественные уравнения. Побитовые уравнения. Система линейных алгебраических уравнений в поле Галуа GF(2). Производная. Дифференцирование булевых функций. Разложение булевой функции в ряд Тейлора и Маклорена. Алгебра переключательных схем. Комбинационные схемы и схемы с памятью. Методы решения логических задач.
  • Критерий Поста.
    Замкнутые классы логических функций. Полные системы булевых функций в сильном и слабом смысле. Базисы. Теорема Поста. Минимизация булевых функций в классе дизъюнктивных и конъюнктивных нормальных форм. Коды Грея. Карты Карно. Частично-определенные функции и их минимизация. Минимизация булевых функций в заданных базисах.
  • Конечные автоматы.
    Автоматы Мили и Мура. Представление данных. Алфавит. Операция конкатенации. Транзитивное и рефлексивное замыкание Клини. Регулярные выражение и регулярные языки. Префиксные, суффиксные и инфиксные коды. Грамматики. Минимизация автоматов. Компьютер, как программно управляемый цифровой автомат.
  • Формальные аксиоматические системы.
    Аксиоматическая теория высказываний. Язык и метаязык в логике высказываний. Аксиоматические системы. Системы аксиом. Правило вывода. Полнота, непротиворечивость и разрешимость формализованного исчисления высказываний. Независимость системы аксиом. Логическое следование. Принцип дедукции. Формальный вывод. Метод резолюций. Метод Вонга. Натуральное исчисление. Язык и метаязык, теоремы и метатеоремы формальной теории. Интерпретация и модели формальной теории. Синтаксис и семантика языка логики предикатов. Непротиворечивость формализованного исчисления предикатов. Теорема Геделя о неполноте. Клаузуальная форма. Клаузальная логика. Семантика клаузальной формы. Инфиксная нотация. Семантические сети. Клаузы Хорна и их интерпретация. Метол резолюций в логике предикатов. Принцип логического программирования.
  • Неклассические логики.
    Интуиционистская логика. Конечнозначные логики. Нечеткая логика. Модальная логика. Типы модальностей. Модальные исчисления. Семантика Крипке. Временные (темпоральные) логики. Алгоритмические логики.
  • «Введение в логику» (Introduction to Logic).
    Самостоятельное прохождение семестрового массового открытого онлайн-курса (Coursera).
  • Формализация понятия алгоритма.
    Понятие алгоритма и вычислимой функции. Качественная и количественная теория алгоритмов. Понятие алгоритмической системы. Машина Тьюринга. Машина Поста. Тезис Тьюринга. Основная гипотеза теории алгоритмов в форме Тьюринга. Универсальная машина Тьюринга. Универсальная машина Поста.
  • Нормальный алгоритм Маркова.
    Основная гипотеза теории алгоритмов в форме Маркова. Эквивалентность определений алгоритма в виде машины Тьюринга и нормального алгоритма Маркова. Универсальный алгоритм Маркова.
  • Рекурсивные функции.
    Базовые функции. Операторы суперпозиции, примитивной рекурсии и минимизации. Примитивно рекурсивные функции. Частично-рекурсивные функции. Тезис Черча. Универсальная частично-рекурсивная функция. Эквивалентность формальных определений алгоритма. Алгоритмически неразрешимые задачи. Не-вычислимые функции.
  • Меры сложности алгоритмов.
    Понятие сложности алгоритмов и вычислений, эффективные алгоритмы. Легко и трудно разрешимые задачи. Полиномиальная эквивалентность. Недетерминированные алгоритмы. Недетерминированная машина Тьюринга. Классы задач P и NP. NP – полные и NP – трудные задачи. Квантовый компьютер и квантовые вычисления.
  • Основы теории информации.
    Кодирование информации. Блоковые коды. Префиксные коды. Кома-код. Код Грея. Расстояние Хемминга. Коды, обнаруживающие ошибки. Коды, исправляющие ошибки. Код Хаффмана. Информационный объем сообщения. Формула Хартли. Информация, вероятность, энтропия. Формула Шеннона.
  • Системы счисления.
    Позиционные системы с натуральным основанием. Представление. Арифметические операции. Алгоритмы перевода чисел из одной системы счисления в другую. Смешанные системы счисления. Нетрадиционные системы счисления: симметричные и ассиметричные, уравновешенная троичная, с отрицательным основанием, негодвоичная, фибоначчиевая, факториальная, остаточных классов.
  • Форматы представления информации в компьютере.
    Стандарт IEEE 754-2019. Представление целых положительных, отрицательных и беззнаковых чисел. Прямой и дополнительный код. Представление вещественных чисел. Форматы для представления вещественных чисел со скрытой единицей. Представление текстовой информации. Представление графической информации. Представление звуковой информации. Методы сжатия информации.
  • Вычислительная погрешность.
    Приближенное представление вещественных чисел. Абсолютная и относительная погрешность. Погрешность выполнения арифметических операций. Аксиоматическое построение множества действительных чисел. Ошибки перевода вещественных чисел из десятичной системы в двоичную систему счисления. Ошибки представления. Ошибки округления. Ошибки сдвига и компенсации при выполнении арифметических операций.
  • «Введение в логику» (Introduction to Logic).
    Самостоятельное прохождение семестрового массового открытого онлайн-курса (Coursera).
  • Функции и отношения.
    Бинарные отношения и их свойства. Соответствия и функции. Изоморфизм и гомоморфизм отношений. Композиция отношений. Степень отношения. Ядро отношения. Отношение эквивалентности. Классы эквивалентности. Фактор множество. Отношения порядка. Замыкание отношений.
  • Основы теории графов.
    Графы, мультиграфы, псевдографы, орграфы. Изоморфизм графов. Способы задания графов. Операции над графами. Маршруты, цепи, циклы. Ациклический граф. Топологическая сортировка. Расстояния между вершинами. Диаметр, радиус, центр графа. Сильная и слабая связность. Компоненты связности. Точки сочленения. Вершинная и реберная связность. Мосты и блоки. Меры связности. Обходы графов. Циклы Эйлера, де Брейна, Гамильтона. Функциональные и контрфункциональные графы. Дерево и лес. Характеристические свойства деревьев. Каркасы (остовы) и хорды в связном графе. Ориентированные, упорядоченные, бинарные деревья. Алгоритмы обхода деревьев.
  • Фундаментальные системы циклов и разрезов (коциклов).
    Циклы в графах. Линейное пространство бинарных наборов. Линейное пространство подграфов данного графа. Подпространство четных подграфов. Циклический и коциклический ранг графа (цикломатическое и коцикломатическое число). Матричная теорема Киркгофа о деревьях. Алгоритм построения фундаментальной системы циклов в графе.
  • Алгоритмы на графах.
    Алгоритмы поиска в глубину и ширину. Взвешенные графы. Алгоритмы Крускала и Прима построения минимального остовного дерева. Алгоритмические задачи траекторного типа во взвешенном графе. Обобщенный алгоритм Дейкстры. Обобщенное уравнение Беллмана-Маслова. Обобщенный алгоритм Флойда-Уоршала.
  • Двудольные графы.
    Паросочетания. Алгоритм построения совершенного паросочетания для двудольного графа. Системы различных представителей для конечного семейства конечных множеств (трансверсаль). Теорема Холла о совершенных паросочетаниях.
  • Планарные графы.
    Укладка графа. Плоские графы. Эйлерова характеристика (формула Эйлера). Графы К5 и К3,3. Критерий планарности Понтрягина-Куратовского.
  • Раскраска графов.
    Хроматическое число и хроматический класс. Верхняя и нижняя оценка хроматического числа. Внутренне и внешне устойчивые множества вершин графа. Оптимальная раскраска вершин графа. Раскрашивание планарных графов. Теоремы о пяти и о четырех красках.
  • Потоки в сетях.
    Двухполюсные сети. Дивергенция. Разрезы (сечения). Величина потока и пропускная способность сети. Максимальный поток. Теорема Форда-Фалкерсона о максимальном потоке. Алгоритм построения максимального потока в сети. Многополюсная сеть. Обобщенная задача о назначениях и обобщенная транспортная задача. Алгоритмы решения обобщенной задачи о назначениях и обобщенной транспортной задачи.
  • «Математика для компьютерных наук» (Mathematics for Computer Science, 6.042J / 18.062J).
    Самостоятельное прохождение семестрового открытого курса (MIT OpenCourseware).
  • Универсальные алгебры.
    Операция суперпозиции. Замыкания и подалгебры. Система образующих. Морфизмы, гомоморфизм и изоморфизм алгебр. N-арные отношения. Конгруенции и фактор-алгебры. Группы, кольца, области целостности и поля. Век-торные пространства. Решетки. Конечные группы, кольца и поля.
  • Матроиды.
    Базы и ранг матроида. Аксиоматические определения матроидов. Теорема о базах. Графовый матроид. Матроид Фано. Матроид паросочетаний. Матричный матроид. Жадный алгоритм. Теорема Радо-Эдмондса.
  • Сети Петри.
    Операционная семантика сетей Петри. Поведенческие свойства сетей Петри. Проблема достижимости и покрытие. Граф достижимости и деревья Карпа-Миллера. Живость и ограниченность. Инварианты позиций и переходов сетей Петри.
  • Модулярная арифметика.
    Делимость. Простые числа. Решето Эратосфена для нахождения простых чисел и неприводимых полиномов. Факторизация целых чисел. Метод выделения множителей Ферма. Наибольший общий делитель. Расширенный алгоритм Евклида. Наименьшее общее кратное. Функция Мебиуса и Эйлера. Теоремы Эйлера и Ферма.
  • Цепные и подходящие дроби.
    Алгоритм вычисления подходящих дробей. Решение линейных диофантовых уравнений. Полная и приведенная система вычетов. Решение сравнений. Китайская теорема об остатках.
  • Элементы теории кодирования.
    Алфавитное кодирование. Префиксный код. Кодирование с минимальной избыточностью. Алгоритмы Фано и Хаффмена. Хеммингово расстояние, Хемминговы сферы и корректирующая способность. Коды, обнаруживающие и исправляющие ошибки. Линейные блоковые коды. Порождающая и проверочная матрицы. Кодирование и декодирование линейных блоковых кодов. Коды Хэмминга. Двоичные циклические коды. Порождающий и проверочный полиномы.
  • Применение модулярной арифметики в криптографии.
    Симметричные и несимметричные криптосистемы. Криптографические протоколы. Криптография с открытым ключом. Шифросистемы и электронная цифровая подпись. Хэш-функция. Проблема квадратичного вычета. Проблема дискретного логарифма. Проблема подмножества суммы. Проблема факторизации целых чисел. Проблема RSA. Факторизация полиномов над конечным полем. Криптосистема RSA. Криптосистема ЭльГамаля. Применение эллиптических кривых над конечными полями в криптографии. Обмен ключами по схеме Диффи-Хеллмана с использованием эллиптических кривых. Шифрование/дешифрование с использованием эллиптических кривых
  • Элементы комбинаторики.
    Порождение комбинаторных конфигураций и их пересчет. Размещения, перестановки, сочетания без повторений и с повторениями. Подстановки, группа подстановок. Генерация перестановок. Биномиальные и полиномиальные коэффициенты, треугольник Паскаля, генерация подмножеств. Разбиения. Числа Стирлинга первого и второго рода, число Белла. Принцип включения и исключения. Производящие функции для комбинаторных конфигураций и их чисел. Аппарат формальных степенных рядов.
  • Числовые рекуррентные уравнения.
    Линейные рекуррентные уравнения (ЛРУ). Фундаментальная система решений. Общее решение ЛРУ с помощью фундаментальной системы решений. Стационарные ЛРУ (СЛРУ). Характеристический полином и характеристическое уравнение. Общее решение однородного и неоднородного СЛРУ. Частное решение неоднородного СЛРУ с правой частью – квазиполиномом.
  • «Математика для компьютерных наук» (Mathematics for Computer Science, 6.042J / 18.062J).
    Самостоятельное прохождение семестрового открытого курса (MIT OpenCourseware).
Элементы контроля

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

  • неблокирующий Created with Sketch. Компьютерное тестирование (К1)
    Количество включенных в работу тестовых заданий – 20. Продолжительность компьютерного тестирования составляет 120 минут.
  • неблокирующий Created with Sketch. Компьютерное тестирование (К2)
    Количество включенных в работу тестовых заданий – 20. Продолжительность компьютерного тестирования составляет 120 минут.
  • неблокирующий Created with Sketch. Компьютерное тестирование (М12)
    Количество включенных в работу тестовых заданий – 20. Продолжительность компьютерного тестирования составляет 120 минут.
  • неблокирующий Created with Sketch. Компьютерное тестирование (К3)
    Количество включенных в работу тестовых заданий – 20. Продолжительность компьютерного тестирования составляет 120 минут.
  • неблокирующий Created with Sketch. Компьютерное тестирование (К4)
    Количество включенных в работу тестовых заданий – 20. Продолжительность компьютерного тестирования составляет 120 минут.
  • неблокирующий Created with Sketch. Компьютерное тестирование (М34)
    Количество включенных в работу тестовых заданий – 20. Продолжительность компьютерного тестирования составляет 120 минут.
Промежуточная аттестация

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

  • Промежуточная аттестация (2 модуль)
    Пусть X - число правильно решенных тестовых заданий компьютерного теста. Формулы оценивания результатов компьютерного тестирования по десятибалльной шкале приведены в нотации Microsoft Excel. В формулах оценивания результатов компьютерного тестирования К1, К2, М12, К3, К4, М34 используется стандартное арифметическое округление с точностью до десятых балла. К1 = МАКС(ОКРУГЛ((X*5-40)/6;1);0) К2 = МАКС(ОКРУГЛ((X*5-40)/6;1);0) М12 = МАКС(ОКРУГЛ((X*5-40)/6;1);0) Промежуточная оценка за первый семестр вычисляется по формуле П1 = ОКРУГЛ(0.4*К1+ 0.4*К2 + 0.2*М12;0) с учетом правил округления до целого числа баллов. В случае если промежуточная оценка за первый семестр П1 > 3, то итоговая оценка за первый семестр Э1 = П1. В случае если промежуточная оценка за первый семестр П1 < 4, студенту предлагается выполнить итоговое контрольное задание, состоящее из компьютерного тестирования К12, которое оценивается с точностью до десятых долей балла по десятибалльной шкале. Количество включенных в тест K12 тестовых заданий – 20. Продолжительность тестирования составляет 120 минут. Набор тестовых заданий теста K12 представляет собой подмножество тестовых заданий компьютерных тестов за первый и второй модули. В формуле оценивания результатов компьютерного тестирования К12 используется стандартное арифметическое округление с точностью до десятых балла. К12 = МАКС(ОКРУГЛ((X*5-40)/6;1);0) Итоговая оценка за первый семестр Э1 в этом случае вычисляется по формуле Э1 = ОКРУГЛ(0.7*К12 + 0.3*П1;0) с учетом правил округления до целого числа баллов. К3 = МАКС(ОКРУГЛ((X*5-40)/6;1);0) К4 = МАКС(ОКРУГЛ((X*5-40)/6;1);0) М34 = МАКС(ОКРУГЛ((X*5-40)/6;1);0) Промежуточная оценка за второй семестр вычисляется по формуле П2 = ОКРУГЛ(0.4*К3+ 0.4*К4 + 0.2*М34;0) с учетом правил округления до целого числа баллов. В случае если промежуточная оценка за второй семестр П2 > 3, то итоговая оценка за второй семестр Э2 = П2. В случае если промежуточная оценка за второй семестр П2 < 4, студенту предлагается выполнить итоговое контрольное задание, состоящее из компьютерного тестирования К34, которое оценивается с точностью до десятых долей балла по десятибалльной шкале. Количество включенных в тест K34 тестовых заданий – 20. Продолжительность тестирования составляет 120 минут. Набор тестовых заданий теста K34 представляет собой подмножество тестовых заданий компьютерных тестов за третий и четвертый модули. В формуле оценивания результатов компьютерного тестирования К34 используется стандартное арифметическое округление с точностью до десятых балла. К34 = МАКС(ОКРУГЛ((X*5-40)/6;1);0) Итоговая оценка за второй семестр Э2 в этом случае вычисляется по формуле Э2 = ОКРУГЛ(0.7*К34 + 0.3*П2;0) с учетом правил округления до целого числа баллов. Результирующая оценка Р по дисциплине формируется по десятибалльной шкале как взвешенная сумма итоговых оценок Э1 и Э2 за первый и второй семестры с учетом правил округления до целого числа баллов по следующей формуле Р = ОКРУГЛ(0.5*Э1 + 0.5*Э2;0)
  • Промежуточная аттестация (4 модуль)
    Пусть X - число правильно решенных тестовых заданий компьютерного теста. Формулы оценивания результатов компьютерного тестирования по десятибалльной шкале приведены в нотации Microsoft Excel. В формулах оценивания результатов компьютерного тестирования К1, К2, М12, К3, К4, М34 используется стандартное арифметическое округление с точностью до десятых балла. К1 = МАКС(ОКРУГЛ((X*5-40)/6;1);0) К2 = МАКС(ОКРУГЛ((X*5-40)/6;1);0) М12 = МАКС(ОКРУГЛ((X*5-40)/6;1);0) Промежуточная оценка за первый семестр вычисляется по формуле П1 = ОКРУГЛ(0.4*К1+ 0.4*К2 + 0.2*М12;0) с учетом правил округления до целого числа баллов. В случае если промежуточная оценка за первый семестр П1 > 3, то итоговая оценка за первый семестр Э1 = П1. В случае если промежуточная оценка за первый семестр П1 < 4, студенту предлагается выполнить итоговое контрольное задание, состоящее из компьютерного тестирования К12, которое оценивается с точностью до десятых долей балла по десятибалльной шкале. Количество включенных в тест K12 тестовых заданий – 20. Продолжительность тестирования составляет 120 минут. Набор тестовых заданий теста K12 представляет собой подмножество тестовых заданий компьютерных тестов за первый и второй модули. В формуле оценивания результатов компьютерного тестирования К12 используется стандартное арифметическое округление с точностью до десятых балла. К12 = МАКС(ОКРУГЛ((X*5-40)/6;1);0) Итоговая оценка за первый семестр Э1 в этом случае вычисляется по формуле Э1 = ОКРУГЛ(0.7*К12 + 0.3*П1;0) с учетом правил округления до целого числа баллов. К3 = МАКС(ОКРУГЛ((X*5-40)/6;1);0) К4 = МАКС(ОКРУГЛ((X*5-40)/6;1);0) М34 = МАКС(ОКРУГЛ((X*5-40)/6;1);0) Промежуточная оценка за второй семестр вычисляется по формуле П2 = ОКРУГЛ(0.4*К3+ 0.4*К4 + 0.2*М34;0) с учетом правил округления до целого числа баллов. В случае если промежуточная оценка за второй семестр П2 > 3, то итоговая оценка за второй семестр Э2 = П2. В случае если промежуточная оценка за второй семестр П2 < 4, студенту предлагается выполнить итоговое контрольное задание, состоящее из компьютерного тестирования К34, которое оценивается с точностью до десятых долей балла по десятибалльной шкале. Количество включенных в тест K34 тестовых заданий – 20. Продолжительность тестирования составляет 120 минут. Набор тестовых заданий теста K34 представляет собой подмножество тестовых заданий компьютерных тестов за третий и четвертый модули. В формуле оценивания результатов компьютерного тестирования К34 используется стандартное арифметическое округление с точностью до десятых балла. К34 = МАКС(ОКРУГЛ((X*5-40)/6;1);0) Итоговая оценка за второй семестр Э2 в этом случае вычисляется по формуле Э2 = ОКРУГЛ(0.7*К34 + 0.3*П2;0) с учетом правил округления до целого числа баллов. Результирующая оценка Р по дисциплине формируется по десятибалльной шкале как взвешенная сумма итоговых оценок Э1 и Э2 за первый и второй семестры с учетом правил округления до целого числа баллов по следующей формуле Р = ОКРУГЛ(0.5*Э1 + 0.5*Э2;0)
Список литературы

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

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

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