Алгоритмизация. Понятие алгоритма и алгоритмической системы. Свойства алгоритма. Проектирование алгоритмов. Блок-схема алгоритма. Основн

Министерство образования  и науки РФ

Сибирская государственная  автомобильно-дорожная академия

(СибАДИ)

Кафедра «Информационные  технологии»

 

 

 

 

 

 

 

 

 

Курсовая работа по информатике

 

Название: РАЗРАБОТКА ОБУЧАЮЩЕГО МОДУЛЯ

                                    ПО ИНФОРМАТИКЕ

 

Раздел 7. АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ. ТЕХНОЛОГИИ ПРОГРАММИРОВАНИЯ

   Тема 7.1. Алгоритмизация. Понятие алгоритма и алгоритмической системы. Свойства алгоритма. Проектирование алгоритмов. Блок-схема алгоритма. Основные типы алгоритмов, их сложность и их использование для решения задач

 

 

 

 

 

 

 

Выполнил: М.Е.Кудряшова, группа ПГСб-11П2

Руководитель: В.И.Макеев

Защитил: ________ , __________ , _________

             ^{оценка           дата              подпись}

 

 

 

 

 

 

 

 

 

 

 

 

Омск-2011

Оглавление

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

Благодаря бурному развитию науки информатики и проникновению  её в различные отрасли народного  хозяйства слово «алгоритм» стало  часто встречающимся и наиболее употребляемым в житейском плане понятием. Более того, с переходом к информационному обществу алгоритмы становятся одним из важнейших факторов цивилизации.

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

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

Для разработки алгоритмов и программ используется алгоритмизация — процесс систематического составления алгоритмов для решения поставленных прикладных задач. Алгоритмизация считается обязательным этапом в процессе разработки программ и решении задач на ЭВМ.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7.1.2 Понятие алгоритма

 

 

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

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

Несмотря на все усилия исследователей, отсутствует одно исчерпывающе строгое определение понятия  «алгоритм». Поэтому в теории алгоритмов были введены различные формальные определения алгоритма:

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

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

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

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

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

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

Система команд исполнителя – совокупность команд, которые данный исполнитель умеет выполнить.

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

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

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

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

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

1. Сделать один шаг  вперед.

2. Повернуться направо.

3. Поднять вверх правую  руку.

4. Поднять вверх левую  руку.

5. Опустить вниз правую  руку.

6. Поднять вверх левую  руку

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

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

Программа - запись алгоритма на языке исполнителя.

 

 

 

 

 

 

7.1.3 Алгоритмическая система

 

 

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

Всякий общий способ задания алгоритмов называется алгоритмической системой.

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

«Алгебраическая» теория строится в некоторой конкретной символике, при которой алгоритмы  рассматриваются как некоторые  линейные тексты.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

Значение слова «алгоритм» очень схоже со значениями слов «рецепт», «метод», «процесс». Но, в отличие  от рецепта или процесса, алгоритм характеризуется следующими свойствами: дискретностью, детерминированностью, результативностью, массовостью и понятностью.

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

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

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

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

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

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

 

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

 

 

 

Рассмотрим следующие  способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.

7.1.5.1 Словесное описание

 

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

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

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

7.1.5.2 Псевдокод

 

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

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

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

7.1.5.3 Блок-схема

 

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

Этот способ имеет  ряд преимуществ. Благодаря наглядности, он обеспечивает «читаемость» алгоритма  и явно отображает порядок выполнения отдельных команд. В блок-схеме  каждой формальной конструкции соответствует  определенная геометрическая фигура или связанная линиями совокупность фигур.

Правила выполнения схем определяются следующими документами:

ГОСТ 19.701-90. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения.

ГОСТ 19.002-80. Схемы алгоритмов и программ. Правила выполнения.

ГОСТ 19.003-80. Схемы алгоритмов и программ. Обозначения условные графические.

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

Основные элементы схем алгоритма:

 

Наименование	Обозначение	Функция
Блок начало-конец  (пуск-остановка)		Элемент отображает вход из внешней среды или выход  из нее (наиболее частое применение −  начало и конец программы). Внутри фигуры записывается соответствующее  действие.
Блок вычислений (вычислительный блок)		Выполнение одной или  нескольких операций, обработка данных любого вида (изменение значения данных, формы представления, расположения). Внутри фигуры записывают непосредственно  сами операции, например, операцию присваивания: a = 10*b + c.
Логический блок (блок условия)		Отображает решение  или функцию переключательного  типа с одним входом и двумя  или более альтернативными выходами, из которых только один может быть выбран после вычисления условий, определенных внутри этого элемента. Вход в элемент обозначается линией, входящей обычно в верхнюю вершину элемента. Если выходов два или три то обычно каждый выход обозначается линией, выходящей из оставшихся вершин (боковых и нижней). Если выходов больше трех, то их следует показывать одной линией, выходящей из вершины (чаще нижней) элемента, которая затем разветвляется. Соответствующие результаты вычислений могут записываться рядом с линиями, отображающими эти пути.
Предопределенный процесс		Символ отображает выполнение процесса, состоящего из одной или  нескольких операций, который определен  в другом месте программы (в подпрограмме, модуле). Внутри символа записывается название процесса и передаваемые в  него данные. Например, в программировании − вызов процедуры или функции.
Данные  (ввод-вывод)		Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов  обработки (вывод). Данный символ не определяет носителя данных (для указания типа носителя данных используются специфические символы).
Граница цикла		Символ состоит из двух частей − соответственно, начало и конец цикла − операции, выполняемые  внутри цикла, размещаются между  ними. Условия цикла и приращения записываются внутри символа начала или конца цикла − в зависимости от типа организации цикла. Часто для изображения на блок-схеме цикла вместо данного символа используют символ решения, указывая в нем условие, а одну из линий выхода замыкают выше в блок-схеме (перед операциями цикла).
Соединитель		Символ отображает вход в часть схемы и выход из другой части этой схемы. Используется для обрыва линии и продолжения ее в другом месте (для избежания излишних пересечений или слишком длинных линий, а также, если схема состоит из нескольких страниц). Соответствующие соединительные символы должны иметь одинаковое (при этом уникальное) обозначение.
Комментарий		Используется для более  подробного описания шага, процесса или  группы процессов. Описание помещается со стороны квадратной скобки и охватывается ей по всей высоте. Пунктирная линия идет к описываемому элементу, либо группе элементов (при этом группа выделяется замкнутой пунктирной линией). Также символ комментария следует использовать в тех случаях, когда объём текста, помещаемого внутри некоего символа (например, символ процесса, символ данных и др.), превышает размер самого этого символа.

7.1.5.4 Программа

 

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

Программа – описание структуры алгоритма на языке алгоритмического программирования.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7.1.6 Основные типы алгоритмов

 

 

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

7.1.6.1 Линейная алгоритмическая конструкция

 

Линейной называют алгоритмическую  конструкцию, реализованную в виде последовательности действий (шагов), в которой каждое действие (шаг) алгоритма  выполняется ровно один раз, причем после каждого i-го действия (шага) выполняется (i+1)-е действие (шаг), если i-е действие — не конец алгоритма.                                

7.1.6.2 Разветвляющаяся алгоритмическая конструкция

 

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

При полной форме ветвления  действия выполняются в обоих случаях: и при истинности и при ложности условия. Ей соответствует следующее выражение: если <условие>, то <действие 1>, иначе <действие 2>. При неполной форме ветвления действие выполняется в единственном случае, то есть, когда выполняется условие. Ей соответствует выражение: если <условие>, то <действие 1>.

7.1.6.3 Алгоритмическая конструкция «Цикл»

 

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

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

7.1.6.3.1 Арифметический цикл

 

В арифметическом цикле  число его шагов (повторений) однозначно определяется правилом изменения параметра, которое задается с помощью начального (N) и конечного (K) значений параметра и шагом (h) его изменения. То есть, на первом шаге цикла значение параметра равно N, на втором – N+h, на третьем – N+2h и так далее. На последнем шаге цикла значение параметра не больше K, но такое, что дальнейшее его изменение приведёт к значению, большему, чем K.

7.1.6.3.2 Цикл с предусловием

 

В данной циклической  структуре сначала проверяется  значение условного выражения (условие) перед выполнением очередного шага цикла. Если значение условного выражения истинно, исполняется тело цикла. После чего управление вновь передается проверке условия и т.д. Эти действия повторяются до тех пор, пока условное выражение не примет значение ЛОЖЬ. При первом же несоблюдении условия цикл завершается. Количество шагов цикла заранее не определено и зависит от входных данных задачи.  

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

7.1.6.3.3 Цикл с постусловием

 

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

7.1.6.4 Рекурсивный алгоритм

 

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

7.1.6.5 Вспомогательный алгоритм

 

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7.1.7 Проектирование алгоритмов

 

 

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

Существенным шагом  на пути снижения трудоемкости процесса программирования стал структурный  подход к проектированию алгоритмов. Его основным принципами являются нисходящее проектирование и модульное программирование. Нисходящее проектирование заключается в последовательном разбиении задачи на все более мелкие участки, т.е. процесс программирования идет «сверху вниз». Модульное программирование предполагает создание для каждого такого участка отдельной автономной программы — модуля. Специально созданная программа объединяет все модули в целое и управляет их работой.

7.1.7.1 Нисходящее проектирование

 

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

На практике «чистую» нисходящую разработку осуществить практически невозможно, так как выбор более конкретизированных элементов на каждой стадии должен производиться на основе представления и понимания возможностей языка реализации. Однако даже в данном случае на более поздней стадии часто обнаруживается, что некоторый выбор, сделанный ранее, был неверным. Это приводит к необходимости разработки новых и корректировки уже имеющихся модулей.