Cтраница 1
Интуитивное понятие алгоритма Рввнообъемно с точным понятием алгоритма Поста. [1]
Анализируя интуитивное понятие алгоритма, мы замечаем еще одну особенность. Предполагается, что исполнитель правила всегда знает, как его выполнять. Говорят, что алгоритм понятен для исполнителя. В первых книгах по теории алгоритмов говорится даже об их общепонятности. [2]
Одна из причин расплывчатости интуитивного понятия алгоритма состоит в том, что объектом алгоритма может оказаться все, что угодно. [3]
В этом случае достаточно и интуитивного понятия алгоритма, чтобы удостовериться в том, что описанный процесс есть алгоритм. Доказать несуществование алгоритма таким путем невозможно. Для этого надо точно знать, что такое алгоритм. [4]
Математики долго пользовались такими описаниями алгоритмов и довольствовались интуитивным понятием алгоритма. В этих рамках формулировались и успешно применялись на практике различные вычислительные алгоритмы. Например, были получены алгоритмы поиска корней квадратных и кубических уравнений. [5]
Черча тезиса, утверждающего, что понятие общерекурсивной функции является уточнением интуитивного понятия алгоритма. Из других эквивалентных уточнений понятия алгоритма наибольшее распространение получили понятия Тьюринга машины и нормального алгорифма Маркова. По существу вся математика связана с теми или иными алгоритмами. [6]
Тем не менее при переходе от алгоритмов к вычислимым функциям возникает одно очень существенное Обстоятельство: совокупность процессов, подпадающих под интуитивное понятие алгоритма, очень обширна и мало обозрима. Совокупность вычислимых функций для самых разных пониманий процессов оказалась одной и той же и притом легко описываемой в обычных математических терминах. [7]
В этом случае достаточно и интуитивного понятия алгоритма, чтобы удостовериться в том, что описанный процесс решения задачи есть алгоритм. [8]
Тему Алгоритм и его свойства традиционно считают главной темой теоретической информатики, вводящей в обширные практические разделы алгоритмизации различные процедурные языки программирования, а также методы программирования. Нельзя не отметить, что в данном случае рассматривается интуитивное понятие алгоритма, а также интуитивно ясные его свойства. Данное обстоятельство приводит к тому, что у разных авторов определения алгоритма несколько различаются, также различаются и наборы свойств алгоритмов. Важно не становиться в данном случае на догматические позиции. [9]
Интерес к точному определению понятия алгоритма возник в среде логиков в 1930 - х годах, и было предложено несколько формулировок. Эти различные формулировки оказались эквивалентными, что обычно воспринимается как подтверждение так называемого тезиса Черча ( или принципа нормализации Маркова), выражающего веру в то, что интуитивное понятие алгоритма точно отражается в этих эквивалентных определениях. Работая с точным определением, оказалось возможным понять идею построения проблемы разрешения, не допускающей возможности алгоритмического решения; примеры таких проблем вскоре были найдены в математической логике. Чтобы обнаружить такие проблемы в теории групп, потребовалось много дополнительных усилий, но в конце концов оказалось, что для общих проблем разрешения, включающих в свою формулировку представления групп, существование таких примеров является скорее правилом, чем исключением. [10]
Уже на самых ранних ступенях развития математики в ней стали возникать различные вычислительные процессы чисто механического характера; с их помощью искомые величины ряда задач вычислялись последовательно из данных исходных величин по определенным правилам и инструкциям. До тех пор пока перед математиками стояла проблема доказательства существования того или иного алгоритма, а это можно сделать путем фактического описания процесса, решающего задачу, то интуитивного понятия алгоритма было достаточно, чтобы удостовериться, что описанный процесс есть алгоритм. [11]