Поручения

ТЕМА 1

ПОНЯТИЕ АЛГОРИТМА

План

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

Примеры алгоритмов в быту, математике.

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

Формы представления алгоритма.

ГОСТ на описание блок-схем.

Виды алгоритмов.

Типовые алгоритмы программ.

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

В Оксфордском словаре указано, что Algorithm – это ошибочное от algorism, который считается синонимом алгебры и арифметики и восходит к IX в.

Позднее этим символом обозначались в трудах Евклида правила нахождения общего делителя двух чисел – алгоритм Евклида.

История появления понятия “алгоритм” связана с именем выдающегося узбекского ученого Мухаммеда бен Муса ал-Хорезми (жил в IX в.), который был математиком, астрономом, географом. Он написал “Арифметический трактат”, по которому европейцы впервые познакомились с десятичной позиционной системой счисления, пришедшей к арабам из Индии. После этого четыре арифметических действия долго называли ал-Хорезми (по латыни Algorithmi). В литературе встречалось “алгоритмус”, “алгорифм”, а в современном варианте произносится как “алгоритм”. Этот термин расширил свое первоначальное значение.

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

2. Примеры алгоритмов в быту, математике

В школе правила сложения, вычитания, умножения, деления – это алгоритмы. Многие инженерные, экономические и прочие задачи поддаются алгоритмизации. Количество действий, которое нужно выполнить, может быть очень большим. Многие правила в воинских уставах представляют собой подробнейшие указания, годные во всех мыслимых ситуациях, – их можно считать алгоритмами. Но инструкции с фразой “Действуй по обстановке” алгоритмом считать нельзя.

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

Притча

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

Вопрос. Имеется плита, спички, водопровод, чайник. Как получить чай?

Ответ: 1) из водопровода налить в чайник воду;

2) спичкой зажечь газ;

3) поставить чайник на газ;

4) ждать несколько минут.

Вопрос. А если в чайнике уже есть вода и газ уже горит?

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

Притча имеет, при всей своей нелепости, следующий смысл:

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

Возможно, способ будет не самым коротким, но задача будет решена.

Пример решения задачи по алгоритму и без

Найти площадь прямоугольного треугольника, если известен катет и гипотенуза.

Первый способ без алгоритма основан на том, что мы знаем или вспомним формулы S=ab/2 и теорему Пифагора а²+b²=c². Вычисления сводятся к подстановке в формулу .

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

1) получить разность с–а;

2) получить сумму с+а;

3) перемножить результаты 1 и 2 шага;

4) взять корень из результата 3 шага;

5) умножить результат 4 шага на а;

6) поделить результат 5 шага на 2;

7) запись ответа;

8) конец.

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

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

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

К алгоритму предъявляется ряд требований:

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

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

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

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

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

Результативность, или выполнимость, означает, что при любых допустимых исходных данных и точном выполнении всех предписаний Вы закончите проект за конечное число шагов. Но это требование может не учитывать реальных условий, поэтому говорят о “потенциальной” выполнимости.

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

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

4. Формы представления алгоритма

Алгоритм фиксируется разными способами:

На естественном языке (см. примеры выше).

С помощью специальных схем, графически.

На алгоритмическом языке.

5. ГОСТ на описание блок-схем

Для графического представления алгоритма используют определенные геометрические фигуры. Такое представление называется блок-схемой. Размеры и соотношения размеров фигур приводятся в ГОСТ 19–002–80 и ГОСТ 19–003–80. Согласно им все размеры связаны с двумя величинами: а и в, где а – величина, кратная 5, а в вычисляется по формуле в = 1,5а, допускается в = 2а.

В январе 1992 года введен новый ГОСТ 19–701–90. Он описывает, как и где следует использовать фигуры. Согласно ему допускаются следующие символы для изображения схем:

1. Для изображения данных

1.1.

вводимые данные, носитель данных не определен

1.2.

хранимые данные, носитель не определен

1.3.

данные, хранимые в оперативной памяти

1.4.

данные, хранимые в запоминающих устройствах с последовательным доступом

1.5.

данные, хранимые в запоминающих устройствах с прямым доступом

2. Для изображения документов

2.1.

данные на носителе (машинограммы, документы для оптического считывания, микрофильмы, бланки ввода)

2.2.

отображаемые данные, вводимые вручную (клавиатура, переключатели, кнопки, световое перо и т.д.)

2.3.

данные на бумажной ленте

2.4.

данные в читаемой форме на носителе в виде отображающего устройства (дисплей и т.д.)

3. Для отображения действий

3.1.

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

3.2.

предопределенный (т.е. определенный заранее) процесс (процедуры, функции, подпрограммы)

3.3.

ручная операция – процесс, выполняемый человеком.

3.4.

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

3.5

решение, блок “условие”

3.6.

выполнение параллельных действий

Например

3.7.

обозначение цикла осуществляется двумя блоками, внутри первого или второго обозначается условие инициализации или условие цикла. Между ними размещаются другие блоки

3.8.

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

3.9. Соединитель (межстраничный, межлистовой)

к странице

от страницы

Внутри используют уникальные одни и те же буквенные обозначения

3.10.

выход и вход во внешнюю среду, блок “ввод/вывод”

3.11.

комментарий

3.12.

канал связи

В зависимости от того, что описывает алгоритм, ГОСТ оговаривает, какие фигуры можно использовать. Использование символов представлено в табл. 1.1. В таблице знаком “+” обозначается использование фигуры, а знаком “–” – запрет использования.

Таблица 1.1

Использование символов

Номер эл–та	Схема данных	Схема программы		Схема работы системы		Схема взаимодействия программ		Схема ресурсов
1	2	3		4		5		6
1.1 1.2 1.3 1.4 1.5 2.1 2.2 2.3 2.4 3.1 3.2 3.3 3.4	+ + + + + + + + + + – + _+	+ – – – – – – – – + + – +		+ + + + + + + + + + + + +		+ + + + + + + + + + + + +		+ + + + + + + + + + – – –

Окончание табл. 1.1
1	2		3		4		5	6
3.5 3.6 3.7 3.8 3.9 3.10	– – – – + +		+ + + – + +		+ + + – + +		– + – + + –	– – – – + –

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

Пример изображения схемы данных банковской системы (рис.1.1).

Рис. 1.1

Пример схемы работы системы (рис. 1.2).

Рис. 1.2

Пример схемы взаимодействия программ (рис.1.3).

Рис. 1.3

Пример схемы ресурсов системы (рис.1.4).

Рис.1.4

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

Для блока 3.5 “решение” над каждым выходом следует подписать условие.

Например:

Можно использовать перекрытые изображения.

Пример.

именно в направлении спереди назад

Пропуск группы элементов изображается как … только в линиях.

Правила соединения блоков в программе.

Все фигуры соединяются линиями (вертикальными и горизонтальными) к середине блока. Направление вниз и вправо является основным, и стрелки направления не указываются, в других случаях указываются обязательно. Внутри фигуры указывается операция. Каждый блок имеет только одну точку входа и только одну точку выхода (кроме блока “условие”, где может быть два и более выходов, на каждом помечается причина\условие). Несколько линий могут соединяться над блоком, нисходящая линия не может разбиваться.

Примеры правильной и неправильной блок-схемы:

Правильные

Неправильные

6. Виды алгоритмов

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

1. Линейные.

2. Ветвящиеся.

3. Циклические.

3.1. По счетчику.

3.2. Итерационные.

Линейные обычно состоят из блоков “ввод/вывод” и “процесс”.

Пример. Вычислить функцию F=x² при любом х.

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

Рис.1.5

Такой способ записи, как F=х·х называется присвоением. Сначала вычисляется результат х·х, который записывается в переменную с именем F.

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

Ветвящиеся алгоритмы в зависимости от выполнения или невыполнения в них некоторых условий осуществляют ту или иную последовательность вычислений. При разветвлении происходит однократный проход по одной из ветвей решения задачи. Классический пример ветвящегося алгоритма – это алгоритм решения квадратного уравнения ах²+вх+с=0 при любых а, в, с. В добавление к предыдущим блокам ветвящиеся алгоритмы содержат блок “решение” (условие). В этом примере A,B,C,D, x, x₁, x₂ – переменные.

Сначала проверяют возможность А=0, тогда уравнение ах²+вх+с=0 приводится к виду вх+ с=0, откуда . Затем вычисляют дискриминант D, если он отрицателен, уравнение корней не имеет, если положительный, будут два корня, если равен 0, оба корня будут одинаковы. Алгоритм представлен на рис.1.6.

Рис.1.6

Ветвления могут быть полные и неполные:

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

1) подготовительные к циклу;

2) действия, которые будут повторяться (их называют тело цикла);

3) условия выхода из цикла.

Согласно новому ГОСТу цикл можно изобразить и так:

Циклические алгоритмы бывают нескольких видов:

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

В циклических алгоритмах часто вычисляют последующий член последовательности через предыдущий. Например, для всех i от 1 до N, причем а₀ задается заранее. Говорят, что в этих случаях единая формула вычислений называется рекуррентной, т.е. выражает рекуррентное соотношение между последующим и предыдущим шагами вычислений.

Пример.

Найти сумму N слагаемых, т.е. вычислить .

Решение: Ведем S=Ш, тогда S₁=S+a₁;

S₂=S₁+a₂;
·

·

·
S_i=S_i–1+a_i;
·

·

·

S_n=S_n-1+a_n,

значению суммы на i-м шаге присваивается значение суммы на предыдущем шаге плюс слагаемое очередного шага а_i:

Рис.1.7(а)

На рис.1.7(а) пример цикла со счетчиком. Здесь заранее известно количество повторений N раз. Блоки 5–8 можно было бы оформить и так (рис.1.7(б)):

Рис.1.7(б)

Рассмотрите самостоятельно алгоритм нахождения произведения N сомножителей Р=Р₁·Р₂·…·Р_n.

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

Рассмотрим алгоритм выделения разрядов из числа 1579, т.е. требуется последовательно получить 9, 7, 5, 1.

Очевидно, 9 получится, если 1579 разделить на 10 и выделить остаток; 7 получится, если целое частное предыдущего шага (157) разделить на 10 и выделить остаток; 5 получится, если целое частное предыдущего шага (15) разделить на 10 и выделить остаток; и, наконец, 1 получится, если целое частное предыдущего шага (1) разделить на 10 и выделить остаток.

Когда же требуется закончить вычисления? При последнем вычислении в частное запишется 0. Это и можно считать признаком окончания счета.

Словесное описание решения требуется формализовать. Обозначим у – очередной разряд, N – промежуточное частное. Фразы “остаток”, “целое”будут заменять функции получения соответственно остатка и целой части.

У = остаток (N/10).

N = целое (N/10).

Опять здесь = не знак равенства, а знак присвоения.

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

Требуется проверить кратность 5 суммы цифр любого числа Х. Алгоритм представлен на рис.1.8.

Рис.1.8

Рассмотрите самостоятельно алгоритм, основанный на алгоритме выделения цифр и алгоритме нахождения произведений N чисел.

Требуется составить алгоритм перевода числа Х, заданного в недесятичной системе счислений Р в десятичную. (Р – основание системы). Число Х целое и занимает М разрядов. Формула перевода целого числа из одной системы в другую будет рассмотрена в теме “Системы счисления”.

Для контроля алгоритм приводится без комментариев (рис.1.9).

Рис.1.9

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

7. Типовые алгоритмы программ

Рассмотрим алгоритм получения суммы ряда (рис.1.10). Как и в прошлом примере, задача сводится к организации цикла. Однако нерационально выполнять действия типа S=S+aⁱ, т.к. в течение работы цикла уже будет получено значение a^i-1, а аⁱ легче получить по формуле . Такая формула получается в результате соотношения а_i к a_i-1:

, следовательно, в данном алгоритме потребуется хранить элемент а_i–1, в остальном же данный алгоритм похож на предыдущий.

Проанализируйте, почему второй алгоритм более эффективен, чем первый:

1) 2)

Рис. 1.10

Рассмотрим вычисление полинома (многочлена) n-й степени

у=a₁·xⁿ+a₂x^n–1+…+a_nx+a_n+1.

Чтобы реализовать алгоритм вычисления такого многочлена при любых а_iи х, используем формулу Горнера:

у=(…((а₁х+а₂)х+а₃)х+…+а_n)х+а_n+1.

Внутренние скобки обозначим у_i, тогда у_i+1=у_iх+а_i+1. Похожая формула уже встречалась. Реализуя цикл из n шагов, получим искомый результат (рис. 1.11).

Рис.1.11

Сайт управляется системой uCoz