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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Задание 2.)
м
 
(не показаны 17 промежуточные версии 1 участника)
Строка 1: Строка 1:
 +
[[Категория:Спецкурсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]
 
[[Категория:Магистерская программа Дискретные структуры и алгоритмы]]
Строка 13: Строка 14:
  
  
=== Лекция 1. Регулярные выражения и обработка тескта. ===
+
=== Лекция 1. Переборные алгоритмы и их применения. ===
  
=== Лекция 2. Преобразование Фурье в приложении к обработке аудио и видео сигналов. ===
+
Использование переборных алгоритмов для задач комбинаторной оптимизации.
 +
Перебор остовных деревьев, решение задачи коммивояжёра, поиск минимальных полиномов.
  
Лекция 3. Sat-решатели и их приложения.
+
Распараллеливание программы.
  
Лекция 4. Задачи машинного обучения. Классические модели Machine Learning.
+
=== Лекция 2. Оптимизация перебора. ===
  
Лекция 5. Нейронные сети и их применение к задачам ML.
+
Метод ветвей и границ. Применение МВГ на примере задачи коммивояжёра.
  
Лекция 6. Final State Transducers и их применение к задачам распознавания звука.
+
=== Лекция 3. Подходы к построению быстрых алгоритмов. ===
  
Лекция 7. Лингвистические модели и задачи обработки текста.
+
Градиентный метод. Динамическое программирование.
  
Лекция 8. Скрытые Марковские модели и их приложения.
+
=== Лекция 4. Sat-решатели и их приложения - 1. ===
  
== Получение зачёта. ==
+
Пример SAT решателя, применения для задач построения схемы минимальной сложности для функции.
  
В рамках данного курса предусмотрено 7 практических заданий. Для получения зачёта необходимо сдать все 7 заданий.
+
=== Лекция 5. Sat-решатели и их приложения - 2. ===
Приём заданий происходит на семинарах во время выступления студента.  
+
  
== Практические задания ==
+
Применение SAT решателей для поиска минимальных полиномиальных форм.
  
=== Задание 1. ===
+
=== Лекция 6. Эвристические алгоритмы. ===
  
''Часть 1.''
+
Моделирование отжига, генетические алгоритмы, роевые алгоритмы.
  
Написать скрипт с использованием утилит bash, который выполняет следующие действия.
+
=== Лекция 7. Применение эвристических алгоритмов. ===
На вход подаётся путь к директории.
+
В заданной директории (и всех поддиректориях) найти аудио файлы (с расширением .wav), рядом с ними могу лежать отекстовки, они называются также как wav файлы, только с расширением .txt. Для всех файлов, у которых есть отекстовка, сформировать 3 файла:
+
  
wav.scp:
+
== Получение зачёта. ==
уникальный_id путь_к_файлу
+
...
+
  
utt2spk:
+
В рамках данного курса предусмотрено 3 практических задания. Для получения зачёта необходимо сдать все 7 заданий.
уникальный_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 решателю и получить ответ.
+
 
+
=== Задание 3. Обучение простейшей нейронной сети ===
+
 
+
1. Получить вариант задания, подготовить описание с примерами в виде презентации.
+
 
+
2. Найти входные данные для обучения. Поделить обучающую выборку на трейновую, тестовую и валидационную. Показать пример входных данных (визуализировать например)
+
  
3. Реализовать нейросеть, обучить её
+
=== Задание 1. Переборные алгоритмы ===
  
4. Визуализировать кривые обучения
+
=== Задание 2. Применение SAT решателей к задачам минимизации функций ===
  
5. Провести тестирование
+
Дан базис из булевых функций от 2 переменных (базис определяется вариантом задания, который можно получить у преподавателя). Написать программу, которая получив на вход число N и вектор значений функции строит кнф, которая выполнима, если СФЭ для данной функции сложности N существует, невыполнима иначе. Можно использовать вариант сведения, который был рассказан на лекции. Полученную КНФ подать на вход SAT решателю и получить ответ.
  
6. Провести анализ ошибок, т.е. выбрать 20 примеров из тестовой выборки, где модель сработала неверно.
+
Визуализировать схему, которая была найдена при помощи 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. Эвристические алгоритмы