2015-05-27
2046
Тема № 3
Алгоритмические основы вычислительных процессов. Элементы теории алгоритмов и формальных языков.
Сведение произвольных алгоритмов к числовым функциям. Понятие вычислимой функции. Алгоритмическая полнота ЭВМ.
Сведение произвольных алгоритмов к числовым функциям
В процессе построения теории численных алгоритмов было выяснено, что любой логический алгоритм можно простыми методами свести к численному алгоритму. По мере усовершенствования этих методов стало ясно, что вообще любой алгоритм может быть всегда сведен к численному алгоритму.
Рассмотрим, каким образом любую алгоритмическую проблему можно свести к вычислению значений некоторой целочисленной функции при целочисленных значениях аргументов.
Включим все условия задачи, доступные для переработки данным алгоритмом А, в занумерованную неотрицательными целыми числами последовательность
А0, А1, А2, …, Аn, …
Совершенно аналогично записи возможных решений также включим в занумерованную последовательность
|
|
|
B0, B1, B2, …, Bn, …
Как только проведена нумерация, становится очевидным, что любой алгоритм, перерабатывающий запись условий Аn в запись решения Вn, можно свести к вычислению значений некоторой числовой функции
m=φ(n),
так как после введения нумерации мы можем иметь дело уже только с соответствующими номерами записей условий и решений, а не с самыми записями, и можем говорить об алгоритме, перерабатывающем номер записи условий в номер записи решения. Этот алгоритм будет численным алгоритмом.
Понятие вычислимой функции
Исходная идея построения точного определения алгоритма состоит в том, что любые данные (безусловно, дискретные) можно закодировать натуральными числами в некоторой системе счисления, и тогда всякое их преобразование сведется к последовательности вычислительных операций, а результат обработки также будет представлять собой целое число.
В данном подходе любой алгоритм, единый для данной числовой функции, вычисляет ее значение, а его элементарными шагами оказываются обычные арифметические и логические операции. Такие функции получили название вычислимых.
Пусть имеется класс функций типа y(x1, x2,..., xn), особенностями которых является то, что все аргументы функции x1,..., xn целочисленны, и значение функции y также выражается целым числом. Другими словами, рассматриваются функции, аргументы и значения которых дискретны.
Функция y(x1, x2,..., xn) называется эффективно вычислимой, если существует алгоритм, позволяющий вычислить ее значение по известным значениям аргументов.
