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

1. Гусаров В.М.Теория статистики: учеб. – М., Изд-во Юнити, 2006-463с.

2. Гинзбург А.И. Статистика: учеб. пособие для студ. вузов. – СПб.: Питер, 2007. – 128с.

3. Сборник задач по теории статистики: Учебное пособие/Под ред.проф. В.В. Глинского. – изд. 3-е. – М.: ИНФРА – М; Новосибирск: Сибирское соглашение, 2006. – 257с.

4. Статистика: учебник для вузов/под. ред. И.И. Елисеевой. – М.: Проспект: Велби, 2007. – 448с.

5. Шмойлова Р.А.Практикум по теории статистики: учеб. пособ. – М., Изд-во Финансы и статистика, 2006 – 656с.

ТЕМА 3: АЛГОРИТМ КАК АБСТРАКТНАЯ МАШИНА

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

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

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

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

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

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

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

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

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

Пусть исходные данные из области определения алгоритма представлены посредством алфавита А и образуют при этом конечную последовательность знаков { a₁…a_n } – такая последовательность называется словом. В результате выполнения алгоритма сформируется новое слово { b₁…b_m }, представленное, в общем случае, в другом алфавите B. На первый взгляд для проведения такого преобразования в качестве элементарных выделяются следующие операции (шаги):

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

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

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

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

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

Поиск по сайту: