• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Logic and Algorithms

2019/2020
Academic Year
ENG
Instruction in English
3
ECTS credits

Instructors

Course Syllabus

Abstract

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

Learning Objectives

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

Expected Learning Outcomes

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

Course Contents

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

Assessment Elements

  • non-blocking Контрольная работа
  • non-blocking Контрольная работа
  • non-blocking Контрольная работа
Interim Assessment

Interim Assessment

  • Interim assessment (3 module)
    0.35 * Контрольная работа + 0.35 * Контрольная работа + 0.3 * Контрольная работа
Bibliography

Bibliography

Recommended Core Bibliography

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

Recommended Additional Bibliography

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