АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. I. ОБЩИЕ ПОЛОЖЕНИЯ
  2. I. ОБЩИЕ СВЕДЕНИЯ
  3. I. Общие требования безопасности.
  4. I. ОБЩИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ КУРСОВОЙ РАБОТЫ
  5. II ОБЩИЕ НАЧАЛА ПУБЛИЧНО-ПРАВОВОГО ПОРЯДКА
  6. IV.1. Общие начала частной правозащиты и судебного порядка
  7. V.1. Общие начала правового положения лиц в частном праве
  8. VIII.1. Общие понятия обязательственного права
  9. Альтернативные подходы в области информационной подготовки
  10. Боги, общие для всех славян
  11. Бразилия: общие сведения
  12. Бытие, как объект философского исследования. Основные подходы к пониманию бытия в истории философии

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 


1 | 2 | 3 | 4 | 5 | 6 | 7 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)