Файл: Алгоритмизация как обязательный этап разработки программы. (ПОНЯТИЕ АЛГОРИТМА. СВОЙСТВО И ВИДЫ АЛГОРИТМОВ).pdf

ВВЕДЕНИЕ

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

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

1.АЛГОРИТМИЗАЦИЯ

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

---

2.ПОНЯТИЕ АЛГОРИТМА. СВОЙСТВО И ВИДЫ АЛГОРИТМОВ

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

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

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

Са?мо сл?ово «а?лгоритм» пр?оисходит от им?ени уч?ёного Аб?у Аб?дуллах Му?хаммеда иб?н Му?са аль-Хорезми. Ок?оло 82?5 г. он на?писал сочинение, в ко?тором вп?ервые да?л оп?исание пр?идуманной в Ин?дии по?зиционной де?сятичной си?стемы счисления. К сожалению, ар?абский ор?игинал кн?иги не сохранился. Пр?иблизительно в эт?о же вр?емя ин?дийские ци?фры на?чали пр?именять и др?угие ар?абские учёные. В пе?рвой по?ловине XI?I ве?ка кн?ига ал?ьХорезми в ла?тинском пе?реводе пр?оникла в Европу. Переводчик, им?я ко?торого до на?с не дошло, да?л ей на?звание Al?goritmi de nu?mero In?dorum («?Алгоритми о сч?ёте индийском»). По?-арабски же кн?ига им?еновалась Ки?таб ал?ь-джебр ва?ль-мукабала («?Книга о сл?ожении и вычитании»). Из ор?игинального на?звания кн?иги пр?оисходит сл?ово Алгебра.

Об?язательные св?ойства ал?горитма :

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

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

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

---

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

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

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

Ли?нейный ал?горитм -  об?разуется командами, вы?полняемыми од?нократно в то?й последовательности, в ко?торой он?и записаны.

  Ал?горитм с ве?твлением - эт?о алгоритм, в ко?тором в за?висимости  от не?которого ус?ловия вы?полняется ли?бо одна, ли?бо по?следовательность команд. Дл?я за?писи ал?горитма с ве?твлением мо?жет ис?пользоваться по?лная и со?кращенная (н?еполная) фо?рма записи.

Ал?горитм с ци?клом - эт?о алгоритм, со?держащий команды, ко?торые по?вторяются по?ка вы?полняется за?данное условие.

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

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

3.СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ

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

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

---

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

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

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

Су?ществует не?сколько ос?новных бл?оков:

1. Те?рминатор ил?и бл?ок на?чало-конец: об?означает на?чало ил?и ко?нец программы. Да?нный бл?ок от?деляет гр?аницы пр?ограммы от вн?ешней среды. Ка?к правило, в да?нный эл?емент вп?исывают фр?азы «Начало», «С?тарт» ил?и «Конец», «Финиш».

1. Бл?ок команды, процесса, де?йствия: да?нный бл?ок от?вечает за вы?полнение од?ной ил?и не?скольких операций. Ка?к правило, в да?нный эл?емент бл?ок-схемы вп?исывают команды, ко?торые ме?няют данные, зн?ачения переменных. Например, ар?ифметическая оп?ерация на?д дв?умя пе?ременными бу?дет за?писана в да?нном блоке.

1. Бл?ок ло?гического ус?ловия: ре?зультатом ло?гического ус?ловия вс?егда яв?ляется од?но из дв?ух пр?едопределенных зн?ачения: ис?тина ил?и ложь. Вн?утри да?нного эл?емента-ромба за?писывается ло?гическое условие, а из ве?ршин ро?мба вы?ходят ал?ьтернативные ве?тви решения. Об?язательно сл?едует по?дписывать ве?тви сл?овами «Да», «Нет», чт?обы не вв?одить в за?блуждение чи?тателя блок-схемы.

1. Пр?едопределенный пр?оцесс: ес?ли ва?ша пр?ограмма пр?едусматривает на?личие по?дпрограмм: пр?оцедур ил?и функций, то вы?зов по?дпрограммы за?писывается вн?утри да?нного элемента.

---

1. Бл?ок вв?ода-вывода да?нных: от?вечает за фо?рму по?дачи данных, например, за по?льзовательский вв?од да?нных с кл?авиатуры ил?и за вы?вод да?нных на мо?нитор пе?рсонального компьютера.

1. Бл?ок ци?кла со сч?етчиком: от?вечает за вы?полнение ци?клических ко?манд ци?кла for. Вн?утри эл?емента за?писывается за?головок ци?кла со счетчиком, а оп?ерации те?ла ци?кла ра?сполагаются ни?же элемента. Пр?и ка?ждой ит?ерации ци?кла пр?ограмма во?звращается к за?головку цикла, ис?пользуя ле?вую стрелку. Вы?ход из ци?кла fo?r ос?уществляется по пр?авой стрелке.

1. Па?рный бл?ок дл?я ци?клов с пр?ед- и по?стусловием: да?нный бл?ок со?стоит из дв?ух частей. Оп?ерации те?ла ци?кла ра?змещаются ме?жду ними. За?головок ци?кла и из?менения сч?етчика ци?кла за?писываются вн?утри ве?рхнего ил?и ни?жнего бл?ока – в за?висимости от ар?хитектуры цикла.

1. Соединитель: пр?именяется дл?я об?рыва ли?нии св?язи ме?жду эл?ементами блок-схемы. Например, ес?ли вы ст?роите ма?сштабную бл?ок-схему на ли?сте фо?рмата А4, и он?а не по?мещается на од?ин лист, то ва?м пр?идется ос?уществить пе?ренос бл?ок-схемы на вт?орой лист. В эт?ом сл?учае не?обходимо бу?дет во?спользоваться да?нным соединителем. Ка?к правило, вн?утри ок?ружности ук?азываются ун?икальный идентификатор, ко?торый яв?ляется на?туральным числом.

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

4.ОСНОВНЫЕ СТРУКТУРНЫЕ АЛГОРИТМИЧЕСКИЕ КОНСТРУКЦИИ

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

1. Следование. Пр?едполагает по?следовательное вы?полнение ко?манд св?ерху вниз. Ес?ли ал?горитм со?стоит то?лько из ст?руктур следования, то он яв?ляется линейным.
2. Ветвление. Вы?полнение пр?ограммы ид?ет по од?ной из двух, не?скольких ил?и мн?ожества ветвей. Вы?бор ве?тви за?висит от ус?ловия на вх?оде ве?твления и по?ступивших сю?да данных.
3. Цикл. Пр?едполагает во?зможность мн?огократного по?вторения оп?ределенных действий. Ко?личество по?вторений за?висит от ус?ловия цикла.
4. Фу?нкция (подпрограмма). Команды, от?деленные от ос?новной программы, вы?полняются ли?шь в сл?учае их вы?зова из ос?новной пр?ограммы (и?з лю?бого ее места). Од?на и та же фу?нкция мо?жет вы?зываться из ос?новной пр?ограммы ск?оль уг?одно раз.

---