Практикум по дискретным структурам — различия между версиями
(→Задание 2. Применение SAT решателей к задачам минимизации функций) |
|||
| Строка 53: | Строка 53: | ||
=== Задание 2. Применение SAT решателей к задачам минимизации функций === | === Задание 2. Применение SAT решателей к задачам минимизации функций === | ||
| − | Дан базис функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности | + | Дан базис из булевых функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ. |
| − | + | Визуализировать схему, которая была найдена при помощи SAT решателя. | |
=== Задание 3. Эвристические алгоритмы === | === Задание 3. Эвристические алгоритмы === | ||
Текущая версия на 08:49, 27 марта 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 решателя.
