Свойство алгоритма понятность означает что
2.1.3. Свойства алгоритма
Не любая инструкция, последовательность предписаний или план действий может считаться алгоритмом. Каждый алгоритм обязательно обладает следующими свойствами: дискретность, понятность, определённость, результативность и массовость.
Свойство дискретности означает, что путь решения задачи разделён на отдельные шаги (действия). Каждому действию соответствует предписание (команда). Только выполнив одну команду, исполнитель может приступить к выполнению следующей команды.
Свойство понятности означает, что алгоритм состоит только из команд, входящих в систему команд исполнителя, т. е. из таких команд, которые исполнитель может воспринять и по которым может выполнить требуемые действия.
Свойство определённости означает, что в алгоритме нет команд, смысл которых может быть истолкован исполнителем неоднозначно; недопустимы ситуации, когда после выполнения очередной команды исполнителю неясно, какую команду выполнять следующей. Благодаря этому результат алгоритма однозначно определяется набором исходных данных: если алгоритм несколько раз применяется к одному и тому же набору исходных данных, то на выходе всегда получается один и тот же результат.
Свойство результативности означает, что алгоритм должен обеспечивать получение результата после конечного, возможно, очень большого, числа шагов. При этом результатом считается не только обусловленный постановкой задачи ответ, но и вывод о невозможности продолжения по какой-либо причине решения данной задачи.
Свойство массовости означает, что алгоритм должен обеспечивать возможность его применения для решения любой задачи из некоторого класса задач. Например, алгоритм нахождения корней квадратного уравнения должен быть применим к любому квадратному уравнению, алгоритм перехода улицы должен быть применим в любом месте улицы, алгоритм приготовления лекарства должен быть применим для приготовления любого его количества и т. д.
Пример 8. Рассмотрим один из методов нахождения всех простых чисел, не превышающих некоторое натуральное число п. Этот метод называется «решето Эратосфена» по имени предложившего его древнегреческого учёного Эратосфена (III в. до н. э.).
Алгоритм. Свойства алгоритма
Существует множество определений понятия «алгоритм»:
Из определений вытекают свойства алгоритма [5]:
Теперь покажем, что конкретный алгоритм обладает этими свойствами. В качестве примера, возьмем алгоритм, изображенный на рис. 1 в виде блок-схемы [6].
Рис 1 Блок-схема алгоритма проверки правильности расстановки скобок
Приведенный алгоритм проверяет правильность расстановки скобок, если скобки расставлены правильно – то каждой закрывающей скобке предшествует соответствующая открывающая, а каждой открывающей соответствует закрывающая.
Суть алгоритма заключается в подсчете глубины вложенности скобок друг в друга. Если в какой-то момент глубина получает значение меньше нуля – то скобки расставлены неправильно. Если просмотрены все символы строки, но счетчик не равен нулю – то в строке есть не закрытые скобки (расставлены неправильно). В противном случае скобки расставлены правильно.
Можно сказать, что алгоритм обладает свойством дискретности, так как весь алгоритм разбит на отдельные части (на блок-схеме это хорошо видно).
Доказать детерминированность алгоритма, достаточно сложно, например, когда алгоритм содержит части, которые выполняются параллельно, но не будем сейчас на этом останавливаться. Скажем, что в данном случае программа является детерминированной, т.к. не содержит фрагментов, зависящих от времени выполнения, т.е. сколько бы мы не тестировали алгоритм на одной и той же строке результат не изменится.
Чтобы показать результативность алгоритма, в данном случае достаточно заметить, что любой путь из начальной вершины в конечную содержит блок вывода результата. Перед блоком «конец» алгоритм содержит лишь 2 альтернативные ветви, каждая из которых выводит некоторый результат.
Алгоритм обладает свойством массовости, т.к. исходными данными для него может быть любая конечная последовательность символов. Алгоритм не обладал бы этим свойством, если бы работал лишь ограниченном наборе исходных данных, например на строках «()» и «())», но на остальных наборах не работал или работал не правильно.
Проверить свойство правильности алгоритма достаточно просто, для этого можно взять несколько примеров исходных данных, для которых результат очевиден и протестировать алгоритм на них, но доказать правильность алгоритма достаточно сложно. Доказательство правильности называется верификацией и явно выходит за рамки этой статьи.
В этой статье мы разобрались с тем, что такое алгоритм и какими основными свойствами он должен обладать. К теме алгоритмов я обязательно вернусь в будущих статьях.
Понятие алгоритма. Свойства алгоритма.
Одним из фундаментальных понятий в информатике является понятие алгоритм. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi – латинского написания имени Мухаммеда аль-Хорезми (787 – 850), выдающегося математика средневекового Востока. В XII в. был выполнен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами. Сложение, вычитание, умножение столбиком, деление уголком многозначных чисел – вот первые алгоритмы в математике.
Любой алгоритм должен удовлетворять основным свойствам::
Конечность алгоритма означает, что за конечное число шагов должен быть получен результат. Поэтому иногда это свойство называют результативностью.
Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
Понятностьалгоритма означает, что алгоритм должен содержать только те команды, которые входят в СКИ-система команд исполнителя.
Определенность – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
Корректность – свойство алгоритма, заключающееся в способности алгоритма давать правильные результаты при различных исходных данных.
Массовость – алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
ТЫ, Я и ИНФОРМАТИКА
Как упоминалось в предыдущей статье, основные свойства алгоритма — массовость, конечность и однозначность. Кроме этих свойств упоминают еще такие свойства алгоритмов, как их понятность и результативность. Рассмотрим подробнее — что же это за свойства.
Массовость алгоритма
Ценность алгоритма возрастает, если его можно применить к решению не одной, а целого класса задач. Такое свойство алгоритма называется его массовостью. Известные из арифметики правила сложения и умножения чисел «столбиком» — массовые алгоритмы, применяемые к любым слагаемым или сомножителям.
Кулинарные рецепты и инструкции по применению того или иного товара, как правило, не обладают массовостью — они составляются для каждого конкретного случая, и от этого никуда не уйти. Ведь каждый кулинарный рецепт обладает персональными пошаговыми инструкциями приготовления и набором ингредиентов.
Однако компьютерный алгоритм, разработанный для решения только одной частной задачи, чаще всего бесполезен, поскольку за время, потраченное на его создание, кодирование и ввод в компьютер, можно было решить задачу вручную.
Вполне закономерно, что разработчики алгоритмов стремятся расширить область их применения, сделать как бы более массовыми. Идеально было бы найти универсальный алгоритм на все случаи жизни, но такое, к счастью, невозможно, хотя бы потому, что есть алгоритмически неразрешимые классы задач. А к счастью — потому, что программисты благодаря этому факту без работы никогда не останутся.
С другой стороны, массовые алгоритмы, в силу своей общности, не учитывают конкретные особенности каждой решаемой ими задачи. Поэтому для особо важных задач приходится разрабатывать специальные «персональные» алгоритмы. Этим объясняется великое разнообразие алгоритмов компьютерных задач.
Конечность
Алгоритм должен решить задачу за конечное число шагов. Мы не можем вечно ждать результата. Если же алгоритм по каким-то причинам не может решить задачу, он должен сообщить об этом и завершить работу.
Несмотря на очевидность этого требования, иногда приходится прикладывать значительные усилия для того, чтобы предотвратить зацикливание алгоритма. При этом зачастую приходится уменьшать его массовость, ограничивая область применения.
Иногда время решения задачи составляет несколько часов или даже несколько суток. В таком случае в алгоритм обычно вводят инструкции, которые время от времени передают сообщения пользователю, сигнализирующие о нормальной, как говорят — штатной работе алгоритма. Даже программа, работающая непрерывно всего несколько минут, как правило, выводит на экран графические индикаторы своего выполнения — песочные часы, «градусник», различные вращающиеся или бегущие предметы, надписи и т. п., успокаивая таким образом пользователя — «все ok, я не зависла, я работаю!»
Конечность алгоритма обычно связывают с еще одним свойством – результативностью. Под результативностью алгоритма подразумевается, что по завершении каждого шага (или всего алгоритма в целом) должна быть получена среда (результат), в которой все объекты однозначно определены и можно приступать к выполнению следующего шага или следующего алгоритма, либо анализировать полученный результат. Если алгоритм не может получить такую полностью определяемую среду, он должен сообщить пользователю, что порученная задача не имеет однозначного решения.
Однозначность
Действия, выполняемые алгоритмом, должны следовать одно за другим, при этом очередное действие начинается после окончания предыдущего. После окончания каждого действия компьютер должен точно знать, что делать дальше, каково следующее предписание.
Компьютеру не скажешь: «Купи что-нибудь: колбасу или ветчину» и уж тем более — «Сыграй что-нибудь грустное или романтическое». Посылая компьютеризированного робота за покупками (почему бы нет?), надо дать ему точную, однозначную инструкцию: «Если колбаса свежее ветчины, купи колбасу, в противном случае купи ветчину». И даже такая, казалось бы, подробная команда может оказаться недостаточной, если вдруг колбасы в магазине не окажется, либо окажется несколько сортов колбасы или ветчины. Ваш робот растеряется и надолго задумается (если замешательство робота можно считать мыслительным процессом) над неподдающейся его скудному «разуму» задачей.
Требование однозначности (иногда это свойство называют дискретностью) обычно учитывается уже при разработке алгоритмического языка. Сами конструкции языка исключают неоднозначное их толкование и выполнение. На стадии обдумывания программы следует помнить об однозначности применяемого алгоритма.
Часто в программах встречаются несколько вариантов продолжения работы алгоритма. В таком случае нужно тщательно продумать условия выбора одного и только одного варианта.
Понятность
Это свойство алгоритма означает, что он должен быть понятен конкретному исполнителю – вычислительной машине, роботу или человеку. Приведем простой пример – если необходимо объяснить рецепт какого-либо блюда профессиональному повару, то для того, чтобы он понял технологическую последовательность приготовления достаточно несколько довольно-таки общих фраз о шагах и ингредиентах. Школьнику, для того, чтобы он смог приготовить это блюдо, следует тщательно описывать порядок приготовления со всеми мельчайшими подробностями, иначе он просто испортит продукты. При этом даже самое подробное описание рецептуры не гарантирует, что блюдо, приготовленное новичком от кулинарии, получится таким же вкусным, как у профи, поскольку поварское искусство имеет столько нюансов, нарабатываемых годами стажа работы, что их сложно предусмотреть и учесть в виде алгоритмической последовательности действий по приготовлению блюда.
То же самое в отношении ЭВМ – необходимо быть уверенным, что программная начинка компьютера и его «железо» смогут выполнить последовательность действий, предусмотренных алгоритмом.
Каждый шаг алгоритма обязательно должен представлять собой какое-либо допустимое и выполнимое действие конкретного исполнителя. Это свойство алгоритма и называют понятностью.
Теперь, после рассмотрения основных свойств алгоритма, можно сформулировать его определение. По отмеченным выше причинам оно не отличается строгостью, но вполне пригодно для использования в среде специалистов по практическому программированию.
Алгоритм – это точное пошаговое описание в системе команд исполнителя последовательности действий, однозначно приводящей к результату за конечное число шагов.
Это определение свело вместе все отмеченные выше свойства алгоритма. Оно отвечает не на вопрос: «что такое алгоритм», а на вопрос: «что делает алгоритм». В практическом программировании второй вопрос возникает гораздо чаще и ответ на него для программиста-практика значительно важнее.
Кто же ты такой, алгоритм?
Сегодня довольно легко столкнуться с недобросовестными школьными учебниками, в частности с учебниками по информатике. В главах, посвященных алгоритмам, вы можете найти непосредственно определение алгоритма. Не пояснение, о чем идет речь, не рассказ о предмете, а именно определение. Причем выделенное жирным шрифтом, старательно обведенное в рамку и помеченное какой-нибудь заметной пиктограммой в виде восклицательного знака. Обычно приправлено всё это соусом из кучи обязательных и необязательных свойств, образуя в итоге феерический кавардак. Давайте попытаемся понять, что же такое алгоритм, почему мы не может дать ему конкретного определения и выясним, какие свойства являются обязательными, а какие нет.
Составителей учебников легко понять, ведь на самом деле строгого определения алгоритма не существует, и более того, такого определения быть не может. Но вместо попыток объяснить, что к чему, авторы подсовывают бедным ученикам еще одно задание по зубрежке бесполезных и неправильных терминов. Чтобы не быть голословным, приведу выдержку из одного весьма распространенного учебника:
В университетах дела обстоят получше, однако автору этих строк на курсе по математической логике и теории алгоритмов пришлось столкнуться все с тем же винегретом из определения алгоритма и его свойств. Разберемся, что тут не так.
Бесконечность не предел
Такой же трюк с нумерацией не пройдет для бесконечных непериодических дробей (иррациональных чисел). Допустим такое множество счетное, то есть элементы этого множества можно пронумеровать натуральными числами. Тогда рассмотрим бесконечную десятичную дробь с нулевой целой частью, у которой первая цифра после запятой не равняется цифре на той же позиции у дроби с номером 1, вторая цифра не равняется цифре на второй позиции у дроби с номером 2 и т.д. Тогда полученная дробь будет заведомо отличаться от всех дробей хотя бы одной цифрой. Получается для нее не нашлось номера в нашей бесконечной нумерации! Примененная схема доказательства называется канторовским диагональным методом в честь придумавшего ее математика Георга Кантора.
Про бесконечные дроби
Не стоит делать ошибку, записывая в иррациональные числа все бесконечные дроби. Иррациональными являются только те числа, которые нельзя представить в виде несократимой дроби вида m/n. В десятичной системе счисления дроби 1/3 и 2/7 тоже окажутся бесконечными, однако их «бесконечность« обусловлена выбранной системой счисления. В системе счисления по основанию 21 эти дроби будут иметь конечное представление, а вот, например, дробь 1/2 окажется бесконечной (периодической).
Говорят, что множество бесконечных десятичных дробей имеет мощность континуум, которая обозначается символом ℵ1 (алеф-один). В дальнейшем нам понадобится следующее множество. Рассмотрим некоторый алфавит (конечное множество символов). Теперь представим множество всех конечных цепочек символов алфавита A*. Коль скоро алфавит конечен, и каждая цепочка конечна, то множество таких цепочек счетно (их можно пронумеровать натуральными числами).
На сколько велика бесконечность?
Допустим в наш алфавит вошли все придуманные на земле символы: русский алфавит, японские иероглифы, шумерская клинопись и т.д. Тогда в наше множество войдут все написанные когда-либо книги, все книги, которые будут написаны и все книги, которые никто не стал бы писать (например, хаотичные последовательности символов). Кроме того, представим книгу, толщиной в Солнечную систему и диагональю листа равной диаметру Млечного Пути, набранную 12-м шрифтом. В наше придуманное множество войдут все такие книги, отличающиеся хотя бы одним символов, и не только они, ведь вселенная бесконечна! Кто мешает представить себе книгу, размером в миллиарды световых лет? А все такие книги? Уже на этом этапе воображение может давать сбои, а ведь наше множество всего лишь счетное. Чтобы дополнить множество до континуума, нужно рассмотреть бесконечную книгу, по сравнению с которой, предыдущие книги — детские игрушки. Но и одной бесконечной книги нам не хватит, нужно рассмотреть все бесконечные книги.
Конструктивно оперировать континуальными бесконечностями невозможно. Даже работая со счетными множествами, мы не рассматриваем сами множества, а только говорим, что какой бы не был элемент N, всегда найдется элемент N+1. Если мы ставим себе прикладную задачу, появление в наших рассуждениях континуальной бесконечности должно служить нам «тревожной лампочкой»: осторожно, выход за пределы конструктивного.
Алгоритмы и вычислимость
Компьютер проводит свои вычисления, подчиняясь некоторой программе, которая воплощает собой конструктивную процедуру, или алгоритм. Не сложно догадаться, что алгоритм как раз и есть то правило, по которому вычисляется функция. Можно сказать, функция считается вычислимой, если для нее существует некоторый алгоритм.
Понятия алгоритм и вычислимая функция оказываются настолько заковыристыми, что некоторые составители учебной литературы не утруждают себя попытками разъяснить их суть. Дело в том, что определения алгоритма не существует, и кроме того, существовать не может, иначе пришлось бы выбросить на свалку целый раздел математики — теорию вычислимости. Попробуем разобраться более подробнее.
Частично-рекурсивные функции и тезис Черча
Все началось с того, что математик Давид Гильберт в 1900 году предложил список нерешенных на тот момент математических проблем. Позже выяснилось, что десятая проблема (проблема решения произвольного диофантового уравнения) оказалось неразрешимой, но для доказательства этого факта пришлось составить целую новую математическую теорию. Вопросами того, какие задачи можно конструктивно решить, и что такое конструктивное решение, занялись математики Курт Гедель, Стивен Клини, Алонсо Черч и Алан Тьюринг.
Курт Гедель наиболее известен тем, что сформулировал и доказал 2 теоремы о неполноте. Между прочим, сделал он это в возрасте всего лишь 24 лет.
Как выяснилось выше, континуальные бесконечности не всегда подходят под конструктивные рассуждения, поэтому Гедель и Клини предложили рассматривать только функции натурального аргумента (при необходимости любые функции над счетными множествами можно привести к «натуральным функция» путем замены элементов множеств их номерами). Изучая вычислимость таких функций, Гедель, Клини, Аккерман и другие математики пришли к так называемому классу частично-рекурсивных функций. В качестве определения этого класса рассматривается набор базовых, очень простых функций (константа, увеличение на единицу и проекция, которая сопоставляет функции многих аргументов один из ее аргументов) и операторов, позволяющих из функций строить новые функции (операторы композиции, примитивной рекурсии и минимизации). Слово «частичные» показывает, что эти функции определены лишь на некоторых числах. На остальных они не могут быть вычислены. Попытки расширить класс частично-рекурсивных функций ни к чему не привели, так как введение новых операций приводило к тому, что получалось множество функций, совпадающее с классом частично-рекурсивных. В дальнейшем Алонсо Черч отказался от попыток расширения этого класса, заявив, что, видимо:
Частично-рекурсивные функции соответствуют вычислимым функциям в любом разумном понимании вычислимости.
Это утверждение называют тезисом Черча. Стоит отметить, что тезис Черча не является теоремой или доказанным утверждением. Во-первых, не понятно, что такое «разумное понимание», во-вторых, превратив тезис Черча в доказанный факт, мы лишаем себя перспектив дальнейшего исследования вычислимости и механизмов вычислений. Никто, впрочем, не мешает попробовать определить такой набор операций, который был бы мощнее базиса для частично-рекурсивных функций. Только вот, до сих пор это никому не удавалось сделать.
Ученые долго не могли привести пример частично-рекурсивной функции, не являющейся примитивно-рекурсивной (без оператора минимизации). Наконец это удалось Вильгельму Аккерману. Предложенная функция Аккермана растет так быстро, что количество цифр в десятичной записи числа A(4,4) превосходит количество атомов во Вселенной.
Формальная теория алгоритмов во многом построена аналогично теории вычислимости. Считается, что алгоритм есть некое конструктивное преобразование входного слова (цепочки символов некоторого алфавита) в некоторое выходное слово. Опять же, здесь мы имеем с функциями вида A*->A*. Конечно, предложенное описание не подходит под определение алгоритма, так как неясно, что же такое «конструктивное преобразование». Хоть понятия алгоритма и вычислимой функции близки, не стоит их смешивать. Для одного и того же алгоритма может быть предъявлено сколько угодно его записей на каком-нибудь формальном языке, но соответствующая вычислимая функция всегда одна. Один из основателей формальной теории алгоритмов, Алан Тьюринг, предложил формальную модель автомата, известного как машина Тьюринга. Тезис Тьюринга гласит:
Каково бы не было разумное понимание алгоритма, любой алгоритм, соответствующий такому пониманию, может быть реализован на машине Тьюринга.
Любые попытки построить более мощные автомат заканчивались неудачей: для каждого такого автомата (машина Поста, нормальные алгоритмы Маркова, автоматы с регистрами и несколькими лентами) удавалось построить аналогичную машину Тьюринга. Некоторые ученые объединяют тезис Черча и тезис Тьюринга в тезис Черча-Тьюринга, так как они весьма близки по духу.
С помощью такого незамысловатого автомата можно формализовать любой алгоритм.
Таким образом, определив понятие алгоритма, мы будем вынуждены забыть о тезисе Черча-Тьюринга, и отказаться от целой математической теории, богатой содержанием и подарившую нам множество практических результатов.
Свойства алгоритмов
Мы выяснили, почему у алгоритма не может быть конкретного определения. Однако можно определить свойства, которыми должен обладать каждый алгоритм. К сожалению, в литературе часто смешивают обязательные и необязательный свойств. Разберемся подробнее.
Обязательные свойства
Начнем с обязательных свойств. Алгоритм можно записать в виде конечного текста из символов конечного алфавита. Действительно, бесконечный текст мы не можем записать чисто технически, а раз алгоритмы имеют отношение к конструктивной деятельности, бесконечными они быть не могут. Возможность представить алгоритм в виде конечного текста можно назвать свойством объективности и конечности.
Еще одно достаточно очевидное свойство любого алгоритма — его дискретность. Независимо от исполнителя, исполнение алгоритма представляет собой дискретный процесс, при рассмотрение распадающийся на элементарные действия. Понимать дискретность можно и в том смысле, что любая информация, над которой работает алгоритм может быть представлена в виде текста.
Третье фундаментальное свойство алгоритмов называется детерминированностью. Оно заключается в том, что следовать предписанной процедуре можно только одним способом. Единственное, что может повлиять на ход выполнения — это исходные данные, однако при одних и тех же исходных данных, алгоритм всегда выдает один и тот же результат.
Эти три свойства присущи всем алгоритмам. Если нарушено хотя бы одно из них, перед нами уже не алгоритм. С натяжкой к обязательным свойствам можно добавить понятность для исполнителя, хотя это уже на грани фола. По большей части. это относится не к самому алгоритму, а к его записи.
«Винегрет» из свойств из того же учебника по информатике.
Необязательные свойства
Наряду с обязательными свойствами, алгоритм может обладать некоторыми частными свойствами, которые вовсе не обязательны. Начнем с массовости. Конечно, хочется, чтобы алгоритмы решали классы задач в зависимости от входных данных. Однако существуют алгоритмы, которые вообще не зависят от входных данных, например всем известный вывод на экран «Hello world». Как среди вычислимых функций существуют константные, так и среди алгоритмов существуют генераторы единственного результата.
Теперь рассмотрим широко распространенное убеждение, что алгоритмы должны обладать свойством правильности и завершаемости. Начнем с правильности. Такое свойство попросту невозможно формализовать, так как отсутствуют критерии этой правильности. Наверняка, многие из вас сталкивались с ситуацией, когда программист считает программу правильной, а заказчик нет. С завершаемостью дела обстоят интереснее. Рассмотрим термин «применимость« — алгоритм называется применимым к слову, если, получив на вход это слово, он завершается за конечное число шагов. Самое интересное то, что проблема применимости является алгоритмически неразрешимой, то есть невозможно составить алгоритм, которые определял бы по записи алгоритма и входному слову, завершится ли он за конечное число шагов. Никто не мешает вам составить программу, состоящую только из одного бесконечного цикла. И эта программа все еще будет алгоритмом.
Про зависающие программы
Программы, которые не могут зациклиться, на самом деле входят в класс примитивно-рекурсивных — подмножество частично-рекурсивного класса. Отличает их отсутствия оператора минимизации. Он то и вносит пикантности. Если вы используете «неарифметический цикл» while или рекурсию, для которых нельзя заранее определить, сколько раз они выполняться, то ваша программа сразу переходит из класса примитивно-рекурсивных в класс частично-рекурсивных.
Теперь перейдем к пресловутой последовательности шагов. Дело в том, что алгоритм может быть представлен в любой из имеющихся формальных систем (частично-рекурсивные функции, машина Тьюринга, лямбда-исчисление и т.д.). Воплощение алгоритма в виде компьютерной программы далеко не всегда будет описанием последовательности шагов. Здесь все зависит от парадигмы программирования. В императивной парадигме программисты действительно оперируют последовательностью действий. Однако существуют и другие парадигмы, такие как функциональная (привет Haskell программистам), где нету никаких действий, а лишь функции в сугубо математическом смысле, или чистая объектно-ориентированная, которая основана не на «последовательности действий», а на обмене сообщениями между абстрактными объектами.
Заключение
Иногда мир устроен несколько сложнее, чем хотелось бы. Существующие формализмы в теории алгоритмов не более чем абстрактные математические системы, наподобие геометрии Евклида или теории вероятности, тогда как понятие вычислимости, возможно, находится вне математики и является свойством нашей Вселенной наряду со скоростью света и законом всемирного тяготения. И хотя, скорее всего, нам так и не удастся ответить на вопрос, что такое алгоритмы и вычислимость, попытки найти ответ на этот вопрос оказались более ценными, чем возможный однозначный ответ.
Материал данной статьи во многом опирается на 1-ый том «Программирование: введение в профессию» А. В. Столярова. Тем, кто хочет подробнее изучить вопросы, связанные с алгоритмами и теорией вычислимости, кроме этой книги, советую Босс В «От Диофанта до Тьюринга» и трехтомник А. Шеня по математической логике и теории алгоритмов.
Дата-центр ITSOFT — размещение и аренда серверов и стоек в двух дата-центрах в Москве. За последние годы UPTIME 100%. Размещение GPU-ферм и ASIC-майнеров, аренда GPU-серверов, лицензии связи, SSL-сертификаты, администрирование серверов и поддержка сайтов.