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

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

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

(СибАДИ)

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

 

 

 

 

 

 

 

 

 

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

 

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

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

 

Раздел 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 Словесное описание

 

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