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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
м
 
(не показаны 34 промежуточных версий 2 участников)
Строка 1: Строка 1:
 +
[[Категория:Спецкурсы кафедры МК]]
 +
[[Категория:Лекционные курсы кафедры МК]]
 +
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]
 +
 
Курс по магистерской программе Дискретные структуры и алгоритмы.
 
Курс по магистерской программе Дискретные структуры и алгоритмы.
  
Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]], Мельник Марина Владимировна.
+
Чтение курса обеспечивается кафедрой математической кибернетики, лекторы — м.н.с. [[Бухман Антон Владимирович]].
  
== Программа курса ==
+
== Цель курса ==
  
=== Тема 1. Алгоритмы на графах ===
+
Цель: изучить/повторить наиболее изветсные дискретные модели, которые используются на практике, и освоить програмные инструменты работы ними.
Структуры данных для представления графов на С/C++/Python.
+
Сложность реализации простейших операций на на графах
+
=== Тема 2. Применение параллельной обработки данных для задач дискретной математики ===
+
Метод ветвей и границ
+
Средства ОС для реализации многопроцессорной обработки
+
=== Тема 3. Дискретные структуры в задачах DataMining и MachineLearning ===
+
Классификаторы. Деревья решений.
+
Бустинг.
+
Задача кластеризации. Простейшие алгоритмы кластеризации.
+
Библиотеки для работы с задачами ML и DM.
+
=== Тема 4. Элементы функционального программирования ===
+
Парадигма функционального программирования.
+
Списки и работа с ними.
+
Представление дискретных структур на Lisp (Haskell)
+
Представление графов. Алгоритмы на графах.
+
  
 +
== Лекции по курсу ==
  
=== Домашние задания ===
 
Реализовать алгоритм перебора всех остовных деревьев заданного графа
 
Построить классификатор применяя бустинг на основе деревьев решений
 
Проверка выполнимости КНФ на основе метода ветвей и границ
 
  
 +
=== Лекция 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. Эвристические алгоритмы