Практикум по дискретным структурам — различия между версиями

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

Текущая версия на 23:14, 7 октября 2024


Курс по магистерской программе Дискретные структуры и алгоритмы.

Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. Бухман Антон Владимирович.

Цель курса

Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними.

Лекции по курсу

Лекция 1. Переборные алгоритмы и их применения.

Использование переборных алгоритмов для задач комбинаторной оптимизации. Перебор остовных деревьев, решение задачи коммивояжёра, поиск минимальных полиномов.

Распараллеливание программы.

Лекция 2. Оптимизация перебора.

Метод ветвей и границ. Применение МВГ на примере задачи коммивояжёра.

Лекция 3. Подходы к построению быстрых алгоритмов.

Градиентный метод. Динамическое программирование.

Лекция 4. Sat-решатели и их приложения - 1.

Пример SAT решателя, применения для задач построения схемы минимальной сложности для функции.

Лекция 5. Sat-решатели и их приложения - 2.

Применение SAT решателей для поиска минимальных полиномиальных форм.

Лекция 6. Эвристические алгоритмы.

Моделирование отжига, генетические алгоритмы, роевые алгоритмы.

Лекция 7. Применение эвристических алгоритмов.

Получение зачёта.

В рамках данного курса предусмотрено 3 практических задания. Для получения зачёта необходимо сдать все 7 заданий. Приём заданий происходит на семинарах во время выступления студента.

Практические задания

Задание 1. Переборные алгоритмы

Задание 2. Применение SAT решателей к задачам минимизации функций

Дан базис из булевых функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.

Визуализировать схему, которая была найдена при помощи SAT решателя.

Задание 3. Эвристические алгоритмы