|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Временная сложность схем из функциональных элементовдипломная работа (Бакалавр)
- Научные руководители: Гасанов Э.Э., Шуткин Ю.С.
- Автор: Хасанов Родион Ильмирович
- Тип: Бакалавр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2012
- Аннотация: В работе Родиона Хасанова исследуются вопросы сложности вычисления значений функций, реализуемых схемами из функциональных элементов. Ранее А.В.Чашкин предложил использовать для этих целей неветвящиеся программы и показал, что сложность вычисления значения функций с помощью неветвящихся программ экспоненциально зависит от числа переменных функции. С другой стороны Ю.С.Шуткиным было показано, что значение функции, представленной в виде контактной схемы, может быть вычислено за линейное время. Это позволяло надеяться, что при правильном выборе модели вычислений и для случая схем из функциональных элементов может быть получена линейная временная сложность. . В работе Р.Хасановым было показано, что если в неветвящиеся программы добавить оператор условного перехода, то для любой булевой функции значение функции может быть вычислено за линейное время. К сожалению, работа написана небрежно. В постановочной части нет строгого и полного описания предлагаемой модели. Доказательства требуют более детальной проработки. Результаты достаточно тривиальны. Не удалось получить точной (или асимптотически точной) оценки временной сложности.
- Добавил в систему: Гасанов Эльяр Эльдарович