Практикум по дискретным структурам — различия между версиями
(→Задание 2. Применение SAT решателей к задачам минимизации функций) |
PodymovVV (обсуждение | вклад) м |
||
| Строка 1: | Строка 1: | ||
| + | [[Категория:Спецкурсы кафедры МК]] | ||
[[Категория:Лекционные курсы кафедры МК]] | [[Категория:Лекционные курсы кафедры МК]] | ||
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]] | [[Категория:Магистерская программа Дискретные структуры и алгоритмы]] | ||
Текущая версия на 23:14, 7 октября 2024
Курс по магистерской программе Дискретные структуры и алгоритмы.
Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. Бухман Антон Владимирович.
Содержание
- 1 Цель курса
- 2 Лекции по курсу
- 2.1 Лекция 1. Переборные алгоритмы и их применения.
- 2.2 Лекция 2. Оптимизация перебора.
- 2.3 Лекция 3. Подходы к построению быстрых алгоритмов.
- 2.4 Лекция 4. Sat-решатели и их приложения - 1.
- 2.5 Лекция 5. Sat-решатели и их приложения - 2.
- 2.6 Лекция 6. Эвристические алгоритмы.
- 2.7 Лекция 7. Применение эвристических алгоритмов.
- 3 Получение зачёта.
- 4 Практические задания
Цель курса
Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними.
Лекции по курсу
Лекция 1. Переборные алгоритмы и их применения.
Использование переборных алгоритмов для задач комбинаторной оптимизации. Перебор остовных деревьев, решение задачи коммивояжёра, поиск минимальных полиномов.
Распараллеливание программы.
Лекция 2. Оптимизация перебора.
Метод ветвей и границ. Применение МВГ на примере задачи коммивояжёра.
Лекция 3. Подходы к построению быстрых алгоритмов.
Градиентный метод. Динамическое программирование.
Лекция 4. Sat-решатели и их приложения - 1.
Пример SAT решателя, применения для задач построения схемы минимальной сложности для функции.
Лекция 5. Sat-решатели и их приложения - 2.
Применение SAT решателей для поиска минимальных полиномиальных форм.
Лекция 6. Эвристические алгоритмы.
Моделирование отжига, генетические алгоритмы, роевые алгоритмы.
Лекция 7. Применение эвристических алгоритмов.
Получение зачёта.
В рамках данного курса предусмотрено 3 практических задания. Для получения зачёта необходимо сдать все 7 заданий. Приём заданий происходит на семинарах во время выступления студента.
Практические задания
Задание 1. Переборные алгоритмы
Задание 2. Применение SAT решателей к задачам минимизации функций
Дан базис из булевых функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.
Визуализировать схему, которая была найдена при помощи SAT решателя.
