ВУЗ:
Составители:
99
общем виде исходными данными и результатами алгоритмов могут служить
разнообразные конструктивные объекты.
Таким образом, алгоритмический процесс есть процесс последователь-
ного преобразования конструктивных объектов, происходящий дискретными
шагами. Каждый шаг состоит в смене одного конструктивного объекта другим.
Причем каждый последующий конструктивный объект полностью определяется
(в рамках данного алгоритма) непосредственно предшествующим.
Уточнения понятия
алгоритма. Принцип уточнения понятия «алго-
ритм» сводится к тому, что для каждого из указанных 7 параметров алгоритма
точно описывается некоторый класс, в пределах которого этот параметр может
изменяться. Выбор таких классов и отличает одно уточнение алгоритма от дру-
гого. Однако, возможные уточнения понятия алгоритма приводят, строго гово-
ря, к сужению этого
понятия.
Так, известный подход для уточненного описания алгоритма состоит в
следующем. Выбирается конечный набор исходных объектов, которые объяв-
ляются элементарными, и конечный набор способов построения из них новых
объектов. Под данными понимаются множества слов в конечных алфавитах.
Для выражения детерминизма используются либо описание механизма реализа-
ции алгоритма, либо блок-схемы и
эквивалентные им вербальные описания.
Кроме того, фиксируется набор элементарных шагов, и договариваются об ор-
ганизации памяти. Результатом такого подхода является конкретная алгорит-
мическая модель, которую можно считать уточненной формализацией понятия
«алгоритм».
Сохранение общности формализации в конкретных моделях при раз-
личном выборе исходных средств, приводит к моделям разного вида. Можно
выделить
три основных типа универсальных алгоритмических моделей, разли-
чающихся исходными эвристическими соображениями относительно понятия
«алгоритм». Первый тип связывает понятие алгоритма с наиболее традицион-
ными понятиями математики – вычислениями и числовыми функциями. Наибо-
лее развитая и изученная модель этого типа – рекурсивные функции – является
исторически первой формализацией понятия алгоритма. Второй тип основан на
представлении
об алгоритме как о некотором детерминированном устройстве,
способном выполнять в каждый отдельный момент лишь весьма примитивные
операции. Основной теоретической моделью этого типа, предложенной в 30-х
А.М. Тьюрингом годах является машина Тьюринга. Наконец, третий тип алго-
ритмических моделей – это преобразования слов в произвольных алфавитах, в
которых элементарными операциями являются подстановки,
т. е. замены куска
слова (полслова) другим словом. Преимущества этого типа моделей – в его мак-
симальной абстрактности и возможности применить понятие алгоритма к объ-
ектам произвольной (не обязательно числовой) природы. Примеры моделей это-
го типа – канонические системы Э.Л. Поста и нормальные алгорифмы А.А.
Маркова. Известно также уточнение, сформулированное А
.Н. Колмогоровым,
Страницы
- « первая
- ‹ предыдущая
- …
- 97
- 98
- 99
- 100
- 101
- …
- следующая ›
- последняя »
