Файл: Алгоритмизация как обязательный этап разработки программы ( Свойства алгоритма ).pdf

Важный признак структуры данных - характер упорядоченности ее элементов. По этому признаку структуры можно разделить на линейные и нелинейные структуры.

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

Картезианские или прямоугольные структуры названы так по способу записи данных в виде прямоугольных таблиц. К ним относятся матрицы, векторы, множества.

Строчные структуры - одномерные, динамически изменяемые структуры данных, различающиеся способами включения и исключения элементов

Стек - это последовательность, в которой включение и исключение элемента осуществляются с одной стороны последовательности

Очередь - последовательность, в которую включают элементы с одной стороны, а исключают - с другой (рис. 1.7). Структура функционирует по принципу FIFO («первым пришел - первым обслуживается»).

Дек - линейная структура (последовательность), в которой операции включения и исключения элементов могут выполняться как с одного, так и с другого конца последовательности

В списковых структурах логический порядок данных определяется указателями.

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

Классификация нелинейных структур

Нелинейные структуры данных - это СД, у которых связи между элементами зависят от выполнения определенного условия. Пример нелинейных структур - деревья, графы, многосвязные списки.

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

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

Многосвязная структура обладает следующими свойствами:

1.на каждый элемент (узел, вершину) может быть произвольное количество ссылок;

2.каждый элемент может иметь связь с любым количеством других элементов;

3.каждая связка (ребро, дуга) может иметь направление и вес.

Типичными графами являются схемы авиалиний и схемы метро, а на географических картах - изображение железных или автомобильных дорог. Выбранные точки графа называются его вершинами, а соединяющие их линии - ребрами.

Сплетения (многосвязные списки) - это нелинейная структура данных, объединяющая такие понятия, как деревья, графы и списковые структуры.

Сплетения (плексы) обобщают понятия графов и списковых структур.

Основное свойство сплетений, отличное от других типов структур, - наличие у каждого элемента сплетения нескольких полей с указателями на другие элементы того же сплетения (рис. 1.12).

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

Плексы (сплетения) используются для представления различных семейств связей между индивидуумами и владельцами, отражают производственные и отраслевые связи и т. п.

1.2. Свойства алгоритма

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

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

Элементарность (понятность). Каждый шаг алгоритма должен быть простым, чтобы устройство, выполняющее операции, могло выполнить его одним действием.

Дискретность. Процесс решения задачи представляется конечной последовательностью отдельных шагов, и каждый шаг алгоритма выполняется за конечное (не обязательно единичное) время.

Детерминированность (определенность). Каждый шаг алгоритма должен быть однозначно и недвусмысленно определен и не должен допускать произвольной трактовки. После каждого шага либо указывается, какой шаг делать дальше, либо дается команда остановки, после чего работа алгоритма считается законченной.

Результативность. Алгоритм имеет некоторое число входных величин - аргументов. Цель выполнения алгоритма состоит в получении конкретного результата, имеющего вполне определенное отношение к исходным данным. Алгоритм должен останавливаться после конечного числа шагов, зависящего от данных, с указанием того, что считать результатом. Если решение не может быть найдено, то должно быть указано, что в этом случае считать результатом.

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

Эффективность. Одну и ту же задачу можно решить по-разному и соответственно за разное время и с различными затратами памяти. Желательно, чтобы алгоритм состоял из минимального числа шагов и при этом решение удовлетворяло бы условию точности и требовало минимальных затрат других ресурсов.

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

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

В настоящее время можно выделить три основных типа универсальных алгоритмических моделей. Они различаются исходными посылками относительно определения понятия алгоритма.

Первый тип связывает понятие алгоритма с наиболее традиционными понятиями математики - вычислениями и числовыми функциями. Второй тип основан на представлении об алгоритме как о некотором детерминированном устройстве, способном выполнять в каждый отдельный момент лишь весьма примитивные операции. Такое представление обеспечивает однозначность алгоритма и элементарность его шагов. Кроме того, такое представление соответствует идеологии построения компьютеров. Основной теоретической моделью этого типа, созданной в 1930-х гг. английским математиком Аланом Тьюрингом, является машина Тьюринга.

Третий тип — это преобразования слов в произвольных алфавитах, в которых элементарными операциями являются подстановки, т.е. замены части слова (под словом понимается последовательность символов алфавита) другим словом. Преимущества этого типа моделей состоят в его максимальной абстрактности и возможности применить понятие алгоритма к объектам произвольной (необязательно числовой) природы. Примеры моделей третьего типа - канонические системы американского математика Эмиля Л. Поста и нормальные алгоритмы, введенные советским математиком А. А. Марковым.

Модели второго и третьего типа довольно близки и отличаются в основном эвристическими акцентами, поэтому не случайно говорят о машине Поста, хотя сам Пост такое название не вводил.

1.3. Формы записи

Запись алгоритма на некотором языке представляет собой программу. Если программа написана на специальном алгоритмическом языке (например, на ПАСКАЛе или БЕЙСИКе), то говорят об исходной программе. Программа, написанная на языке, который непосредственно понимает компьютер (как правило, это двоичные коды), называется машинной, или двоичной.

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

Средства, используемые для записи алгоритмов, в значительной мере определяются тем, кто будет исполнителем.

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

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

Для записи алгоритмов используют самые разнообразные средства. Выбор средства определяется типом исполняемого алгоритма. Выделяют следующие основные способы записи алгоритмов:

вербальный - алгоритм описывается на человеческом языке;

символьный - алгоритм описывается с помощью набора символов;

графический - алгоритм описывается с помощью набора графических изображений.

Общепринятыми способами записи алгоритма являются графическая запись с помощью схем алгоритмов (блок-схем) и символьная запись с помощью какого-либо алгоритмического языка.

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

Начало и конец алгоритма обозначают с помощью одноименных символов.

Шаг алгоритма, связанный с присвоением нового значения некоторой переменной, преобразованием некоторого значения с целью получения другого значения, изображается символом «процесс».

Выбор направления выполнения алгоритма в зависимости от некоторых переменных условий изображается символом «решение».

Имеются примитивы для операций ввода и вывода данных, а также другие графические символы. В настоящий момент они определены стандартом ГОСТ 19.701-90 (ИСО 5807-85) «Единая система программной документации. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения». Всего сборник ЕСПД содержит 28 документов.

По схеме алгоритма легко составить исходную программу на алгоритмическом языке.

В зависимости от последовательности выполнения действий в алгоритме выделяют алгоритмы линейной, разветвленной и циклической структуры.

1.4. Базовые алгоритмические конструкции

Число реализованных конструкций конечно в любом языке программирования. Структурной элементарной единицей алгоритма является команда, обозначающая один элементарный шаг обработки или отображения информации. Простая команда на языке блок-схем изображается в виде функционального блока «процесс», который имеет один вход и один выход. Из команд проверки условий и простых команд образуются составные команды, имеющие более сложную структуру, но тоже один вход и один выход.

Алгоритм любой сложности может быть представлен комбинацией трех базовых структур:

- следование;

- ветвление (в полной и сокращенной форме);

- цикл (с предусловием или постусловием).

Характерной особенностью этих структур является наличие у них одного входа и одного выхода.