Алгоритмы и программы

Глава 1. Алгоритмы и программы

1.1 История развития теории алгоритмов.

Теория алгоритмов, как наука, непосредственно связана с предметами математической логики и теории конечных автоматов. В Древней Греции Аристотель и его ученик Платон сформулировали основные правила логики, которые используются до нашего времени для доказательства правильности и решения логических задач.

Математическая логика – это наука о правилах формального логического мышления.

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

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

На протяжении многих веков учёные всего мира создали много методов и алгоритмов решения различных задач в математике и физике.

В 1936 году английский ученый Тьюринг разработал модель вычислительной машины для решения задач на основе алгоритмов и доказал:

ü  возможность автоматического решения задач с помощью алгоритмов, реализуемых в виде программы;

ü  реальность создания универсальных вычислительных машин.

На основе этой модели («машина Тьюринга») была построена классическая теория алгоритмов, основу которой составляли формальные описания следующих понятий:

1 – алгоритм;

2 – алгоритмический процесс;

3 – взаимосвязь между алгоритмом и алгоритмическим процессом и др.

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

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

До середины XX века использовалось понятие алгорифма, заимствованное из математики. Позже с возникновением практического аспекта теории алгоритмов стал использоваться термин алгоритм. Причиной этому послужило развитие наук, изучающих структуру и принципы работы ЭВМ. Решение задач на ЭВМ было принято описывать в виде алгоритмов. Создание компьютеров и языков программирования способствовало выделению теории алгоритмов как самостоятельной дисциплины. Сегодня понятие алгоритма вышло за пределы математики и используется в различных областях, где алгоритмом называют точно сформулированное правило, являющееся руководством для достижения необходимого результата. Кроме того, алгоритмы являются первоосновой для программирования задач на ЭВМ.

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

1.2 Основные понятия, определения и задачи теории алгоритмов.

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

Таким образом, алгоритмы являются:

o  формой изложения научных результатов;

o  руководством к действию при решении уже изученных проблем;

o  средством автоматического решения задач;

o  инструментом, используемым при исследовании и решении новых проблем;

o  средством обоснования в математике;

o  одним из средств описания сложных процессов.

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

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

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

1 – интуитивное определение;

2 – формальное определение.

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

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

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

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

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

Алгоритм характеризуется:

Ø  понятностью для исполнителя;

Ø  массовостью, то есть допустимостью для него всех предложений на языке описания исходных данных;

Ø  детерминированностью и другими свойствами.

Неточность интуитивного понятия заключается в неточности тех терминов, через которые оно выражается, а именно:

ü  язык;

ü  понятность;

ü  точность

интуитивные понятия,

смысл которых ясен, а научные

определения не составлены.

1.2.2 Алгоритмический процесс.

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

Конструктивные объекты – это слова, числа, предложения, которые описывают исходные данные, промежуточные результаты и конечные данные.

Алгоритмический процесс состоит из конечного числа шагов, каждый из которых является простым и выполняется за конечное время. Число шагов алгоритмического процесса связано с количеством времени S(t), затрачиваемого на их выполнение, а в ряде случаев и расходом других ресурсов.

1.2.3 Основные вопросы теории алгоритмов.

Основные вопросы теории алгоритмов можно сформулировать следующим образом:

1)  Что может делать ЭВМ.

2)  Каким образом ЭВМ решает задачи.

3)  Существует ли для заданной задачи эффективный алгоритм решения.

4)  Как сравнить различные алгоритмы решения одной и той же задачи.

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

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

2) Ответ на второй вопрос требует рассмотрения принципов работы ЭВМ и организации вычислительных процессов для различных структур ЭВМ в рамках их классификации, а также оценки качества алгоритмов, реализуемых в различных ЭВМ.

3) Эффективным считается алгоритм, обладающий наибольшим быстродействием.

4) Для сравнения различных алгоритмов по быстродействию необходимо рассмотреть следующие параметры:

ü  временная функция T(N);

ü  функция сложности алгоритма O(g(N)), учитывающая зависимость скорости роста числа шагов алгоритма от объема исходных данных.

1.3 Алгоритмы и языки.

Как уже отмечалось, алгоритм – это правило, а любое правило должно быть четко сформулировано на каком-либо языке (1). Это возможно лишь при условии, что исходные данные и искомые результаты могут быть описаны в полном объеме на каком-либо другом языке (2). Т. е. каждому исходному данному, промежуточному и конечному результатам соответствует некоторое предложение на этом языке. Смысл предложения должен быть однозначным.

Язык (1) – это язык описания алгоритмов (алгоритмический язык).

Язык (2) – это язык описания данных (язык операндов).

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

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

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

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

Существуют различные формы (способы) представления алгоритмов. Основными среди них являются:

1. Словесное описание алгоритма на естественном языке (вербальная форма).

2. Построчная запись алгоритма (более строгое описание на естественном языке).

3. Представление алгоритма в виде блок-схемы.

4. Способ изображения алгоритма с помощью структурограммы (схема Насси-Шнейдермана).

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

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

Вербальное представление алгоритма.

«Чтобы найти НОД двух целых положительных чисел составим таблицу из двух столбцов и назовем их m и n. Запишем первое из заданных чисел в столбец m, а второе - в столбец n. Если данные числа не равны, заменим большее из них результатом вычитания из большего меньшего числа. Повторяем такие замены до тех пор, пока числа не окажутся равными, после чего число из столбца m считаем искомым результатом». Очевидно, такая форма представления алгоритма может тяжело восприниматься читателем и применяется в основном при решении простых задач.

Построчная запись алгоритма.

1. Начало.

2. Ввод m, n.

3. Если m¹n, перейти к пункту 4, иначе - к пункту 7.

4. Если m>n, перейти к пункту 5, иначе - к пункту 6.

5. m=m-n; перейти к пункту 3.

6. n=n-m; перейти к пункту 3.

7. НОД=m.

8. Вывод результата.

9. Конец.

Представление алгоритма в виде блок-схемы отличается высокой степенью наглядности. Блок-схема состоит из соединенных между собой стрелками (линиями потока информации) блоков различного вида, начертание которых регламентируется ГОСТ . Применительно к рассматриваемой задаче блок-схема алгоритма выглядит:

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

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

Program nod;

Var m, n: integer;

Begin

Writeln(‘Введите исходные числа m и n’); Read(m, n);

While m<>n do

If m>n Then m:=m-n Else n:=n-n;

Writeln(‘НОД равен’, m:3);

End.

1.5 Свойства алгоритмов.

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

Примеры:

«Уходя, гасите свет» - примитивный алгоритм.

«Правила пользования междугородним телефоном» - пошаговый процесс.

«Не курить» - непрерывный процесс, не являющийся алгоритмом.

2. Массовость. Алгоритм должен решать не одну конкретную задачу (ограниченное множество неизменных исходных данных), а серию однотипных задач. Т. е. множество различных исходных данных порождает различные результаты.

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

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

Массовость алгоритма – это допустимость всех объектов соответствующего класса, а не допустимость какого-либо их количества.

3. Детерминированность. Реализация алгоритма является детерминированным (определенным) процессом. Всякий раз при запуске алгоритма с одинаковыми исходными данными должен получаться одинаковый результат, т. е. алгоритм может быть повторен сколько угодно раз.

4. Потенциальная осуществимость алгоритма. Говорят, что алгоритм применим к допустимому исходному данному, если с его помощью можно получить искомый результат. Иначе, хотя исходное данное и допустимо, но алгоритм к нему не применим.

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

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

Пример1. Бесконечный цикл:

i=0

while i<= 10 do

k=k*2;

Пример 2. Последовательность вычислений:

1. b=2*a

2. b=b+1

3. c=b mod 3 a=6®d=6

4. d=a/c a=7®алгоритм не применим (ошибка деления на ноль).

Кроме потенциальной осуществимости алгоритма на практике требуется и реальная осуществимость.

5. Понятность. Алгоритм понятен для исполнителя, если он знает, как его выполнять (know how). Возникает вопрос: что именно должен знать исполнитель?

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

6. Корректность. Алгоритм корректен, если выполняются три условия:

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

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

3.  Результат работы алгоритма устойчив к вычислительной погрешности (свойство обусловленности).

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

Вычислительная погрешность (машинная точность) возникает из-за ограниченной разрядной сетки ЭВМ и операций округления.

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

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

Для плохо обусловленного алгоритма .

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

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

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

Пример4: Рассмотрим задачу нахождения корней квадратного уравнения:

Пусть точное значение выходного данного x=5, а результат измерений и ввода в компьютер значений входных данных a,b,c содержит малую погрешность .

Тогда для точных значений входных данных существует единственный действительный корень (D=0), а погрешность входных данных приводит к появлению комплексных корней, не имеющих физического смысла при решении задачи.

Пример5: Вычислить значение интеграла

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

Выполним интегрирование по частям и получим рекуррентную формулу

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

Вывод: Алгоритм неустойчив при .

Однако, устойчивость алгоритма зависит от порядка вычислений. Так, если проводить вычисления в обратном порядке по формуле , начиная с конца, например, n=54, то на первом шаге ошибка будет велика порядка 0,05, но с каждым шагом она будет уменьшаться со скоростью факториала, что обеспечивает правильное решение в целом.

Пример 6: Вычислить значение функции .

А) при объявлении в программе переменной X : real вещественного типа, для её хранения в памяти компьютера отводится 6 байт, что позволяет хранить числа в диапазоне {10-38…1038}. Прямой порядок произведения чисел уже на первом шаге выдает ошибку переполнения в программе: .

Б) тоже самое возникает при обратном порядке перемножения чисел: .

В) Сгруппируем пары произведений чисел и обеспечим корректность алгоритма

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

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

7. Эффективность. Данное свойство определяет быстродействие и связано с понятием вычислительной сложности алгоритма.

Эмпирические алгоритмы, как правило, не являются эффективными. Теоретические алгоритмы являются корректными и эффективными, но могут быть реально неосуществимы.

1.6 Классификация алгоритмов.

I. Т. к. алгоритм создается для решения задач одного класса, то вводят классификацию алгоритмов по типу решаемых задач:

1)  Табличные алгоритмы имеют в своей основе таблицу (поле исходных значений) и правила поиска решений.

2)  Численные алгоритмы задаются в виде формул и блок-схем. В их основе значительную роль играют арифметические операции (+,–, /, *).

3)  Алгоритмы игр имеют в основе логические задачи.

4)  Комбинационные алгоритмы представляют собой совокупность алгоритмов других классов.

II. По способу создания (источники) различают:

1)  Эмпирические алгоритмы – алгоритмы, полученные в ходе эксперимента или имитационного моделирования.

2)  Теоретически обусловленные алгоритмы – алгоритмы, возникшие из основных положения какой-либо теории.

3)  Эвристические алгоритмы – алгоритмы, основанные на личном опыте, таланте и изобретательности разработчика.

4)  Комбинационные алгоритмы – генерируются из уже известных алгоритмов.

III. По критерию реализуемости различают:

1)  Простые алгоритмы – хорошо обусловленные алгоритмы.

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

3)  Нереализуемые алгоритмы.

IV. По критерию сложности различают:

1)  Алгоритмы с логарифмической сложностью.

2)  Полиномиальные алгоритмы (класс P).

3)  Недетерминированные полиномиальные алгоритмы (класс NP), имеющие степенную или факториальную сложность.

1.7 Методы доказательства корректности алгоритмов.

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

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

III. Корректность комбинационных алгоритмов, полученных на основе других ранее известных и заведомо корректных алгоритмов, определяется различными методами:

1)  Конструирование алгоритмов. Новый алгоритм получают комбинированием уже известных алгоритм как составных частей.

2)  Метод эквивалентных преобразований алгоритма. Два алгоритма считаются эквивалентными, если:

ü  всякий вариант исходных данных, допустимый для одного алгоритма, также допустим и для другого;

ü  применимость одного алгоритма к каким-либо исходным данным гарантирует, что и другой алгоритм тоже к ним применим;

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

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

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

3)  Метод сужающих преобразований дает алгоритмы, являющиеся частными случаями решения задач, для которых имеются исходные алгоритмы.

4)  Применение формального метода к нематематической проблеме, существующей в какой-либо предметной области.

Запись проблемы на математическом языке позволяет:

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

Ø  разработать теоретически обусловленный корректный алгоритм.

Комментарии:

1.  Корректность алгоритмов, полученных первым методом, не вызывает сомнений, если исходные алгоритмы дают точный результат. Если же они дают приближенный результат (алгоритмы численных методов), то обоснование корректности таких алгоритмов может потребовать сложных исследований.

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

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

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

a)  оценкой адекватности полученной математической модели, т. е. возможностью получения при ее решении результата, достаточно близкого к искомому результату;

b)  доказательством корректности алгоритма решения математической задачи.

5.  Эвристические алгоритмы тоже требуют обоснования. Их корректность доказывается так же, как для эмпирических алгоритмов, либо согласно формальному методу.

1.8 Традиционные подходы в теории алгоритмов.

1.8.1 Рекурсивные функции.

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

Пусть задана некоторая функция w = f(x1, x2, …, x n).

Здесь f (или знак функционала) – это правило, задающее связь функции и аргумента. Функционал f может быть любым, в том числе и алгоритмом.

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

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

Базовые рекурсивные функции могут быть трех типов:

1) Функции любого числа независимых переменных, тождественно равные нулю jn()=0,где n – число аргументов функции (n может быть равным нулю).

Например:

АСФ в данном случае гласит: если задана функция jn ,то для любой совокупности значений аргументов значение функции равно нулю. Например,

2) Тождественные функции любого числа независимых переменных Yn,i, где n – число аргументов функции, i – номер одного из аргументов.

АСФ гласит: если задана функция Yn,i, то значение функции равно значению i-го аргумента (слева направо).

Например:

Y3,2(5, 8, 0)=8

Y1,1(6)=6

Для тождественных функций:

3) Функции следования одного независимого переменного l(х).

АСФ гласит: если задана функция l(х), то значением функции нужно считать число, непосредственно следующее за числом, являющимся значением аргумента.

При этом l(х)=х’ – последователь аргумента.

Например: l(5)=5’=6

Знак апострофа показывает на получение последователя для x.

Операторы.

1. Оператор суперпозиции (подстановки) S. Этот оператор по заданной функции F(f1,f2,…,fn) строит новую функцию Ф, такую, что для нее справедливо тождество:

Ф= F(f1,f2,…,fn), где fi – значение некоторых функций.

Формальная запись оператора суперпозиции выглядит следующим образом:

Ф::=S[ F, f1, f2,, …, fn],

где знак ::= обозначает «равно по определению».

Например, если функция F=l(f1) задана как функция следования, а функция l(y)=f1, то, согласно оператору суперпозиции, получаем некоторую функцию

t(y)::=S[l(f1); l(y)]

Ее числовое значение определяется:

t(y)= l(l(y))= l(y’)=y’’

t(5)=7

2. Оператор рекурсии R. Этот оператор строит по двум функциям f1n-1 и f2n+1 новую функцию fn.

Формальная запись:

f::=R[f1, f2, x, (y)],

где переменная х – главный дополнительный аргумент;

у – вспомогательный аргумент.

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

Здесь f1 ~ f1(x1, x2,…, xn-1, 0 ), x=0

i’ – последователь текущего аргумента.

АСФ в данном случае гласит: значением получаемой функции для х=0 (главный дополнительный элемент) считать значение исходной функции f1(x1, x2,…, xn ).

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

Например, пусть f1=j0=0 (n=0), f2=Y2,1(x, y)=X (n=2), тогда некоторая новая функция Z(x)::=R[j0,, Y2,1(x, y); X, (y)] удовлетворяет следующим условиям:

Т. о. Z(1)=0, Z(2)=1, Z(3)=2 и т. д.

3. Оператор минимизации m (оператор построения по первому нулю). Этот оператор по заданной функции, зависящей от n+1 аргументов, строит новую функцию, зависящую от n аргументов. При этом исключаемый аргумент является вспомогательным.

Формальная запись: f::=m [f1; (x)]

АСФ гласит: придавать вспомогательному аргументу (х) последовательные значения, начиная с 0 до тех пор, пока не окажется, что функция f1 становится равной нулю в первый раз, полученное значение вспомогательного аргумента х* считать значением искомой функции f.

Замечание: Базовые функции и функции, получаемые при помощи операторов S и R определены для любых значений аргументов, чего не следует для функций, полученных через оператор m, поскольку для многих комбинаций аргументов функции f1 они могут быть не определены, т. к. исходная функция не обращается в ноль.

Например:

f1=Y2,1(x, y)

r(x)::= m[Y2,1(x, y); (y)]

r(0)=0, r(i) не существует при i ¹ 0

Пусть i=2.

Y2,1(2, 0)=2

Y2,1(2, 1)=2

Т. о. при любых значениях у эта функция возвращает один и тот же результат.

Вывод: Рекурсивными называются базовые функции и любые функции, полученные из них с помощью конечного числа операторов суперпозиции S,рекурсии R, минимизации m. При этом, функции, получаемые без использования оператора минимизации называются примитивно рекурсивными. Рекурсивные функции, которые определены не для всех возможных значений аргументов называют частично рекурсивными. Функции полученные с использованием операторов S, R, m называют общерекурсивными.

Примеры рекурсивных функций:

1) y = x+1 = l(x) = x’.

2) Y3,3(x, y, z)=z

Если z*:z®(z+1), то f*(x, y, z*)::=S[Y3,3; z+1]=z+1

С помощью введенной функции f* и базовой функции Y1,1(x)=x можно определить новую функцию F(x, y) как рекурсивную функцию

F(x, y)::=R[Y1,1(x), f*(x, y, z*), y, (z)], удовлетворяющую следующим условиям:

3) Можно показать, что функция w=x*y является рекурсивной. Это же справедливо и для других арифметических операций. Таким образом, можно сделать вывод, что алгоритмы являются рекурсиями.

Гипотеза Черча: понятием рекурсивной функции исчерпывается полностью понятие вычислимой функции.

Какова бы ни была вычислимая неотрицательная целочисленная функция от неотрицательных целочисленных аргументов существует тождественно равная ей рекурсивная функция.

Проводя аналогию этого тезиса с алгоритмами, состоящими из простых операций, можно сказать:

Каков бы ни был алгоритм, перерабатывающий наборы целых неотрицательных чисел в целые неотрицательные числа, существует алгоритм, сопутствующий рекурсивной функции, который ему эквивалентен.

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

Невозможность создания рекурсивной функции для решаемой задачи означает невозможность реализации алгоритма ее решения.

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

1.8.2 Нормальные алгорифмы Маркова.

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

Если алфавит А входит во множество В, но А¹В, то говорят, что В – расширение алфавита А.

Пусть RÎA и существует некоторое PÎR, в этом случае говорят, что Р – это вхождение подстроки в высказывание R.

Марковская подстановка – это замена первого вхождения подслова Р в слове R на слово Q: (P, Q)=P®Q.

Если PÏR, то говорят, что Марковская подстановка не применима к слову R. Частными случаями Марковских подстановок являются пустые вхождения:

( ,Q), (P, ), ( , ). Здесь пустые слова в скобках эквивалентны Æ.

Пример 1:

Если R=ÎA, тогда

(923, 0000)ÞR=

Пример 2:

Пусть R=слово, тогда

(ра, да)Þ (не применимо)

Пример 3:

R=паровоз

(овоз, _)ÞR=пар_

Пример 4:

R=книга

( , ) ÞR=книга

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

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

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

Машина Тьюринга преобразует какие-либо объекты (например, строку символов, принадлежащих некоторому алфавиту) в некоторый искомый результат. При этом, хотя слова алгоритма машины Тьюринга могут иметь некоторый смысл, для теории алгоритмов это несущественно.

Для записи слов в машине Тьюринга используется бесконечная лента с последовательным доступом.

А – внешний алфавит машины Тьюринга.

Некоторый алфавит Р=р1, р2, …рn, характеризующий состояние машины в конкретный момент времени, называют внутренним алфавитом.

Состояние движения ленты описывается множеством возможных состояний

-¥, …, dj, …, d0, d1, …, +¥.

Опишем принцип работы машины Тьюринга.

1) Чтение ai из ячейки d0, на которой позиционируется головка чтения/записи (R/W Head). Состояние машины в этот момент определяется pj.

Начальный кортеж: {ai, d0, p0}

2) В зависимости от значений ai и pj изменяется поведение машины:

{ax, dy, pz}

Данный кортеж означает: записать вместо ai символ aх, переместить головку чтения/записи в позицию dy, блоку управления перейти в состояние pz.

3) Если после второго шага состояние машины Тьюринга описывается исходным кортежем, то машина останавливается. Иначе – повтор пункта 2.

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

	p1	p2	…	pj	…	pm
a0
a1
…
ai				{ax dy pz}
…
an

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

Устройство машины Тьюринга одинаково для решения различных задач, а алфавиты А и Р – различны.

Функция, для которой существует алгоритм вычисления, называется вычислимой функцией. Если для некоторой функции f(x) существует машина Тьюринга, то говорят, что f(x) вычислима по Тьюрингу.

Тезис Тьюринга:

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

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

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

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

Контрольные вопросы

1.  Дайте определение терминам «алгоритм» и «алгоритмический процесс».

2.  Сформулируйте основные задачи теории алгоритмов.

3.  В чём заключается теоретический аспект теории алгоритмов?

4.  В чём заключается практический аспект теории алгоритмов?

5.  Перечислите основные свойства алгоритмов и дайте их интерпретацию.

6.  Дайте характеристику понятия «корректность алгоритма».

7.  Какие существуют методы доказательства корректности алгоритмов?

8.  Какие известны классические теории алгоритмов?

9.  Что такое алгоритмически неразрешимые проблемы? Приведите примеры.

10.  Какие существуют методы описания алгоритмов?