|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Оптимизация фильтров приёмов решателя, описанных на языке ГЕНОЛОГдипломная работа (Бакалавр)
- Научный руководитель: Калачев Г.В.
- Автор: Вагапов Рашид Юнирович
- Тип: Бакалавр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2016
- Аннотация: Данная работа является частью проекта по созданию нового интерфейса, а также оптимизиру-ющего компилятора для решателя математических задач. Решатель – программа, написанная А. С. Подколзиным, способная решать задачи из различных областей математики. Решатель основан на огромной базе приёмов, которые А.С. Подколзин вручную вводил в Решатель и отлаживал на про-тяжении 20 лет. На данный момент основным недостатком Решателя является отсутствие стан-дартных и привычных обычному пользователей действий таких, как копирование и вставка текста из других приложений, а также загрузка данных из файла, не являющегося частью программы и множество других привычных функций. Все эти особенности представляют для большинства пользователей непреодолимый барьер, препятствующий полноценному освоению основной воз-можности Решателя – вводить и отлаживать новые приёмы решения задач. Это сильно препят-ствует развитию системы. В текущей версии Решателя приемы записаны на языке ГЕНОЛОГ и хранятся в бинарных фай-лах и могут отображаться лишь через интерфейс решателя таким образом, что не всегда удается увидеть весь прием целиком. Редактирование приемов осуществляется в том же интерфейсе, что не всегда удобно. Таким образом, ГЕНОЛОГ не является языком программирования в обычном смысле, а скорее задает общую структуру приема. ГЕНОЛОГ компилируется в язык ЛОС. В настоящий момент разрабатывается новый интерфейс и архитектура решателя математиче-ских задач. Одной из задач было перевести все приёмы из бинарного формата в текстовый и запи-сать всю базу приёмов в файлы, чтобы их можно было загрузить из новой версии Решателя, а так-же использовать системы контроля версий для отслеживания изменений. С этой задачей Рашид успешно справился, написав модуль к программе LOS reader, который считывает всю базу приё-мов и выдаёт их в виде множества текстовых файлов. Вторая задача более сложная и связана с оптимизацией программы на ЛОСе, получающейся в результате компиляции множества приёмов, записанных на языке ГЕНОЛОГ. Приём содержит множество фильтров, каждый из которых представляет из себя некоторый предикат, который ис-тинен с заданной вероятностью и имеет заданную сложность (эти параметры измеряются экспе-риментально). Приём применяется, если все предикаты истинны. Требуется задать порядок вы-числения предикатов таким образом, чтобы минимизировать среднее время вычисления фильтров в предположении, что значения всех предикатов – независимые случайные величины. Рашид реализовал жадный алгоритм, оптимизирующих последовательность вычисления пре-дикатов и провёл ряд экспериментов, сравнив полученное решение с оптимальным, которое было получено полным перебором. Во всех случаях, где переборный алгоритм работает за разумное время, жадный алгоритм выдал оптимальное решение. При этом в работе нет ни доказательства, что оптимальное решение всегда будет найдено, ни контрпримера. Также нет никаких оценок сложности жадного алгоритма. Это является существенным недостатком работы, поскольку в этой задаче предполагалось получить теоретические результаты, включая оценки сложности по-иска оптимального и приближённого решения. Текст работы в настоящий момент написан очень небрежно, его местами очень трудно пра-вильно понять, если заранее не знать постановку задачи.
- Добавил в систему: Гасанов Эльяр Эльдарович