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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
м
 
(не показаны 7 промежуточные версии 1 участника)
Строка 1: Строка 1:
 +
[[Категория:Спецкурсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]
 
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]
Строка 15: Строка 16:
 
=== Лекция 1. Переборные алгоритмы и их применения. ===
 
=== Лекция 1. Переборные алгоритмы и их применения. ===
  
=== Лекция 2. Оптимизация перебора. ===
+
Использование переборных алгоритмов для задач комбинаторной оптимизации.
 +
Перебор остовных деревьев, решение задачи коммивояжёра, поиск минимальных полиномов.
  
Лекция 3. Подходы к построению быстрых алгоритмов.
+
Распараллеливание программы.
  
Лекция 4. Sat-решатели и их приложения - 1.
+
=== Лекция 2. Оптимизация перебора. ===
  
Лекция 5. Sat-решатели и их приложения - 2.
+
Метод ветвей и границ. Применение МВГ на примере задачи коммивояжёра.
  
Лекция 6. Эвристические алгоритмы.
+
=== Лекция 3. Подходы к построению быстрых алгоритмов. ===
  
Лекция 7. Применение эвристических алгоритмов.
+
Градиентный метод. Динамическое программирование.
  
== Получение зачёта. ==
+
=== Лекция 4. Sat-решатели и их приложения - 1. ===
  
В рамках данного курса предусмотрено 7 практических заданий. Для получения зачёта необходимо сдать все 7 заданий.
+
Пример SAT решателя, применения для задач построения схемы минимальной сложности для функции.
Приём заданий происходит на семинарах во время выступления студента.  
+
  
== Практические задания ==
+
=== Лекция 5. Sat-решатели и их приложения - 2. ===
  
=== Задание 1. Регулярные выражения ===
+
Применение SAT решателей для поиска минимальных полиномиальных форм.
  
''Часть 1.''
+
=== Лекция 6. Эвристические алгоритмы. ===
  
Написать скрипт с использованием утилит bash, который выполняет следующие действия.
+
Моделирование отжига, генетические алгоритмы, роевые алгоритмы.
На вход подаётся путь к директории.
+
В заданной директории (и всех поддиректориях) найти аудио файлы (с расширением .wav), рядом с ними могу лежать отекстовки, они называются также как wav файлы, только с расширением .txt. Для всех файлов, у которых есть отекстовка, сформировать 3 файла:
+
  
wav.scp:
+
=== Лекция 7. Применение эвристических алгоритмов. ===
уникальный_id путь_к_файлу
+
...
+
  
utt2spk:
+
== Получение зачёта. ==
уникальный_id имя_спикера
+
...
+
  
text:
+
В рамках данного курса предусмотрено 3 практических задания. Для получения зачёта необходимо сдать все 7 заданий.
уникальный_id отекстовка
+
Приём заданий происходит на семинарах во время выступления студента.  
...
+
  
Имя спикера - это имя директории, в которой лежит файл (пробелы в имени допустимы, но в строке utt2spk они недопустимы - их надо как-то заменить)
+
== Практические задания ==
  
Отекстовка берётся из файла отекстовки, переводится в нижний регистр, далее удаляется всё, что не является русской или английской буквой + удаляются вставки вида <какой-то текст>.
+
=== Задание 1. Переборные алгоритмы ===
 
+
''Часть 2.''
+
 
+
Дан список файлов list (только имя) и набор трёх файлов из части 1 (utt2spk, text, wav.scp). Надо из файов трёх файлов удалить всё, то относится к файлам из списка list (при этом естественно не испортить информации об остальных файлах.
+
 
+
Например, есть файл 1.wav c диктором dict, если больше никто не имеет диктора dict, то стереть этого диктора.
+
 
+
Замечание: писать на bash c использованием утилит linux, не использовать python perl gcc и вообще языки программирования.
+
 
+
 
+
Пример входных данных:
+
 
+
wav.scp:
+
id1 /tmp/wavs/Name/1.wav
+
 
+
text:
+
id1 пример текста
+
 
+
utt2spk:
+
id1 Name
+
  
 
=== Задание 2. Применение SAT решателей к задачам минимизации функций ===
 
=== Задание 2. Применение SAT решателей к задачам минимизации функций ===
  
Дан базис функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности <=N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.
+
Дан базис из булевых функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.
 
+
Часть 2. Визуализировать схему, которая была найдена при помощи SAT решателя.
+
 
+
=== Задание 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. Преобразование Фурье ===
+
Визуализировать схему, которая была найдена при помощи SAT решателя.
  
=== Задание 7. Марковские модели ===
+
=== Задание 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. Эвристические алгоритмы