Мощенский В. А. Обобщенный метод нитей и некоторые его применения. - Мн.: БГУ, 2000. - 69 с.

ISBN 985-445-385-5

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

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

Оглавление

ПРЕДИСЛОВИЕ

3

Раздел 1. ОБОБЩЕННЫЙ МЕТОД НИТЕЙ

4

1.1. T(α,k_α,m) - нити

4

1.2. Первые сложностью характеристики

7

1.3. Дальнейшие сложностные характеристики

11

1.4. Некоторые качественные характеристики

16

1.5. Пути

21

Раздел 2. ПРИМЕНЕНИЕ ОБОБЩЕННОГО МЕТОДА НИТЕЙ

34

2.1. Некоторые свойства on - line вычислений

34

2.1.1. Синхронные on-line вычисления

35

2.1.2. On - line вычисления с одной рабочей лентой

37

2.2. Нижняя оценка временной сложности синхронных on - line вычислений умножения

39

2.3. Нижняя оценка временной сложности on - line вычислений умножения

44

2.4. Другие вспомогательные утверждения

50

2.5. Нижняя оценка существенной сложности on - line вычислений умножения

55

2.6. Нижняя оценка временной сложности одного класса универсальных машин Тьюринга

61

ЛИТЕРАТУРА

68