Вычислимые функции и алгоритмы

Определение. Вычислимая функция — это такая функция, для ко­торой существует вычисляющий ее значения алгоритм, т.е. функция называется вычислимой, если существует алгоритм, по­зволяющий определить значения функции при любых значениях перемен­ных .

Определение. Алгоритмом называется точное предписание, определяю­щее вычислительный процесс, который ведет от варьируемых исходных данных к искомому результату, т.е. алгоритм — это совокупность правил, определяющих данный вычислительный процесс.

Для каждого алгоритма существует некоторая совокупность возмож­ных исходных данных — объектов, к которым имеет смысл применять рассматриваемый алгоритм. Для каждого алгоритма выделяется область применимости: если процесс применения алгоритма к какому-либо объ­екту заканчивается выдачей результатов, то говорят, что он применим к этому объекту.

Алгоритм задает функцию, определенную на его области применимо­сти и ставящую в соответствие каждому элементу этой области результат применения к нему алгоритма.

Не все объекты, встречающиеся в математике, могут служить ис­ходными данными, результатами или промежуточными данными алго­ритма.

В алгоритмических процессах могут участвовать лишь конструктив­ные объекты.

Определение. Конструктивными объектами будем называть натуральные и рациональные числа, полиномы с натуральными или рациональными ко­эффициентами, матрицы с натуральными или рациональными элементами, слова в некотором алфавите и т. д., т. е. такие объекты, которые могут быть построены целиком и представлены для рассмотрения.

Поскольку возможными исходными данными и результатами алгоритма могут быть лишь конструктивные объекты, то лишь конструктивные объекты могут быть аргументами и значениями вычислимой функции.

Свойства алгоритмов

Анализ известных в математике алгоритмов дал возможность вы­явить характерные его свойства.

Свойство 1. Дискретность. Алгоритм описывает процесс последова­тельного построения величин, идущий в дискретном времени. Необхо­димый для вычисления интервал времени разбит на малые отрезки — такты. Система величин в конце каждого такта получается в результате осуществления элементарного шага алгоритма (определенной програм­мы преобразования) из системы величин, имеющейся к началу такта.

Свойство 2. Детерминированность (определенность) требуется, что­бы метод действия (вычисления) был настолько точен и общепонятен, что­бы не оставалось места произволу. Этот метод можно сообщить другому лицу в виде конечного числа указаний, т. е. программа преобразований в каждом такте однозначно определена.

Свойство 3. Результативность. Это свойство, называемое иногда еще направленностью алгоритма, требует, чтобы алгоритмическая процеду­ра, примененная к любой задаче данного типа, через конечное число ша­гов останавливалась и после остановки можно было бы прочесть искомый результат.

Свойство 4. Массовость. Алгоритм служит не для решения какой-либо одной конкретной задачи, а для решения целого класса задач. Про­цедуру для решения одной индивидуальной задачи не называют алгорит­мом.

Понятия разрешимого предиката, разрешимого множества, перечислимого множества

На основе понятий вычислимой функции и алгоритма определяются понятия разрешимого предиката, разрешимого множества и перечисли­мого множества.

Определение. Предикат , определенный на множестве це­лых чисел, называется алгоритмически разрешимым или просто разреши­мым, если существует алгоритм для определения значения предиката Р при любых значениях переменных .

Определение. Множество называется разрешимым, если существует ал­горитм, распознающий принадлежность произвольного элемента к этому множеству.

Определение. Множество называется перечислимым, если оно есть мно­жество значений какой-нибудь вычислимой функции, определенной на всем натуральном ряду.

Пример алгоритма

Прежде, чем перейти к точным определениям, рассмотрим пример вычислительного алгоритма: алгоритм вычисления числа я, основанный на формуле удвоения.

Исторически первый и в течение длительного времени единствен­ный алгоритм вычисления числа к был основан на подсчете периметров

правильных вписанных и описанных многоугольников с помощью фор­мул удвоения. Эта формула связывает длины сторон правильных п- и 2n-угольников, вписанных в окружность радиуса R. Положим диаметр рассматриваемой окружности равным единице: d = 2R = 1 (длина такой окружности равна π ), тогда формула удвоения примет вид:

Умножим и разделим выражение под знаком общего корня на сопряжен ное. В результате получим:

Введем периметр многоугольника р_п = па_п и подставим выражения сторон а_п и через периметры в формулу, тогда она преобразуется к виду

Мы получили рекуррентную формулу.

Сторона правильного описанного n-угольника при d = 2R = 1 выра­жается через сторону вписанного n-угольника а_п с помощью соотношения

Перейдем в нем от сторон а_п и b_п к соответствующим периметрам, обозначая периметр вписанного многоугольника через q_n: q_n = nb_n. В ре­зультате будем иметь:

Но

Вычисление числа я с помощью данного метода можно начать с какого-нибудь простого правильного многоугольника, например с ше­стиугольника, для которого

Далее процесс строится следующим образом: по рекуррентной форму­ле находятся последовательно . По ним с помощью формулы вычисляются соответствующие значения q_n.

Двухстороннее неравенство р_п < π < q_n позволяет утверждать, что найденные на некотором шаге числа дают приближенные значения π с недостатком и избытком с ошибкой ϵ _п < ∆ = q_n — р_п, которая стремится к нулю при п → ∞.

Используя описанные идеи и проводя сложнейшие для своего време­ни вычисления, древнегреческий ученый Архимед дошел до правильного 96-угольника и получил для π двухстороннюю оценку:

В Европе французский математик Ф. Виет нашел 9 правильных цифр числа π после запятой с помощью 3 ∙ 2¹⁷-угольника (16 удвоений числа сторон).

Приведем таблицу 16 удвоений числа сторон: повторение результата Ф. Виета.

k
		3, 000 000 000 000	3, 464 101 615 138
		3, 105 828 541 230	3, 630 002 002 236
		3, 132 628 613 281	3, 245 155 564 194
		3, 139 350 203 047	3, 166 557 423 678
		3, 141 031 950 890	3, 147 778 817 495
		3, 141 452 472 285	3, 143 135 797 312
		3, 141 557 607 912	3, 141 978 227 840
		3, 141 583 892 148	3, 141 689 033 932
		3, 141 590 463 228	3, 141 616 747 849
		3, 141 592 105 999	3, 141 598 677 103
		3, 141 592 516 692	3, 141 594 159 465
		3, 141 592 619 365	3, 141 593 030 059
		3, 141 592 645 034	3, 141 592 747 706
		3, 141 592 651 034	3, 141 592 677 119
		3, 141 592 653 055	3, 141 592 659 472
		3, 141 592 653 456	3, 141 592 655 060
		3, 141 592 653 556	3, 141 592 653 957

 

Для оценки точности определения к с помощью этих расчетов со­ставим разность периметров q_n и р_п, приведенных в последней строке (n = 6-2¹⁶ = 39321):

Первые 10 знаков у чисел р_п и q_n совпадают, т. е. π = 3, 141 592 653….

 

 

⇐ Предыдущая12345678Следующая ⇒

Поделиться:

Популярное:

1. B. Функции языка как театральной коммуникативной системы
2. I. КРАТКИЕ СВЕДЕНИЯ О СТРОЕНИИ И ФУНКЦИИ МИОКАРДА
3. III. Вегетативные функции НС.
4. Xlabel('Значения x'); ylabel('Значения функции'), grid
5. АЛГОРИТМЫ ВРАЧЕБНОЙ ПРАКТИКИ
6. Алгоритмы сортировки массивов
7. Алгоритмы сортировки слиянием (MergeSort)
8. Анализ структуры и выполняемые функции информационной подсистемы «Кадры» ОГУ
9. Асимптоты графика функции и их отыскание
10. Билет 5 Основные черты, функции и Юридические свойства Конституции
11. Биологические функции пептидов и белков
12. Блок 20. Функции администратора зала и администратора кассы