Студопедия
Обратная связь


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram


Сопоставление алгоритмических моделей

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

Все алгоритмические задачи принято делить на два больших класса: первый - это задачи, связанные с вычислением значения функции; второй - задачи, связанные с распознаванием принадлежности объекта заданному множеству (что равносильно получению ответа на вопрос: обладает ли объект заданным свойством?). В первом случае алгоритм Q начинает работать с исходными данными - словом Р, составленным на основе алфавита А, и за конечное число шагов (преобразований) он должен остановиться и выдать результат Pk = fQ(P). Результат зависит (является функцией) от исходного слова, а также последовательности обработки, т.е. самого алгоритма. При этом вычисление понимается в широком смысле - как алфавитное преобразование.

В задачах, отнесенных ко второму классу, в результате выполнения алгоритма получается ответ на вопрос: «Истинно ли высказывание, что хМ»? или, что то же самое, проверяется истинность предиката хМ и выдается один из двух возможных результатов: ИСТИНА или ЛОЖЬ. Этот класс можно считать разновидностью первого, поскольку предикат - это функция, принимающая два значения в зависимости от условия. Тем не менее, разделение этих классов задач полезно, так как приводит к двум важным понятиям теории алгоритмов - вычислимая функция и разрешимое множество.

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

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

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





 

Читайте также:

Глава 10. Модели и системы

Определение системы

Классификация данных. Проблемы представления данных

Коды, исправляющие одиночную ошибку

Коды, обнаруживающие ошибку

Вернуться в оглавление: Теоретические основы информатики

Просмотров: 1533

 
 

© studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам. Ваш ip: 54.162.168.187