Что такое алгоритм

Исходная версия статьи (Ворожцов А. В., «Что такое алгоритм?») была опубликована в журнале «Потенциал»

Вступление

Геометрия развивает геометрическое мышление, математика — абстрактное математическое, логика — логическое, физика — физическое… А какое мышление развивает информатика? Информатика есть наука, служащая информационным технологиям. Но фундаментальными достижениями этой науки оказались не сами технологии, а общие методы построения систем и решения сложных задач. Базисом этих методов являются алгоритмы и системный подход к решению задач. Поэтому информатика развивает алгоритмическое мышление и учит системному подходу к решению задач.

Сегодня мы познакомимся с понятиями алгоритма и исполнителя. Оказывается, не так-то просто понять, чем определяется сущность алгоритма.

Понятие алгоритма

Понятие алгоритма — одно из основных в программировании и информатике^[1]. Это последовательность команд, предназначенная исполнителю, в результате выполнения которой он должен решить поставленную задачу. Алгоритм должен описываться на формальном языке, исключающем неоднозначность толкования. Исполнитель может быть человеком или машиной. Исполнитель должен уметь выполнять все команды, составляющие алгоритм. Множество возможных команд конечно и изначально строго задано. Действия, выполняемые по этим командам, называются элементарными.

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

Приведём для примера простой алгоритм действия пешехода, который позволит ему безопасно перейти улицу:

1. Подойти к дороге.
2. Дождаться зелёного сигнала светофора.
3. Перейти дорогу.
4. Если впереди есть ещё одна дорога, то перейти к шагу 1.

Алгоритмы обладают свойством детерминированности (определённости): каждый шаг и переход от шага к шагу должны быть точно определены так, чтобы его мог выполнить любой другой человек или механическое устройство.

Кроме детерминированности, алгоритмы также должны обладать свойством конечности и массовости:

Конечность

Алгоритм всегда должен заканчиваться за конечное число шагов, но это число не ограничено сверху.

Массовость

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

Поясним эти свойства на простом примере. Рассмотрим следующую формулу вычисления числа $\pi$: $\pi =4\left(1-{\frac {1}{3}}+{\frac {1}{5}}-{\frac {1}{7}}+\dots \right)=4\sum _{i=0}^{\infty }{\frac {(-1)^{i}}{2i+1}}$.

Является ли эта формула алгоритмом вычисления числа $\pi$? Ответ на этот вопрос — «нет», так как здесь нет ни свойства массовости (нет входных данных), ни свойства конечности (сумма бесконечного количества чисел)^[2].

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

Понятие элементарных объектов и элементарных действий

Алгоритмы по определению должны сводиться к последовательности элементарных действий над элементарными объектами. Какие действия и объекты элементарны, а какие — нет, зависит от исполнителя (вычислительной машины). Набор элементарных действий и элементарных объектов для каждого исполнителя чётко зафиксирован. Элементарные действия оперируют с небольшим числом элементарных объектов. Все остальные объекты и действия являются совокупностью элементарных. В современных компьютерах рациональные числа и иррациональные числа не являются элементарными объектами^[3]. Элементарным объектом в современных компьютерах является бит — это ячейка памяти, в которую может быть записано число 0 или 1. С помощью набора бит можно записывать целые и действительные числа. В частности, существует простой способ представить целые числа от $0$ до $2^{8}-1=255$ в виде последовательности 8 бит:

0	→ 00000000
1	→ 00000001
2	→ 00000010
3	→ 00000011
4	→ 00000100
5	→ 00000101
…	→ …
250	→ 11111010
251	→ 11111011
252	→ 11111100
253	→ 11111101
254	→ 11111110
255	→ 11111111

Указанный способ представления натуральных чисел в виде последовательности нулей и единиц называется двоичной записью числа. Каждому биту в этом представлении соответствует степень двойки. Самому правому биту соответствует $1=2^{0}$, второму справа — $2=2^{1}$, третьему справа — $4=2^{2}$, и так далее. Двоичная запись соответствует разложению числа в сумму неповторяющихся степеней двойки. Например:

3 →	11 →	$1\cdot 2^{1}+1\cdot 2^{0}$	$=2+1$
5 →	101 →	$1\cdot 2^{2}+0\cdot 2^{1}+1\cdot 2^{0}$	$=4+0+1$
7 →	111 →	$1\cdot 2^{2}+1\cdot 2^{1}+1\cdot 2^{0}$	$=4+2+1$
31 →	11111 →	$1\cdot 2^{4}+1\cdot 2^{3}+1\cdot 2^{2}+1\cdot 2^{1}+1\cdot 2^{0}$	$=16+8+4+2+1$
32 →	100000 →	$1\cdot 2^{5}+0\cdot 2^{4}+0\cdot 2^{3}+0\cdot 2^{2}+0\cdot 2^{1}+0\cdot 2^{0}$	$=32+0+\ldots +0$

Задача 1

Докажите, что каждое натуральное число единственным образом представляется в виде суммы неповторяющихся степеней двойки. Подсказка: для данного числа $n$ найдите максимальную степень двойки $2^{m}$, которая меньше $n$. Рассмотрите число $n'=n-2^{m}$. Воспользуйтесь методом математической индукции.

Конечный набор элементарных объектов может принимать лишь конечное число значений. Так, например, упорядоченный набор 8 бит (один байт) имеет 256 возможных значений. Из этого простого факта следует очень важное утверждение: среди команд исполнителя не может быть команд сложения или умножения произвольных натуральных (действительных) чисел.

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

Итак, для компьютеров лишь некоторые действительные числа являются элементарными объектами^[4]Множество этих чисел конечно. Какие именно действительные числа элементарны, зависит от используемого машинного представления. Многие современные процессоры поддерживают несколько типов машинного представления действительных чисел. Целые числа практически везде представляются одинаковым образом. В процессорах с 32-битной архитектурой большая часть команд связана с числами, записанными в 32 битах. При представлении неотрицательных чисел в 32 бита помещается просто двоичная запись. Множество представимых таким образом чисел — это все неотрицательные числа меньше $2^{32}$. Этому машинному представлению в языке Си соответствует тип данных unsigned int. Если мы попытаемся сложить с помощью команды процессора два числа типа unsigned int, сумма которых больше либо равна $2^{32}$, то возникнет переполнение — старший 33-й бит результата будет утерян.

При представлении отрицательных чисел в виде 32 бит один бит необходимо выделить под знак — «плюс» или «минус». Неотрицательные числа, меньшие $2^{31}$, записываются обычным образом в виде двоичной записи. Старший бит у них равен нулю. Отрицательное число $-a$, модуль $a$ которого меньше либо равен $2^{31}$, записывается в 32 битах как двоичная запись числа $2^{32}-a$. Старший бит для отрицательных чисел равен 1. Этому машинному представлению соответствует тип int. Представимые таким образом числа — это числа на отрезке $[-2^{31},\;2^{31}-1]$.

Подведём итоги:

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

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

В компьютерах элементарным объектом является бит. Есть несколько стандартных способов записи чисел (действительных, целых, и целых неотрицательных) в виде последовательности бит фиксированной длины.

Алгоритм входным данным сопоставляет выходные данные и этим он чем-то похож на обыкновенную функцию. Но главной особенностью алгоритма является то, что он содержит описание того, как это сделать. Функция может быть задана неявно, а алгоритм — нет. Алгоритм описывает, что нужно сделать с входными данными, чтобы получить результат. При этом предполагается, что инструкции алгоритма выполняет исполнитель с ограниченными способностями: собственная память исполнителя конечна, также конечен и чётко зафиксирован набор инструкций, которые он может исполнять. В большинстве классических исполнителей присутствует внешняя память, которая в принципе не ограничена. Например у человека под рукой есть сколь угодно много листов бумаги, уложенных в бесконечный ряд (ячеек памяти), которые он может использовать. Заметьте, что информация о том, что на каком листке записано в какой-то момент может не поместиться в конечную память исполнителя и эту информацию ему также нужно будет записывать на листах.

Способы записи алгоритмов

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

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

Разницу между программой и алгоритмом можно пояснить следующим образом. Алгоритм — это метод, схема решения какой-то задачи. А программа — это конкретная реализация алгоритма, которая может быть скомпилирована и выполнена на компьютере. Алгоритм, в свою очередь, является реализацией идеи решения. Это можно проиллюстрировать следующей схемой:

Идея решения → Алгоритм → Программа

Стрелка означает переход к следующему этапу решения задачи с повышением уровня подробности описания метода решения.

Алгоритм Евклида

Описание алгоритма:

1. Если $a=b$, то НОД (наибольший общий делитель) $=a=b$ и заканчиваем вычисления.
2. Если $a>b$, то из $a$ вычитаем $b$ ($a\gets a-b$). Переходим к 1.
3. Если же $b>a$, то из $b$ вычитаем $a$ ($b\gets b-a$). Переходим к 1.

Запишем этот алгоритм с помощью псевдокода.

Псевдокод 1. Алгоритм Евклида

 1 Function НОД(a, b)
 2   While $a\neq b$
 3     If $a>b$
 4       $a\gets a-b$
 5     Else
 6       $b\gets b-a$
 7     End If
 8   End While
 9   Return a
10 End Function

Конструкция While(A) B End While псевдокода означает «повторять последовательность операций B, записанных в теле оператора While, пока выполнено условие A». Тело оператора While — это все инструкции между While(A) и End While. Если условие A не выполнено в самом начале, то тело оператора While не выполняется ни разу. Один шаг выполнения тела цикла называется итерацией цикла.

Конструкция If(A) B Else C End If» псевдокода означает «если верно A, то выполнить инструкции B, иначе выполнить инструкции C».

Инструкция return a означает «вернуть как результат вычислений объект a».

Покажем, что наш алгоритм нахождения НОДа чисел $a$ и $b$.

Действительно, НОД$(a,\;b)=\;$НОД$(a-b,\;b)$ при $a>b$, поэтому, несмотря на то, что на каждом шаге меняется одно из чисел, значение НОД$(a,\;b)$ остаётся неизменным. Максимальное из чисел $a$ и $b$ с каждым шагом уменьшается, и в какой-то момент они становятся равны друг другу и равны искомому значениюЗадача 2

Докажите, что НОД$(a,\;b)=\;$НОД$(a-b,\;b)$ для любых неотрицательных целых $a$ и $b$, таких что $a>b$.

Задача 3

Усовершенствуйте вышеприведённый алгоритм, используя то, что НОД$(a,\;b)=\;$НОД$(a\;{\bmod {\;}}b,b)$ при положительных $a$ и $b$ (выражение $a\;{\bmod {\;}}b$ означает остаток при делении $a$ на $b$).

Алгоритм вычисления чисел Фибоначчи

В математике для описания функций часто используются рекуррентные соотношения, в которых значение функции определяется через её значение при других (обычно меньших) аргументах. Наиболее известным примером является последовательность Фибоначчи 1, 1, 2, 3, 5, 8, 13, …, определяемая следующими соотношениями:

$F_{1}=1,\quad F_{2}=1,\quad F_{n}=F_{n-1}+F_{n-2}$.

Используя это рекуррентное соотношение, можно построить рекурсивный алгоритм вычисления чисел Фибоначчи:

Псевдокод 2. Числа Фибоначчи

1 Function Fibo(n)
2   If n = 1 Or n = 2
3     Return 1
4   End If
5   Return Fibo(n - 1) + Fibo(n - 2)
6 End Function

При анализе рекурсивной функции обычно возникает два вопроса: почему функция работает правильно и почему она завершает работу? Ответ на первый вопрос обычно прост, — если рекуррентные отношения правильны и интерпретатор (компилятор) сработал правильно, то единственное значение, которое может вернуть программа, — правильное. Но есть ещё другая альтернатива — программа может не закончить свою работу^[5].

Наибольший интерес в этом алгоритме представляет строчка 5:

Return Fibo(n - 1) + Fibo(n - 2)

Она означает следующее: «Запустить процесс вычисления Fibo(n - 1), затем запустить процесс вычисления Fibo(n - 2), результаты вычислений сложить и вернуть в качестве результата». Можно считать что в этой строчке исполнитель нашего алгоритма просит другого исполнителя вычислить Fibo(n - 1), а сам ждёт, когда тот закончит вычисления. Узнаёт у него результат, просит вычислить Fibo(n - 2) и снова ждёт результата. Два полученных результата складывает, возвращает значение суммы как результат и заканчивает работу. Интерес заключается в том, что этот дополнительный исполнитель действует по такому же алгоритму — если его аргумент больше 1, он также вызывает очередного исполнителя для вычисления нужных ему значений. Получается серия вызовов, которые выстраиваются в дерево рекурсивных вызовов.

Рис. 1. Дерево рекурсивных вызовов для $F_{6}$.

На рисунке 1 изображено дерево рекурсивных вызовов, возникающее при вычислении $F_{6}$. Это дерево демонстрирует как функция сама себя использует при вычислении. Например, при вычислении $F_{6}$ были вызваны функции вычисления $F_{5}$ и $F_{4}$. Для вычисления $F_{5}$ понадобились $F_{4}$ и $F_{3}$, и так далее.

Для того, чтобы рекурсивный алгоритм заканчивал свою работу, необходимо, чтобы дерево рекурсивных вызовов при любых входных данных обрывалось и было конечным. В данном примере дерево рекурсивных вызовов обрывается на $F_{1}$ и $F_{2}$, для вычисления которых не используются рекурсивные вызовы.

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

Задача 4

Сколько раз вызывались вычисления $F_{2}$ и $F_{1}$ при вычислении $F_{6}$? Нарисуйте дерево рекурсивных вызовов для $F_{7}$ и определите, сколько раз будут вызваны $F_{1}$ и $F_{2}$. Найдите общую формулу для числа вызовов $F_{1}$ и $F_{2}$ при вычислении $F_{n}$.

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

Для вычисления Fibo(n) нам потребуется вызвать Fibo(n - 1) и Fibo(n - 2), поэтому $T(n)\geq T(n-1)+T(n-2)$. Используя это соотношение и то, что $T(1)=T(2)>1$, можно по индукции доказать, что $T(n)\geq F_{n}$. Но числа Фибоначчи возрастают достаточно быстро ($F_{50}=20365011074$). Поэтому даже на мощном компьютере с помощью этого алгоритма нам не удастся вычислить больше, чем первые несколько десятков членов последовательности Фибоначчи. Вы, наверное, уже догадываетесь, в чём здесь проблема. В нашей программе очень много избыточных вызовов — в дереве рекурсивных вызовов много повторений. Например Fibo(n - 2) будет вызвана два раза: сначала из Fibo(n), а потом из Fibo(n - 1), и оба раза будут проводится одни и те же вычисления. Простой «человеческий» алгоритм вычисления чисел Фибоначчи работает существенно быстрее: нужно помнить последние два числа Фибоначчи, вычислять следующее число и повторять этот шаг нужное число раз. Приведём его описание на псевдокоде (см. псевдокод 3).

Алгоритм 3 для вычисления $F_{n}$ выполнит $n-2$ итераций цикла While. Видно, что время работы алгоритма растёт линейно с $n$ (увеличение $n$ в $k$ раз приведёт к тому, что время работы алгоритма тоже увеличится примерно в $k$ раз).

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

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

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

Псевдокод 3. Числа Фибоначчи: нерекурсивный алгоритм

 1 Function FiboNR(n)
 2   If $n<3$ Then
 3     Return 1
 4   Else
 5     $b\gets 1$         \\ Предпоследнее вычисленное число Фибоначчи
 6     $a\gets 1$         \\ Последнее вычисленное число Фибоначчи
 7     For $i\in 3\ldots n$
 8       $c\gets a+b$    \\ Вычисляем следующее число Фибоначчи
 9       $b\gets a$       \\ Старое последнее число стало предпоследним
10       $a\gets c$       \\ Новое вычисленное число стало последним
11     End For
12     Return c
13   End If
14 End Function

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

Задача «Ханойские башни»

Рассмотрим ещё один классический пример на рекурсивные алгоритмы — игру «Ханойские башни», придуманную ещё в 1883 году Эдуардом Люка. Есть три стержня и 64 кольца́, нанизанных на них. В начале все ко́льца находятся на первом стержне, причём все ко́льца разного диаметра, и меньшие ко́льца лежат на бо́льших. За ход разрешается взять верхнее кольцо с любого стержня и положить на другой стержень сверху, при этом запрещается класть большее кольцо на меньшее. Цель игры состоит в том, чтобы переместить всю пирамиду с первого стержня на второй.

Заметим, что для того, чтобы переместить пирамиду, нам надо будет переместить и самое нижнее большое кольцо. Для этого нам нужно будет, чтобы все остальные ко́льца были на третьем штыре. Значит, чтобы переместить $N$ колец, нам сначала нужно переместить столбик из верхних $N-1$ колец на третий стержень, затем переместить самое большое кольцо с первого на второй и, наконец, переместить столбик из $N-1$ колец с третьего стержня на второй.

Псевдокод 4. Ханойские башни

1 Function Move(n, x, y)
2   If n = 1 Then
3     передвинуть кольцо с стержня x на стержень y
4   End If
5   Move(n - 1, x        , 6 - x - y)
6   Move(1    , x        , y        )
7   Move(n - 1, 6 - x - y, y        )
8 End Function

Итак, мы опять получили рекурсивный алгоритм: для того, чтобы решить задачу для пирамиды из $N$ колец, достаточно решить её для пирамиды из $N-1$ колец. Посчитаем теперь количество действий, необходимое для проведения всей операции. Пусть $f(N)$ — необходимое число действий, для переноса пирамиды из $n$ колец. Для одного кольца ответ равен единице: $f(1)=1$, для $N$ ответ будет $f(N)=f(N-1)+1+f(N-1)=2f(N-1)+1$. Решая это рекуррентное соотношение, получаем: $f(N)=2^{N}-1$. А значит, $f(64)>1\;000\;000\;000\;000\;000\;000.$ Таким образом, время, необходимое для перемещения пирамидки из 64 колец, очень велико.

Алгоритм 4, записанный на псевдокоде, реализует рекурсивную идею перемещения колец в игре «Ханойские башни». Функция MOVE(n, x, y) перемещает n колец со стержня с номером x на стержень с номером y.

Задачу «Xанойские башни» можно значительно усложнить.

Задача

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

Примеры простых алгоритмических задач

Здесь мы сформулируем несколько простых алгоритмических задач, которые полезно прорешать, чтобы освоится с понятием алгоритма.

Задача 5

Сколько раз в рекурсивном алгоритме вычисления Fibo(10) будет вызвана процедура вычисления Fibo(1)?

Задача 6

Сколько раз в рекурсивном алгоритме вычисления Fibo(n) будет вызвана процедура вычисления Fibo(m)?

Задача 7

Продолжите ряд $F_{n}$ на отрицательные значения n. Измените рекурсивный алгоритм вычисления Fibo так, чтобы он работал и при отрицательных n.

Задача 8

Разработайте алгоритм вычисления числа $F_{1000}$ и реализуйте его в виде программы на языке Паскаль, Си или любом другом языке программирования. Сколько цифр в десятичной записи этого числа?

Задача 9

Напишите рекурсивный алгоритм вычисления $n!=1\cdot 2\cdot \dots \cdot n$ на псевдокоде.

Задача 10

Используя соотношение НОД$(a,\;b)=\;$НОД$(a\;{\bmod {\;}}b,b)$, напишите рекурсивный алгоритм, вычисляющий НОД двух чисел $a$ и $b$.

Задача 11

Напишите алгоритм, который получает на вход чило $n$ и выводит слово «Простое», если это число простое (делится только на себя и на единицу), а иначе — слово «Составное». Попробуйте написать алгоритм, время работы которого ограничено функцией $C{\sqrt {n}}$, где $C$ — некоторая константа.

Задача 12

Дана рекуррентная последовательность $a_{n}=2\cdot a_{n-1}-a_{n-2}+1$, $a_{0}=a_{1}=1$. Напишите рекурсивный и нерекурсивный алгоритмы вычисления $n$-го элемента этой последовательности. Найдите явную формулу члена этой последовательности (рассмотрите последовательность разностей соседних элементов).

Задача 13

Квадратный бумажный лист сложили пополам по вертикали (так, что изгиб шёл посредине, сверху вниз) (1-я операция), потом по горизонтали (2-я операция), затем снова по вертикали (3-я операция) и так далее, сделав всего $n$ операций. Затем сделали разрез по горизонтали. Напишите рекурсивный алгоритм, вычисляющий число получившихся бумажек.

Задача 14

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

Задача 15

Рассмотрим следующее рекуррентное соотношение для функции ${f(n)=a^{n}}$:

$a^{0}=1,\;a^{n}=\left\{{\begin{matrix}a^{n-1}\cdot a,&{\mbox{if }}n{\mbox{ is odd}}\\\left(a^{n/2}\right)^{2}\cdot a,&{\mbox{if }}n{\mbox{ is even}}\end{matrix}}\right.$.

Нарисуйте дерево рекурсивных вызовов для $f(1000)$ (подсказка: это дерево не ветвится и выглядит как цепочка вызовов).

Задача 16

Чем отличается алгоритм от функции?

Чем отличается программа от алгоритма?

В чём разница между идеей решения и алгоритмом решения задачи?

Примечания

1. ^ Определение взято из книги Борисенко В. В., Основы программирования, Интернет ун-т информ. технологий. — М.: Интернет ун-т информ. технологий, 2005.
2. ^ Следует отметить, что в различных системах символьных вычислений число $\pi$ представляется как число с бесконечной точностью как алгоритм, который по мере надобности вычисляет нужное число первых цифр десятичного представления числа $\pi$. Такой алгоритм можно построить и на основе приведённой формулы, но этот алгоритм нельзя идентифицировать с самой формулой.
3. ^ Для человека числа также не являются элементарными — обычно он думает о них как о наборе цифр в десятичной записи и для их сложения и умножения использует алгоритмы сложения и умножения чисел «столбиком», в которых эти операции сводятся к последовательности элементарных действий с цифрами.
4. ^ Несмотря на то, что натуральное число не является элементарным объектом, мы в некоторых алгоритмах позволим себе работать с натуральными числами как с элементарными объектами. При этом мы будем подразумевать, что алгоритм работает лишь для небольших натуральных чисел или что за арифметическими операциями стоят соответствующие алгоритмы сложения, вычитания и умножения столбиком или алгоритм деления уголком сколь угодно больших чисел.
5. ^ Эта неприятная альтернатива оказывается является неотъемлемой частью вычислений. Оказывается в принципе нельзя из множества всех программ каким-либо алгоритмическим образом выделить никогда не зависающие программы. Об этом вы можете подробно узнать на курсе по вычислимые функции (см. теоремы Тарского и Геделя).

См. также

В Википедии:

• Алгоритм
• Математическая индукция

В Викиучебнике:

• Слово «алгоритм»: происхождение и развитие
• Знакомство с методом математической индукции

Литература

• Томас Х. Кормен Алгоритмы: вводный курс Томаса Х. Кормена = Algorithms Unlocked. — М.: «Вильямс», 2014. — 208 с. — ISBN 978-5-8459-1868-0
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ, 3-е издание = Introduction to Algorithms, Third Edition. — М.: «Вильямс», 2014. — 1328 с. — ISBN 978-5-8459-1794-2

• Larry LIU Xinyu AlgoXY - открытая книга об элементарных алгоритмах и структурах данных. = AAlgoXY is an open book about elementary algorithms and data structures.. — github.com: -, 2017. — >600 с. — ISBN -

• Дискретная математика, алгоритмы и структуры данных