Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Модели вычисленийСтр 1 из 3Следующая ⇒
В данной главе рассмотрим различные способы представления вычислений (обработки данных) в виде моделей; эти способы связаны с различной природой вычислений. Модель – математическая абстракция для класса объектов (процессов), в которой выделяются существенные свойства класса и отбрасываются несущественные; чем грубее модель, тем шире класс. Хорошо сформулированная модель обладает ясным физическим смыслом и адекватна (соответствует, отвечает требованиям точности) данному классу. Например, в планетарной модели небесные тела представляются в виде материальных точек, не имеющих размеров, но имеющих конкретную массу; эта модель позволяет достаточно точно предсказывать, например, лунные затмения. Целью построения моделей вычислений является, в первую очередь, возможность уточнения понятия " алгоритм", что необходимо для получения доказательного ответа на главный вопрос теории алгоритмов: существует или нет алгоритм для данного класса задач? С прикладной точки зрения важно также, что подходящая модель вычислений может быть использована и для оценки сложности алгоритма. Для вычислений в широком смысле построены разнообразные модели, учитывающие характер вычислений (численные, логические, символьные), разрядность чисел (битовые либо байтовые), постоянство длины обрабатываемых слов в ЭВМ и т. д. Ниже рассматриваются 2 модели вычислений в узком смысле: · ассоциативные исчисления; · рекурсивные функции, а также 2 модели дискретной переработки информации – автоматы и машины Тьюринга. Логические алгоритмы содержат инструкции, относящиеся не к числам, а к объектам любой природы. Примерами логических алгоритмов могут служить алгоритм поиска пути в лабиринте, игровые алгоритмы, алгоритм переключения светофора и т. д. Моделью логических вычислений являются ассоциативные исчисления. Численные алгоритмы сводят решение поставленной задачи к арифметическим действиям над числами. Пример — алгоритм Евклида для нахождения наибольшего общего делителя двух заданных положительных чисел. К численным алгоритмам сводится решение многих задач: вычисление корней алгебраических уравнений, решение систем уравнений, численное интегрирование и т. п. Моделью таких вычислений являются рекурсивные функции. Очень широкий класс задач связан с дискретной переработкой информации (символов). Это, например, кодирование и декодирование сообщений. В качестве моделей таких преобразований используются конечные автоматы. Автоматная модель с расширенными возможностями – машина Тьюринга – позволяет не только реализовать различные вычисления и преобразования информации, но и проверить существование алгоритма для данного класса задач.
|