МОДЕЛИ ВЫЧИСЛЕНИЙ

В данной главе рассмотрим различные способы представления вычислений (обработки данных) в виде моделей;эти способы связаны с различной природой вычислений.

Модель – математическая абстракция для класса объектов (процессов), в которой выделяются существенные свойства класса и отбрасываются несущественные; чем грубее модель, тем шире класс. Хорошо сформулированная модель обладает ясным физическим смыслом и адекватна (соответствует, отвечает требованиям точности) данному классу. Например, в планетарной модели небесные тела представляются в виде материальных точек, не имеющих размеров, но имеющих конкретную массу; эта модель позволяет достаточно точно предсказывать, например, лунные затмения.

Целью построения моделей вычислений является, в первую очередь, возможность уточнения понятия "алгоритм", что необходимо для получения доказательного ответа на главный вопрос теории алгоритмов: существует или нет алгоритм для данного класса задач? С прикладной точки зрения важно также, что подходящая модель вычислений может быть использована и для оценки сложности алгоритма.

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

Ниже рассматриваются 2 модели вычислений в узком смысле:

· ассоциативные исчисления;

· рекурсивные функции,

а также 2 модели дискретной переработки информации – автоматы и машины Тьюринга.

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

Численные алгоритмы сводят решение поставленной задачи к арифметическим действиям над числами. Пример — алгоритм Евклида для нахождения наибольшего общего делителя двух заданных положительных чисел. К численным алгоритмам сводится решение многих задач: вычисление корней алгебраических уравнений, решение систем уравнений, численное интегрирование и т. п. Моделью таких вычислений являются рекурсивные функции.

Очень широкий класс задач связан с дискретной переработкой информации (символов). Это, например, кодирование и декодирование сообщений. В качестве моделей таких преобразований используются конечные автоматы.

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