Введение к работе
Актуальность темы. Работа посвящена вопросам сложности вычислений. Эта тема является актуальной в связи с потребностью в создании эффективных алгоритмов для'практических задач.
В работе изучаются неуниформные модели вычислений, в которых функция на входах различной длины вычисляется различными программами. При этом длина программы молвт расти с ростом длины входа* Такие модели представляют интерес при разработке спецпроцессоров, предназначенных для обработки ограниченных объемов информации.
Цель. Целью настоящей диссертационной работы являются изучение возможности улучшать сложностнье характеристики за счет отказа от униформности, изучение взаимосвязи времени вычисления и объема программы в нёунифорыных моделях, а также изучение методов построения быстрых неуниформных алгоритмов для практических "задач.
Обшая методика исследования. В работе полуиены нижние оценки Шэнноновского типа для сложностных характеристик, а также ряд нижних оценок через параметра реализуемых функций. Верхние оценки получаются конструктивно. В работе приводятся алгоритмы и оценки их сложности. Общие результаты ил-люстрирются на примере двух модельных задач.
. Научная и практическая ценность. Главное научное значение работы автор видит в том, что в ней получен ряд обидах результатов, связанных с неуниформной реализацией вычислимых
функций, в той числе ряд нижних оценок числа состояний, необходимых для реализации функций односторонними и двусторонними автоматами, а также минимального времени вычисления при ограниченном объеме программ. Нэкоторые из этих оценок в общем случае неулучшаемы. Методы построения быстрых неуниформных алгоритмов, рассмотренные в работе, могут быть использованы при разработке вычислителей для некоторых матричных вадач, задач теории графов, для ускорения алгоритмов типа "разделяй и властвуй".
Публикации и апробация. Основное содержание диссертации изложено в работах [1-41. Кроме того, основные результаты работы докладывались: на Всесоюзном семинаре по дискретной ма-тематики и ее приложениям / Мэсква, январь 1987 г. /, на 8-ой Всесоюзной конференции по проблемам теоретической кибернетики /Горький, ишь 1988 г./ и на конференции молодых ученых факультета Вычислительной математики .. и кибернетики МГУ им. М. И. Ломоносова Результаты работы также обсуждались на заседаниях кафедры математической кибернетики факультета ВЫиК МГУ.
Структура и объем работы. Диссертация состоит из введения, двух глав, заключения и списка литературы, содержащего 30 названий. Общий объем работы 78 страниц.