Практикум по дискретным структурам

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

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

Программа курса

Тема 1. Алгоритмы на графах

Структуры данных для представления графов на С/C++/Python. Сложность реализации простейших операций на на графах

Тема 2. Применение параллельной обработки данных для задач дискретной математики

Метод ветвей и границ Средства ОС для реализации многопроцессорной обработки

Тема 3. Дискретные структуры в задачах DataMining и MachineLearning

Классификаторы. Деревья решений. Бустинг. Задача кластеризации. Простейшие алгоритмы кластеризации. Библиотеки для работы с задачами ML и DM.

Тема 4. Элементы функционального программирования

Парадигма функционального программирования. Списки и работа с ними. Представление дискретных структур на Lisp (Haskell) Представление графов. Алгоритмы на графах.

Домашние задания

Реализовать алгоритм перебора всех остовных деревьев заданного графа Построить классификатор применяя бустинг на основе деревьев решений Проверка выполнимости КНФ на основе метода ветвей и границ