русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Определение алгоритма на основе рекурсивных функций


Дата добавления: 2013-12-23; просмотров: 975; Нарушение авторских прав


Детерминированность. Процесс применения правил к исходным данным (путь решения задачи) определен однозначно или по другому - каждый шаг однозначно определяется состоянием системы

Формальность

Понятность.

Результативность.

Дискретность.

Детерминированность.

Массовость

Конечный набор точных и понятных предписаний (правил, инструкций, команд), позволяющих механически решать конкретную задачу из определенного класса однотипных задач.

Вплоть до 30-х годов прошлого столетия понятие алгоритма носило сугубо интуитивный характер.


Под алгоритмом понимали:

 

Основными свойствами такого «интуитивного» понятия алгоритма являются:

Массовость. Означает, что алгоритм применим к целому классу задач, а при решении конкретной задачи из класса исходные данные могут меняться в определенных пределах или по другому алгоритм применим для разных наборов исходных.

Дискретность. Означает, что путь решения задачи определен в виде последовательности шагов – четко разделенных друг от друга предписаний. Только выполнив одно предписание, можно приступить к выполнению следующего.

Результативность. На каждом шаге процесса применения правил известно, что считать результатом этого процесса, а сам процесс должен закончиться за конечное число шагов.

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

Формальность - инструкции алгоритма могут выполняться формально (бездумно)

Для задач, имеющих положительное решение, этого определения достаточно. Другое дело, когда задача или класс задач не имеют решения. В этом случае требуется строго формализованное понятие алгоритма, чтобы иметь возможность доказать его отсутствие. Определение такого понятия алгоритма стала одной из центральных математических проблем. Решение было получено в середине 30-х годов в работах известных математиков, в двух эквивалентных формулировках: на основе особого класса арифметических функций, называемых рекурсивными (Д. Гильберт, К. Гедель, А. Черч, С. Клини), и на основе абстрактных автоматов (Э. Пост и А. Тьюринг).



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

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

Функция, для которой существует эффективная процедура ее вычисления на основе рекурсии, называется рекурсивной.

Класс рекурсивных функций тождественен с классом всюду определенных вычислимых функций – тезис Черча.

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

Все частичные функции, вычислимые посредством алгоритмов, являются частично рекурсивными – тезис Клини.

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

 

Определение алгоритма на основе абстрактных автоматов
(машины Тьюринга)

Алгоритмические процессы – это процессы, которые может совершать подходяще устроенная «машина».

Под «машиной» в данном случае подразумевается некоторый абстрактный, существующий лишь в воображении автомат.

В общем случае такая машина состоит из следующих частей:

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

- головка чтения/записи, вдоль которой может перемещаться лента (или которая может перемещаться относительно информационной ленты);

- устройство управления, которое в каждый рассматриваемый момент находится в некотором «состоянии». Устройство управления может находиться в некотором конечном числе состояний, если это состояние заключительное, машина заканчивает работу.

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

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

Интуитивное понимание машины Тьюринга:
имеется бесконечная лента, разделённая на клетки. По клеткам ездит каретка. Прочитав букву, записанную в клетке, каретка движется вправо, влево или остаётся на месте, при этом буква заменяется новой. Некоторые буквы останавливают каретку и завершают работу.

На базе теорий рекурсивных функций и абстрактных автоматов появилось целое математическое направление – теория алгоритмов, в которой в основу определения алгоритма было поставлено особое соответствие между словами в том или ином абстрактном алфавите (А. Марков, Л. Калужнин). Теория алгоритмов оказалась тесно связанной не только с теоретической математикой (математической логикой, алгеброй, геометрией, анализом), но и с рядом областей лингвистики, экономики, физиологии мозга, философии, естествознания. Примером задачи этой области может служить описание алгоритмов, реализуемых человеком в процессе умственной деятельности.

А.А. Марков –

Алгоритм– это предписание, ведущее от исходных данных к искомому результату и обладающее свойствами: определенности, массовости и результативности

 

· определенность (общепонятность и точность, не оставляющая места для произвола),

· массовость (возможность применения ко всем процессам данного класса),



<== предыдущая лекция | следующая лекция ==>
Сетевые операционные системы | Правила выполнения соединений


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.003 сек.