Logic and Algorithms

2020/2021

Academic Year

RUS

Instruction in Russian

3

ECTS credits

Delivered at:

Department of Fundamental Mathematics (Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod))

Course type:

Compulsory course

When:

1 year, 4 module

Instructors

Korotkov, Alexander

Kruglov, Vladislav

Nozdrinova, Elena

Polotovskiy, Grigory

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

Аннотация

Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности. Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 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