8_Теория алгоритмов. (Мацнев А.П. - Математическая логика и теория алгоритмов - 2004), страница 3

Определить для любых заданных формул R и S в логическом исчислении, существует ли дедуктивная цепочка, ведущая от R к S, или нет.

Если формула А может быть преобразована в формулу В однократным применением допустимой подстановки, и наоборот, то А и В — смежные формулы. Последовательность формул, соседние из которых смежные, называется дедуктивной цепочкой, ведущей от к . Под решением проблемы распознавания выводимости понимается алгоритм, дающий ответ на вопрос о существовании дедуктивной цепочки (для любых R и S).

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

Теорема 8.1 (теорема Черча). Проблема распознавания выводимости алгоритмически неразрешима.

Далее вставка 8В

8.6 Меры сложности алгоритмов. Классы задач P и NP.

Основы анализа алгоритмов.

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

При анализе алгоритма определяется количество "времени", необходимое для его выполнения. Это не реальное число секунд или других промежутков времени, а приблизительное число операций, выполняемых алгоритмом. Число операций и измеряет относительное время выполнения алгоритма. Таким образом, иногда мы будем называть "временем" вычислительную сложность алгоритма. Фактически количество секунд, требуемое для выполнения алгоритма на компьютере непригодно для анализа, поскольку нас интересует только относительная эффективность алгоритма, решающего конкретную задачу. Действительно алгоритм не становится лучше, если его перенести на более быстрый компьютер, или хуже, если его исполнять на более медленном компьютере.

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

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

Скоростью роста алгоритма называется скорость роста числа операций при возрастании объёма входных данных. Нас интересует только общий характер поведения алгоритма, а не подробности этого поведения. Подводя итоги, при анализе алгоритмов нас будет интересовать скорее класс скорости роста, к которому относится алгоритм, нежели точное количество выполняемых им операций аддитивного и мультикативного типа.

Некоторые часто встречающиеся классы функций приведены в таблице. В этой таблице приведены значения функций из данного класса на широком диапазоне значений аргумента. Видно, что при небольших размерах входных данных значения функций отличаются незначительно, однако при росте этих размеров разница существенно возрастает. Во-вторых, быстродействующие функции доминируют над функциями с более медленным ростом. Поэтому если мы обнаружим, что сложность алгоритма представляет собой сумму двух или нескольких таких функций, то будем часто отбрасывать все функции кроме тех, которые растут быстрее всего. Если, например, установлено, что алгоритму нужно x³-30x операций, то будем считать, что сложность алгоритма растёт как x³. Причина этого в том, что уже при 100 входных данных разница между x³ и x³ -30x составляет лишь 0,3%.

Таблица классов роста функций

Скорость роста сложности алгоритма играет важную роль, скорость роста определяется старшим, доминирующим членом формулы. Отбросив все младшие члены, мы получаем то, что называется порядком функции или алгоритма, скоростью роста сложности которого она является. Алгоритмы можно сгруппировать по скорости роста их сложностей. Мы вводим три категории: алгоритмы, сложность которых растёт по крайней мере так же быстро, как данная функция (класс Ω(f) - читается Омега большое), алгоритмы, сложность которых растёт с той же скоростью(класс О(f) - читается О большое) и алгоритмы, сложность которых растёт медленнее, чем эта функция (класс θ(f) - читается Тета большое).

Мы занимаемся эффективностью алгоритмов, поэтому класс Ω(f) не будет представлять для нас большого интереса: например в Ω(n²) входят все функции, растущие быстрее, чем n².

Класс О(f) состоит из функций, растущих не быстрее f. Функция f образует верхнюю границу для класса О(f). Проверить принадлежит ли данная функция классу О(f) можно двумя способами:

1. С формальной точки зрения функция g принадлежит классу O(f), если g(n) cf(n) для всех n, больших некоторого n₀, и для некоторой положительной константы с.

2. g принадлежит O(f), если lim(g(n)/f(n)) = c (n-> ) для некоторой константы с.

По правилу Лопиталя можно заменить предел самих функций пределом их производных.

Через θ (f) мы обозначаем класс функций, растущих с той же скоростью, что и f. С формальной точки зрения этот класс представляет пересечение двух предыдущих классов θ(f)= Ω(f) O(f). При сравнении алгоритмов нас будут интересовать такие, которые решают задачу быстрее, поэтому класс θ(f) нам не очень интересен.

Алгоритмы полиномиальной сложности (класс Р).

Большинство алгоритмов имеют полиномиальный порядок сложности. Иногда время работы оказывается линейным, как при последовательном поиске: при удлинении списка данных вдвое алгоритм работает вдвое дольше. В алгоритмах последовательного поиска нас интересует процесс просмотра списка в поисках некоторого элемента, называемого целевым. При последовательном поиске предполагается, что список не отсортирован. Например, ключевое значение может быть номером сотрудника, фамилией, или любым другим уникальным идентификатором. Алгоритм последовательного поиска последовательно просматривает по одному элементу списка, начиная с первого, до тех пор пока не найдет нужный элемент. Очевидно, что чем дальше в списке находится конкретное значение ключа, тем больше времени уйдет на его поиск.

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

Рассмотрим наиболее типичный вариант сортировки – пузырьковую сортировку. Алгоритм пузырьковой сортировки совершает несколько проходов по списку. При каждом проходе происходит сравнение соседних элементов. Если порядок соседних элементов неправильный, они меняются местами. Каждый проход начинается с начала списка. Сперва сравниваются 1 и 2 элементы, затем 2 и 3, потом 3 и 4 и т.д. Элементы с неправильным порядком в паре переставляются. При обнаружении на первом проходе наибольшего элемента списка он будет переставляться со всеми последующими пока не дойдет до конца списка. Поэтому при втором проходе нет необходимости производить сравнение с последним элементом. При втором проходе второй по величине элемент списка опустится во вторую позицию с конца и т.д. Стоит заметить, что при каждом проходе ближе к своему месту продвигается сразу несколько элементов, хотя гарантировано занимает окончательное положение лишь один.

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

Сложность стандартного алгоритма матричного умножения равна и при увеличении размеров матриц вдвое такой алгоритм работает в 8 раз дольше.

Матрица – математический объект, эквивалентный двумерному массиву. Если число столбцов в первой матрице совпадает с числом строк во второй, то эти две матрицы можно перемножить:

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