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

Пусть имеем 1 миллион (10^) компьютеров, каждый из них выполняет 1 12 терафлопс (TFLOPS - 10 ) операций в секунду, т.е. на них может выполняться 18 1 о операций в сек. Отметим, что таких компьютеров пока имеется единицы, а не миллионы экземпляров. За 1 год на предполагаемом миллионе компьютеров 7 18 25 может выполняться 3.154х 10 х 10 =3.154х 10 операций. Пусть на рас­ смотрение одного маршрута требуется 100 операций и вычисления продолжа­ ются 100 млн. лет. Тогда число рассмотренных вариантов за 100 млн. лет на 25 8 ^1 этих компьютерах будет равно: 3.154 х 10 х 10 /100 = 3.154 х 10 и это чис­ ло существенно меньше всех вариантов обхода: 3.154 X 10^^ « 1.462x10^"^. Таким образом, если начинать решать эту задачу перебором вариантов, то ее невозможно решить. Поэтому, прежде чем начинать реализовывать указан­ ный алгоритм перебора возможных вариантов обхода городов, прежде всего нужно выяснить сможем ли мы ее решить. Следовательно, возникает проблема анализа сложности алгоритма. § 1. Понятие о сложности Выше указан один пример задачи, которая алгоритмически разрешима, но практически не решаема указанным алгоритмом перебора при больших значе­ ниях размера задачи (числа городов). Существуют и другие задачи, которые теоретически разрешимы, но при практической реализации требуют столь больших вычислений, что их решение практически неосуществимо. Следова­ тельно, принципиальная алгоритмическая разрешимость ещё не означает прак­ тическую реализуемость. Рассмотрим некоторые характеристики вычислений. Считаем, что при вычислении используем алгоритм. Различают сложность описания алгоритма и исходных данных и слож­ ность применения алгоритма к исходным данным. Сложность описания алгоритма зависит от выбора того или иного спосо­ ба задания алгоритма. Если такой способ выбран (машина Тьюринга, нормаль­ ный алгоритм или рекурсивное задание и т.д.), то сложность алгоритма может быть введена как длина записи алгоритма, так и длина встречающихся специ­ альных выражений и т.д. Например, для машины Тьюринга её сложность может быть введена как число букв внешнего и внутреннего алфавитов. Введем следующее определение. Говорят, что неотрицательная функция g(n) есть 0(f(n)), если существует такая постоянная с, что g(n)<cf(n) для всех, кроме конечного (возможно пустого) множества значений п, пе {0,1, 2, 3,...}. В этом случае записываем: g(n)= 0(f(n)). Сложность исходных данных понимается как длина (размер) их записи. Что такое размер входа? Всё зависит от того, что является входом. Размером 218