Причина, по которой машины Тьюринга важны при описании структур данных и алгоритмов, заключается в том, что они предоставляют математическую модель, в которой мы можем описать, что такое алгоритм. В большинстве случаев алгоритмы описываются с использованием языка высокого уровня или псевдокода. Например, я мог бы описать алгоритм поиска максимального значения в массиве следующим образом:
Set max = -infinity
For each element in the array:
If that element is greater than max:
Set max equal to that element.
Из этого описания легко увидеть, как работает алгоритм, и легко перевести его в исходный код. Однако предположим, что я написал это описание:
Guess the index at which the maximum element occurs.
Output the element at that position.
Это действующий алгоритм? То есть можем ли мы сказать «угадать индекс» и точно определить, что он означает? Если мы допустим это, сколько времени это займет? Если мы этого не допустим, то почему? Чем отличается первое описание от второго?
Чтобы иметь математически строгое определение алгоритма, нам нужна некоторая формальная модель того, как работает компьютер, и что он может и что не может делать. Машина Тьюринга - один из распространенных способов формального определения вычислений, хотя есть и другие, которые также можно использовать (регистрация машин, системы переписывания строк, лямбда-исчисление Черча и т. д.). С помощью математической модели вычислений мы можем начать говорить о том, какие типы алгоритмических описаний допустимы, а именно о тех, которые могут быть реализованы с использованием нашей модели вычислений.
Многие современные алгоритмы критически зависят от свойств базовой модели вычислений. Например, алгоритмы без учета кеширования предполагают, что модель вычислений имеет некоторый буфер памяти неизвестный размер и двухуровневая память. Некоторые алгоритмы требуют, чтобы базовая машина была трансдихотомической, что означает, что размер машинного слова должен быть равен наименьший достаточно большой, чтобы вместить размер любой проблемы. Рандомизированные алгоритмы требуют формального определения случайности и того, как машина может использовать случайные значения. Недетерминированные алгоритмы требуют средств определения недетерминированных вычислений. Алгоритмы, основанные на схемах, должны знать, какие примитивы схемы являются, а какие недопустимы. Квантовые компьютеры нуждаются в формальном определении того, какие операции разрешены, а какие не разрешены, а также в том, что определение алгоритма дает вероятностный результат. Распределенным алгоритмам требуется формальное определение взаимодействия между машинами.
Короче говоря, при описании алгоритма важно четко указывать, что разрешено, а что нельзя. Однако, чтобы быть хорошим программистом или хорошо разбираться в алгоритмах, вам не обязательно знать машины Тьюринга как внутри, так и снаружи, а также не нужно знать конкретные детали того, как вы будете кодировать определенные проблемы с их помощью. . Однако вам следует знать, что модель вычислений может и чего не может делать, и какова стоимость одной операции. Таким образом, вы можете понять, насколько эффективны алгоритмы, сколько различных ресурсов (время, пространство, память, связь, случайность, недетерминизм и т. Д.) Они используют. Но при этом не паникуйте, если вы не понимаете лежащую в основе модель.
Есть еще одна причина подумать о базовой модели вычислений - обсудить ее ограничения. Каждая модель вычислений имеет свои пределы, и в некоторых случаях вы можете доказать, что определенные алгоритмы не могут существовать для определенных проблем или что любой алгоритм, который решал бы некоторую проблему, обязательно должен использовать некоторое количество данного ресурса. Самый распространенный пример, когда это возникает при разработке алгоритмов с понятием NP-жесткости. Некоторые проблемы считаются чрезвычайно "трудными" для решения, но формальные определения того, что это за трудность, основаны на знании машин Тьюринга и недетерминированных машин Тьюринга. Понимание модели полезно в этом случае, потому что это позволяет вам рассуждать о вычислительной выполнимости определенных проблем.
Надеюсь это поможет!
person
templatetypedef
schedule
20.08.2011
