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

 

 

 

Содержание.

Введение…………………………………………………………………………...3

1. Алгоритм и его свойства.

   1.1 Различные подходы  к понятию алгоритм…………….……...…………....4

   1.2 Понятие исполнителя  алгоритма…………………………………………..5

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

   1.4 Понятие алгоритмического  языка…………………………………………9

2. Этапы похождения задач на ЭВМ.

   2.1 Постановка задачи………………………………………….……………...10

   2.2Разработка алгоритма………. ……………………………………………. 16

   2.3 Кодирование………………………………………………………………..12

  2.4 Отладка и тестирование  программы………………………………………13

Вывод…………………………………………………………………………….14

Библиография…………………………………………………………………….15 
Введение.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.1Различные подходы  к понятию алгоритм.

 

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

Алгоритмы являются объектом систематического исследования пограничной  между математикой и информатикой научной дисциплины, примыкающей  к математической логике - теории алгоритмов.

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

Само слово «алгоритм» происходит от algorithmi - латинской формы  написания имени великого математика IX века аль-Хорезми, который сформулировал  правила выполнения арифметических действий.

1.2  Понятие  исполнителя алгоритма.

 

Понятие исполнителя невозможно определить с помощью какой-либо формализации. Исполнителем может быть человек, группа людей, робот, станок, компьютер, язык программирования и т.д. Важнейшим  свойством, характеризующим любого из этих исполнителей, является то, что  исполнитель умеет выполнять  некоторые команды. Так, исполнитель-человек  умеет выполнять такие команды  как «встать», «сесть», «включить  компьютер» и т.д., а исполнитель-язык программирования Бейсик - команды PRINT, END, LIST и другие аналогичные. Вся совокупность команд, которые данный исполнитель  умеет выполнять, называется системой команд исполнителя (СКИ).

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

 

Рис.1.11. Исполнитель-робот

 

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

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

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

 

 

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

 

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

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

2. Используемые на практике  алгоритмы составляются с ориентацией  на определенного исполнителя.  Чтобы составить для него алгоритм, нужно знать, какие команды  этот исполнитель может понять  и исполнить, а какие - не  может. Мы знаем, что у каждого  исполнителя имеется своя система  команд. Очевидно, составляя запись  алгоритма для определенного  исполнителя, можно использовать  лишь те команды, которые имеются  в его СКИ. Это свойство алгоритмов  будем называть понятностью. 

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

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

Отмеченное свойства алгоритмов называют определенностью или детерминированностью.

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

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

 

 

 

 

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

 

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

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

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

 

 

 

 

2. Основные этапы  прохождения задач на ЭВМ.

2.1 Постановка задачи.

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

- ко времени решения  поставленной задачи;

- объему необходимых ресурсов, например, оперативной памяти;

- точности достигаемого  результата.

Проектирование программы

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

 

 

 

 

 

2.2 Разработка алгоритма.

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

Алгоритм - центральное понятие  программирования, поэтому познакомиться  с ним следует как можно  раньше.

Само слово “алгоритм” происходит от имени персидского  математика Аль Хорезми, который  в IX веке разработал правила четырех  арифметических действий (сегодня мы бы сказали алгоритмы арифметических действий).

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

Итак, алгоритм - это описание некоторой последовательности действий, но не всякое, а обладающее определенными свойствами. К этим свойствам относятся: 1) дискретность - расчлененность описания на отдельные элементарные действия — операции, которые доступны исполнителю алгоритма (человеку, роботу, компьютеру,...); 2) детерминированность - на одинаковых исходных данных алгоритм должен всегда давать одинаковые результаты; 3) массовость - алгоритм должен работать на множестве однотипных исходных данных, потенциально бесконечном.

2.3 Кодирование.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

2.4 Отладка и тестирование программы

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

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