Учебно-методический комплекс дисциплины для обучающегося «Языки программирования» для специальности 5В010900 Математика

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

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

Два алгоритма считаются эквивалентными, если у них совпада­ют алфавитные операторы, но не совпадают способы их задания (системы правил).

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

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

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

К первому направлению относятся рекурсивные функции, ма­шины Тьюринга, операторные системы Ван Хао, А.А. Ляпунова, логические схемы алгоритмов Ю.И. Янова и др. Ко второму направлению относятся представления нормальных алгоритмов А.А. Маркова в виде граф-схем, предложенных Л.А.Калужниным, блок-схемой метод алгоритмизации и др.