Сравнение алгоритмов вычеслением НОД двух чисел

Наибольший общий делитель двух целых чисел (алгоритм Евклида).

Наибольшим общим делителем (НОД) двух целых чисел называется такое наибольшее по модулю число, которое делит эти два числа. По определению НОД(0,0)=0.

Данный алгоритм вычисления НОД двух целых чисел a и b состоит в следующем: если хотя бы одно из чисел равно нулю, то НОД(a,b)=|a+b|, в других случаях последовательно находятся остатки ri от делений:

aна b-a=bq1+r1, bна r1-b=r1q2+r2, r1 на r2-r1=r2q3+r3,......

и т.д., пока rn+1 не станет равно нулю. Тогда НОД(a,b)=НОД(b,r1)=НОД(r1,r2)=...=НОД(rn-1,rn)=rn. Наверх

Наибольший общий делитель двух целых чисел (бинарный алгоритм Евклида).

Данный алгоритм вычисления НОД(a,b) основан на бинарном алгоритме Евклида. Вычисления проводятся на основании следующих свойств НОД:

НОД(2m,2n)=2 НОД(m,n), НОД(2m,2n+1)= НОД(m,2n+1), НОД(-m,n)= НОД(m,n).

Наверх

Наибольший общий делитель двух целых чисел (расширенный алгоритм Евклида).

Алгоритм, кроме поиска НОД двух целых чисел a,b также находит величины x,y, т.ч. ax+by=НОД(a,b). Алгоритм включает в себя алгоритм Евклида и похож на алгоритм решения диофантового уравнения, который рассматривается здесь. Привожу его поскольку часто возникает необходимость отыскать именно x,y удовлетворяющие приведенному выше условию.

Машина Поста

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис: где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).

Всего для машины Поста существует шесть типов команд:

Машина Тьюринга

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

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

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

Алгоритм как преобразование слов.Связь понятия алгоритма с понятием функции