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

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

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

Цель курса

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

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

Лекция 2. Преобразование Фурье в приложении к обработке аудио и видео сигналов.

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

Лекция 4. Задачи машинного обучения. Классические модели Machine Learning.

Лекция 5. Нейронные сети и их применение к задачам ML.

Лекция 6. Final State Transducers и их применение к задачам распознавания звука.

Лекция 7. Лингвистические модели и задачи обработки текста.

Лекция 8. Скрытые Марковские модели и их приложения.

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

В рамках данного курса предусмотрено 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.

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

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

Задание 3. Обучение простейшей нейронной сети

1. Получить вариант задания, подготовить описание с примерами в виде презентации.

2. Найти входные данные для обучения. Поделить обучающую выборку на трейновую, тестовую и валидационную. Показать пример входных данных (визуализировать например)

3. Реализовать нейросеть, обучить её

4. Визуализировать кривые обучения

5. Провести тестирование

6. Провести анализ ошибок, т.е. выбрать 20 примеров из тестовой выборки, где модель сработала неверно.

7. Написать утилиту с использованием этой модели, чтобы можно было потестировать в аудитории. Например, Ваша модель распознаёт речь, нужна программа, которая получив аудио файл выдаст отестовку.