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

Любой алгоритм должен обладать следующими свойствами:

• Понятность. Используемые на практике алгоритмы составляются с ориентацией на определенного исполнителя. Нужно знать, какие команды этот исполнитель может понять и выполнить, а какие - нет.

• Дискретность - возможностью разбиения алгоритма на отдельные элементарные действия.

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

• Результативность. При точном выполнении всех предписаний алгоритма исполнитель должен получить определенный результат за конечное число шагов. Вывод о том, что решения не существует — тоже результат. Следовательно, результативность означает возможность получения результата после выполнения конечного количества операций.

• Массовость (универсальность) - возможностью получения результата при различных исходных данных для некоторого класса похожих задач.

Независимо от содержания и сложности любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов, или битов, а их значениями являются соответствующие двоичные числа. Данные, рассматриваемые в виде последовательности битов, имеют очень простую организацию или, другими словами, слабо структурированы. Для человека описывать и исследовать сколько-нибудь сложные данные в терминах последовательностей битов весьма неудобно. Более крупные и содержательные, нежели бит, "строительные блоки" для организации произвольных данных получаются на основе понятия "структуры данного".

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

Структуры данных

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

- композиция или следования;

- ветвления (альтернатива, если - то - иначе);

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

Циклический алгоритм – это алгоритм, некоторые шаги которого повторяются N-количество раз.

Тело цикла – шаги алгоритма, которые повторяются.

Параметр цикла – величина, от которой зависит число повторений в цикле.

Цикл с предусловием:

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

Цикл с постусловием:

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

Цикл с конечным числом повторений:

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

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

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

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

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

В информатике линейный список обычно определяется как абстрактный тип данных (АТД), формализующий понятие упорядоченной коллекции данных.

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

К примеру, АТД нетипизированного изменяемого списка может быть определён как набор из конструктора и четырёх основных операций:

• операция, проверяющая список на пустоту;

• операция добавления объекта в список;

• операция определения первого (головного) элемента списка;

• операция доступа к списку, состоящему из всех элементов исходного списка, кроме первого.