Абстрактная машина доступа к данным
Абстрактная вычислительная машина
Компьютерные технологии плотно вошли в жизнь людей. Для выполнения различных задач электронная техника имеет операционную систему – набор программ для взаимодействия пользователя и ресурсов компьютера. Этот факт кажется очевидным, но так было не всегда.
Краткая история создания
Разработал концепцию универсальной пошаговой вычислительной системы английский математик Алан Тьюринг. Идея линейного алгоритма была предложена им в 1936 году. Ученый хотел создать наиболее простой способ для решения широкого спектра задач, своего рода вычислительный мозг, эквивалентный человеческому.
Тьюринг доказал, что механизм машинных вычислений очень прост и имеет последовательную структуру, в которой следующее действие вытекает из предыдущего. Таким образом, вычислительная машина Тьюринга способна создавать иерархические модели данных и принимать решения.
Вначале исследования Тьюринга были теоретическими. Практическим воплощение занялись ученые Британии и Америки уже после окончания Второй мировой войны. Большую роль в создании основ цифровой электроники сыграл Джон Ф. Нейман.
К процессу подключились многие ученые, внося предложения и корректировки. В результате появились также машины Поста, Маркова, Минского и др.
Абстрактная вычислительная машина
Машина Тьюринга или абстрактная вычислительная машина – это не техническая единица, а математическое понятие, алгоритмическая модель вычислений, абстрагированная от конечности и ограниченности технического устройства. Она обладает бесконечной памятью, в ячейках которой находятся инструкции и данные. Символы последовательно считываются сканером, после чего заполняется следующая ячейка.
Проще говоря, абстрактная машина является универсальной системой выполнения заданий. После ввода начальных данных программа выдает результат.
В зависимости от выполняемых функций абстрактные вычислительные машины подразделяются на классы и типы. Самый высокий уровень абстракций работает с теоретическими запросами, матрицами и т.д. Машины с низким уровнем абстракций применяют для оценивания сложности алгоритмов.
ВЫЧИСЛИТЕЛЬНАЯ МАШИНА АБСТРАКТНАЯ
В. м. а. можно разделить на классы по уровню абстракции, а также по типу обрабатываемой информации. Ниже перечислены основные классы В. м. а.
Лит.:[1] Барздинь Я. М., «Докл. АН СССР», 1964, т. 157, № 3, с. 542-45; [2] Ван Вейнгаарден А. и др., Сообщение об алгоритмическом языке АЛГОЛ-68, «Кибернетика», 1969, № 6, с. 23-144; 1970, № 1, с. 13-160; [3] Ершов А. П., «Проблемы кибернетики», 1960, вып. 3, с. 5-48;
[4] Колмогоров А. Н., Успенский В. А., «Успехи матем. наук», 1958, т. 13, № 4, с. 3-28; [5] Минский М., Вычисления и автоматы, пер. с англ., М., 1971; [6] Трахтенброт Б. А., Алгоритмы и вычислительные автоматы, М., 1974; [7] Наrtmanis Т., «Math. Syst. Theory», 1971, v. 5, № 3, p. 232-45; [8] Wegnеr P., «Computing Surveys», 1972, v. 4, № 1, p. 5- 63. В. А. Непомнящий.
Полезное
Смотреть что такое «ВЫЧИСЛИТЕЛЬНАЯ МАШИНА АБСТРАКТНАЯ» в других словарях:
Абстрактная вычислительная машина — теоретическое построение, с помощью которого вводится строгое, математическое определение алгоритма. См. также: Абстрактные вычислительные машины Алгоритмы Финансовый словарь Финам … Финансовый словарь
Машина Тьюринга для умножения чисел — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… … Википедия
Машина тьюринга — (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча Тьюринга, способна … Википедия
Машина Поста — (МП) абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм». Содержание 1 Принцип… … Википедия
Машина поста — (МП) абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм». Содержание 1 Принцип… … Википедия
Машина Тьюринга — Художественное представление машины Тьюринга Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма … Википедия
Детерминированная машина Тьюринга — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… … Википедия
Тьюринга машина — Машина Тьюринга (МТ) абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча… … Википедия
Оптимизация (вычислительная техника) — Это статья об оптимизации программ и данных на всех этапах программирования. Об оптимизациях, применяемых компиляторами, см.: Оптимизация компилятора. В информатике оптимизацией называется процесс модификации системы для улучшения её… … Википедия
Оптимизация вычислений и абстрактные машины
Как было показано в ходе предыдущей лекции, такая формализация вычислительной машины как категориальная абстрактная машина позволяет вполне удовлетворительно реализовать модель транслятора языка функционального программирования.
Кроме того, как показывает практика, именно КАМ больше всего подходит для использования в качестве виртуальной машины при реализации современных языков функционального программирования (в частности, языка CaML), в том числе с объектными расширениями (в частности, языка Object CaML).
Перечислим наиболее существенные (с учетом целей и задач нашего курса) из этих недостатков.
Наконец, очевидно, что повторяющиеся фрагменты программы требуют многократных вычислений, поскольку порядок вычислений предопределен и заведомо не оптимален.
Наконец, следует рассмотреть вопрос о реализации на основе категориальной абстрактной машины поддержки вычислений по необходимости, иначе называемых «ленивыми» (lazy).
Приступим к реализации усовершенствований категориальной абстрактной машины с целью оптимизации стратегии вычислений.
Заменим «встроенные» в систему команд категориальной абстрактной машины одноместные функции на двухместные.
В частности, в целях экономии времени, рассуждая без ограничения общности, приведем пример записи двухместной функции сложения:
C учетом характеристических равенств для категориальной абстрактной машины, выведенных в ходе предыдущих лекций, получим соотношение
| Старое состояние КАМ | Новое состояние КАМ | ||||
|---|---|---|---|---|---|
| Терм | Код | Стек | Терм | Код | Стек |
| true | if abc | sm | S | a c | m |
| false | if abc | sm | S | b c | m |
| (a,b) | add c | S | C | S | |
| (a,b) | eq c | S | true/false | C | S |
«Запрограммируем» ту же задачу в усовершенствованной версии КАМ :
Как видно, объем программы сократился более чем втрое.
| Старое состояние КАМ | Новое состояние КАМ | ||||
|---|---|---|---|---|---|
| Терм | Код | Стек | Терм | Код | Стек |
| T | dum c | sm | $Y | C | S |
| [a:b] | wind c | (t$Y)S | (t.[a:b]) | C | S |
Как видно из приведенной таблицы, пространство состояний категориальной абстрактной машины расширено посредством введения операций wind и dum для обработки рекурсивных объектов.
При вычислении с вызовом по имени (call-by-name) до вычисления операции аппликации необходима подстановка термов вместо всех вхождений формальных параметров перед означиванием. Именно эта стратегия лежит в основе «ленивых» (lazy), «отложенных» (delayed) или «замороженных» (frozen) вычислений, которые принципиально необходимы для обработки потенциально бесконечных структур данных.
Наконец, при вычислении с вызовом по необходимости (call-by-need) ранее вычисленные значения аргументов сохраняются в памяти компьютера только в том случае, если необходимо их повторное использование.
Архитектурное проектирование ПО: структурирование системы, модели управления и модульная декомпозиция
Архитектурным проектированием называют первый этап процесса проектирования, на котором определяются подсистемы, а также структура управления и взаимодействия систем.
Подсистема — это система, операции которой не зависят от сервисов, предоставляемых другими подсистемами. Подсистемы состоят из модулей — системных компонентов, предоставляющих один или несколько сервисов для других модулей.
Модели архитектуры могут зависеть от нефункциональных требований к разрабатываемой системе:
Contents
Структурные модели [ ]
В статических структурных моделях представлены подсистемы или компоненты, разрабатываемые в дальнейшем независимо.
Репозиторий [ ]
Модель репозитория основана на совместном использовании данных. Все совместно используемые данные хранятся в центральной базе данных, доступной всем подсистемам, каждая из которых имеет также собственную базу данных. Взаимообмен даными между подсистемами происходит с помощью передачи сообщений.
Плюсы [ ]
Минусы [ ]
Клиент—сервер [ ]
Модель клиент—сервер — это модель распределённой системы, в которой показано распределение данных и процессов между несколькими процессорами. Модель включает три основных компонента:
Плюсы [ ]
Минусы [ ]
Абстрактная машина [ ]
Модель абстрактной машины организует систему в виде набора уровней, каждый из которых предоставляет свои сервисы. Каждый уровень определяет абстрактную машину, машинный язык которой (сервисы) используется для реализации следующего уровня абстрактной машины (ср. с Java-моделью исполнения программ).
Плюсы [ ]
Минусы [ ]
Модели управления [ ]
Разработчик архитектуры должен организовать подсистемы согласно некоторой модели управления, которая дополняла бы имеющуюся модель структуры. В моделях управления проектируется поток управления между подсистемами.
Централизованное управление [ ]
Одна из подсистем полностью отвечает за управление, запускает и завершает работу остальных подсистем. Различают два класса централизованного управления:
Управление, основанное на событиях [ ]
Вместо одной подсистемы, ответственной за управление, на внешние события может отвечать любая подсистема. События, на которые реагирует система, могут происходить либо в других подсистемах, либо во внешнем окружении системы. Здесь также разделяют два класса моделей:
Модели модульной декомпозиции систем [ ]
После этапа разработки системной структуры следует этап декомпозиции подсистем на модули. На этом этапе распространены две модели проектирования.
Объектно-ориентированная модель [ ]
В этой модели система структурирована в виде совокупности слабо связанных объектов с чётко определёнными интерфейсами. Объекты вызывают сервисы, предоставляемые другими объектами.
Модель потоков данных [ ]
Модули в данной модели выполняют функциональные преобразования. Данные, поступающие на вход системы, проходят через все преобразования и достигают выхода системы.
Проблемно-зависимые архитектуры [ ]
Наряду с основными моделями, используются архитектурные модели, характерные для конкретной предметной области приложения. Эти модели называются проблемно-зависмыми архитектурами.
Модели классов систем [ ]
Модели классов систем отображают классы реальных систем, вобрав в себя основные характеристики этих классов. Как правило, модели классов встречаются в системах реального времени. Модель компилятора — наиболее известный пример этой модели.
Базовые модели [ ]
Базовые модели представляют собой идеализированную архитектуру, в которой отражены все особенности, присущие системам, работающим в данной предметной области. Примером такой архитектуры может служить модель OSI.
Базовые модели обычно не рассматриваются в качестве методов реализации; их основное назначение — служить эталоном для сравнения различных систем в какой-либо предметной области.
ВЫЧИСЛИТЕЛЬНАЯ МАШИНА АБСТРАКТНАЯ
ВЫЧИСЛИТЕЛЬНАЯ МАШИНА АБСТРАКТНАЯ, абстрактная машина,- математическое понятие, к-рое описывает модель вычислительной машины, абстрагируясь от ограниченности емкости запоминающих устройств и других технич. параметров вычислительных машин. В отличие от последних, В. м. а. может вычислять функции, определенные на бесконечной области конструктивных объектов (напр., целых чисел, слов в конечном алфавите, конечных графов, бесконечных деревьев и т. д.). В. м. а. употребляется как понятие, уточняющее интуитивное понятие алгоритма, для исследования вопросов существования алгоритма (т. е. разрешимости или неразрешимости алгоритмических проблем), качества алгоритма (т. е. оценок сложности различных параметров алгоритма), формализации семантики алгоритмических языков, моделирования одних классов В. м. а. другими (напр., с целью так наз. «распараллеливания» алгоритмов).
В. м. а. можно разделить на классы по уровню абстракции, а также по типу обрабатываемой информации. Ниже перечислены основные классы В. м. а.
Лит.: [1] Барздинь Я. М., «Докл. АН СССР», 1964, т. 157, № 3, с. 542-45; [2] Ван Вейнгаарден А. и др., Сообщение об алгоритмическом языке АЛГОЛ-68, «Кибернетика», 1969, № 6, с. 23-144; 1970, № 1, с. 13-160; [3] Ершов А. П., «Проблемы кибернетики», 1960, вып. 3, с. 5-48; [4] Колмогоров А. Н., Успенский В. А., «Успехи матем. наук», 1958, т. 13, № 4, с. 3-28; [5] Минский М., Вычисления и автоматы, пер. с англ., М., 1971; [6] Трахтенброт Б. А., Алгоритмы и вычислительные автоматы, М., 1974; [7] Hartmanis Т., «Math. Syst. Тhеоrу», 1971, v. 5, № 3, p. 232-45; [8] Wegner P., «Computing Surveys», 1972, v. 4, № 1, p. 5-63.