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

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

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

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

Алфавитом языка является не пустое конечное множество символов языка. Слово алфавита – конечная последовательность элементов алфавита, имеющее длину – натуральное число, равное количеству символов в слове, при этом – символ с номером i в слове . Среди слов отдельно выделяется слово e нулевой длины – пустое слово.

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

1. Операция конкатенации – соединение слов , при этом ;

2. Операция объединения – для слов полностью аналогична объединению множеств;

3. Операция итерации слов – повторение одного или нескольких элементов

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

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

Конечные автоматы

Конечными автоматами называется следующая совокупность

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

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

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

Рисунок 67. Графическое представление детерминированного конечного автомата.

При большом количестве состояний, будет большое количество стрелок, также увеличение букв влечет увеличение стрелок.

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