Понятие алгоритма, свойства алгоритма, средства записи алгоритма

Понятие алгоритма, являющееся фундаментальным понятием математики и информатики, возникло задолго до появления вычислительных машин. Первоначально под словом алгоритм понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи. Само слово алгоритм появилось в средние века, когда европейцы познакомились со способами выполнения арифметических действий, описанных узбекским математиком Мухаммедом бен Муса аль-Хорезми. Слово алгоритм – является произношением на европейский манер слов аль-Хорезми.

Алгоритм – это организованная последовательность действий, ориентированная на исполнителя.

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

Так как исполнителем алгоритма является автоматическое устройство, то алгоритм должен обладать следующими свойствами:

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

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

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

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

Свойство результативности содержит в себе свойство конечности – завершение работы алгоритма за конечное число шагов.

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

На практике наиболее распространены следующие формы представления алгоритмов:

· словесно-формульная (запись на естественном языке);

· графическая (изображения из графических символов);

· псевдокоды (полуформальное описание алгоритма на условном языке, включающем как элементы языка программирования, так и фразы естественного языка);

· программная(тексты на языках программирования).

На примере следующей задачи рассмотрим основные формы записи алгоритмов.

Задача. Составить алгоритм начисления зарплаты согласно следующему правилу: если стаж работы сотрудника < 5 лет то зарплата 230 руб.; при стаже работы от 5до 15 лет - 280 руб.; при стаже свыше 15 лет зарплата повышается с каждым годом на 10 руб.

Решение. В математическом виде

ì 230., еслиST<5 ;

ZP = í280 ,если 5 £ ST £ 15 ;

î 280+(ST - 15) 10 , если 15 <ST ,

где ZP - зарплата; ST - стаж работы.

Если ST < 5, то ZP = 230, перейти к п.4, иначе перейти к п.3

1. Словесно-формульное описание алгоритма

1). Ввести ST, перейти к п.2.

2). Если ST £ 15,то ZP = 280, перейти к п.4, иначе ZP = 280 + (ST-15)*10, перейти к п.4.

4). Вывести (отпечатать) значение ZP, перейти к п.5.

5). Вычисления прекратить.

2. Описание алгоритма с помощью псевдокода

алг ЗАРПЛАТА (цел ST, вещ ZP)

арг ST

рез ZP

нач

если ST < 5

то ZP = 230

иначе

если ST £ 15

то ZP=280

иначе ZP = 280 +(ST - 15)*10

все

все

кон

3. Графическое описание алгоритма (см. рис.3)

Рис. 3 Блок-схема решения задачи о зарплате

Вывод. Наиболее наглядный способ - схемы алгоритмов. Это и наиболее естественный способ, т. к. человек мыслит образами (в нашем случае -схемами алгоритмов).

Рассмотрим более подробно графический способ представления алгоритма. Графическое описание алгоритма называется блок-схемой. Описание алгоритма с помощью блок-схем осуществляется рисованием последовательности функциональных блоков, каждый из которых подразумевает выполнение определенного действия алгоритма. Порядок выполнения действий указывается стрелками. Написание алгоритмов с помощью блок-схем регламентируется ГОСТом. Примеры приведены в таблице 2.

Таблица2.

Общие правила построения блок-схем показаны на рис.4. Каждое предписание алгоритма изображается с помощью плоской геометрической фигуры – блока. Переходы от предписания к предписанию изображаются линиями связи – линиями потоков информации.

В блок-схемах всегда есть начало и конец, обозначаемые эллипсами, между ними – последовательность шагов алгоритма, соединенных стрелками. Шаги бывают безусловными (изображаются прямоугольниками, параллелограммами) и условными (изображаются ромбами). Из ромба всегда выходят две стрелки – одна означает дальнейший путь, в случае выполнения условия (обозначается обычно словом «да» или «+»), другая – невыполнение (словом «нет» или «-»). Ввод с клавиатуры или вывод на экран значения выражения изображается параллелограммом. Команда, выполняющая обработку действий (обычно команда присваивания), изображается в прямоугольнике.

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

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

Рис. 4 Общие правила построения блок-схем