понятие алгоритма в интуитивном смысле, основные свойства алгоритма. Способы представления алгоритмов. Обоснование необходимости формал

Интуитивное определение алгоритма

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

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

1. Массовость.
2. Потенциальная выполнимость.
3. Понятность.
4. Определённость.

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

Алгоритм – это точное, сформулированное на определенном языке конечное описание того или иного общего метода, основанного на применении исполнимых элементарных татов обрботки.

Способы представления алгоритмов на интуитивном уровне

• с помощью графического или словесного описания (графически – язык блок-схем)
• в виде таблицы
• последовательность формул
• на алгоритмическом языке или языке программирования

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

Роль алгоритмов

Алгоритмы являются:

1. Формой изложения научных результатов
2. Руководством к действию при решении уже изученных программ
3. Средство, позволяющее экономить умственный труд
4. Этап автоматизации решения задач
5. Инструмент, или средство, исследования новых проблем.
6. Средство описания математики
7. Одно из средств описания сложных процессов

Принципы разработки алгоритмов для решения прикладных задач

Важнейшим компонентом программирования является разработка алгоритмов. На первом этапе главенствовал операционный подход (время первых ЭВМ), то есть алгоритмы составлялись сориентированные на конкретные операции (присвоение, сравнение, условный (безусловный) переход, арифметические операции). Он был основан на особенностях конкретных ЭВМ. Структурный подход (появление машин третьего поколения (70-ые годы)) – логическая структура программы может быть выражена комбинацией трёх базовых структур (Теорема Бома-Якопини):

• следование ()
• условная ()
• цикл ()

Структурный подход состоит в модульности программ и алгоритмов и нисходящее проектирование (задача разбивается на ряд подзадач). (Пример - Паскаль)

Объективный подход

Объект – основное понятие объектного программирования. Процедура описывает алгоритм внутри той программы, для которой он разработан. Объект может быть отнесён к другой предметной области, исполнен в другом стиле. Исходная задача представляется как совокупность взаимодействия объектов (Дельфи).

Декларативный подход (появился в 40-ые годы) направлен на круг задач искусственного интеллекта. Программист описывает свойства исходных данных, свойства которыми должен обладать результат. А не алгоритм задачи, который должен задаваться автоматически системой.

• логический вариант (ПроЛог) – задача описывает совокупность правил и фактов в некотором формальном языке.
• функциональный (Lispt) – описываются функциональные зависимости между фактами.

Развиваются идеи параллельного программирования и другие.

Формализация алгоритма

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

Другим основанием появления точного построения алгоритма является расплывчатость понятия элементарного шага в интуитивном определении. Когда в начале 20 века математика перешла к изучению свойств сложных объектов (матрицы, определители), понятие элементарного шага перестало существовать и возникла потребность в точном определении понятия «алгоритм» - общего для всех видов алгоритмов. Оно должно быть формально строгим и соответствовать интуитивному понятию. Что привело к самостоятельной науке – теория алгоритмов, изучающая методы доказательства, свойства математических процедур и т.д. Появление вычислительной техники показало, что в основе компьютерных наук должно лежать понятие «алгоритм». Первые фундаментальные работы по теории алгоритмов были получены в середине 30-ых годов. А в 1931 году Гёдель доказал, что некоторые математические задачи не могут быть решены алгоритмами из определённого класса. А в середине 30-ых годов Тьюринг заложил фундамент теории алгоритмов. В начале 50-ых годов значительный вклад внесли Колмогоров, Марков. В теоретических подходах к определению строгого определения понятия «алгоритм» выделяют 3 исправления:

1. Связано с понятием «вычислимых функций» и частично рекурсивных функций.
2. Связано с машинной математикой. Алгоритмический процесс – это процесс, который может совершать соответствующим образом устроенная машина в математических терминах описываются узкие классы машин: машина Тьюринга, Поста; было доказано, что посредством этих машин можно осуществить все известные алгоритмические процессы.
3. Связано с понятием «нормального алгоритма» и разработал его Марков в 1954 году.

Несмотря на различные подходы, доказано, что все они эквивалентны.

Нормальные алгоритмы Маркова

В 1954 году А. А. Марков предложил схему, в которой как и в машине Тьюринга преобразуются слова, но на основе других принципов, а именно – в ней нет понятия «лента» и подразумевается непосредственный доступ к различным частям преобразуемого слова. Эта схема была названа нормальным алгоритмом Маркова.

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

осуществляет замену замену и заканчивает процесс(останавливается)

Упорядоченный набор пар слов (где A1…An – могут быть как знаком, так и словом) соединённых между собой стрелками двух видов. Каждая пара представляет собой формулу подстановки для замены подслов в преобразуемом слове. Выполнение нормального алгоритма распадается на такты. Каждый такт включает в себя поиск первой по порядку применимой формулой подстановки и применение этой формулы. Первый такт начинается с проверки: является ли слово A1 частью входного слова, то есть подсловом.

Например: в слове «информатика» есть вхождение слова «ин». Если входит, то это подслово заменяется на правую часть - B1 и т.д. Таким образом, происходит изменение входного слова путём подстановки вместо одного подслова другого. Если нет вхождения, то проверяется вторая пара и т.д. Если при попытке применить формулу подстановки имеется несколько вхождений Ai, то заменяется самое левое вхождение, и если какую-то формулу не удалось применить, то происходит попытка применить следующую формулу. Процесс выполнения нормального алгоритма заканчивается в следующих случаях:

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

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

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

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

Пример: кодировка 0 и 1 алфавита [a,b,c].

a → 101

b → 1001

c → 10001

Слово: caab

c101ab

c101101b

c1011011001

100011011011001

По определению вхождения пустого слова имеется слева и справа от каждого рассматриваемого слова, тогда смотрим _ → a - будет бесконечно присваивать букву a слева к входному слову, то есть этот алгоритм не применим, а применим.

Два простых достаточных признака применимости нормального алгоритма:

1. во всех формулах подстановки левой части не пустые, а правые части не включают буквы, входящие в левые части.
2. в каждом правиле подстановки правая часть короче, чем левая.

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

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

1. Приписать слева *.
2. Если * не последняя в слове, то поменять её местами со следующей буквой.
3. Заменить * на букву a и остановить процесс.

*a → a*, *в → в*, *c → c*, , _ → *.

Слово вас

*вас

в*ас

ва*с

вас*

васа

Сравнение различных алгоритмических схем

Несмотря на различие алгоритмических схем Маркова и Тьюринга доказано, что они эквивалентны. Гипотеза Тьюринга: всякий алгоритм представим с помощью машины Тьюринга. Как и машина Тьюринга, алгоритмическая схема Маркова в общем случае не может быть физически реализована, т.к. она допускает неограниченно большую длину входных слов и слов, возникающих в процессе подстановок. Можно отметить, что у машины Тьюринга сравнительно развито управление при слабых возможностях преобразования информации(т.е. только одну букву можно заменить) тогда как в алг. Схеме Маркова богаче возможности преобразования при менее развитом управлении. В обеих схемах авторы старались простыми средствами обеспечить возможность описания простых алгоритмов. Тьюринг достиг этого за счёт упрощения (шаг влево, шаг вправо) действий, Марков за счёт упрощения логики управления. С помощью той или иной схемы можно показать существование алгоритма неразрешимых проблем, в частности к ним относится проблема самоприменимости алгоритма. Интуитивное определение алгоритма трудно применить, чтобы показать, что нет алгоритма решения задачи. Для этого и потребовалось формализовать понятие «алгоритма». Одной из таких задач является задача самоприменимости.

Если удаётся свести задачу к некоторой неразрешённой задаче, то мы показываем, что задача данная неразрешима. Рассмотрим самоприменимость относительно схемы Маркова. Алгоритм может закончиться, а может - нет. Поэтому алгоритм Маркова можно разделить на два: для которых алгоритм самоприменения существует и для которых не существует.

Алгоритм, который мог бы однозначно решить любую задачу, то есть алгоритм распознания не существует, то есть значит, что проблема самоприменимости является неразрешимой. Если возьмём алгоритм a → a, то не самопименим, а - самоприменим. Для конкретных случаев можно конкретно определить, но универсального алгоритма нет, то есть, нет алгоритма, который решал бы весь класс задач по самоприменимости.