UUP_1 Algoritmi PDF

 Увод ❑ Рачунари су способни да се баве разним сложеним проблемима који су по својој природи досадни и рутински. ❑ Да би рачунар решио проблем, програмер мора да припреми метод за решење и детаљну процедуру. ❑ Решавање проблема укључује: ❑ детаљно проучавање проб...

 Увод ❑ Рачунари су способни да се баве разним сложеним проблемима који су по својој природи досадни и рутински. ❑ Да би рачунар решио проблем, програмер мора да припреми метод за решење и детаљну процедуру. ❑ Решавање проблема укључује: ❑ детаљно проучавање проблема; ❑ редефинисање проблема; ❑ идентификацију улазних података, излазних захтева и услова и ограничења; ❑ алтернативне методе решавања; ❑ избор најпогодније методе; ❑ припрему листе процедура и корака за добијање решења; 2 ❑ генерисање излаза.  Алгоритам - увод ❑ Алгоритам је низ инструкција дизајниран тако да ако се инструкције изврше у одређеном низу, добију се жељени резултати. ❑ Упутства треба да буду прецизна и концизна, а резултат треба да се добије након коначног извршења корака. ❑ То значи да алгоритам не би требало да понавља једну или више инструкција бесконачно. ❑ Требало би да се заврши у неком тренутку и резултира жељеним излазом. ❑ Извршилац (корисник) алгоритма може бити или особа или технички уређај. ❑ Алгоритам се може писати на различите начине (вербални опис, графички опис - блок дијаграм (дијаграм тока), програм на неком од програмских језика итд.). 3 ❑ Програм је алгоритам написан у програмском језику. Пример алгоритма – алгоритам „Љубав“ ❑ На десној обали реке налазе се два младића са својим девојкама. Сви треба да пређу на леву обалу, али у чамцу су само два места. Свака девојка не жели да остане на обали без свог дечка ако је на истој обали још један младић. Како сви могу да пређу на другу страну? ❑ Решење – означимо: девојке и младиће са Д1, Д2, М1, М2, при чему је М1 дечко девојке Д1, односно М2 дечко девојке Д2 прелазак помоћу чамца са леве на десну обалу са → прелазак помоћу чамца са десне на леву обалу са ← ❑ Тада се алгоритам може написати на следећи начин: Прелаз Акција Лева обала Десна обала почетак / Д1, Д2, М1, М2 први Д1, Д2 ← Д1, Д2 М1, М2 други Д1 → Д2 М1, М2, Д1 трећи М1, М2 ← Д2, М1, М2 Д1 четврти М1 → Д2, М2 Д1, М1 4 пети (крај) Д1, М1 ← Д2, М2, Д1, М1 Алгоритам – шта треба знати ❑ Да би се креирао алгоритам, потребно је знати: ❑ комплетан скуп почетних података задатка (почетно стање објекта); ❑ сврху креирања алгоритма (коначно стање објекта); ❑ систем команди корисника (односно скуп команди које корисник разуме и може да изврши). 5  Алгоритам – карактеристике (својства) ❑ јасност (разумљивост), једноставаност, недвосмисленост (јединственост) и ефикасност - сваки корак треба да буде јасан у свим аспектима и да води само до једног значења; алгоритам мора бити једноставан, генерички и практичан, тако да се може извршити са доступним ресурсима; свака инструкција треба да буде прецизна и јасна (јединствена); сваки корак у алгоритму мора бити ефикасан, тј. сваки корак треба да уради неки посао; ❑ општост - алгоритам се прави тако да је у стању да прихвати што већи број различитих улазних величина и на основу њих да креира што већи број излазних величина: ❑ добро дефинисани улази - ако алгоритам каже да захтева улазе (уносе), то би требало да буду добро дефинисани улази; ❑ добро дефинисани излази - алгоритам мора јасно да дефинише који ће резултат (излаз) дати, излаз треба да буде добро дефинисан, требао би да произведе најмање један излаз; ❑ детерминизам (одређеност) - требао би да даје исте излазе за исти улазни случај; ❑ дискретност - алгоритам је подељен на засебне кораке – команде; за сваки алгоритамски корак приликом извршавања потребно је одређено (дискретно) време, тј. временски интервал; ❑ коначност (ефективност) - алгоритам мора бити коначан, тј. треба да се заврши након коначног времена (у коначном броју корака); ❑ независност од језика - алгоритам који је дизајниран мора бити независан од језика, тј. морају бити само обичне инструкције које се могу имплементирати на било ком језику, а резултат ће бити исти. 6 ❑ масовност - већина алгоритама има и ову карактеристику; користећи исти алгоритам, могу се решити многи проблеми истог типа.  Услови при креирању алгоритама ❑ Услови о којима треба водити рачуна приликом креирања алгоритма су да је: ❑ алгоритам заузео што мање меморије ❑ што већа брзина рада ❑ што једноставнија структура 7 Дијаграм тока / алгоритамска шема ❑ Пре него се што почне са кодирањем (писањем) програма, потребно је планирати корак по корак решење задатка који ће програм извршити. ❑ Графички начин описивања алгоритма се назива дијаграм тока (flowchart). ❑ Устаљени називи за дијаграм тока су и блок дијаграм, алгоритамска шема ❑ Алгоритамске шеме (АШ) користе геометријске облике, од којих сваки приказује операцију или радњу, као и корак у процесу решавања проблема. ❑ Свака фигура се зове блок. ❑ Редослед фаза је приказан стрелицама које повезују блокове. ❑ Блокови морају бити постављени одозго према доле или с лева на десно редоследом којим су завршени. ❑ Алгоритамска шема се може развити за практично сваки посао. 8 ❑ Алгоритамска шема омогућава да се прате и открију било какве логичке или друге грешке пре него што су програми написани.  Дијаграм тока - врсте ❑ Постоје две врсте дијаграма тока: ❑ дијаграми тока програма (program flowcharts) – користе их програмери; дијаграм тока програма показује структуру програма, логички ток и извршене операције; чини важан део документације система; ❑ системски дијаграми тока (system flowcharts) – користе их системски аналитичари за приказ различитих процеса, подсистема, излаза и операција над подацима у систему. 9  Дијаграм тока - предности ❑ Предности дијаграма тока: ❑ дијаграм тока је одличан начин да се пренесе логика програма; ❑ лако и ефикасно анализирање проблема коришћењем дијаграм тока; ❑ током циклуса развоја програма, дијаграм тока игра улогу нацрта, што олакшава процес развоја програма; ❑ након успешног развоја програма потребно му је континуирано благовремено одржавање током његовог рада; дијаграм тока олакшава одржавање програма или система; ❑ лако је конвертовати дијаграм тока у било који код 10 програмског језика. Дијаграм тока – програмска окружења ❑ Постоје више програмских окружења, односно визуелних програмских језика (visual programming language) заснованих на дијаграму тока. ❑ Визуелни програмски језик (ВПЛ) је рачунарски програм који развија апликације користећи графичке компоненте, текст, симболе и иконе унутар свог програмског окружења. ❑ Визуелни програмски језици (програмска окружења) су посебно дизајнирани да помогне студентима да визуелизују своје алгоритме: ❑ Flowgorithm, ❑ Raptor, Flint, ❑ Larp, Snap, ❑ Scratch, 11 ❑ Kodu, ❑ Blockly и др.  Препорука! За почетнике се увек препоручује да прво напишу алгоритам и нацртају дијаграм тока (алгоритамску шему) за решавање проблема, а затим напишу програм. 12  Графички симболи Назив (функција) алгоритамске шеме Početak Терминатор (свака алгоритамска шема започиње и Kraj завршава се овим симболом) Аритметичко логички блок или блок обраде (обрада података) Улазни блок (уношење података), лево Излазни блок (испис података - резултат), десно DA DA Логички блок / блок одлуке (провера услова - једноструко гранање) NE NE DEFAULT Вишеструки блок одлуке (провера услова - вишеструко гранање) … NЕ blok naredbi Програмска петља (организација цикличних структура) DA лево – петља са изласком на врху blok naredbi NE десно – петља са изласком на дну DA 13 Стрелице (повезивање алгоритамских корака)  Програмске структуре ❑ Под структуром алгоритма подразумева се редослед извршавања појединих врста алгоритамских корака у алгоритму. ❑ На основу тога може се закључити да постоје три основне алгоритамске структуре: ❑ Линијске алгоритамске структуре - низ алгоритамских корака у коме се сваки алгоритамски корак може извршити највише једанпут током извршавања алгоритма и строго по редоследу. Састоји се од алгоритамских корака улаза, обраде и излаза ❑ Разгранате структуре - сваки алгоритамски корак се извршава највише једном (значи једном или ниједном) и обавезно садржи бар један условни алгоритамски корак. Ако је услов испуњен, излаз из алгоритамског корака биће означен са ‘DA’, а ако услов није испуњен излаз ће бити означен са ‘NE’, или ће бити без ознаке. ❑ Цикличне алгоритамске структуре (петље) - структуре код којих се један или више алгоритамских корака може извршавати више од једанпут у току једног извршавања алгоритма. ❑ Структуре за управљање током извршења: гранање и циклуси (петље) ❑ Сложене алгоритамске структуре – настају композицијом (комбинацијом) елементарних алгоритамских структура (линијских, разгранатих и цикличних структура) ❑ Блок наредби се састоји од једне или више наредби које се blok 14 извршавају једна за другом. Блок наредби има једну улазну naredbi и једну излазну тачку. Програмске структуре - препознавање 1 3 2 1 – проста линијска структура 15 2 – једноструко гранање 3 – вишеструко гранање Програмске структуре - препознавање 6 Početak 4 5 Početak n,m DA m>n n t=n n=m b=0 m=t kor=n i=1,n DA n mod i=0 n mod m0 b=b+1 DA n=n+kor DA b