II. Теория рекурсивных функций

ТЕОРИЯ АЛГОРИТМОВ

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

 

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

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

С точки зрения современной практики алгоритм – это программа, а критерием алгоритмичности процесса является возможность его запрограммировать

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

Чтобы создать алгоритм необходимо знать:

1. какую работу должен выполнять алгоритм.

2. какими должны быть входные данные.

3. какими должны быть выходные данные.

Рассмотрим некоторые основные принципы, по которым строятся алгоритмы,

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

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

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

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

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

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

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

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

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

Шестое, следует различать:

описание алгоритма (программу);

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

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

Связи между шагами можно изобразить в виде графа:

Блок–схемы алгоритмов

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

1) из которой выходит одно ребро – операторы;

2) из которой выходит два ребра – логические условия или предикаты.

Кроме того, имеется единственный оператор конца (из которого не выходит ни одного ребра) и единственный оператор начала. Важной особенностью блок-схем является то, что связи, которые она описывает, не зависят от того, являются ли шаги элементарными или представляют собой самостоятельные алгоритмы – блоки. Для данного блока неважно, как устроены другие блоки; для программирования блока достаточно знать, где лежит исходная информация, какова форма её представления, что должен делать блок и куда записывать результат. Блок-схемы соответствуют логике, которой пользуется программист для создания сложных, многовариантных, итеративных планов действий.

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

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

Определение. Алфавитом будем называть любое непустое конечное множество A = {a0,...,an}. Элементы алфавита принято называть буквами, или символами.

Определение. Словом длины n в алфавите A мы будем называть любой кортеж <a1, a2,..., an> длины n, где a1,..., an ― буквы алфавита A. Слова обычно записывают в виде a1a2... an. Пустое слово ∅ не содержит ни одной буквы, имеет длину 0 и обозначается через Λ.

Определение. Множество всех слов в алфавите A, включая пустое слово, обозначается через A∗. Множество всех непустых слов в алфавите A обозначается через A+, т. е. A+ = A∗ \ {Λ}.

Определение. Длина слова w ∈ A∗ обозначается через |w|.

Определение. Слово u называется подсловом слова v, если существуют слова w1 и w2 такие, что v = w1uw2, при этом вхождением подслова u в слово v назовем упорядоченную тройку <w1,u,w2>. Отметим, что одно и то же слово u может иметь несколько различных вхождений в слово v.

Определение. Слово u называется префиксом слова v, если v = uw для некоторого слова w. Слово u называется суффиксом слова v, если v = wu для некоторого w.

Определение. Введем следующие операции над словами в алфавите A:

(а) Конкатенацией слов u и v называется слово uv, полученное приписыванием к слову u слова v справа.

(б) Степень слова u определяется индукцией по n ∈ ω следующим образом: u0 = Λ, uⁿ⁺¹ = uⁿu.

(в) Обращением слова u = a1a2... an, где a1, a2,..., an ― буквы алфавита A, называется слово u^R = an... a2a1.

Пример. Конкатенацией слов kein и mehrheit является слово keinmehrheit. Если теперь взять конкатенацию тех же слов, но в другом порядке, то получится слово mehrheitkein. Слово ei является подсловом слова keinmehrheit, причем оно имеет два вхождения: первое вхождение начинается со 2-го символа слова, а второе ― с 10-го символа. Обращением слова mehrheit будет слово tiehrhem. Степенями слова kein являются слова Λ, kein, keinkein, keinkeinkein и т. д. При этом каждое слово из данной последовательности является префиксом всех последующих слов.

Определение. Любое подмножество L ⊆ A∗ называется формальным языком над алфавитом A.

Определение. Введем следующие операции над языками в алфавите A:

(а) Объединение L1 ∪ L2 и пересечение L1 ∩ L2 языков L1 и L2 определяются как обычные теоретико-множественные объединение и пересечение.

(б) Дополнением языка L называется язык L = A∗ \ L.

(в) Конкатенацией языков L1 и L2 называется язык L1L2 = {uv | u ∈ L1,v ∈ L2}.

(г) Степень языка L определяется индукцией по n ∈ ω следующим образом: L⁰ ={Λ}, Lⁿ⁺¹ = LⁿL.

(д) Звездочкой Клини от языка L называется язык L∗ = Ụ_n∈ωLⁿ. Другими словами,

L∗ = {w | w = w1w2...wn для некоторых n ∈ ω и w1,w2,..., wn ∈ L}.

В частности, всегда имеет место Λ ∈ L∗ (при n = 0).

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

 

II. ТЕОРИЯ РЕКУРСИВНЫХ ФУНКЦИЙ

 

I.1. Примитивно рекурсивные функции. Базис элементарных функций.

Операции подстановки и примитивной рекурсии. Основные свойства

 

Рекурсивные функции являются одним из вариантов уточнения понятия алгоритма. В общем, теория рекурсивных функций включает следующие классы функций: класс примитивной рекурсивной функции (ПРФ), класс общерекурсивной функции (ОРФ) и класс частично рекурсивной функции (ЧРФ).

В целом теория рекурсивных функций образуется следующим образом. В

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

123Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: