Типовые алгоритмические конструкции
Для описания алгоритмических конструкций могут быть использованы следующих виды обозначений: логические (словесные), графические (графы и диаграммы), табличные и специальные обозначения.
Для графического изображения основных операций на схеме алгоритма приняты обозначения основных блоков, показанные на рисунке 15.
Последовательное и/или параллельное соединение различных блоков позволяет организовать вычисление любых частично-рекурсивных функций. Общую схему соединения нескольких блоков от “начало” до “конец” называют блок-схемой алгоритма.
Рисунок 15. - Основные блоки схемы алгоритма
Выделяют также три основных типа алгоритмов:
· Линейные (следования);
· Разветвляющиеся (развилка);
· Циклические.
Ниже на рисунке 1.1 дан пример описания основных типов алгоритма в виде блок-схемы.
Блок-схема – это ориентированный граф, вершины которого могут быть одного из ниже представленных базовых типов (всегда должен быть один вход и один выход).
Рисунок 1.1 – Примеры блок-схем
1 схема – функциональная вершина. Реализуется композитная функция:
F: x --> Y
Алгоритм называется линейным, вычисления называются аддитивными (последовательными).
2 схема – предикатная вершина. Реализуется предикатная функция (выбор или альтернатива):
P: x - -> (t, f)
Алгоритм называется разветвляющимся, вычисления называются альтернативными.
3 схема – итерационная вершина. Реализуется итерационная функция:
|
|
|
I: x - -> (Yi, Yi+1)
Алгоритм называется циклическим, вычисления называются повторяющимися (итерационными).
Структурная блок-схема – это блок-схема, которая может быть выражена как композиция из трех представленных базовых блоков.
История развития понятия алгоритма
В двадцатых годах нашего века задача точного определения понятия алгоритма стала одной из центральных математических проблем. Решение этой проблемы развивалось по двум направлениям.
Первое направление было основано на точном описании совокупности числовых функций, которые можно вычислять посредством алгоритма, они назывались вычислимыми функциями.
Второе направление развивало точное описание процессов, которые может совершать достаточно просто устроенная «машина». В 1934 г. Курт Гёдель (1906—1978) описал класс числовых функций, вычислимых в некоторой формальной системе (исчислении). В 1936 г. Алонзо Чёрч (1903) предложил другую формальную систему, названную им λ-исчислением. В 1936 г. Клини ввел строгое понятие класса рекурсивных (от лат. recurcio —возвращение) функций, которые вычислимы при помощи алгоритмов. Им было доказано совпадение классов вычислимых функций, построенных Геделем и Черчем с классом рекурсивных функций.
|
|
|
В 1936 г. Черч выдвинул гипотезу, которая стала называться тезисом Черча: «Класс алгоритмически вычислимых числовых функций совпадает с классом рекурсивных функций». Тезис Черча не может быть доказан, так как в нем используется интуитивное (неточное) понятие алгоритма. Однако исследования, проводившиеся математиками в течение последних 50 лет, не смогли опровергнуть тезис, то есть предложить такую числовую функцию, которая была бы с одной стороны, вычислима некоторым интуитивным алгоритмом, а с другой стороны, не была бы представима точным описанием некоторой рекурсивной функции. Все математики считают точное понятие рекурсивной функции научным эквивалентом интуитивного понятия функции, вычислимой алгоритмом.
В 1936 г. английский математик Алан Матисон Тьюринг (1912—1954) предложил точное описание алгоритма в виде некоторой машины — «машины Тьюринга», которая использует конечное множество символов, имеет процессор, выполняющий предписания определенного вида, устройство для хранения входных, промежуточных и выходных результатов. В 1937 г. Тьюринг доказал, что его машина может вычислять совокупность функций, эквивалентную λ-исчислению Черча.
|
|
|
В 1936 г. американский математик Эмиль Леон Пост (1897—1954) независимо от Тьюринга предложил свою конструкцию машины для уточнения понятия алгоритма. Машины Поста и Тьюринга оказались эквивалентными по своим вычислительным возможностям рекурсивным функциям.
В 1951 г. советский математик Андрей Андреевич Марков-сын (1903—1979) предложил принцип нормализации алгоритмов для приведения их к стандартной форме, которая получила название нормального алгорифма Маркова (НАМ).
Алгоритмические модели и их представление
Модель (фр. modèle, от лат. modulus — «мера, аналог, образец») — это упрощенное представление реального устройства и/или протекающих в нем процессов, явлений.
Построение и исследование моделей, то есть моделирование, облегчает изучение имеющихся в реальном устройстве (процессе, …) свойств и закономерностей. Применяют для нужд познания (созерцания, анализа и синтеза).
Моделирование является обязательной частью исследований и разработок, неотъемлемой частью нашей жизни, поскольку сложность любого материального объекта и окружающего его мира бесконечна вследствие неисчерпаемости материи и форм её взаимодействия внутри себя и с внешней средой.
|
|
|
Алгоритмическая модельили модель алгоритмов - это упрощенное представление алгоритма или алгоритмического процесса на основе чего-либо (математической конструкции или гипотетического/реального механизма).
К алгоритмическим моделям относятся такие модели, в которых критерии и ограничения описываются математическими конструкциями, включающими логические условия, приводящие к разветвлению вычислительного процесса, и так называемые имитационные модели — моделирующие алгоритмы, имитирующие поведение элементов изучаемого объекта и взаимодействие между ними в процессе функционирования.
Следующим признаком, по которому можно различать ЭММ, является связь с фактором времени:
· динамические — модели, в которых входные факторы, а, следовательно, и результаты моделирования явно зависят от времени;
· статические — модели, в которых зависимость от времени отсутствует совсем либо проявляется слабо или неявно.
Понятие "алгоритм" было принято для обозначения совокупности правил вычислительных процессов, в которых искомые результаты практических задач находят последовательно из исходных данных по определенным правилам и инструкциям.
Процесс создания компьютерной программы для решения какой-либо практической задачи включает в себя формализацию этой задачи, разработку вычислительного алгоритма её решения, написание и отладку программы, наконец, решение поставленной задачи.
Основными объектами алгоритма стали данные. Для уточнения этого понятия фиксируют конечный алфавит символов (цифр, букв и т.п.) и правил построения алгоритмических объектов. Такими объектами вычислительных алгоритмов являются списки и стеки, множества и отображения. Процесс преобразования алгоритмических объектов от исходных данных до искомого результата выполняется дискретно или, как говорят, "по шагам". Преобразование за один шаг носит локальный характер, т.е. этому преобразованию подвергается не весь объект, а лишь его часть: элемент стека или компонента кортежа, столбец или строка матрицы и т.п. Последовательность шагов детерминирована, т.е. после каждого шага указывается точно, что и как следует выполнять на следующем шаге. Процесс преобразования алгоритмического объекта, включающий в себя заданную последовательность шагов, называют алгоритмическим процессом. Механизм реализации алгоритмического процесса удобнее проследить на алгоритмических моделях, использующих конечные наборы простейших объектов и конечные наборы элементарных действий. Выделяют три основных класса или типа алгоритмических моделей:
1. Вычислительные алгоритмы. Предполагается, что любые данные можно закодировать числами, а всякое их преобразование становится в этом случае арифметическим вычислением. Алгоритмом в таких моделях является вычисление значения некоторой числовой функции, а его элементарными шагами – арифметические операции. Последовательность шагов определяется способами суперпозиции и рекурсии.
2. Символьные алгоритмы. Задается алфавит, конечное множество допустимых подстановок и некоторое правило, определяющее порядок применения подстановок (например, нормальный алгоритм Маркова, формальные грамматики).
3. Алгоритмы для исполнителей. Алгоритм задается последовательностью правил (инструкций), которые может выполнить машина, удовлетворяющая требованиям простоты и универсальности (абстрактные машины Тьюринга и Поста, конечные или магазинные автоматы).
В теории алгоритмов доказана сводимость одного типа модели к другой, т.е. всякий алгоритм, описанный средствами одной модели, может быть описан также средствами другой. Рассмотрим подробнее реализацию алгоритмических процессов для вычисления числовых функций на данных трех типах моделей алгоритмов.
Вычислительные алгоритмы
Первый тип модели алгоритма основывается на вычислительных алгоритмах. Выберем в качестве числовой функции рекурсивные функции. Тогда в данном типе алгоритмической модели понятие алгоритма будет связано с элементарными вычислительными операциями на множестве целых положительных чисел.
Напомним, что общее определение рекурсии как процесс повторения элеменубратьто общее определение рекурсии как виде блок-схемы.
возврат к старой) и перетов самоподобным образом. Например, если два зеркала установить друг напротив друга, то возникающие в них вложенные отражения суть одна из форм бесконечной рекурсии
Рекурсия[i56] здесь есть способ вычисления значения числовой функции по известным значениям независимых переменных аргумента и известному значению функции в некоторой исходной точке. Поэтому любую вычислимую функцию, заданную на множестве натуральных чисел и принимающую значения на том же множестве принято называть рекурсивной функцией.
Если значения функции найдены не для всех значений области определения, то её называют частично рекурсивной функцией и, наоборот, если они найдены для всех значений области определения, то её называют общерекурсивной функцией.
Для формального построения функций вычислимых алгоритмом необходимо иметь:
1) набор элементарных функций, которые изначально считаются вычислимыми;
2) набор элементарных операций над функциями, при помощи которых можно строить более сложные вычислимые функции.
Для формирования механизма вычисления рекурсивных функций даны наборы простейших базовых функций: константы, тождества и следования и наборы элементарных операций: суперпозиции, рекурсии, минимизации и итерации.
Дата добавления: 2018-11-24; просмотров: 1033; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!