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

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

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

Цель курса

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задание 1. Регулярные выражения

Часть 1.

Написать скрипт с использованием утилит bash, который выполняет следующие действия. На вход подаётся путь к директории. В заданной директории (и всех поддиректориях) найти аудио файлы (с расширением .wav), рядом с ними могу лежать отекстовки, они называются также как wav файлы, только с расширением .txt. Для всех файлов, у которых есть отекстовка, сформировать 3 файла:

wav.scp: уникальный_id путь_к_файлу ...

utt2spk: уникальный_id имя_спикера ...

text: уникальный_id отекстовка ...

Имя спикера - это имя директории, в которой лежит файл (пробелы в имени допустимы, но в строке utt2spk они недопустимы - их надо как-то заменить)

Отекстовка берётся из файла отекстовки, переводится в нижний регистр, далее удаляется всё, что не является русской или английской буквой + удаляются вставки вида <какой-то текст>.

Часть 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 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число 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 на тестовом и обучающем.