Алгоритм и его свойства

Содержание

 

1. Определение  алгоритма       3

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

3. Способы описания  алгоритма      3

4. Базовые структуры  блок-схем, линейные и разветвляющие 

структуры, циклические структуры, типы циклов     4

5. Структурированные  блок-схемы      7

6. Предопределенные  процессы. Рекурсия       8

Список литературы        9

 

 

 

1. Определение алгоритма

 

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

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

 

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

алгоритм блок схема цикл рекурсия

Алгоритм имеет следующие свойства:

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

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

3 Результативность (конечность) - алгоритм решает поставленную  задачу за конечное число шагов.

4 Массовость - алгоритм разрабатывается  так, чтобы его можно было применить для целого класса задач, например, алгоритм вычисления определенных интегралов с заданной точностью.

 

3. Способы описания алгоритма

 

Наиболее распространенными способами описания алгоритмов являются словесное и графическое описания алгоритма.

Словесное описание алгоритма рассмотрим на конкретном примере: необходимо найти корни квадратного уравнения a*x2+b*x+c=0

1. вычислить D = b2 - 4ac;
2. если D < 0, перейти к 4;
3. вычислить корни уравнения x1=(-b+ )/(2a); x2=(-b- )/(2a);
4. конец.

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

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

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

 

4. Базовые структуры блок-схем, линейные и разветвляющие структуры, циклические структуры, типы циклов

 

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

1 Базовая структура "следование". Образуется последовательностью действий, следующих одно за другим:

 

 

 

2. Базовая структура "ветвление". Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура "ветвление" существует в четырех основных вариантах:

1. "если - то";

 

 

2. "если - то - иначе";

 

 

 

3. "выбор";

 

 

4. "выбор - иначе".

 

 

3. Базовая структура "цикл". Обеспечивает многократное выполнение  некоторой совокупности действий, которая называется телом цикла. Основные разновидности циклов:

- Цикл типа "пока". Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока.

 

 

 

- Цикл типа "для". Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне.

 

5. Структурированные блок-схемы

 

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

 

 

 

Рассмотрим пример использования диаграмм МЭСИД.

Задан одномерный массив из положительных и отрицательных чисел. Требуется определить частное от деления суммы положительных элементов на сумму отрицательных элементов этого массива.

 

 

 

6. Предопределенные процессы. Рекурсия

 

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

Функция называется рекурсивной, если во время ее обработки возникает ее повторный вызов, либо непосредственно, либо косвенно, путем цепочки вызовов других функций.

Прямой (непосредственной) рекурсией является вызов функции внутри тела этой функции.

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

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

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

 

 

Список литературы

 

1. Информатика: Учебник / Под ред. И.В. Макаровой. – М.: Финансы и статистика, 1997. – 768 с.

2. Информатика. Базовый курс/Симонович С.В. и др. – СПб.: Изд-во «Питер», 2000. – 640 с.

3. Компьютер для студентов./ Под ред. Комягина В.Б. – М.: Лучшие кни-ги, 2005.– 224 с.