Основные типы алгоритмических моделей. (с8)

Несмотря на принципиально разные модели вычислений, использующиеся в теории алгоритмов для определения термина алгоритм, интересным результатом является формулировка гипотезы об эквивалентности этих формальных определений, так как все они привели к одному и тому же классу алгоритмически вычислимых функций.

В теории алгоритмов были предугаданы основные концепции, заложенные в аппаратуру и языки программирования ЭВМ

Несмотря на то, что упомянутые выше алгоритмические модели математически эквивалентны, на практике они существенно различаются сложностными эффектами, возникающими при реализации алгоритмов, и породили различные направления в программировании.

Первый тип алгоритмических моделей.

Идея заключается в том, что поскольку алгоритм процедура механическая, поэтому её может выполнять некая абстрактная машина (АМ) (1936 год).

Поэтому идея вычислительной машины (ВМ), это идея не физическая или инженерная, а математическая.

Несмотря на то, что и АМ и реальные ВМ предназначены для одной и той же цели, а именно для реализации различного рода алгоритмов, тем не менее их акценты и различного рода свойства в некотором роде противоположны.

Для ВМ главными целями являются скорости и физические объемы вычислений, удобства программирования, что приводит к различного рода усложнениям.

С математической точки зрения акценты другие. Во-первых, в математике стремятся строить конструкции, о которых можно точно доказывать утверждения. Во-вторых, одна из основных идей математики это малыми средствами построить как можно больше.

Итак, АМ более простая, но способная выполнять все то, что делает более сложная машина просто гораздо дольше, т.е. в этой модели идея обычной прикладной эффективности не рассматривается.

Все основные свойства, связанные с возможностью и невозможностью решения задачи на АМ и которые можно доказать, верны и для сколь угодно мощных ЭВМ.

Принципы, положенные в основу функционирования алгоритмических машин.

1) Однопроцессорность - последовательная работа процессора только над одним потоком команд.

2) Управление процессором происходит под действием внешних либо внутренних событий.

3) Алгоритм понимается как последовательность переходов из одного состояния в другое состояние под действием команд или последовательностей команд.

4) Управляющие внутренние события воспринимаются как изменения в памяти процессора.