ВУЗ:
Составители:
1 Алгоритмы и вычислимые функции
1.1 Понятие алгоритма и неформальная вычислимость
Под алгоритмом понимается способ преобразования представления информации.
Слово algorithm – произошло от имени аль-Хорезми – автора известного арабского
учебника по математике (от его имени произошли также слова «алгебра» и «логарифм»).
Интуитивно говоря, алгоритм – некоторое формальное предписание, действуя
согласно которому можно получить решение задачи.
Алгоритмы типичным образом решают не только частные задачи, но
и классы
задач. Подлежащие решению частные задачи, выделяемые по мере надобности из
рассматриваемого класса, определяются с помощью параметров. Параметры играют роль
исходных данных для алгоритма.
Основные особенности алгоритма
Определенность. Алгоритм разбивается на отдельные шаги (этапы), каждый из
которых должен быть простым и локальным.
•
•
•
•
Ввод. Алгоритм имеет некоторое (
быть может, равное нулю) число входных данных,
т.е. величин, заданных ему до начала работы.
Вывод. Алгоритм имеет одну или несколько выходных величин, т. е. величин,
имеющих вполне определенное отношение к входным данным.
Детерминированность. После выполнение очередного шага алгоритма, однозначно
определено, что делать на следующем шаге.
Обратите внимание
, что мы не требуем, чтобы алгоритм заканчивал свою работу
для любых входных данных.
Примеры алгоритмов широко известны: изучаемые в школе правила сложения и
умножения десятичных чисел или, скажем, алгоритмы сортировки массивов. Для
алгоритмически разрешимой задачи всегда имеется много различных способов ее
решения, т. е. различных алгоритмов.
Примеры «почти» алгоритмов: медицинский
и кулинарный рецепты. Кстати,
почему такие рецепты во многих случаях нельзя рассматривать как алгоритмы?
Данное здесь определение алгоритма не является, конечно, строгим, но оно
интуитивно кажется вполне определенным. К сожалению, для решения некоторых задач
не существует алгоритма. Установление таких фактов требует введения строгого понятия
алгоритма.
Мы будем рассматривать алгоритмы, имеющие дело
только с натуральными
числами. Можно доказать, что это не является потерей общности, так как объекты другой
природы можно закодировать натуральными числами. Для пользователей компьютеров
такое утверждение должно быть очевидным.
Пусть N обозначает множество натуральных чисел {0, 1, 2, ...}. Объекты, которые
мы будем рассматривать, будут функциями с областью определения D
f
⊆ N
k
(k – целое
положительное число) и с областью значений R
f
⊆ N. Такие функции будем называть k-
местными частичными. Слово «частичная» должно напомнить о том, что функция
определена на подмножестве N
k
(конечно, в частном случае может быть D
f
= N
k
, тогда
функция называется всюду определенной).
Вычислимые функции
Назовем k-местную функцию f: N
k
→ N эффективно вычислимой (или просто
вычислимой), если существует алгоритм A, её вычисляющий, то есть такой алгоритм A,
что:
1. Если на вход алгоритма A поступил вектор x = <x
1
, x
2
, ..., x
k
> из D
f
, то вычисление
должно закончиться после конечного числа шагов и выдать f(x).
Страницы
- « первая
- ‹ предыдущая
- …
- 5
- 6
- 7
- 8
- 9
- …
- следующая ›
- последняя »
