4. Формализованное понятие алгоритма

4. Формализованное понятие алгоритма

Алгоритм может существовать только тогда, когда в то же самое время существует некоторый математический объект. Формализованное понятие алгоритма связано с понятием рекурсивных функций, нормальных алгоритмов Маркова, машин Тьюринга.

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

Рекурсивные функции – это подкласс вычислимых функций, а алгоритмы, определяющие вычисления, называются сопутствующими алгоритмами рекурсивных функций. Сначала фиксируются базовые рекурсивные функции, для которых сопутствующий алгоритм тривиален, однозначен; затем вводятся три правила – операторы подстановки, рекурсии и минимизации, при помощи которых на основе базовых функций получаются более сложные рекурсивные функции.

Базовыми функциями и их сопутствующими алгоритмами могут выступать:

1) функция n независимых переменных, тождественно равная нулю. Тогда, если знаком функции является ?n, то независимо от количества аргументов значение функции следует положить равным нулю;

2) тождественная функция n независимых переменных вида ?ni. Тогда, если знаком функции является ?ni, то значением функции следует взять значение i-го аргумента, считая слева направо;

3) ? – функция одного независимого аргумента. Тогда, если знаком функции является ?, то значением функции следует взять значение, следующее за значением аргумента. Разные ученые предлагали свои подходы к формализованному

представлению алгоритма. Например, американский ученый Черч предположил, что класс вычислимых функций исчерпывается рекурсивными функциями и, как следствие, каким бы ни был алгоритм, перерабатывающий один набор целых неотрицательных чисел в другой, найдется алгоритм, сопутствующий рекурсивной функции, эквивалентный данному. Следовательно, если для решения некоторой поставленной задачи нельзя построить рекурсивную функцию, то и не существует алгоритма для ее решения. Другой ученый, Тьюринг, разработал виртуальную ЭВМ, которая перерабатывала входную последовательность символов в выходную. В связи с этим им был выдвинут тезис, что любая вычислимая функция вычислима по Тьюрингу.

Данный текст является ознакомительным фрагментом.



Поделитесь на страничке

Похожие главы из других книг:

Понятие об ODS

Из книги автора

Понятие об ODS ODS - это аббревиатура для On-Disk Structure, т. е. структура данных баз данных InterBase на диске. ODS определяет, как организованы данные внутри файлов базы данных. Определение основных констант и структур данных для реализации On-Disk Structure находится в файле из комплекта


1. Понятие вспомогательного алгоритма

Из книги автора

1. Понятие вспомогательного алгоритма Алгоритм решения задачи проектируется путем декомпозиции всей задачи в отдельные подзадачи. Обычно подзадачи реализуются в виде подпрограмм.Подпрограмма – это некоторый вспомогательный алгоритм, многократно использующийся в


55. Понятие системы VВА

Из книги автора

55. Понятие системы VВА VBA представляет собой подмножество VB и включает средства образования приложений VB, его структуры данных и управляющие структуры, возможность создания пользовательских типов данных. Также как и VB, VBA является системой визуального программирования,


7.10. Написание собственного алгоритма

Из книги автора

7.10. Написание собственного алгоритма ПроблемаДля диапазона требуется выполнить алгоритм, и ни один из стандартных алгоритмов не удовлетворяет требованиям.РешениеНапишите алгоритм в виде шаблона функции и с помощью имен параметров шаблона укажите свои требования к


Понятие гистограммы

Из книги автора

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


Понятие выделения

Из книги автора

Понятие выделения Создавая выделение, мы обозначаем в документе область, с которой хотим работать, а вся остальная часть документа для редактирования становится недоступной. Это правило справедливо для всех случаев, когда мы работаем с инструментами и командами


Понятие шаблона

Из книги автора

Понятие шаблона Для упрощения работы по созданию и форматированию текстов, стандартизации расположения и оформления текста, графики, типизации операций обработки документов и прочего используются шаблоны документов. Пакет Microsoft Office дает различные определения шаблона


5. Понятие ключей

Из книги автора

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


5. Понятие индексов

Из книги автора

5. Понятие индексов Создание ключей в базовых отношениях автоматически связано с созданием индексов.Дадим определение понятия индекса.Индекс – это системная структура данных, в которой размещается обязательно упорядоченный перечень значений какого-либо ключа со


Понятие текстуры

Из книги автора

Понятие текстуры Бытует мнение, что текстура — это изображение, накладываемое на трехмерную модель. Данное утверждение совершенно не верно. Изображение, накладываемое на модель в рамках текстуры, называется картой (Map), понятие же текстуры — шире.Текстура в 3ds Max


Пример 25-8. Пример реализации алгоритма Решето Эратосфена

Из книги автора

Пример 25-8. Пример реализации алгоритма Решето Эратосфена #!/bin/bash# sieve.sh# Решето Эратосфена# Очень старый алгоритм поиска простых чисел.# Этот сценарий выполняется во много раз медленнее# чем аналогичная программа на C.LOWER_LIMIT=1 # Начиная с 1.UPPER_LIMIT=1000 # До 1000.# (Вы можете


2. Представление чисел в ЭВМ. Формализованное понятие алгоритма

Из книги автора

2. Представление чисел в ЭВМ. Формализованное понятие алгоритма 32-разрядные процессоры могут работать с оперативной памятью емкостью до 232-1, а адреса могут записываться в диапазоне 00000000 – FFFFFFFF. Однако в реальном режиме процессор работает с памятью до 220-1, а адреса


6. Понятие вспомогательного алгоритма

Из книги автора

6. Понятие вспомогательного алгоритма Алгоритм решения задачи проектируется путем декомпозиции всей задачи в отдельные подзадачи. Обычно подзадачи реализуются в виде подпрограмм.Подпрограмма – это некоторый вспомогательный алгоритм, многократно использующийся в