Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

г 1, если п = 2, (7.1) Т(п) = \ \2Т(п/2) + 2, если п>2. Решением рекуррентных уравнений (7.1) служит функция Т(п)=(3/2)п-2. Таким образом, вместо 2п-2 сравнений получили {3/2)п-2 сравнений чисел, т.е на (п/2) сравнений меньше. Рассмотрим второй пример. Пусть требуется умножить два п разрядных двоичных чисел. При традиционном (школьном) алгоритме требуется 0(п ) би­ товых операций. Применим стратегию дублирования и разобьем числа х и на две части одинакового размера (по числу цифр): а b с d Считаем, что п есть степень числа 2. Тогда можно получить XJ/ = (2^+2^'^)bd + 2^'^(a-b)(d-c) + (2''^^+\)ас. (7.2) Равенство (7.2) даёт способ вычисления ху с помош,ью трех умножений fn/2J разрядных чисел и нескольких сложений и сдвигов (умножений на степень числа 2). Здесь вычисляются умножения: bd, (a-b)(d-c) и ас. Можно получить, что при этом вместо 0(п^) битовых операций нужно ) ~ 0(n^'^^) бито­ вых операций. Этот алгоритм предложил Анатолий Карацуба в 1960 году. От­ метим, что в 1956 году А.П. Колмогоров сформулировал гипотезу, что нижняя оценка числа операций при любом методе умножения есть величина порядка 2 2 (так называемая «гипотеза п » Колмогорова). Па правдоподобность гипотезы п указывал тот факт, что метод умножения «в столбик» известен не менее четы­ рёх тысячелетий (например, этим методом пользовались шумеры), и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден. Од­ нако, в 1960 году Анатолий Карацуба нашёл новый метод умножения двух п- значных чисел с оценкой сложности ) и тем самым опроверг «гипо­ тезу П^У>. Используя быстрое преобразование Фурье, был найден алгоритм умноже­ ния двух чисел, который имеет сложность 0(п log2n log2 log2n) (алгоритм Шён- хаге-Штрассена). Алгоритм Шёнхаге-Штрассена начинает превосходить алго­ ритм Карацубы и алгоритм Тоома-Кука начиная с целых чисел, имеюш,их от 10 ОО до 40 ОО десятичных знаков. В настояш,ее время получен еш,е более бы­ стрый алгоритм умножения, превосходяш,ий указанные выше алгоритмы еш,е для более больших чисел, чем алгоритм Шёнхаге-Штрассена. Абстрактной моделью полиномиального алгоритма является так назы­ ваемая детерминированная машина Тьюринга. Эта машина в каждый данный момент времени находится в строго определённом состоянии, за один шаг она совершает одно из некоторого конечного множества действий. Затем она пере­ 224