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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Задание 1. Регулярные выражения)
Строка 57: Строка 57:
 
Часть 2. Визуализировать схему, которая была найдена при помощи SAT решателя.
 
Часть 2. Визуализировать схему, которая была найдена при помощи 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. Марковские модели ===
+

Версия 15:11, 14 февраля 2024


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

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

Цель курса

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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