Практикум по дискретным структурам — различия между версиями
PodymovVV (обсуждение | вклад) м |
(→Задание 2. Применение SAT решателей к задачам минимизации функций) |
||
| (не показаны 32 промежуточных версий 1 участника) | |||
| Строка 4: | Строка 4: | ||
Курс по магистерской программе Дискретные структуры и алгоритмы. | Курс по магистерской программе Дискретные структуры и алгоритмы. | ||
| − | Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]] | + | Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]]. |
| − | == | + | == Цель курса == |
| − | + | Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| + | == Лекции по курсу == | ||
| − | === | + | |
| − | + | === Лекция 1. Переборные алгоритмы и их применения. === | |
| − | + | ||
| − | + | Использование переборных алгоритмов для задач комбинаторной оптимизации. | |
| + | Перебор остовных деревьев, решение задачи коммивояжёра, поиск минимальных полиномов. | ||
| + | |||
| + | Распараллеливание программы. | ||
| + | |||
| + | === Лекция 2. Оптимизация перебора. === | ||
| + | |||
| + | Метод ветвей и границ. Применение МВГ на примере задачи коммивояжёра. | ||
| + | |||
| + | === Лекция 3. Подходы к построению быстрых алгоритмов. === | ||
| + | |||
| + | Градиентный метод. Динамическое программирование. | ||
| + | |||
| + | === Лекция 4. Sat-решатели и их приложения - 1. === | ||
| + | |||
| + | Пример SAT решателя, применения для задач построения схемы минимальной сложности для функции. | ||
| + | |||
| + | === Лекция 5. Sat-решатели и их приложения - 2. === | ||
| + | |||
| + | Применение SAT решателей для поиска минимальных полиномиальных форм. | ||
| + | |||
| + | === Лекция 6. Эвристические алгоритмы. === | ||
| + | |||
| + | Моделирование отжига, генетические алгоритмы, роевые алгоритмы. | ||
| + | |||
| + | === Лекция 7. Применение эвристических алгоритмов. === | ||
| + | |||
| + | == Получение зачёта. == | ||
| + | |||
| + | В рамках данного курса предусмотрено 3 практических задания. Для получения зачёта необходимо сдать все 7 заданий. | ||
| + | Приём заданий происходит на семинарах во время выступления студента. | ||
| + | |||
| + | == Практические задания == | ||
| + | |||
| + | === Задание 1. Переборные алгоритмы === | ||
| + | |||
| + | === Задание 2. Применение SAT решателей к задачам минимизации функций === | ||
| + | |||
| + | Дан базис из булевых функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ. | ||
| + | |||
| + | Визуализировать схему, которая была найдена при помощи SAT решателя. | ||
| + | |||
| + | === Задание 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 решателя.
