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

Сколько стоит твоя работа?
Тип работы:*
Тема:*
Телефон:
Электронная почта:*
Телефон и почта ТОЛЬКО для обратной связи и нигде не сохраняется.

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

Общие подходы

Точное описание класса частично рекурсивных функций вместе с тезисом Черча дает одно из возможных решений задачи об уточнении понятия алгоритма. Однако это решение не вполне прямое, так как понятие вычислимой функции является вторичным по отношению к понятию алгоритма. Спрашивается, нельзя ли уточнить непосредственно само понятие алгоритма и уже затем при его помощи определить точно и класс вычислимых функций? Такое направление поиска привело к построению иного, нежели рекурсивные функции, класса моделей алгоритма. Основная его идея состоит в том, что алгоритмические процессы - это процессы, которые может осуществлять определенным образом устроенная машина, моделирующая тем самым выполнение отдельных операций человеком. Функционирование такой машины и есть выполнение некоторого алгоритма. Исходя из свойств алгоритма (п.7.1), можно сформулировать общие требования к таким машинам:

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

* В дальнейшем указание по выполнению шага будем называть командой.

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

3) перед началом работы машине предоставляются исходные данные из области определения алгоритма;

4) за конечное число шагов работы машины должен быть получен результат (или информация о том, что считать результатом);

5) машина должна быть универсальной, т.е. такой, чтобы с ее помощью можно было бы выполнить любой алгоритм.

Чем проще структура (т.е. устройство) описанной машины и чем элементарнее ее шаги, тем больше оснований считать, что ее работа и есть выполнение алгоритма. Чтобы ответить на вопрос, какие шаги работы машины следует отнести к элементарным, вернемся к тому обстоятельству, что нас интересует преобразование информации, представленной с помощью некоторого конечного алфавита. Требование конечности алфавита является очевидным следствием того обстоятельства, что решение должно быть получено за конечное число шагов. Если информация не представлена в дискретной форме, например, вещественное число, то его обработка в общем случае может содержать бесконечное число шагов (например, нахождение цифр числа п или извлечение квадратного корня из числа 2). Таким образом, алгоритм оказывается конечной последовательностью действий, производимых над данными, представленными с помощью конечного алфавита. С учетом сказанного становится понятным определение алгоритма, которое дает В. М. Глушков [12, с.38]:

Алгоритм - это любая конечная система правил преобразования информации (данных) над любым конечным алфавитом.

Пусть исходные данные из области определения алгоритма представлены посредством алфавита А и образуют при этом конечную последовательность знаков {a1an} - такая последовательность называется словом. В результате выполнения алгоритма сформируется новое слово {b1...bm}, представленное, в общем случае, в другом алфавите 6. На первый взгляд для проведения такого преобразования в качестве элементарных выделяются следующие операции (шаги):

1) замена одного знака исходного слова ai знаком bj из алфавита B;

2) удаление знака исходного слова;

3) добавление к исходному слову знака из алфавита B.

Однако если в алфавиты включен знак, имеющий смысл пустого знака, добавление которого к слову слева или справа не изменяет этого слова (аналог числового нуля), то легко видеть, что операция (2) есть ни что иное, как замена ai пустым знаком, а операция (3) есть замена пустого знака знаком bj. Таким образом, все возможные алфавитные преобразования сводится к операции (1) -замене одного знака другим. Именно по этой причине функционирование абстрактной машины сводится к тому, что она обозревает символы (т.е. считывает и распознает их), записанные в памяти (в этом качестве выступает бесконечная лента), и в зависимости от своего состояния и того, каков обозреваемый символ, она заменяет его другим символом; после этого она переходит в новое состояние, читает следующий символ и т.д. до команды о прекращении работы. Поскольку подобные машины являются чисто модельным, теоретическим построением, они получили название абстрактных машин и рассматриваются в качестве одной из возможных универсальных алгоритмических систем.

Концепция алгоритма как абстрактной машины была выдвинута практически одновременно (1936 - 1937 гг.) английским математиком Аланом Тьюрингом и его американским коллегой Эмилем Постом. Высокая значимость их построений еще и в том, что они в абстрактной форме предвосхитили основные принципиальные черты реальных устройств по обработке данных (вычислительных машин), которые появились лишь спустя 8-9 лет.





 

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

Пример 2.8

Пример 4.15

Постановка задачи

Заключение

Пример 9.2.

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

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

 
 

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