Алгоритм, алгоритмизация, алгоритмический язык

Некоторые постановки задач допускают их решение с помощью схематического, механического способа действий. Такие схематические способы решения называют алгоритмами. Алгоритм – одно из понятий математики и информатики. Термин «алгоритм» происходит от имени средневекового математика Абу Джафара ибн Мусы аль-Хорезми. Латинская транслитерация имени последней части имени учёного аль-Хорезми ‑ algorismi, algorismus привела к образованию терминов «алгоритм» или «алгорифм» в европейских языках. Европейцы, начавшие использовать современную десятичную систему счисления в XII веке, знакомились с трудами арабских учёных, и труд упомянутого выше жителя Хорезма, посвящённый правилам счета в десятичной системе счисления, был широко известен. Поэтому и наполнение термина «алгоритм»» было следующим: операции над числами. Через века старое, прежнее понимание этого термина стало утрачиваться, и данный термин стали применять по отношению к одному единственному алгоритму – алгоритму Евклида, предназначенного для нахождения наибольшего общего делителя пары натуральных чисел (m, n).

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

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

Если алгоритм должен быть выполнен компьютером, то необходимо точное, «формальное» его описание. Тогда для представления алгоритмов применяются, как правило, алгоритмические языки или графические формы изображения.

Рассмотрим современное содержание понятия алгоритма. Развитие теории алгоритмов начинается с доказательства К. Гёделем[1] теорем о неполноте формальных систем, включающих арифметику, первая из которых была доказана в 1931. Гёдель доказал свои теоремы для определённой формальной системы, основанной на простой теории типов над натуральным рядом и аксиомах Дедекинда-Пеано.

Простейшая формулировка первой теоремы Гёделя о неполноте говорит о том, что существует предложение, не доказуемое и не опровержимое в рамках рассматриваемой теории P. Вторая теорема Гёделя утверждает, что в качестве такого предложения можно взять формализацию в P утверждения о ее собственной непротиворечивости [Беклемишев].

Возникшее в связи с этими теоремами предположение о невозможности алгоритмического разрешения многих математических проблем вызвало необходимость стандартизации понятия алгоритма. Современное формальное определение алгоритма было дано в 30-50-х годы XX века в работах Тьюринга[2], Поста[3], Маркова[4], Чёрча[5]. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Чёрча оказались эквивалентными друг другу. Основываясь на работах Гёделя, С. Клини ввел понятие рекурсивной функции, также оказавшееся эквивалентным вышеперечисленным.

Следует отметить также немалый вклад в теорию алгоритмов, сделанный Д. Кнутом, A. Ахо и Дж. Ульманом. Одной из лучших работ на эту тему является книга «Алгоритмы: построение и анализ» Томаса Х. Кормена, Чарльза И. Лейзерсона, Рональда Л. Ривеста, Клиффорда Штайна.

Машина Тьюринга (МТ) - это абстрактная модель вычислительной машины. Она была предложена Аланом Тьюрингом в 1936 году с целью формализации понятия алгоритм и определения, какие функции можно представлять в виде алгоритмов.
В состав машины Тьюринга входит лента, бесконечная в обе стороны и разделенная на ячейки (внешняя память); читающая и записывающая каретка (управляющий блок), способная находиться в одном из нескольких конечных состояний, например, соответствующих верхнему или нижнему положению головки "печатаемой" капли; и программа (логический блок). В начале работы машины задаются входные условия - состояние ленты и положение каретки.

Универсальной называется машина Тьюринга, способная заменить собой любую другую МТ, то есть, по сути, вычислить любую функцию, для которой есть разрешающий алгоритм. Ценность машин Тьюринга заключается в логической простоте (они совершают элементарные и последовательные действия), что позволяет проводить исследования в области алгоритмов.

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

Рекурсивные функции Гёделя-Эрбрана [6] -Клини[7] (от лат. recursio - возвращение), название, закрепившееся за одним из наиболее распространённых вариантов уточнения общего понятия арифметического алгоритма, т.е. такого алгоритма, допустимые исходные данные которого представляют собой системы натуральных чисел, а возможные результаты применения являются натуральными числами.

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

Алгоритмический язык – формальный язык для однозначной записи алгоритмов. Состоит из набора символов (алфавит), синтаксических правил и семантических определений. Является основой языков программирования.

Язык программирования – формальный язык для описания данных (информации) и алгоритма (программы) и их обработки на компьютере. Примерами современных языков программирования являются Паскаль, С, Си++.

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

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

Блок-схемы решения программных задач были предложены в 1940 г. Г. Голдстайном[8] и Дж. фон Нейманом[9], по-английски называются flow-chart.

Правила оформления блок-схем определяются стандартом ГОСТ 19.701-90. «Единая система программной документации. Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения». Настоящий стандарт распространяется на условные обозначения (символы) в схемах алгоритмов, программ, данных и систем и устанавливает правила выполнения схем, используемых для отображения различных видов задач обработки данных и средств их решения. Стандарт не распространяется на форму записей и обозначений, помещаемых внутри символов или рядом с ними и служащих для уточнения выполняемых ими функций

Программой называют описание алгоритма на языке программирования.

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

Псевокод является промежуточным шагом между естественным, в данном случае, английский языком описания алгоритма и его записью на программном языке.

Преимущества использования псевдокода состоит в следующем:

- легкость переноса алгоритма от записи на псевдокоде до записи на подлинном языке программирования.

Базовые структуры нашего псевдокода заимствованы из языка Паскаль (Pascal), который является наиболее популярным языком обучения. Предложенный псевдокод является менее формальным языком, чем Паскаль.

Алгоритм должен удовлетворять следующим свойствам:

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

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

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

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

Оптимальность определяется по времени и по памяти.

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: