Методы получения нижних оценок сложности ветвящихся программ, вычисляющих булевы функции


Скачать 100,28 Kb.
PDF просмотр
НазваниеМетоды получения нижних оценок сложности ветвящихся программ, вычисляющих булевы функции
страница1/7
ОКОЛЬНИШНИКОВА Елизавета Антоновна
Дата конвертации03.09.2012
Размер100,28 Kb.
ТипАвтореферат
СпециальностьДискретная математика и математическая кибернетика
Год2007
На соискание ученой степениДоктор физико-математических наук
  1   2   3   4   5   6   7
На правах рукописи
ОКОЛЬНИШНИКОВА Елизавета Антоновна
МЕТОДЫ ПОЛУЧЕНИЯ НИЖНИХ ОЦЕНОК
СЛОЖНОСТИ ВЕТВЯЩИХСЯ ПРОГРАММ,
ВЫЧИСЛЯЮЩИХ БУЛЕВЫ ФУНКЦИИ
специальность 01.01.09  дискретная математика и
математическая кибернетика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
доктора физико-математических наук
Новосибирск  2007

Работа выполнена в Институте математики им. С. Л. Соболева
СО РАН РФ
Официальные оппоненты:
доктор физико-математических наук, профессор
Аблаев Фарид Мансурович
доктор физико-математических наук, профессор
Мошков Михаил Юрьевич
доктор физико-математических наук, профессор
Шоломов Лев Абрамович
Ведущая организация:
механико-математический
факультет
Московского
государственного университета им. М.В. Ломоносова
Защита состоится 24 октября 2007 г. в
час.
мин.
на заседании диссертационного совета Д 003.015.01 при
Институте математики им. С. Л. Соболева СО РАН : 630090,
г. Новосибирск, пр. Академика Коптюга, 4, к. 417.
С диссертацией можно ознакомиться в библиотеке
Института математики им. С. Л. Соболева СО РАН.
Автореферат разослан "
"
2007 г.
Ученый секретарь
диссертационного совета
д.ф.-м.н.
Ю.В. Шамардин
2

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Теория сложности вычислений
является важным разделом математической кибернетики.
Целью теории является оценивание величины ресурсов,
необходимых для решения тех или иных вычислительных
задач. Рассматриваются различные модели вычисления такие,
например, как машины Тьюринга, автоматы, нормальные
алгоритмы, схемы из функциональных элементов, формулы в
различных базисах и т. д.1) В качестве оцениваемых ресурсов
рассматриваются время вычисления, объем используемой па-
мяти, длина программы и др. Под сложностью вычисления по-
нимается величина этого ресурса. При этом сложность зависит
как от модели вычислений, так и от выбранного оцениваемого
ресурса. Основным объектом теории является получение
верхних и нижних оценок сложности. При этом получение
нижних оценок сложности в большинстве рассматриваемых
моделях вычислений представляет наибольшую трудность.
Это объясняется тем, что при установлении нижних оценок
сложности надо в той или иной мере просмотреть все
возможные способы вычисления рассматриваемого объекта и
показать, что вычислить этот объект с меньшими затратами
невозможно. При получении нижних оценок сложности
возникают, решаются и используются важные и интересные
задачи из различных областей дискретной математики.
Известно [2, 4, 5, 18, 19], что во многих моделях
вычисления, таких как схемы из функциональных элементов,
контактные схемы, формулы в конечных базисах, ветвящиеся
программы, почти все булевы функции вычисляются очень
сложно (экспонента от числа переменных функции), тем не
менее, лишь для небольшого числа полностью определенных
булевых функций доказано, что их нельзя вычислить с
1)Важным понятием в теории сложности является также сложность
объектов по Колмогорову, введенная в [3] для алгоритмического
определения понятия количества информации.
3

линейной сложностью (для схем из функциональных элемен-
тов удалось получить лишь линейные оценки) относительно
числа переменных булевой функции. К этому направлению
относятся работы А. А. Разборова [8] и А. Е. Андреева [1],
в которых были получены сверхполиномиальные2) нижние
оценки сложности для схем из функциональных элементов в
монотонном базисе, реализующих известные функции.
Сложность вычисления булевой функции зависит от
модели вычисления. Так, например, линейная булева функция
вычисляется с линейной сложностью в классе схем из
функциональных элементов, контактных схем, ветвящихся
программ, но реализуется схемой не менее чем квадратичной
сложности в классе формул в базисе (?, ?, ¬), и дизъюнктив-
ными нормальными формами не менее чем экспоненциальной
сложности.
В связи с этим возникает проблема нахождения таких
функций, для которых удается получить нетривиальные
нижние оценки сложности в данной модели вычислений.
Удобным объектом для изучения сложности являются ха-
рактеристические функции двоичных кодов. Эти функции
детально изучаются в дискретной математике, в частности,
в теории кодов, исправляющих ошибки. Интерес к этим
функциям вызван как их структурными свойствами (одним
из таких свойств является ѕдостаточно равномернаяї распре-
деленность множества единиц значений характеристических
функций этих кодов по n-мерному булеву кубу), так и
широким практическим применением.
В данной работе рассматриваются вопросы сложности
ветвящихся программ, вычисляющих булевы функции, а так-
же операции над булевыми функциями, которые позволяют
из просто вычислимых функций получать функции большей
сложности.
2)Функция ?(n) называется сверхполиномиальной, если ее можно
представить в виде ?(n) = n?(n), где ?(n) ? ? при n ? ?.
4
  1   2   3   4   5   6   7

Разместите кнопку на своём сайте:
поделись


База данных защищена авторским правом ©dis.podelise.ru 2012
обратиться к администрации
АвтоРефераты
Главная страница