Описание:Учебный курс состоит из трех частей. В первой части курса изучаются задачи минимизации дизъюнктивных нормальных форм. Рассматриваются булевы функции и представление булевых функций дизъюнктивными нормальными формами (ДНФ), сокращённые ДНФ и тупиковые ДНФ. Изучаются способы построения некоторых ДНФ (сокращённой, пересечения тупиковых, Квайна, суммы тупиковых) и особенности ДНФ для булевых функций из некоторых классов. Решается задача покрытия множеств, ее приложения и ее связь с задачей минимизации ДНФ. Приводится алгоритм построения всех тупиковых ДНФ и градиентный алгоритм построения покрытий. Устанавливается оценка размера покрытия, полученного градиентным алгоритмом.
Вторая часть курса посвящена задачам синтеза и оценкам сложности дискретных управляющих систем. Изучаются различные классы дискретных управляющих систем, которые используются в качестве структурных математических моделей различных типов электронных схем, систем обработки информации и управления, алгоритмов и программ. Вводятся схемы из функциональных элементов (СФЭ), контактные схемы (КС), двоичные решающие диаграммы (BDD), определяются их структура, меры сложности, функционирование, применение. Рассматривается задача синтеза дискретных управляющих систем и приводятся простейшие методы синтеза схем, реализация некоторых булевых функций и оценка их сложности. Изучаются метод каскадов, метод Шеннона, а также мощностные методы получения нижних оценок для функций Шеннона и асимптотически наилучшие методы синтеза схем из некоторых классов. Рассматриваются операции над BDD и алгоритмы их реализации. Изучается применение BDD как структуры данных в комбинаторных алгоритмах.
В третьей части курса изучаются задачи построения и анализ комбинаторных алгоритмов и основы теории алгоритмической сложности задач. Изучаются методы доказательства корректности алгоритмов и меры сложности алгоритмов. Описываются алгоритмы поиска и сортировки и оценки их сложности. Изучаются принципы построения эффективных алгоритмов - «разделяй и властвуй», динамическое программирование – и примеры их применения. Приводятся примеры алгоритмов, построенных указанными методами. Вводится понятие алгоритмической сводимости задач и приводятся примеры алгоритмически сводимых задач. Вводятся классы сложности задач P и NP и доказывается теорема Кука-Левина об NP-полноте задачи проверки выполнимости булевых формул. Рассматриваются примеры NP-полных задач. Вводятся классы сложности NL и PSPACE и приводятся примеры полных задач из классов сложности P, NL, PSPACE.