|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Автоматный подход к решению задачи 3 выполнимостикурсовая работа (Бакалавр)
- Научный руководитель: Половников В.С.
- Автор: Давыдов Ф.Г
- Тип: Бакалавр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Кафедра: Филиал МГУ в г. Ташкент
- Год защиты: 2014
- Курс: 3
- Аннотация: Проблема P=NP остается открытой многие годы и возникает вопрос: может ли параллельное (автоматное, нейросетевое) или приближенное вычисление позволить решать задачи класса NP за приемлемое время. Давыдов Ф.Г. рассмотрел классическую NP-полную задачу 3-ВЫП, проверки на выполнимость (наличие единицы в таблице истинности) функции по ее формуле, записанной в форме 3-КНФ, то есть конъюнкции некоторого количества дизъюнктов состоящих ровно из трех литералов (литерал, это символ переменной или его отрицание). Федору удалось построить множество из 2^n универсальных структурных автоматов, определяющих выполнимость формулы от n переменных, записанной в форме 3-КНФ из m дизъюнктов. Были оценены такие параметры как сложность схемы автомата (количество элементов) и время работы (количество тактов, необходимое для получение ответа о выполнимости формулы на выходе автомата). Оказалось, что в зависимости от параметра k=1,…,2^n, время вычисления можно уменьшить в k раз (по сравнению с алгоритмом полного перебора значений x1,…,xn), но при этом сложность предложенной схемы возрастает также в k раз.
- Добавил в систему: Половников Владимир Сергеевич