МЛиТА-2018‎ > ‎

Проекты по МЛиТА-2018

Проект 1. Автоматический тематический кроссворд
Идея проекта. В газетах и журналах на последних страницах часто публикуют кроссоврды. Однако их тематика случайна и не связана с тематикой статей. Нужно создать средство для автоматического или полуавтоматического составления кроссвордов на основе текстов статей.
Подпроект 1. Анализ текстов статей, выделение корпуса существительных, приведение их к именительному падежу, выделение важных для тематики статьи существительных (вместе с удалением незначащих слов-связок).
Основа для работы: рекомендации И.А.Посова к проекту прошлого года "Ярмарка тщеславия": "рекомендую взять Томита Парсер от Яндекса и научиться им пользоваться".
Новизна и область для самостоятельных исследований: выделение из текста важных для её тематики существительных.
Подпроект 2. Поиск определений существительных в интернете. Можно сузить задачу до поиска в википедии. Сокращение текста определений до размера заданий кроссворда.
Основа для работы: позакомиться с ситемой SciSearch (возможно удастся получить консультации от её автора А.А.Паньгина).
Новизна и область для самостоятельных исследований: сокращение текста определений до размера заданий кроссворда.
Подпроект 3. Автоматическое составление кроссворда из заданного (избыточного) множества слов.
Основа для работы: использование переборнах алгоритмов, в том числе, метода перебора с возвратом и метода ветвей и границ. 
Новизна и область для самостоятельных исследований: построение различных симетричных шаблонов для кроссовордов, выбор оптимального шаблона для заданного множества слов, учет дополнительных ограничений, таких как макисмизация числа статей, из которых взяты существительные, оценка трудоемкости возникающих задач.

Проект могут взять две команды, каждая из 3 человек, которые могут работать параллельно (обмениваясь по желанию информацией) и сравнивая эффективность различных решений поставленных задач (главное, чтобы у каждой команды был свой взгляд на решение задачи).

Проект 2.  Исследование клеточных автоматов на примере игры "Жизнь"
Идея проекта. По заданной конфигурации определить, какие конфигурации могут породить её и в каком поколении.
Подпроект 1. По заданной конфигурации автоматически построить систему логических уравнений и привести к 3-КНФ.
Подпроект 2. Задача 3-SAT. Доказательство NP-полноты задачи об игре "Жизнь" или опровержение этой гипотезы.
Подпроект 3. Участие в интернет соревнованиях на самую быструю программу для решения проблемы 3-SAT (самостоятельно выяснить в сети, все связанное с этим конкурсом, одним из её организаторов был профессор математико-механического факультета, специалист в области сложности вычислений Э.А. Гирш (https://www.lektorium.tv/lecture/13563 - одна из лекций Гирша про доказательство NP-полноты, можно посмотреть лекции Куликова "Алгоритмы для NP-трудных задач")
Новизна и область для самостоятельных исследований: выяснить, является ли исходная задача NP-полной, то есть можно ли по произвольной 3-КНФ построить конфигурацию игры "Жизнь", которую она определяет. Если ответ отрицательный, то нужно описать множество функций, который описывают один шаг игры "Жизнь".

Проект могут взять двк команды, каждая из 3 человек, которые могут работать параллельно (обмениваясь по желанию информацией) и сравнивая эффективность различных решений поставленных задач (главное, чтобы у каждой команды был свой взгляд на решение задачи).

Проект 3. “Инструкция к гаджету” (тема “Автоматы”)

Проблема. В современных устройствах часто бывает минимум кнопок, однако нажатие на них может вызывать различные результаты в зависимости от состояния других кнопок. Примером тому может служить портативная колонка ginzzu gm 875 (она ни чем не примечательна, кроме того, что преподаватель читал её инструкцию). Инструкция описывает поведение колонки при различных воздействиях на неё. Инструкция фактически описывает работу конечного автомата, но состояния этого автомата явно не выделены. Требуется написать программу, на входе которой будет инструкция, а на выходе описание (а ещё интереснее виртуальная модель) автомата. Это может быть полезным проектом, так как вместо инструкций можно будет предлагать пользователям поработать с моделью устройства.

Замечание. Полезная книга для проекта (да и для курса МЛиТА)

Джон Хопкрофт и др. "Введение в теорию автоматов, языков и вычислений", 2-е издание, 2008. https://vk.com/wall-54530371_7597



Comments