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

Логика и алгоритмы

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус: Курс обязательный (Математика)
Направление: 01.03.01. Математика
Когда читается: 1-й курс, 4 модуль
Формат изучения: без онлайн-курса
Преподаватели: Коротков Александр Геннадьевич, Круглов Владислав Евгеньевич, Ноздринова Елена Вячеславовна, Полотовский Григорий Михайлович
Язык: русский
Кредиты: 3
Контактные часы: 40

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

Аннотация

Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности. Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 01.03.01 «Математика», изучающих дисциплину «Логика и алгоритмы».
Цель освоения дисциплины

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

  • Целями освоения дисциплины «Логика и алгоритмы» являются, с одной стороны, освоение теоретико-множественных конструкций, возникающих во многих областях высшей математики, а с другой стороны – знакомство с некоторыми темами, классическими в математической логике. В курсе рассмотрены: булевые функции, графы, конечные автоматы, машина Тьюринга
Планируемые результаты обучения

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

  • Знает определение булевой функции. Может назвать все булевые функции одной переменной и основные булевые функции двух переменных (конъюнкция, дизъюнкция, импликация, эквивалентность, штрих Шеффера, стрелка Пирса)
  • Знает определение классов Поста (монотонных функций, самодвойственных, сохраняющих 0, сохраняющих 1, линейные функции). Знает определение замыкания множества булевых функция, умеет доказывать основные свойства замыкания. Знает и умеет доказывать теорему Поста.
  • Знаком с понятием схемы из функциональных элементов. Умеет составлять схему из функциональных элементов для произвольных булевых функций.
  • Знает определение графа, знает основные способы задания графа (матрица смежности, списки смежности, матрица инцидентности)
  • Знает формулировки теорем Холла и Дилуорса.
  • Знает определение паросочетания. Владеет алгоритмом построения паросочетаний.
  • Знает определение размеченного графа. Владеет понятием графа размеченного над полукольцом.
  • Знает определение пути, цепи, длинны пути в графе. Владеет алгоритмами поиска в ширину и в глубину.
  • Знает определение регулярного выражения. Умеет строить автомат, допускающий данный язык и язык, допускаемы данным автоматом.
  • Знает определение графа, размеченного над полукольцом языков, может привести примеры его применения.
  • Знает определение схем с памятью.
  • Знает определение программы и вычислимой функции. Знает определение и может привести примеры перечислимых и разрешимых множеств натуральных чисел.
  • Может привести пример функции, вычислимой на машине Тьюринга, но не вычислимой конечным автоматом.
Содержание учебной дисциплины

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

  • Булевы функции
    Законы де Моргана для конъюнкции и дизъюнкции. Монотонные, линейные, самодвойственные, сохраняющие 0, сохраняющие 1 булевы функции. Теорема Поста. Схемы из функциональных элементов.
  • Графы
    Матрица инцидентности. Теоремы Холла и Дилуорса. Алгоритм построения паросочетаний. Графы, размеченные над полукольцом. Алгоритмы поиска в глубину и в ширину.
  • Конечные автоматы
    Язык, допускаемый конечным автоматом. Регулярные выражения, регулярные языки. Построение языка по автомату и автомата по языку. Граф, размеченный над полукольцом языков, его применения. Соответствие схем с памятью и автоматов.
  • Машина Тьюринга
    Программы. Вычислимые функции. Перечислимые и разрешимые множества натуральных чисел. Существование функции, вычислимой на машине Тьюринга, но не вычислимой конечным автоматом
Элементы контроля

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

  • неблокирующий Контрольная работа
  • неблокирующий Контрольная работа
  • неблокирующий Контрольная работа
Промежуточная аттестация

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

  • Промежуточная аттестация (4 модуль)
    0.3 * Контрольная работа + 0.3 * Контрольная работа + 0.4 * Контрольная работа
Список литературы

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

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

  • Бинарные отношения, графы и коллективные решения, учебное пособие, 2-е изд., перераб. и доп., 341 с., Алескеров, Ф. Т., Хабина, Э. Л., Шварц, Д. А., 2017
  • Дискретная математика для программистов, учебное пособие, 2-е изд., 364 с., Новиков, Ф. А., 2006
  • Логика, сборник упражнений : учебное пособие, 248 с., Ивлев, Ю. В., 2002
  • Методы представления знаний и алгоритмы поиска в задачах искусственного интеллекта, учебное пособие, 146 с., Бабкин, Э. А., Козырев, О. Р., Куркина, И. В., 2005

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

  • Графы и алгоритмы. Структуры данных. Модели вычислений, учебник, 319 с., Алексеев, В. Е., Таланов, В. А., 2012