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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Задание 1. Регулярные выражения)
(→‎Задание 2. Применение SAT решателей к задачам минимизации функций)
 
(не показаны 2 промежуточных версий 1 участника)
Строка 44: Строка 44:
 
== Получение зачёта. ==
 
== Получение зачёта. ==
  
−
В рамках данного курса предусмотрено 7 практических заданий. Для получения зачёта необходимо сдать все 7 заданий.
+
В рамках данного курса предусмотрено 3 практических задания. Для получения зачёта необходимо сдать все 7 заданий.
 
Приём заданий происходит на семинарах во время выступления студента.  
 
Приём заданий происходит на семинарах во время выступления студента.  
  
Строка 53: Строка 53:
 
=== Задание 2. Применение SAT решателей к задачам минимизации функций ===
 
=== Задание 2. Применение SAT решателей к задачам минимизации функций ===
  
−
Дан базис функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности <=N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.
+
Дан базис из булевых функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.
  
−
Часть 2. Визуализировать схему, которая была найдена при помощи SAT решателя.
+
Визуализировать схему, которая была найдена при помощи SAT решателя.
  
−
=== Задание 3. Классические модели машинного обучения ===
+
=== Задание 3. Эвристические алгоритмы ===
−
 
+
−
 
+
−
1. Выбрать 3 модели машинного обучения (список https://scikit-learn.org/stable/user_guide.html). Рассказать о ней (презентация) кратко.
+
−
 
+
−
2. Визуализировать данные и результаты работы обученных алгоритмов. (matplotlib)
+
−
 
+
−
3. Обучить 3 классификатора на наборе данных (2 признака на входе 2 класса на выходе)
+
−
 
+
−
4. Провести тест посчитать acc/rec/F1 метрику.
+
−
 
+
−
5. Сравнить модели используя 5x2 кросс валидацию (https://machinelearningmastery.com/hypothesis-test-for-comparing-machine-learning-algorithms/)
+
−
 
+
−
=== Задание 4. Обучение простейшей нейронной сети ===
+
−
 
+
−
1. Получить вариант задания, подготовить описание с примерами в виде презентации.
+
−
 
+
−
2. Найти входные данные для обучения. Поделить обучающую выборку на трейновую, тестовую и валидационную. Показать пример входных данных (визуализировать например)
+
−
 
+
−
3. Реализовать нейросеть, обучить её
+
−
 
+
−
4. Визуализировать кривые обучения
+
−
 
+
−
5. Провести тестирование
+
−
 
+
−
6. Провести анализ ошибок, т.е. выбрать 20 примеров из тестовой выборки, где модель сработала неверно.
+
−
 
+
−
7.  Написать утилиту с использованием этой модели, чтобы можно было потестировать в аудитории. Например, Ваша модель распознаёт речь, нужна программа, которая получив аудио файл выдаст отестовку.
+
−
 
+
−
=== Задание 5. Рекурентные нейронные сети ===
+
−
 
+
−
1. Из датасета на базе open_stt сформировать обучающую и тестовую выборки (по варинту).
+
−
 
+
−
2. Собрать модель на основе ctc_voxforge.py.
+
−
 
+
−
3. Обучить модели согласно заданию (по варианту, в котором 3 размера датасета + 2 варианта слоёв слоёв)
+
−
 
+
−
4. Провести эксперименты
+
−
размер датасета, время обучения, скорость inference, число эпох, число слоёв, cer/wer на тестовом и обучающем.
+
−
 
+
−
=== Задание 6. Преобразование Фурье ===
+
−
 
+
−
=== Задание 7. Марковские модели ===
+

Текущая версия на 08:49, 27 марта 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. Эвристические алгоритмы

Источник — «https://mk.cs.msu.ru/index.php?title=Практикум_по_дискретным_структурам&oldid=11070»