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