Проблемы с программой алгоритмом

Для статистического метода сложности времени, в начале мы придумали метрику [скачкообразность] (стандарт обнаружения). Как следует из названия, это написать N видов решений для решаемой проблемы, а затем поместить кучу данных, позволить им работать на разных компьютерах и сравнить время работы после запуска. По этому (критерии обнаружения) определяют уровень своевременности алгоритма.

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

Это несправедливый метод обнаружения для чуть более медленных машин. Как будто люди делают 50-метровый забег, чтобы сравнить его с вашим 100-метровым забегом. Это сравнение бессмысленно!

Слабое место математики: можно ли доказать всё, что истинно? [Veritasium]

Это обсуждение понятно, следующее легче понять!

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

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

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

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

Давайте посмотрим на простую функцию суммирования:

def get_sum(n): sum = 0 for i in range(1,n+1): sum += i return sum print(get_sum(10))

Давайте внимательно проанализируем приведенный выше код. Фактически можно обнаружить, что число выполнений оператора присваивания суммирования может быть хорошей базовой единицей подсчета. В приведенной выше функции get_sum количество операторов присваивания равно 1 (сумма = 0) плюс n ( Количество выполнений суммы + = i).

Обычно мы используем функцию T для представления общего количества операторов присваивания. Например, приведенный выше пример может быть выражен как T (n) = n + 1.

Здесь n обычно относится к «размеру данных».

Для n это может занять 10, 100, 1000 или другие большие числа. Все мы знаем, что для решения крупномасштабной задачи требуется больше времени, чем мелкой, поэтому наша следующая цель ясна. , То есть «как найти время выполнения программы, меняется в зависимости от масштаба проблемы».

Наши ученые и специалисты более глубоко задумались об этом методе анализа. Они обнаружили, что влияние ограниченных операций на T (n) не так важно, как некоторые из основных операций. Другими словами, » По мере увеличения размера данных одна часть функции T (n) маскирует влияние другой части на функцию ».

Оценка сложности алгоритмов | О большое | Алгоритмы и структуры данных

В конце концов, эта доминирующая часть используется для сравнения функций, поэтому следующим является время, когда известно, что большой O дебютирует.

Обозначение Big O

Функция «величина» используется для описания наиболее быстро растущей части функции T (n) при увеличении масштаба n. Обычно мы используем «большой O» для представления этой функции и записываем ее как O (f (n)).

Он обеспечивает приблизительное количество фактических шагов в вычислении.Функция f (n) является упрощенным представлением доминирующей части исходной функции T (n).

В приведенном выше примере функции суммирования T (n) = n + 1, так как n увеличивается, константа 1 становится все меньше и меньше для конечного результата. Если нам нужно приближение T (n), все, что нам нужно сделать, это игнорировать 1 и думать, что время работы T (n) равно O (n). Это похоже на то, что мы стремимся к ограничению в больших количествах

Вы должны понять это здесь. Дело не в том, что 1 не имеет значения для T (n), но в том, что, когда n увеличивается до большого значения, приблизительное значение, полученное путем удаления 1, также очень точно.

Для другого примера, например, существует алгоритм T (n) = 2n ^ 2 + 2n + 1000. Когда n равно 10 или 20, постоянная 1000, по-видимому, играет решающую роль в T (n). Но что, если n равно 1000 или 10000 или больше? п ^ 2 сыграло главную роль.

Фактически, когда n очень велико, последние два члена несущественны для конечного результата. Подобно примеру функции суммирования выше, когда n становится больше, мы можем игнорировать другие члены и сосредоточиться только на приблизительном значении T (n) с 2n ^ 2.

Точно так же влияние коэффициента 2 будет становиться все меньше и меньше по мере увеличения n, поэтому его можно игнорировать. Затем мы скажем, что величина T (n) равна f (n) = n ^ 2, то есть O (n ^ 2).

Лучший случай, худший случай и средний случай

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

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

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

Для «оптимальной ситуации» нет большой ценности, поскольку она не дает никакой полезной информации, она отражает только наиболее оптимистичную и идеальную ситуацию и не имеет справочной ценности.

«Средняя ситуация» — это комплексная оценка алгоритма, поскольку она полностью и всесторонне отражает природу алгоритма, но, с другой стороны, нет гарантии для этого измерения. Не каждая операция может быть выполнена таким способом. Завершено в данных обстоятельствах.

Для «наихудшего сценария» он дает гарантию, что гарантия больше не будет действовать, поэтомуВ общем, сложность времени, которую мы рассчитываем, — это сложность времени в худшем случае, это та же самая причина, по которой мы обычно должны учитывать худший случай при выполнении каких-либо действий.

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

Чтобы определить, какие из этих функций доминируют в T (n), нам нужно сравнить их при увеличении n, см. рисунок ниже (рисунок из Google Images):

На рисунке выше мы можем видеть, что когда n мало, трудно различать функции, трудно сказать, кто является доминирующим, но когда n увеличивается, мы можем видеть, что Очевидная разница, кто является боссом с первого взгляда:

Давайте проанализируем некоторые из «функций величины», упомянутых выше:
Постоянная функция

n = 100 # 1 раз сумма = (1 + n) * n / 2 # 1 раз печать (сумма) # 1 раз

Приведенный выше алгоритм программы f (n) = 3, некоторые люди могут увидеть, что он скажет, что временная сложность O (f (n)) = O (3), на самом деле это неправильно, временная сложность этой функции на самом деле O (1). Это тот результат, который трудно понять новичкам, на самом деле вы можете скопировать сумму = (1 + n) * n / 2 несколько раз и увидеть снова:

а = 100 # 1 раз сумма = (1 + n) * n / 2 # 1 раз сумма = (1 + n) * n / 2 # 1 раз сумма = (1 + n) * n / 2 # 1 раз сумма = (1 + n) * n / 2 # 1 раз сумма = (1 + n) * n / 2 # 1 раз сумма = (1 + n) * n / 2 # 1 раз печать (сумма) # 1 раз

Вышеприведенный алгоритм f (n) = 8, фактически вы можете обнаружить, что независимо от того, чем является n, вышеуказанные два фрагмента кода являются разницей между выполнением 3 и 8 раз. Этот тип алгоритма не имеет ничего общего с размером данных n. Мы называем его алгоритмом с постоянным временем выполнения с O (1) временной сложностью. Независимо от этой константы мы будем записывать ее как O (1), а не O (3) или O (8).

Логарифмическая функция

cnt = 1 while cnt < n: cnt *= 2 # O(1)

Временная сложность вышеуказанного алгоритма программы O (logn). Как это рассчитывается? На самом деле это очень просто: приведенный выше код можно интерпретировать как умножение cnt на 2, прежде чем оно станет больше или равно n. Предположим, что число равно x, то есть найти 2 ^ x = n, то есть x = log2n, поэтому временная сложность этого цикла Это O (logn).

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

a = 1 b = 2 c = 3 for i in range(n): for j in range(n): x = i * i # Думайте о теле цикла как 3, потому что для вычисления цикла используется умножение, поэтому оно равно 3n ^ 2 y = j * j z = i * j for k in range(n): u = a * k + b # Подумайте о теле цикла как 2, потому что цикл вычисляется умножением, так что это 2n v = c * c d = 4

Приведенный выше код не имеет никакого смысла. Это даже не исполняемый код. Я просто использую его для объяснения того, как вы можете анализировать код в будущем. Что касается возможности выполнения самого кода, вам не нужно об этом заботиться.

Фактически, приведенный выше код можно разделить на 4 части: первая часть — это три оператора присваивания a, b и c, а число выполнения — 3 раза, вторая часть — 3n ^ 2, потому что это структура цикла, которая имеет x, y, z три оператора присваивания, каждый оператор выполняется n ^ 2 раза;

Третья часть — 2n, потому что есть два оператора присваивания, каждый из которых выполняется n раз, последняя часть 4 — это константа 1, только d — один оператор присваивания. Таким образом, мы получаем T (n) = 3 + 3n ^ 2 + 2n + 1 = 3n ^ 2 + 2n + 4. Глядя на экспоненциальный член, мы естественным образом обнаруживаем, что n ^ 2. доминирует. Когда n увеличивается, последний Два члена можно игнорировать, поэтому порядок фрагмента кода O (n ^ 2).

Пространство сложности

Аналогично обсуждению временной сложности, пространственная сложность алгоритма относится к пространству памяти, занимаемому алгоритмом, формула расчета рассчитывается как: S (n) = O (f (n)). Где n также размер данных, а f (n) здесь относится к функции пространства хранения, занимаемого n.

В общем, когда наша программа работает на компьютере, в дополнение к входным данным, которые должны хранить саму программу, ей также необходимо хранить «модуль хранения», который работает с данными.

Если пространство, занимаемое входными данными, не имеет ничего общего с алгоритмом, оно зависит только от самой проблемы, тогда вам нужно только проанализировать «вспомогательные единицы», занятые алгоритмом в процессе реализации. Если требуемая вспомогательная единица является константой, сложность пространства составляет O (1).

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

Поэтому, когда мы пишем код ежедневно, мы вывели практику «пространства для времени», и это стало нормой.

Например, когда мы решаем последовательность Фибоначчи, мы можем напрямую использовать формулу, чтобы рекурсивно найти, какой из них использовать, и мы также можем сначала вычислить много результатов и сохранить их, а затем напрямую вызвать, какой из них используется. Это типичное использование Практика смены пространства на время, но вы говорите, какая из этих двух особенностей хороша. Великий Маркс сказал нам «конкретный анализ конкретных проблем».

Написать после

Если вы внимательно прочитаете вышеприведенную статью, вы обнаружите, что я не говорю вам напрямую, как найти сложность во времени, но от генерации проблемы, до решения проблемы, до «коня», а затем до T (n ) И, наконец, шаг за шагом к O (n).

Для этого есть две причины: одна — дать вам понять, откуда появился Big O, и иногда понять происхождение, что очень полезно для вашего следующего изучения и понимания.

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

Многие люди, от колледжа до работы, пишут много кода и до сих пор не оценивают сложность времени. Я не думаю, что не могу выучить это, но я не обращаю на это внимание.

Вы можете подумать, что компьютер быстро обновляется, скорость обработки ЦП становится все лучше и лучше, не нужно беспокоиться о некоторых мелких аспектах, на самом деле я думаю, что вы слишком молоды, слишком наивны.

Давайте просто посчитаем простой пример: есть два компьютера, ваш компьютер работает в 100 раз быстрее моего компьютера, та же проблема, очевидно, можно подумать об использовании O (n), вы должны быть ленивыми Прямо насильственный O (n ^ 2), а затем, когда данные n слегка увеличиваются, например, на десятки тысяч или 100 000, кто является самой высокой скоростью вычислений, я вам скажу?

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

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

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

Я использовал несколько небольших примеров в этой статье, и примерный метод оценки такой. После этого я продолжу писать статьи о «структурах данных и алгоритмах» и некоторых конкретных практических темах, в которых каждый будет продолжать анализировать сложность своего времени, так что следите за обновлениями.

Источник: russianblogs.com

Алгоритмически неразрешимые проблемы

Математики в течение веков пользовались интуитивным понятием алгоритма (см. “Алгоритм”). В рамках подобного определения были сформулированы и успешно применялись на практике алгоритмы для решения таких задач, как выполнение арифметических действий “столбиком”, нахождение корней квадратных уравнений, решение систем линейных уравнений и т.д.

Постепенно они переходили к постановке и решению все более сложных задач. Так, Г.Лейбниц в XVII веке пытался построить общий алгоритм решения любых математических задач. В XX веке эта идея приобрела более конкретную форму: построить алгоритм проверки правильности любой теоремы при любой системе аксиом. Построить такие алгоритмы не удавалось, и математики выдвинули предположение: а вдруг для того или иного класса задач в принципе невозможно построить алгоритм решения? На основе этого предположения возникло понятие алгоритмически неразрешимой задачи — задачи, для которой невозможно построить процедуру решения.

Проблема останова

Одной из первых проблем, для которых была строго доказана алгоритмическая неразрешимость, была так называемая проблема останова. Сформулируем ее для программ, написанных на процедурных языках программирования (см. “Языки программирования”).

Зададимся следующим вопросом. Нельзя ли определить программным способом, с помощью самого компьютера, зациклится ли данная программа на определенных входных данных? Может быть, можно написать некоторую универсальную программу (обозначим ее через U), которая принимала бы на вход текст заданной программы и входные данные к ней, анализировала его и выдавала бы ответ, зациклится эта программа на этих входных данных или нет 1 . Возможность написания программы U кажется правдоподобной: ведь, например, программа-компилятор умеет анализировать текст заданной программы на наличие в нем возможных синтаксических ошибок и т.п. Программа U могла бы стать надстройкой над компилятором, которая вылавливала бы ошибку особого рода — ошибку “бесконечного цикла”.

Уточним формулировку задачи. Каждая программа П в каждом конкретном случае работает с входными данными. (Строго говоря, некоторые программы, например программа вычисления числа с точностью до 100 000 знаков, могут и ничего не получать на вход — в этом случае будем считать, что входные данные для такой программы образуют “пустой набор” — файл из нуля байт.) Можно считать, что эти входные данные берутся всегда из какого-то файла Д. Действительно, все входные данные — символы, вводимые с клавиатуры, файлы и даже движения мышки (здесь подразумевается, что нажатие определенных кнопок в интерфейсе программы — это тоже ввод данных в нее) — можно закодировать в одном общем файле данных. Может случиться, что некоторая программа, получая на вход одни данные, зацикливается, а получая другие — нет.

Работу программы U можно спроектировать следующим образом. Программа U должна получать на вход, во-первых, текст программы П (текстовый файл), а во-вторых, некоторый файл с данными Д (текстовый файл). Затем она должна проанализировать эти два файла и выдать точный ответ: зациклится ли программа П, если П получила на вход файл Д. Можно всегда считать, что программа U может воспринимать на вход любые файлы: например, если файл П не является синтаксически правильной программой на выбранном языке программирования (скажем, Паскале), то программа U это легко определяет, но все равно считает, что в этом случае П является “программой”: например, такой, которая “ничего не делает” и, следовательно, не зацикливается. Соответственно, если файл Д имеет “неправильный формат” (например, на вход программе П требуется число, а в файле Д имеется что-то другое), то программа П всегда останавливается на этих “неправильных данных”. Итак, вот более точное описание программы U:

а) программа U читает два произвольных файла: П и Д;

б) если файл П содержит синтаксически правильную программу (для определенности, на Паскале), а файл Д представляет собой корректные данные для программы П, то программа U проверяет, зациклится ли П на данных Д. Если она зациклится, то на экран компьютера будет выдано сообщение “зациклится”, иначе — “не зациклится”;

в) если файлы П и Д не удовлетворяют условиям б), то на экран выдается сообщение “не зациклится” (и в этой ситуации для простоты мы все равно называем П программой, а Д — данными, и П в этом случае не зацикливается на Д “по определению”).

Предположим, что нам удалось написать такую программу U. Можно считать, что она тоже написана на Паскале. Теперь мы собираемся написать новую программу, которую обозначим через U1. Но прежде мы введем специальное понятие — стандартный номер файла. Любой файл можно представить как слово, быть может, очень длинное.

Каждая “буква” этого слова берется из некоторого алфавита. Например, можно считать, что алфавит для таких слов состоит из 256 символов, а каждая буква в слове — это один байт в файле; в качестве “букв” здесь выступают все ASCII-символы — “настоящие буквы”, знаки препинания, пробел, специальные символы и т.д. Таким образом, все файлы могут быть расположены в некоторую упорядоченную бесконечную последовательность:

(Сначала идет пустой файл Ф0, в котором нет ни одного байта. Затем перечисляются в алфавитном порядке все файлы, состоящие из одной “буквы”, затем — состоящие из двух “букв”, и т.д.) В этой последовательности каждый файл получает некоторый номер. Этот номер мы и назовем стандартным номером файла. Ясно, что можно написать программу, которая по заданному файлу вычислит стандартный номер этого файла. (Мы считаем, что у нас есть “идеальный” компьютер. Он не имеет ограничений памяти и поэтому может работать с числами, состоящими из сколь угодно большого количества цифр.) Можно также написать программу, которая по заданному числу восстанавливает файл, стандартный номер которого равен n.

Итак, любой файл попадает в последовательность (*) и имеет в ней свой уникальный номер, который мы называем стандартным номером этого файла. Значит, и у любого файла с программой (П), и у любого файла данных (Д) есть свои стандартные номера.

Теперь можно написать программу U1, которая будет делать следующее:

1) получать на вход натуральное число i;

2) восстанавливать файл Фi из последовательности (*), т.е. восстанавливать файл со стандартным номером i;

3) запускать программу U, подавая ей на вход в качестве файла П файл Фi, а в качестве файла Д — тот же самый файл Фi.

Коротко работу программы U1 можно описать так: по заданному числу i она определяет, зациклится ли программа, реализованная в файле со стандартным номером i при работе с данными, записанными в файле, который имеет стандартный номер i (эта программа решает проблему самоприменимости).

Ясно, что программу U1 всегда можно написать так, чтобы она в самом конце работы некоторой переменной z присваивала значение 0 или 1, и в соответствии с этим значением выводила одно из двух сообщений:

if z = 0 then writeln(‘нe зациклится’)

else writein(‘зациклится’)

Теперь подвергнем программу U1 маленькой переделке. Фрагмент, приведенный выше, заменим на такой (**):

if z = 0 then

else writeln(‘зациклится’)

Эту программу (назовем ее U2) сохраним в другом файле. Что делает U2? Она тоже, как и U1, получает на вход число i, но отличается от U1 вот чем: если выяснилось, что исследуемая программа со стандартным номером i не зацикливается на файле данных со стандартным номером i, то сама U2 зацикливается, а в противном случае U2 выдает сообщение “зациклится” и после этого завершает работу.

Программа U2 сама тоже записана в файле. Этот файл обязательно находится в последовательности (*) и имеет некоторый стандартный номер. Пусть k — этот номер. Здесь начинается самое интересное. Что произойдет, если на вход программе U2 в качестве числа i мы подадим число k?

В этом случае, конечно, выполнение программы U2 может либо зациклиться, либо остановиться. Предположим, что оно остановится. Тогда, как только компьютер дойдет до выполнения фрагмента (**), переменная z должна получить нулевое значение. После этого, в соответствии с (**), произойдет зацикливание. Предположив, что выполнение остановится, мы выяснили, что выполнение зациклится!

Это невозможно. Теперь предположим, что выполнение зациклится. Но тогда программа U2, как говорилось выше, должна выдать сообщение “зациклится” и после этого остановиться. Это тоже невозможно.

Таким образом, программа должна зациклиться, если она остановится, и должна остановиться, если она зациклится. В чем тут дело? Конечно же в том, что мы предполагали возможность написания универсальной программы U, которая определяла бы любую программу на возможность зацикливания. Итак, такой программы U не существует в принципе, или, как говорят математики, проблема останова алгоритмически неразрешима.

Неразрешимость проблемы останова впервые была доказана Аланом Тьюрингом в его работе, опубликованной в 1936 г. Конечно, тогда не было никаких компьютеров и тем более языков программирования, да и сам Тьюринг в той работе даже не пользовался термином “программа”. Но его изложение, по сути, мало чем отличалось от нашего. Мы использовали язык Pascal и говорили о привычных нам компьютерах, однако ясно, что эти подробности (о файлах, о конкретном языке программирования) были совсем не важны: существо наших рассуждений было чисто логическим.

Другие алгоритмически неразрешимые задачи

Упомянутая в начале статьи проблема проверки правильности любых математических утверждений также оказалась алгоритмически неразрешимой. Сформулируем ее формально в более общем виде.

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

Проблему распознавания выводимости можно сформулировать следующим образом: Существует ли для любых двух слов R и S дедуктивная цепочка, ведущая от R к S? Решение понимается в смысле существования алгоритма, дающего ответ на этот вопрос для любых слов R и S. В 1936 г. американский математик Черч доказал теорему о том, что проблема распознавания выводимости алгоритмически неразрешима. Тем самым выяснилась причина безуспешности всех прошлых попыток решения задачи, поставленной Лейбницем.

Неразрешимой оказалась и так называемая “10-я проблема Гильберта”. В упрощенной формулировке она звучит так: требуется выработать алгоритм, позволяющий для любого алгебраического уравнения P(x1, x2, …, xn) = 0, где P — многочлен с целыми коэффициентами, выяснить, имеет ли оно целочисленное решение. В 1970 г. советский математик Ю.В. Матиясевич доказал невозможность построения алгоритма для решения этой задачи. Интересно, что если для конкретного уравнения известно, что решение в целых числах есть, то алгоритм отыскания этого решения существует.

Какие методы используются для доказательства алгоритмической неразрешимости? Обычно неразрешимость новых задач доказывается методом сведения к этим задачам известных алгоритмически неразрешимых задач. Тем самым доказывается, что если бы была разрешима новая задача, то можно было бы решить и заведомо неразрешимую задачу. Применяя метод сведения, обычно ссылаются на искусственные задачи, которые не представляют самостоятельного интереса, но для которых легко непосредственно доказать их неразрешимость, например, описанную выше проблему самоприменимости.

Методические рекомендации

Данная тема включена в стандарт профильного курса информатики в следующей формулировке: диагональное доказательство несуществования. Здесь имеется в виду канторовский диагональный процесс, который можно использовать для доказательства алгоритмической неразрешимости, в частности, проблемы останова. Именно поэтому в качестве основного материала статьи приведено такое доказательство этой проблемы, которое легко сводится к рассуждениям Кантора. Следует лишь описать канторовские массив-таблицу Т и массив-строку D.

В проблеме останова T[i,j] — крестик, если программа, реализованная в файле со стандартным номером i, зацикливается на данных, расположенных в файле со стандартным номером j, иначе — нолик. Значения T[i,j] для любых заданных i и j могла бы вычислять, после небольших модификаций, программа U (если бы, конечно, она существовала).

Значение D[i] — нолик, если программа, реализованная в файле со стандартным номером i, зацикливается на данных, расположенных в файле со стандартным номером i, иначе — крестик. Значения D[i] можно было бы вычислять, используя программу U1. Тогда D[i] не равно Т[i,i] для всех индексов i и D не совпадает ни с одной строкой таблицы Т. А если бы программа U1 существовала, то она имела бы свой номер и ей соответствовала бы одна из строк таблицы T.

Подробнее о канторовском диагональном процессе и соответствующем доказательстве проблемы останова можно прочитать в уже упомянутой статье И.Долмачева “Алан Тьюринг”, которую также можно найти на сайте газеты “Информатика” (в архивных материалах № 5/2000). Два других доказательства алгоритмической неразрешимости данной проблемы можно прочитать в учебнике Е.В. Андреевой, Л.Л.

Босовой, И.Н. Фалиной “Математические основы информатики” (М.: БИНОМ. Лаборатория Знаний, 2005) и в методическом пособии к этому учебнику (М.: БИНОМ. Лаборатория Знаний, 2006). Выбор доказательства остается на усмотрение учителя.

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

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

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

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

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

1 При доказательстве алгоритмической неразрешимости этой проблемы использованы материалы статьи Ивана Долмачева “Алан Тьюринг”, “Информатика” № 5/2000.

Источник: xn—-7sbbfb7a7aej.xn--p1ai

8.5 Алгоритмически неразрешимые проблемы.

Далеко не все задачи решаются алгоритмически или, как принято говорить в математике, конструктивно.

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

Поскольку каждая машина однозначно задается своей программой, а программу можно записать как последова­тельность команд — строку конечной длины в конечном алфави­те то имеем счетное количество строк, т. е. множество всех ма­шин Тьюринга счетно. В то же время множество всех функций натуральных аргументов, дающих в качестве результата натуральные числа — несчетно!

Следовательно, существуют функции, не вычисляемые никакой машиной Тьюринга. Такие функции называются невычислимыми. Если теперь сказать, что вычисление функции — это решение зада­чи, а программа машины Тьюринга — алгоритм, то мы делаем вы­вод о существовании алгоритмически неразрешимых задач.

В теории алгоритмов известно много таких задач. Перечис­лим наиболее важные из них.

1. Проблема остановки. При обсуждении машин Тьюринга было сказано, что на некоторых исходных данных машина может не останавливаться, т. е. не давать результата. Любая ма­шина Тьюринга может быть представлена некоторым кодом (номером), отличающимся от всех других. Например, каждое состояние можно закодировать числом, символы движения за­ кодировать различными числами.

Тогда каждая команда пред­ ставляет собой строку чисел, которую можно интерпретировать как одно большое число, а последовательность всех команд — как еще большее число N. Эта или какая-либо другая процедура устанавливает однозначное соответствие между множеством натуральных чисел и множеством алгоритмов. Функция  : Natur —> Algorithmus, называется нумерацией алгоритмов, а ее аргу­мент N — номером алгоритма при нумерации . Функция  по номеру N восстанавливает описание алгоритма,  (N) = а. Об­ратная функция по описанию алгоритма определяет его номер. Введение нумераций позволяет работать с алгоритмами как с натуральными числами, что особенно удобно при исследовании алгоритмов над алгоритмами: алгоритм, закодированный чис­лом, может рассматриваться как входные данные другого алго­ритма. Проблема остановки состоит в построении машины Тью­ринга М, которая получая на входе код (номер) N произвольной машины Т и входные данные этой машины X, определяет, оста­новится ли машина Т на данных X. Иначе говоря,

M(N,X) = 1, если Т останавливается на X,

M(N,X) = О, если Т не останавливается на X.

Доказано, что машину М построить нельзя, т. е. проблема остановки алгоритмически неразрешима.

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

Проблема эквивалентности состоит в построении машины Тьюринга, получающей на входе описания (коды) двух машин Т1 и Т2 и определяющей, эквивалентны ли Т1 и Т2. С практической точки зрения можно поста­вить аналогичный вопрос: можно ли написать программу, кото­рая по текстам двух программ на Паскале определяет, закончатся ли они одинаковыми результатами.

Ответ отрицательный — проблема эквивалентно­сти алгоритмически неразрешима. Это не означает, что для двух конкретных программ нельзя выяснить, эквивалент­ны ли они. Просто не существует общего метода. Для каждой пары программ придется применять собственные методы, завися­щие от существа этих программ.

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

Тривиальный пример: к тексту алгоритма, вычисляющего функ­цию, припишем текст тождественного алгоритма (результат ко­торого всегда равен его входным данным); новый алгоритм пред­ставляет ту же самую функцию; теперь припишем текст тождест­венного алгоритма еще раз, затем еще раз; получим бесконечную последовательность различающихся алгоритмов, представляю­щих одну функцию. Подобные факты и порождают множество проблем в теории алгоритмов, связанных с разрешимостью. Су­ществует даже теорема Раиса, утверждающая, что «никакое не­тривиальное свойство вычислимых функций не является алгорит­мически разрешимым».

Тривиальное свойство означает принадлежность функции либо множеству всех функций, либо пустому множеству. Нетри­виальное свойство — «функция f принадлежит классу C», где С — такой непустой класс, что существуют функции, не принад­лежащие ему. Нумерация всех алгоритмов является одновремен­но и нумерацией всех вычислимых функций: функции можно приписать номер одного из вычисляющих ее алгоритмов. Теперь теорему Раиса можно сформулировать иначе: «Не существует алгоритма, который по номеру функции f определял бы, принадле­жит эта функция заданному классу С или нет».

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

Источник: studfile.net