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

Говорят, что задача разрешима за полиномиальное время или полиноми­ ально разрешима, если для неё существует полиномиальный алгоритм. При этом считается, что задача является «хорошей». Множество всех задач, для каждой из которых существует полиномиаль­ ный алгоритм, называется классом Р. Среди полиномиальных алгоритмов быстрыми являются линейные алго­ ритмы, которые обладают сложностью порядка п, где п - размерность входных данных. К линейным алгоритмам относится школьный алгоритм нахождения суммы десятичных чисел, каждое из которых состоит из п цифр. Сложность этого алгоритма - 0(п). В класс Р, кроме линейных задач, попадают, например, следующие задачи. Умножение целых чисел. Школьный метод умножения двух и-разрядных чисел имеет временную сложность порядка 0(п ). Существуют алгоритмы ум­ ножения чисел (заданных в двоичной системе счисления) с меньшей сложно­ стью, например, алгоритм Шёнхаге-Штрассена со сложностью порядка 0(п log2 п log2 log2 п). Подробнее будет изложено далее. л Умножение матриц. Обычный метод имеет порядок сложности 0(п ). Су­ ществует более быстрый алгоритм умножения матриц - алгоритм Штрассена, который имеет сложность порядка ^). Пайти кратчайший путь на графе, состоящем из п вершин и т рёбер. Сложность алгоритма 0(тп). Быстрое преобразование Фурье требует 0(п log2 п) арифметических опера­ ций. Задача Прима - Краскала - Кэли. Дано п городов. Нужно соединить все города телефонным кабелем так, чтобы общая длина кабеля была минимальной. Эта задача решается с помощью жадного алгоритма сложности 0(nlog2 п). Нахождение эйлерова цикла в графе с т рёбрами. Алгоритм нахождения эйлерова цикла имеет сложность порядка 0(т). Задачи, для которых не существует полиномиального алгоритма, считают­ ся трудно разрешимыми. Рассмотрим пример определения сложности вычислений (алгоритма) на примерах. Пусть задано множество S, содержащее п действительных чисел. Требует­ ся найти наибольший и наименьший элементы из S. Положим, что каждое одно сравнение двух любых чисел осуществляется за одинаковое время. Один из возможных методов состоит в поиске сначала наибольшего эле­ мента из S, а затем - наименьшего. Наибольший элемент можно найти, проводя п-1 сравнений, например, по следующему алгоритму. begin МАХ^произвольный элемент из S; 222