ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 14.02.2021
Просмотров: 125
Скачиваний: 1
Основные
требования
к
алгоритмам
.
1
.
Первое
,
что
следует
отметить
в
любом
алгоритме
-
это
то
,
что
он
применяется
к
исходным
данным
и
выдает
результаты
.
В
привычных
технических
терминах
это
означает
,
что
алгоритм
имеет
входы
и
выходы
.
Кроме
того
,
в
ходе
работы
алгоритма
появляются
промежуточные
результаты
,
которые
используются
в
дальнейшем
.
Таким
образом
,
каждый
алгоритм
имеет
дело
с
данными
—
входными
,
промежуточными
и
выходными
.
Поскольку
мы
собираемся
уточнять
понятие
алгоритма
,
нужно
уточнить
и
понятие
данных
,
т
.
е
.
указать
,
каким
требованиям
должны
удовлетворять
объекты
,
чтобы
алгоритмы
могли
с
ними
работать
.
Ясно
,
что
эти
объекты
должны
быть
четко
определены
и
отличимы
как
друг
от
друга
,
так
и
от
«
необъектов
».
Во
многих
важных
случаях
хорошо
понятно
,
что
это
значит
:
к
таким
алгоритмическим
объектам
относятся
числа
,
векторы
,
матрицы
смежностей
графов
,
формулы
.
Изображения
(
например
,
рисунок
,
графа
)
представляются
менее
естественными
в
качестве
алгоритмических
объектов
.
Если
говорить
о
графе
,
то
дело
даже
не
в
том
,
что
в
рисунке
больше
несущественных
деталей
и
два
человека
один
и
тот
же
граф
изобразят
по
-
разному
(
в
конце
концов
,
разные
матрицы
смежности
тоже
могут
задавать
один
и
тот
же
граф
с
точностью
до
изоморфизма
),
а
в
том
,
что
матрица
смежности
легко
разбивается
на
элементы
,
причем
из
элементов
всего
двух
видов
(
нулей
и
единиц
)
состоят
матрицы
любых
графов
,
тогда
как
разбить
на
элементы
рисунок
гораздо
труднее
.
Наконец
,
с
такими
объектами
,
как
«
хорошая
книга
»
или
«
осмысленное
утверждение
»,
с
которыми
легко
управляется
любой
человек
(
но
каждый
по
-
своему
!),
алгоритм
работать
откажется
,
пока
они
не
будут
описаны
как
данные
с
помощью
других
,
более
подходящих
объектов
.
Вместо
того
чтобы
пытаться
дать
общее
словесное
определение
четкой
определенности
объекта
,
в
теории
алгоритмов
фиксируют
конкретные
конечные
наборы
исходных
объектов
(
называемых
элементарными
)
и
конечный
набор
средств
построения
других
объектов
из
элементарных
.
Набор
элементарных
объектов
образует
конечный
алфавит
исходных
символов
(
цифр
,
букв
и
т
.
д
.),
из
которых
строятся
другие
объекты
;
типичным
средством
построения
являются
индуктивные
определения
,
указывающие
,
как
строить
новые
объекты
из
уже
построенных
.
Простейшее
индуктивное
определение
-
это
определение
некоторого
множества
слов
,
классическим
примером
которого
служит
определение
идентификатора
в
Паскале
:
идентификатор
-
это
либо
буква
,
либо
идентификатор
,
к
которому
приписана
справа
буква
или
цифра
.
Слова
конечной
длины
в
конечных
алфавитах
(
в
частности
,
числа
) —
наиболее
обычный
тип
алгоритмических
данных
,
а
число
символов
в
слове
(
длина
слова
) —
естественная
единица
измерения
объема
обрабатываемой
информации
.
Более
сложный
случай
алгоритмических
объектов
-
формулы
.
Они
также
определяются
индуктивно
и
также
являются
словами
в
конечном
алфавите
,
однако
не
каждое
слово
в
этом
алфавите
является
формулой
.
В
этом
случае
обычно
основным
алгоритмам
предшествуют
вспомогательные
,
которые
проверяют
,
удовлетворяют
ли
исходные
данные
нужным
требованиям
.
Такая
проверка
называется
синтаксическим
анализом
.
2.
Данные
для
своего
размещения
требуют
памяти
.
Память
обычно
считается
однородной
и
дискретной
,
т
.
е
.
состоит
из
одинаковых
ячеек
,
причем
каждая
ячейка
может
содержать
один
символ
алфавита
данных
.
Таким
образом
,
единицы
измерения
объема
данных
и
памяти
согласованы
.
При
этом
память
может
быть
бесконечной
.
Вопрос
о
том
,
нужна
ли
одна
память
или
несколько
и
,
в
частности
,
нужна
ли
отдельная
память
для
каждого
из
трех
видов
данных
(
входных
,
выходных
и
промежуточных
),
решается
по
-
разному
.
3.
Алгоритм
состоит
из
отдельных
элементарных
шагов
,
или
действий
,
причем
множество
различных
шагов
,
из
которых
составлен
алгоритм
,
конечно
.
Типичный
пример
множества
элементарных
действий
-
система
команд
ЭВМ
.
4.
Последовательность
шагов
алгоритма
детерминирована
,
т
.
е
.
после
каждого
шага
либо
указывается
,
какой
шаг
делать
дальше
,
либо
дается
команда
остановки
,
после
чего
работа
алгоритма
считается
законченной
.
5.
Естественно
от
алгоритма
потребовать
результативности
,
т
.
е
.
остановки
после
конечного
числа
шагов
(
зависящего
от
данных
)
с
указанием
того
,
что
считать
результатом
.
В
частности
,
всякий
,
кто
предъявляет
алгоритм
решения
некоторой
задачи
,
например
вычисления
функции
f(x),
обязан
показать
,
что
алгоритм
останавливается
после
конечного
числа
шагов
(
как
говорят
,
сходится
)
для
любого
х
из
области
задания
f.
Однако
проверить
результативность
(
сходимость
)
гораздо
труднее
,
чем
требования
,
изложенные
в
пп
. 1 - 4.
В
отличие
от
них
сходимость
обычно
не
удается
установить
простым
просмотром
описания
алгоритма
;
общего
же
метода
проверки
сходимости
,
пригодного
для
любого
алгоритма
А
и
любых
данных
х
,
вообще
не
существует
.
6.
Следует
различать
:
а
)
описание
алгоритма
(
инструкцию
или
программу
);
б
)
механизм
реализации
алгоритма
(
например
,
ЭВМ
),
включающий
средства
пуска
,
остановки
,
реализации
элементарных
шагов
,
выдачи
результатов
и
обеспечения
детерминированности
,
т
.
е
.
управления
ходом
вычисления
;
в
)
процесс
реализации
алгоритма
,
т
.
е
.
последовательность
шагов
,
которая
будет
порождена
при
применении
алгоритма
к
конкретным
данным
.
Итак
,
алгоритм
–
точное
предписание
,
которое
задает
вычислительный
процесс
,
начинающийся
с
произвольных
исходных
данных
и
направленный
на
получение
полностью
определенных
этими
исходными
данными
результы
.
Вообще
говоря
,
не
предполагается
,
что
результат
будет
обязательно
получен
:
процесс
применения
алгоритма
к
конкретным
возможным
исходным
данным
может
также
оборваться
безрезультатно
или
не
закончится
вовсе
.
В
случае
,
если
процесс
заканчивается
(
соответственно
не
заканчивается
)
получением
результата
,
говорят
,
что
алгоритм
применим
(
соответственно
неприменим
)
к
рассматриваемым
исходным
данным
.
Владение
некоторым
алгоритмом
означает
умение
решить
задачу
“
в
общем
виде
”.
Понятие
задачи
“
в
общем
виде
”
уточняется
при
помощи
понятия
массовой
проблемы
,
которая
состоит
в
требовании
найти
единый
алгоритм
решения
серии
отдельных
,
единичных
задач
(
когда
такого
алгоритма
не
существует
,
говорят
,
что
рассматриваемая
массовая
проблема
неразрешима
).
Так
численное
решение
уравнения
данного
типа
и
автоматический
перевод
–
массовые
проблемы
;
соответстствующие
им
единичные
задачи
–
численное
решение
отдельных
уравнений
данного
типа
и
перевод
отдельных
фраз
.
Установление
неразрешимости
к
.-
л
.
массовой
проблемы
является
важным
познавательным
актом
,
показывающим
,
что
для
решения
конкретных
единичных
задач
данной
серии
принципиально
необходимы
специфические
для
каждой
отдельной
задачи
методы
.
Как
правило
,
для
алгоритма
можно
выделить
7
характеризующих
его
пара
-
метров
: 1)
совокупность
возможных
исходных
данных
, 2)
совокупность
возможных
результатов
, 3)
совокупность
возможных
промежуточных
результатов
, 4)
правило
начала
, 5)
правило
непосредственной
переработки
, 6)
правило
окончания
, 7)
правило
извлечения
результата
.
Алгоритмический
процесс
есть
процесс
последовательного
преобразования
конструктивных
объектов
,
происходящий
дискретными
“
шагами
”;
каждый
шаг
состоит
в
смене
одного
конструктивного
объекта
другим
.
Переход
от
каждого
конструктивного
объекта
к
непосредственно
следующему
достаточно
“
элементарен
” –
в
том
смысле
,
что
происходящее
за
один
шаг
преобразование
предыдущего
конструктивного
объекта
в
следующий
носит
локальный
характер
(
преобразованию
подвергается
не
весь
конструктивный
объект
,
а
лишь
его
некоторая
,
заранее
ограниченная
для
данного
алгоритма
его
части
,
и
само
это
преобразование
определяется
не
всем
предыдущим
конструктивным
объектом
,
а
лишь
этой
ограниченной
частью
).
О
подходах
к
уточнению
понятия
«
алгоритм
»
Ранее
были
сформулированы
основные
требования
к
алгоритмам
.
Однако
понятия
,
использованные
в
этих
формулировках
(
такие
,
как
ясность
,
четкость
,
элементарность
),
сами
нуждаются
в
уточнении
.
Очевидно
,
что
их
словесные
определения
будут
содержать
новые
понятия
,
которые
снова
потребуют
уточнения
,
и
т
.
д
.
Поэтому
в
теории
алгоритмов
принимается
другой
подход
:
выбирается
конечный
набор
исходных
объектов
,
которые
объявляются
элементарными
,
и
конечный
набор
способов
построения
из
них
новых
объектов
.
Этот
подход
был
уже
использован
при
обсуждении
вопроса
о
данных
:
уточнением
понятия
«
данные
»
в
дальнейшем
будем
считать
множества
слов
в
конечных
алфавитах
.
Для
уточнения
детерминизма
будут
использоваться
либо
блок
-
схемы
и
эквивалентные
им
словесные
описания
,
либо
описание
механизма
реализации
алгоритма
.
Кроме
того
,
нужно
зафиксировать
набор
элементарных
шагов
и
договориться
об
организации
памяти
.
После
того
как
это
будет
сделано
,
получится
конкретная
алгоритмическая
модель
.
Алгоритмические
модели
,
рассматриваемые
в
дальнейшем
,
претендуют
на
право
считаться
формализацией
понятия
«
алгоритм
».
Это
значит
,
что
они
должны
быть
универсальными
,
т
.
е
.
допускать
описание
любых
алгоритмов
.
Поэтому
может
возникнуть
естественное
возражение
против
предлагаемого
подхода
:
не
приведет
ли
выбор
конкретных
средств
к
потере
общности
формализации
?
Если
иметь
в
виду
основные
цели
,
стоявшие
при
создании
теории
алгоритмов
, -
универсальность
и
связанную
с
ней
возможность
говорить
в
рамках
какой
-
либо
модели
о
свойствах
алгоритмов
вообще
,
то
это
возражение
снимается
следующим
образом
.
Во
-
первых
,
доказывается
сводимость
одних
моделей
к
другим
,
т
.
е
.
показывается
,
что
всякий
алгоритм
,
описанный
средством
одной
модели
,
может
быть
описан
средствами
другой
.
Во
-
вторых
,
благодаря
взаимной
сводимости
моделей
в
теории
алгоритмов
удалось
выработать
инвариантную
по
отношению
к
моделям
систему
понятий
,
позволяющую
говорить
о
свойствах
алгоритмов
независимо
от
того
,
какая
формализация
алгоритма
выбрана
.
Эта
система
понятий
основана
на
понятии
вычислимой
функции
,
т
.
е
.
функции
,
для
вычисления
которой
существует
алгоритм
.
Тем
не
менее
,
хотя
общность
формализации
в
конкретной
модели
не
теряется
,
различный
выбор
исходных
средств
приводит
к
моделям
разного
вида
.
Можно
выделить
три
основных
типа
универсальных
алгоритмических
моделей
,
различающихся
исходными
эвристическими
соображениями
относительно
того
,
что
такое
алгоритм
.
Первый
тип
связывает
понятие
алгоритма
с
наиболее
традиционными
понятиями
математики
-
вычислениями
и
числовыми
функциями
.
Наиболее
развитая
и
изученная
модель
этого
типа
-
рекурсивные
функции
—
является
исторически
первой
формализацией
понятия
алгоритма
.
Второй
тип
основан
на
представлении
об
алгоритме
как
о
некотором
детерминированном
устройстве
,
способном
выполнять
в
каждый
отдельный
момент
лишь
весьма
примитивные
операции
.
Такое
представление
не
оставляет
сомнений
в
однозначности
алгоритма
и
элементарности
его
шагов
.
Кроме
того
,
эвристика
этих
моделей
близка
к
ЭВМ
и
,
следовательно
,
к
инженерной
интуиции
.
Основной
теоретической
моделью
этого
типа
(
созданной
в
30-
х
годах
)
является
машина
Тьюринга
.
Наконец
,
третий
тип
алгоритмических
моделей
-
это
преобразования
слов
в
произвольных
алфавитах
,
в
которых
элементарными
операциями
являются
подстановки
,
т
.
е
.
замены
куска
слова
(
подслова
)
другим
словом
.
Преимущества
этого
типа
—
в
его
максимальной
абстрактности
и
возможности
применить
понятие
алгоритма
к
объектам
произвольной
(
не
обязательно
числовой
)
природы
.
Впрочем
,
как
будет
ясно
из
дальнейшего
,
модели
второго
и
третьего
типа
довольно
близки
(
их
взаимная
сводимость
доказывается
просто
)
и
отличаются
в
основном
эвристическими
акцентами
.
Примеры
моделей
этого
типа
—
канонические
системы
Поста
и
нормальные
алгоритмы
Маркова
.