Словесная форма

Алгоритмы, их типы и свойства. Формы записи алгоритмов

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

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

· Дискретность – последовательность выполнения одного за другим отдельных законченных шагов.

· Массовость – применимость к целому классу задач.

· Определенность – однозначное толкование каждого шага.

· Результативность – получение результата через конечное число шагов.

· Формальность – способность любого исполнителя выполнить все шаги алгоритма, не понимая их смысла.

Например, инструкция по использованию утюга является алгоритмом, а инструкция как встретить и устроить в гостинице гостя фирмы не является алгоритмом (нет свойства массовости).

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

Алгоритмы бывают сходящимися и расходящимися.

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

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

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

Алгоритмический язык – это язык формализованной записи алгоритма.

Формы записи алгоритма:

Словесная форма

Пример описания алгоритма Евклида – нахождения наибольшего общего делителя двух чисел (НОД).

Шаг 1-й. Ввести два числа.

Шаг 2-й. Если числа равны, то взять первое и закончить выполнение алгоритма, иначе – перейти на следующий шаг.

Шаг 3-й. Определить большее число. Заменить большее число на разность большего и меньшего и перейти на шаг 2-й.

Достоинство – универсальность, недостаток – неформальность.

2. Блок – схема

Шаги алгоритма изображаются в виде специальных графических символов, которые связываются линиями передачи управления:

Начало, конец, прерывание

Ввод или вывод данных

Линейный процесс

Магнитный диск

Сортировка

Подпрограмма

Вывод на принтер

Проверка условия

Магнитная лента

Дисплей

Соединитель

Межстраничный соединитель

Блок‑схема алгоритма Евклида – нахождения НОД

Лист бумаги делится на колонки и строки. Строки нумеруются, а колонки обозначаются латинскими буквами. В одной ячейке (зоне) размещается один графический символ. Адрес зоны обозначается именем колонки и номером строки (B3). В соединителе указывается адрес зоны (куда или откуда передается управление). В межстраничном соединителе дополнительно указывается номер листа.

Достоинство: наглядность; недостаток: трудоемкость разработки.

Псевдокоды

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

Пример алгоритма Евклида

Алгоритм – определение наибольшего общего делителя чисел А, В.

Ввод двух чисел A, B.

Делать пока А не равно В.

Если А>В То А=А-В Иначе В=В-А Конец если

Конец делать

Вывести значение А на печать.

Конец алгоритма

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

4. Метод HIPO (иерархия, ввод, обработка, вывод). Используется для описания больших программных проектов. Проект состоит из оглавления, обзорных и детальных таблиц. В оглавлении указываются назначение проекта и список основных функций. Каждая функция в дальнейшем расписывается в виде иерархической системы обзорных таблиц. Каждой обзорной таблице присваивается код, который включает в себя код вышестоящей таблицы (через точку); таким образом, код показывает ветвь проекта (1.2, 1.2.1, 1.2.2). Детальные таблицы заканчивают описание всего проекта и являются терминальными таблицами в дереве обзорных таблиц. Детальная таблица состоит из трех колонок: входная информация, обработка и выходная информация.

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

Дата добавления: 2015-11-14