О некоторых сложностных характеристиках неуниформных вычислений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МЭСКОВСКИЙ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ

И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИЫШ М Е ЛОМОНОСОВА

Факультет вычислительной математики и кибернетики

На правах рукописи СЕТИН Анатолий Алексеевич

УДК 619.95

О НЕКОТОРЫХ СЛОШЮСТЕЫХ ХАРАКТЕРИСТИКАХ НЕУШФОРШШ ВЫЧИСЛЕНИЙ

Специальность 01.01.09 - математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1992

Работа выполнена на кафедре 1&теиагической кибернетики факультета Вычислительной математики и кибернетики МГУ ИМ.Ц.В. Ломоносова

Нзучный руководитель:

кандидат физико-математических наук, доцент Ь В. Алексеев. Официальные оппоненты:

доктор физико-математических наук, профессор Б. К. Леонтьев, кандидат физико-математических наук, H. Е Кузюрин.

Ведущая организация:

Институт математики Сибирского отделения Российской Академии наук.

* - V

. Защита состоится "¿g*4 1392 .г. в ÎL час.

СО мин. на • заседании специализированного совета Д. 053.05.38. при МГУ им. IL R Ломоносова. " — Адрес: Нэсква, 119899, ¿ГУ, факультет Вычислительной математики и кибернетики.

С диссертацией можно ознакомиться в библиотеке ШиК МГУ.

• Автореферат разослан " 1992 г.

Ученый секретарь специализированного

совета, кандидат физико-математических

наук, профессор Е. П. Трифонов.

- ! ОЭДАЯ ХАРАКТЕРИСТИКА ДИООКРТАЦИОЮЮЙ РАБОТИ.

Актуальность темы. Работа посвящена вопросам сложности вычислений. Эта тема является актуальной в связи с потребностью в создании эффективных алгоритмов для'практических задач.

В работе изучаются неуниформные модели вычислений, в которых функция на входах различной длины вычисляется различными программами. При этом длина программы может расти с ростом длины входа* Такие модели представляют интерес при разработке спецпроцессоров, предназначенных для обработки ограниченных объемов информации.

Цель. Целью настоящей диссертационной работы являются изучение возможности улучшать сложностные характеристики за счет отказа от униформности, изучение взаимосвязи времени вычисления и объема программы в неуниформных моделях, а также изучение методов построения быстрых неуниформных алгоритмов для практических 'задач.

Обшая методика исследования. В работе получены нижние оценки Шэнноновского типа для сложностных характеристик, а также ряд нижних оценок через параметра реализуемых функций. Верхние оценки получаются конструктивно. В работе приводятся алгоритмы и оценки их сложности. Общие результаты ил-люстрирюгся на примере двух модельных задач.

. Научная и практическая ценность. Главное научное значение работы автор видит в том, что в ней получен ряд обидах результатов, связанных с неуниформной реализацией вычислимых

- А -

функций, в той числе ряд нижних оценок числа состояний, необходимых для реализации функций односторонними и двусторонними автоматами, а также минимального времени вычисления при ограниченном объеме программ. Шкоторые ив этих оценок в общгм случае неулучшаемы. Методы построения быстрых неуниформных алгоритмов, рассмотренные в работе, могут быть использованы при разработке вычислителей для некоторых матричных вадач, задач теории графов, для ускорения алгоритмов типа "разделяй и властвуй".

Публикации и апробация. Основное содержание диссертации изложено в работах [1-41. Кроме того, основные результаты работы докладывались: на Всесоюзном семинаре по дискретной ма-

*

тематики и ее приложениям / Москва, январь 1987 г. /, на 8-ой Всесоюзной конференции по проблемам теоретической кибернетики /Горький, ишь 1988 г./ и на конференции молодых ученых факультета Вычислительной математики .. и кибернетики МГУ им. М. И. Ломоносова Результаты работы также обсуждались на заседаниях кафедры математической кибернетики факультета ВЫиК МГУ.

Структура и объем работы. Диссертация состоит из введения, двух глав, заключения и списка литературы, содержащего 30 названий. Общий объем работы 78 страниц.

СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ.

Как уже отмечалось.выше, работа посвящена изучению неу-ниформньи моделей вычислений. В отличие от униформных моде-

- Б -

лей, когда некоторая функция вычисляется на входе любой длины с помощью одного конечного вычислителя (конечного автомата, машины Тьюринга, конечной РАК-прбграммы и т.д.), в неуниформных моделях вычисляемая функция Г представляется как последовательность где Тп,определена на словах длины п и совпадает с Г в своей области определения, и каждая функция реализуется своим вычислителем. При этом объем программы может расти с ростом а

Неуниформная реализация может оказаться выгоднее униформной в разных отношениях. Во-первых, в этом случае возможна реализация функции более простыми вычислителями. Во-вторых, за счет отказа от униформности можно уменьшить сложность вычислений (время или память). В связи с неуниформными вычислениями возникают следующие задачи: 1) для заданий функции исследовать рост длины программы при реализации этой функции вычислителями из определенного класса, например детерминированными или недетерминированными автоматами и т. д.; 2) для заданной функции и заданного класса вычислителя исследовать зависимость сложностей характеристик от роста длины программ.

Сложность неуниформных вычислений естественно сравнивать с униформной сложностью. Однако проблема получения нижних оценок даже для унифзрмной сложности является весьма трудной, для многих задач не известно точных оценок. В такой ситуации логично поступать двумя способами. Во-первых, исследовать достачочно простые модели вычислений, для которых получены

нижние оценки униформной сложности, и сравнивать неуниформную сложность с этими оценками. Во-вторых, сравнивать неуниформ-нуо сложность практических задач со сложностью известных униформных алгоритмов.

Пэрвая глава посвящена следующим вопросам. Рассматривается неуниформная реализация булевых функций односторонними и двусторонними автоматами (детерминированными и недетерминированными). Исследуется минимальное число состояний, необходимое для реализации "самых сложных" функций, т.е. функция Шеннона Показано, что функция Шеннона для детерминированных автоматов (односторонних и двусторонних) имеет порядок 2 /п, а для недетерминированных автоматов (односторонних и двусто-

. . »Л.

ронних ) имеет порядок 2 . Далее получен ряд оценок сложности реализации в этих моделях через параметры реализуемых функций. Некоторые из этих оценок в общем случае неулуч-шаемы, т.е. ссуществуют функции, для которых эти оценки точны по порядку. В частности общие оценки, примененные к модельным задачам, позволяют получить точные по порядку оценки 0(п) для распознавания симметрии и 0( 1оелп/1од1ое п) для распознавания языка {О^^У.

Далее изучается вопрос, как может измениться число состояний при сравнительно небольшом усилении модели, а именно рассматривается вычисления в реальное время машинами Тьюринга с к рабочими лентами (обычный автомат является частным случаем при к=0). Показано, что для перехода от к+1-ленточной машины к к-ленточной может потребоваться экспоненциальный рост числа состояний.

■ - 7 -

При неунифэршой реализации вычислимых функций машинами Тьюринга вопрос о порядке минимального числа состояний тривиален - это константа. Существенным является вопрос о соотношении времени вычисления'и числа состояний. •

Для одаоленточных машин Тьюринга. получено две нижние *

оценки времени работы через число подфункций специального вида и число состояний. Обе оценки в обдем случае не улучшаемы. Для двух модельных задач получены точные по порядку оценки:

L '

0(n/logQ(n)) для распознавания симметрии и 0(п log n/logQ(n)) для распознавания языка ,''где Q(n) - число состояний машины Тьюринга.

Цри рассмотрении многоленточных машин исследовались машины, работающие в префиксном режиме. Пжазано существование языков, распознающихся униформно в префиксном режиме многоленточными машинами Тьюринга за время Т(п), таких что любое уменьшение порядка времени распознавши требует зкспонециаль-ного роста числа состояний при неуниформном распознавании.

далее рассматриваются вероятностные , неуниформные вычисления машинами Тьюринга Для модельных задач получены точные по порядку оценки времени распознавания: 0(n log n/logQCn)) для распознавания симметрии и 0(nloglogn/logQ(n)) для . распознавания языка {О* Г'}. Кроме того получена нижняя граница длины максимального следа при распознавании нерегулярных языков. Вторая глава посвящэна методам ускорения известных алгоритмов для практических задач за счет увеличения длины программы при неуниформных вычислениях. Для задачи о кратчайших путях методом декомпозиции алгоритма по известному униформно-

ну алгоритму с временной битовой сложностью 0(nJlogn) строится неуниформный алгоритм с временной слозшостъй

1 VA

0(n log n (log n/logQ(n)) ), где Q(n) - длина программы. Штод декомпозиции задачи применяется к задачам, решаемым методом "разделяй и властвуй", и иллюстрируется с помощью задачи умножения матриц. Показано, что если известен алгоритм ум- . ножения матриц с битовой сложностью 0(n fi log n)), где lf(i) - сложность умножения i-значных чисел, то можно построить неунифорыньй алгоритм с временной сложностью OCn^log n (log n/logQCn))"^ ), где Q(n) - длина программы.

В сходной по форме задаче умножения n-значных чисел не удается уменьшить порядок времени вычисления без экспоненциального роста длины программы. Показано, что умножение в префиксном режиме многоленточными машинами Тьюринга п-аначных т Я-1

чисел на КА= 2 за время меньшее по порядку чем n log п требует экспоненциального числа состояний ( известна верхняя оценка порядка n log п для униформного умножения на К*,).

В заключении пользуюсь случаем поблагодарить своего научного руководителя Е Б. Алексеева за постановку задачи и большую помощь при ее решении.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ.

1. to лучены оценки функции Шэннона для неуниформной реализации булевых функций односторонними и двусторонними (детерминированными и недетерминированными) автоматами.

2. Излучены нижние оценки числа состояний для неуниформной реализации функций детерминированныим и недетерминирован-

ними автоматами через параметры реализуемых функций.

3. Показано, что добавление рабочих лент при неуниформных вычислениях в реальное время может экспоненциально уменьшить число состояний.

4. Исследована связь времени вычисления и числа состояний для неуниформных вычислений машинами Тьюринга.

5. Исследованы методы ускорения известных алгоритмов за счет увеличения длины программ. Построены быстрые неуниформные алгоритмы для задач о кратчайших путях и задачи умножения матриц.

СПИСОК РАБОТ ПО СОДЕРЖАНИЮ' ДИССЕРТАЦИИ.

1. Сетин А". А. О сложности распознавания симметрии // Некоторые вопросы вычислительной математики, математической физики и программного обеспечения ЭВМ. - М.: Изд-во МГУ, 1987. - С. 49.

2. Сетин А. А. Нижние оценки неуниформной сложности вычислений // Труды семинара по дискретной математике и ее приложениям.- - №: Изд-во МГУ, 1989. - С. 176-178.

3. Сетин А. А. Реализация предикатов односторонними и двусторонними недетерминированными автоматами // Проблемы теоретической кибернетики. Тезисы докладов 8-ой Всесоюзной конференции. Горький, 1988. - С. 109-110.

4. Сетин А. А. О сложности неуниформных вычислений для некоторых-дискретных задач.// Вестн. Моск. ун-та. Сер 15, Вычислительная математика и кибернетика. - 1989. - N0 3. - С. 51-56.