Файл: 3.3.6 - Дескриптивная и метрическая теория алгоритмов.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 13.02.2021
Просмотров: 153
Скачиваний: 1
Ввиду
инвариантности
основных
результатов
общей
теории
алгоритмов
прикладное
значение
ее
результатов
никак
не
связано
с
тем
,
насколько
близки
к
практике
используемые
в
ней
теоретические
модели
алгоритмов
.
Машины
Тьюринга
весьма
далеки
от
современных
ЭВМ
,
а
рекурсивные
функции
—
от
языков
программирования
прежде
всего
из
-
за
предельной
скромности
используемых
средств
.
Однако
именно
скромность
средств
,
во
-
первых
,
делает
эти
модели
чрезвычайно
удобным
языком
доказательств
,
а
во
-
вторых
,
позволяет
по
-
нять
,
без
чего
обойтись
нельзя
,
а
без
чего
можно
и
какой
ценой
,
т
.
е
.
отличать
удобства
от
принципиальных
возможностей
.
Иначе
говоря
,
прикладное
значение
рассматриваемых
здесь
моделей
заключается
в
том
,
что
с
их
помощью
удобно
строить
теорию
,
верную
для
любых
алгоритмических
моделей
,
в
том
числе
и
для
сколь
угодно
близких
к
практике
.
Поскольку
несмотря
на
их
универсальность
,
эти
способы
описания
алгоритмов
оказались
практически
неприемлемыми
для
описания
алгоритмов
решения
задач
при
их
реализации
на
ЭВМ
,
возникла
необходимость
создания
языков
программирования
(
алгоритмических
языков
),
в
которых
находят
свое
отражение
такие
важные
особенности
решения
задач
на
современных
ЭВМ
,
как
наличие
различных
запоминающих
сред
,
внешние
среды
,
с
которым
связаны
ввод
и
вывод
данных
и
др
.
Вообще
говоря
,
теорию
алгоритмов
можно
разделить
на
дескриптивную
(
качественную
)
и
метрическую
(
количественную
).
Первая
исследует
алгоритмы
с
точки
зрения
устанавливаемого
между
исходными
данными
и
результатами
;
к
ней
относятся
,
в
частности
,
проблемы
построения
алгоритма
,
обладающего
теми
или
иными
свойствами
, -
алгоритмические
проблемы
.
Вторая
исследует
алгоритмы
с
точки
зрения
сложности
как
самих
алгоритмов
,
так
и
задаваемых
ими
вычислений
,
т
.
е
.
процессов
последовательного
преобразования
конструктивных
объектов
.