Лекция № 25 Алгоритмизация

Лекция № 25

Алгоритмизация

Понятие алгоритма. Свойства алгоритма

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

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

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

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

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

Алгоритм — это информационная модель, описывающая процесс преобразования объекта из начального состояния в конечное, в форме последовательности понятных исполнителю команд.

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

2. Налить в чайник воду.

3. Довести воду до кипения и снять с огня.

4. Всыпать в чайник чай.

5. Довести воду до кипения (но не кипятить), снять с огня.

6. Чай готов.  Процесс прекратить.

Исполнитель алгоритма – это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.

Исполнителя характеризуют:

-       среда;

-       элементарные действия;

-       система команд;

-       отказы.

Среда (или обстановка) – это «место обитания» исполнителя.

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

После вызова команды исполнитель совершает элементарное действие.

Отказы исполнителя возникают, если команда вызывается при недопустимом для неё состоянии среды.

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

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

-       понятность (исполнитель алгоритма должен знать, как его выполнять);

-       дискретность (алгоритм должен представлять процесс решения задачи как последовательное выполнение простых или ранее определённых шагов);

-       определённость (каждое правило алгоритма должно быть чётким, однозначным и не оставлять места для произвола);

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

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

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

Алгоритмы могут описывать процессы преобразования самых разных объектов. Широкое распространение получили вычислительные алгоритмы, которые описывают преобразование числовых данных. Само слово алгоритм происходит от algorithmi - латинской формы написания имени выдающегося математика IХ века аль-Хорезми, который сформулировал правила выполнения арифметических операций.

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

Рассмотрим работу пользователя, например, в среде текстового редактора Word. Word предоставляет пользователю возможность работы в мире своих объектов, которыми являются документ, фрагмент документа, символ и т.д.    

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

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

1. Выделить слово информационная + пробел.

2. Вырезать этот фрагмент и поместить его в буфер.

3. Установить курсор на позицию после слова модель + пробел.

4. Вставить вырезанный фрагмент текста.

Алгоритм должен обладать свойством точности, т.е. каждая команда алгоритма должна однозначно определять действие исполнителя. Для этого необходимо формализовать запись алгоритма и заменить содержательную модель текста на его формальную модель. Формальная модель представляет текст, делящимся на страницы, состоящие из определенного количества строк, которые, в свою очередь, включают определенное количество знакомест (символов). Наш текст состоит из одной страницы, которая содержит одну строку. Команде Выделить слово информационная пробел на формальном языке соответствует команда Выделить символы с 1 по 15, а команде Установить курсор после слова модель пробел соответствует команда Установить курсор после 7-го символа.
          1. Выделить символы с 1 по 15.

2. Вырезать этот фрагмент и поместить его в буфер.

3. Установить курсор на позицию после 7-го символа.

4. Вставить вырезанный фрагмент текста.

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

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

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

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

В настоящее время используется несколько таких способов.

1. Словесно-формульное описание алгоритма, т. е.
описание алгоритма с помощью слов и формул. Это наиболее простой способ.

Задача. Составить алгоритм начисления зарплаты согласно следующему правилу: если стаж работы сотрудника менее 5 лет, то зарплата 130 тыс. руб., при стаже работы от 5 до 15 лет — 180 тыс. руб., при стаже свыше 15 лет зарплата повышается с каждым годом на 10 тыс. руб. Сформулируем задачу в математическом виде: вычислить

Словесно-формульное описание алгоритма решения задачи:
1. Ввести SТ, перейти к п. 2.
2. Если SТ<5, то ZР:=13О, перейти к п. 4, иначе — перейти к п. З.
З. Если SТ <15, то ZР:= 180, перейти к п. 4, иначе ZР:=180+( SТ —15)*10, перейти к п. 4.
4. Вывести (отпечатать) значение ZР, перейти к п. 5.
5. Вычисления прекратить.

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

Это графическое изображение алгоритма в виде определенным образом связанных между собой нескольких типов блоков. Первое понятие о языке блок-схем ввели в 1956 г. русские математики А.А. Ляпунов и Ю.Н. Янов. В каждой такой схеме последовательность выполняемых исполнителем действий изображается с помощью линий, соединяющих отдельные блоки. Существуют заранее оговоренные условные обозначения для блоков различных типов. Чтобы придать блок-схемам наглядность и единообразие, все эти графические элементы стандартизированы.

Графические элементы блок-схем:

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

Блок конца используется для обозначения конца алгоритма (конца подпрограммы).

Блок ввода – вывода обозначает ввод данных в переменные с указанными именами или вывод содержимого указанных переменных на экран монитора или на принтер.

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

Блок разветвления: в зависимости от результата проверки условия, выполняются только действия ветки "Да" или только действия ветки "Нет" (если она есть). Это – так называемая "полная альтернатива". Если ветка "Нет" отсутствует (неполная альтернатива), то при невыполнении условия никакие действия в рамках этого блока не производятся.

3. Описание алгоритма на алгоритмическом языке (алгоязыке).  Алгоритмический язык — это средство для записи алгоритмов в аналитическом виде, промежуточном между записью алгоритма на естественном (человеческом) языке и записью на языке ЭВМ (языке программирования).

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

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

Базовые алгоритмические структуры

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

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

ЕСЛИ условие ТО действие 1 ИНАЧЕ команда 2 (конструкция выбора в полной форме)

ЕСЛИ условие ТО действие 1 (конструкция выбора в сокращённой форме)

Разветвляющиеся алгоритмы используются:

-       в цепях управления;

-       в механизмах терморегуляции живых организмов;

-       в схемах воздействия на социальные и другие процессы.

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

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

Телом цикла называются команды, многократно повторяющиеся в процессе его выполнения.

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

Анализ работы алгоритмов. Анализ правильности алгоритмов

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

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

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

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

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

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

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

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

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

Скачано с www.znanio.ru