Základy algoritmizace

Základy algoritmizace

Algoritmus Algoritmus je postup pro řešení určité úlohy, který v každém kroku říká, jak dále postupovat.

ALGORITMUS

MNOŽINA VSTUPNÍCH DAT

Počítače a programování 1

transformace množiny vstupních dat na množinu výstupních dat

MNOŽINA VÝSTUPNÍCH DAT

2

Vlastnosti algoritmu Elementárnost – Skládá se z konečného počtu jednoduchých (elementárních) činností (kroků).

Determinovanost – V každém kroku lze rozhodnout, jak se má pokračovat (a jestli nenastal konec).

Konečnost – Algoritmus vždy skončí po konečném počtu kroků.

Rezultativnost – Vede ke správnému výsledku (k nějakému…).

Hromadnost – Použitelný pro celou třídu podobných problémů.

Opakovatelnost – Pro stejné vstupy vždy stejný výstup. Souvisí s determinovaností a rezultativností. Počítače a programování 1

3

Algoritmické jazyky Představují souhrn prostředků a pravidel způsobilých vyjadřovat výpočetní algoritmy. Mezi algoritmické jazyky patří : – vývojové diagramy • Představují normou (dnes již nadnárodní) definované symbolické značky a pravidla pro jejich používání, sloužící k jednoznačnému grafickému vyjadřování výpočetních operací a postupů. Vývojový diagram tak slouží jednak k popisu výpočetního algoritmu a zároveň jako podklad pro sestavení programu pro počítač.

– programovací jazyky • Programovací jazyky jsou důsledně formalizované algoritmické jazyky, určené pro zápis algoritmu pro počítač. Zápis algoritmu v programovacím jazyku nazýváme program. – počítačově orientované » strojový kód (závislý na typu procesoru, instrukce ve formě čísel) » assembler (jazyk symbolických adres)

– vyšší programovací jazyky Î Počítače a programování 1

4

Vyšší programovací jazyky

Jazyky s výrazně propracovanou syntaxí. Zahrnují v sobě složité programové konstrukce struktury a objekty. Vzhledem k obecnosti nejsou tyto jazyky vázané na žádný konkrétní typ počítače. Transformace programu, napsaném v některém z těchto jazyků, se provádí speciálním programem, nazývaným překladač (kompilátor). Počítače a programování 1

5

Vyšší programovací jazyky

V současné době se používají dva programovací jazyky vyššího typu. PASCAL, který je užíván zejména ve školství jako jazyk vhodný pro výuku programování (umožňující tzv. strukturované programování) a jeho nadstavba DELPHI C, resp. C++ , který nachází své uplatnění v komerční oblasti při vytváření systémového a aplikačního software

(DELPHI a C++ pak zajišťující možnost tzv. objektově orientovaného programování). Počítače a programování 1

6

Strukturované programování

Využívá tři základní typy jazykových konstrukcí: sekvence, podmínky cykly.

Každá taková struktura má v zásadě jenom jeden vstup a jeden výstup. Tímto se při programování vyhýbáme nesledovatelným vazbám v programu, které u klasických programovacích jazyků vyplývají z používání příkazu nepodmíněného skoku (GOTO). Počítače a programování 1

7

Objektově orientované programování

Objekty, nebo také komponenty, jsou předem vytvořené a plně funkční konstrukce (softwarové stavební díly) daného programovacího jazyka, které řeší některý dílčí problém nebo úkol. Úkolem uživatele je pak místo podrobného psaní programu, jenom vybrat vhodné objekty (často jenom pomocí myší) a tyto příslušným způsobem seřadit (uložit do formuláře). Navíc uživatel má možnost měnit některé vlastnosti těchto objektů, případně si některé objekty definovat a zkonstruovat sám. Počítače a programování 1

8

Historie programovacích jazyků

Pojem „programovací jazyk“ Pod pojmem programovací jazyk rozumíme prostředek pro zápis programů, jež mohou být provedeny na počítači. V tomto smyslu je programovací jazyk komunikačním nástrojem mezi: – uživatelem počítače, který jeho jazykovými prostředky specifikuje algoritmus řešení daného problému, a – počítačem, jenž svými technickými prostředky algoritmus interpretuje a realizuje tak transformaci vstupních údajů na výstupní.


10

Vývoj programovacích jazyků Vývoj programovacích jazyků určovaly a určují mnohé faktory; k nejzávažnějším z nich pravděpodobně patří: – – – –

vývoj technických prostředků vývoj metod strojového překladu jazyků vývoj metod programování stále širší oblasti využívání počítačů


11

Strojový jazyk V prvním období existence počítačů zastával roli programovacího jazyka výhradně strojový kód, nazývaný proto také strojový jazyk. Vyjadřovacími prostředky strojového jazyka jsou instrukce. Jejich sémantika je definována technickými prvky počítače. Nedostatky: – závislost na konkrétním typu počítače – velmi nízká úroveň popisovaných akcí – pro člověka nepohodlný číselný zápis instrukcí.

V současné době je používání strojového jazyka jako nástroje programování zcela ojedinělé.


12

Jazyky symbolických instrukcí Prvním krokem ve vývoji programovacích jazyků byla náhrada numericky kódované informace instrukcí strojového jazyka informací symbolickou. Vzniká tak důležitá třída programovacích jazyků - jazyky symbolických instrukcí. Překlad (kompilace) - počítačem realizovaná transformace určitého textu na text reprezentující program ve strojovém jazyce. Assembler - překladač jazyka symbolických instrukcí. Nevýhody: závislost na konkrétním typu počítače Výhody: • rychlost překladu a zpracování přeloženého programu • možnost programování na elementárních úrovních, která je v některých případech nepostradatelná a ve vyšším programovacím jazyce nedostupná (hodně se používá při vytváření programů operačního systému)


13

Vyšší programovací jazyky Další vývoj směrem k vyšším programovacím jazykům sledoval dva cíle: odstranit strojovou závislost jazyků, vyžadující od programátora detailní znalosti strojového jazyka a znemožňující použití programů vypracovaných pro jeden typ počítače na počítači jiného typu poskytnout programátorům takové prostředky pro popis algoritmů, které odrážejí povahu řešených problémů, a nikoliv technickou realizaci výpočetních procesů na počítači


14

Fortran

Zahájil éru skutečných vyšších programovacích jazyků Ve své první podobě byl Fortran opravdu snadno naučitelným jazykem vedoucím k maximálně efektivnímu programu Programování přestalo být výsostnou doménu skupiny úzce specializovaných odborníků Fortran byl však původně jazykem určeným pro vědeckotechnické výpočty, proto nemohl vyřešit úplně všechno Pro vědeckotechnické výpočty se používá dodnes (Digital Fortran – Compaq)


15

Algol První programovací jazyk, který poskytoval ucelenou a jednotnou množinu jazykových prostředků pro popis algoritmů Byl to první programovací jazyk, který obsahoval explicitní řídící příkazy pro reprezentaci posloupnosti příkazů, iteraci a výběr alternativ Počátky strukturovaného programování Značná složitost a obtíže spojené s jeho zvládnutím i implementací Malé rozšíření Řada myšlenek, které se zde objevily poprvé, se uplatnila při koncipování jazyků široce používaných v praxi


16

COBOL Jazyk Cobol byl vyvinut společným úsilím výrobců a uživatelů počítačů ve spolupráci s ministerstvem obrany USA. Ve dnech 28. - 29. 5. 1959 se konala konference, jejímž cílem bylo uvážit různé aspekty zavedení společného jazyka pro programování elektronických počítačů. Konference rozhodla o zahájení tohoto projektu s tím, že jazyk byl měl umožňovat – sestavení programů v minimálním čase s minimálním programovacím úsilím – zápis programů v jazyce blízkém angličtině – snadný převod programů na nové typy počítačů – úplnou dokumentaci programu


17

Lisp V roce 1960, kdy vznikl COBOL-60, také vznikl na MIT Lisp, první jazyk zcela nového typu. Je to tzv. funkcionální jazyk, který používá jako jediné řídící struktury funkce a jejich skládání. Přinesl i nové pojmy v oblasti rekurzivních datových struktur a stal se základem programů pro symbolické manipulace. AutoLisp – programování v AutoCADu


18

BASIC V původní podobě neobsahoval podprogramy v dnešním slova smyslu Nerozlišoval typy číselných proměnných K jeho popularitě přispěla: – jednoduchost – možnost interaktivní práce – snadná implementace na mikropočítačích


19

PASCAL Navazoval na ALGOL Navržen profesorem Niklausem Wirthem (Eidgenoessische Technische Hochschule Zurich) v roce 1971 pro potřeby výuky programování. Dnes má Pascal ve světě nejen dominantní postavení při výuce programování, ale velmi se používá i pro běžné programování. Konečný tvar normy jazyka byl vydán v 80. letech pod označením ISO 7105.


20

Jazyk C Vyvíjel se společně s OS UNIX C-jazyk se v prapůvodní podobě nazýval B-jazyk (Thomson, Ritchie na PDP-7, 1970) C-jazyk je unikátní, neboť je jakési střední úrovně. – Není to jazyk vysoké úrovně jako BASIC nebo PASCAL, – Není to však ani jazyk nízké úrovně jako assembler.

Jazyk C může pracovat na úrovni systému a umožňuje programátorovi napsat téměř všechno, co ho napadne (funkce assembleru). Navíc je C-jazyk dostatečně univerzální i pro aplikační programování (funkce jazyka vyšší úrovně). Největší předností jazyka C je jeho schopnost rozšiřovat sama sebe. Knihovny C-jazyka se snadno rozšiřují co do velikosti a je snadné napsat novou funkci, jakmile ji potřebuji. Počítače a programování 1

21

Algoritmizace úlohy Etapy řešení problému 1. 2. 3. 4. 5.

Specifikace (vymezení) problému Analýza problému Sestavení algoritmu Kódování (zápis) algoritmu Testování algoritmu (u programů ladění)


22

Algoritmus - příklad

Úloha: Sestavit návod na čištění zubů ve formě algoritmu

Cíl: Vyčištění zubů daného člověka

Prostředky: zdravá osoba (ústa, zuby, pohyblivá ruka, …) zubní kartáček, zubní pasta, sklenička na vodu, umyvadlo


23

Člověk s nevyčištěnými zuby

Algoritmus - příklad ALGORITMUS ČIŠTĚNÍ ZUBŮ Příprava kelímku a čisticího kartáčku

Vlastní čištění zubů

Uklizení kelímku a kartáčku


Člověk s vyčištěnými zuby 24


Algoritmus - příklad ALGORITMUS ČIŠTĚNÍ ZUBŮ

Příprava kelímku a čisticího kartáčku


Vytáhni kartáček a kelímek ze skříňky. Do kelímku nalej pitnou vodu. Na kartáček nanes pastu. Krouži kartáčkem postupně po všech zubech, asi 2 minuty. Vypláchni si ústa. Smyj zbytky pasty z kartáčku. Opět krouži 2 min. čistým kartáčkem po zubech. Vypláchni si ústa.



Umyj kartáček proudem vody. Vylij vodu z kelímku a vypláchni ho čistou vodou. Ukliď kelímek i kartáček do skříňky.



Algoritmus - příklad ALGORITMUS ČIŠTĚNÍ ZUBŮ

Příprava kelímku a čisticího kartáčku


Vytáhni kartáček a kelímek ze skříňky.

Otevři skříňku. Je tam kelímek ?

Do kelímku nalej pitnou vodu.

Ne – konec

Na kartáček nanes pastu.

Ano – pokračuj

Pusť kohoutkem vodu. Krouži kartáčkem postupně po všech zubech, asi 2 Teče ? minuty. Ne – konec Vypláchni si ústa. Smyj zbytky pasty z kartáčku. Ano – pokračuj Opět krouži 2 min. čistým kartáčkem po zubech. Natoč do ¾ kelímku vodu. Vypláchni si ústa. Zavři kohoutkem vodu.



Umyj kartáček proudem vody.

…… Vylij vodu z kelímku a vypláchni ho čistou vodou. Zavři skříňku. Ukliď kelímek i kartáček do skříňky.


Základní prvky algoritmu I Při vytváření a popisu algoritmu používáme základní prvky, z nichž se algoritmus skládá: začátek algoritmu – počáteční bod, od nějž začíná zpracování konec algoritmu – konečný bod, na němž po vytvoření výsledků zpracování dále nepokračuje, ukončuje algoritmus kroky algoritmu – jednotlivé přesně vymezené a oddělené operace, které předepisují úkony, prováděné s proměnnými podprogramy – předem definované části algoritmu, které figurují v algoritmu jako jeden krok, ale mají svou vlastní strukturu


27

Základní prvky algoritmu II podmínka – binární relace, případné zřetězení více relací pomocí logických spojek. Výsledkem vyhodnocení podmínky je hodnota TRUE (pravda) = podmínka je splněna nebo FALSE (nepravda) = podmínka není splněna. rozhodování – postup, kdy na se základě vyhodnocení podmínky provádí větvení algoritmu. Při splněné podmínce se provádí jedna sekvence kroků, při nesplněné podmínce jiná sekvence krokù. sekvence – posloupnost kroků po sobě jdoucích v uvedeném pořadí cyklus – opakování kroku nebo sekvence kroků nula-krát až nkrát, dokud je (nebo není) splněna podmínka cyklu. skok – přerušení přirozené posloupnosti průchodu algoritmem a přenesení zpracování na jiné místo označené návěštím. [nehodí se pro strukturované programování] Počítače a programování 1

28

Příklad – vyhledání max. nebo min. hodnoty


29

Datové struktury Proměnné: symbolicky pojmenované údaje, které se při zpracování nahradí konkrétními hodnotami (texty, čísla, obrázky, schémata, počítačové soubory dat). Proměnné mohou být vstupní, pracovní a výstupní. Identifikátor: námi zvolené pojmenování proměnné Datový typ: určuje množinu hodnot, kterých může proměnná nabýt a množinu operací, které lze s proměnnými daného typu provádět (rovněž určuje, kolik místa proměnná zabere v paměti). Zavedení proměnné

– Odhadnu, jaký datový typ budu pro danou proměnnou potřebovat (odvíjí se od řešené úlohy - rozsah, přesnost) • Příklad: • mezivýsledek výpočtu obsahu plošného útvaru Æ zvolím reálné číslo • pořadí pokusu Æ zvolím celočíselný typ

Proměnnou názorně pojmenuji, tj. zvolím identifikátor • Příklad • obsah_kruhu • CisloPokusu


NIKOLIV NIKOLIV

x i

30

Řídicí struktury – jednoduché příkazy Přiřazovací příkaz MojePromenna Identifikátor proměnné (v plovoucí řádové čárce)

= 12.6

Operátor PŘIŘAZENÍ

Přiřazovaný výraz

Složený výraz může obsahovat číselné konstatnty, závorky ( ), operátory + - * /

MojePromenna

= 12.6 + (10 * 2) / 4

MojePromenna

= 12.6 + (10 * obvod) / pocet

MojePromenna

= 12.6 + MojePromenna

Složený výraz může obsahovat další proměnné

Přiřazovací příkaz může obsahovat ve výrazu napravo tutéž proměnnou jako nalevo Počítače a programování 1

31

Řídicí struktury – jednoduché příkazy Operace vstupu Prozatím potřebujeme pouze možnost vstupu dat z klávesnice Načti MojePromenna Na příkazu „Načti“ se algoritmus přeruší a očekává vstup hodnoty příslušné proměnné.

Více proměnných: Načti p1, p2, x


32

Řídicí struktury – jednoduché příkazy Operace výstupu potřebujeme pouze možnost vypsat na obrazovku obsah proměnné Vypiš MojePromenna Příkaz „Vypiš“ vypíše obsah specifikované proměnné.

Možnost výpisu řetězce jako komentáře: Vypiš “Obsah proměnné x je“, x


33

Řídicí struktury – složené příkazy Sekvence

Je tvořena posloupností jednoho nebo více příkazů, které se provádějí v pevně daném pořadí. Příkaz se začne provádět až po ukončení předchozího příkazu.

Př. Nakreslete vývojový diagram algoritmu pro výpočet obvodu kruhu. Poloměr kruhu bude zadán z klávesnice, výsledek vypište na obrazovku. start

Načti polomer

P1 obvod

P2

=

2 * 3.1415926 * polomer

Vypiš obvod stop


34

Řídicí struktury – složené příkazy Selekce (podmínka, větvení)

Provedení dalšího kroku závisí (je podmíněno) splněním podmínky. Numerický zápis podmínky: +

Podm

-

Polomer <= 0 P1

P2

Relační operátory == ~= > < <= >= Počítače a programování 1

je rovno není rovno větší než menší než menší nebo rovno větší nebo rovno

-

+

Logické operátory & and (logický součin) | or (logický součet) ~ not (negace)

35

Podmíněný příkaz Př. Ošetření vstupu v předchozím příkladu start Načti polomer

Polomer > 0

-

+ obvod

=

2 * 3.1415926 * polomer

Vypiš obvod

Vypiš “chybny polomer“

stop Počítače a programování 1

36

Přepínač

Struktura je určena pro vícenásobné větvení programu. Podle hodnoty klíče K dojde k přepnutí na příslušnou spojku Ki se stejnou hodnotou a vykonání sekvence Si. V případě, že ani jedna hodnota spojky nemá hodnotu klíče, celá struktura se obejde a pokračuje se následnými operacemi za tímto přepínačem. Počítače a programování 1

37

Cykly cyklus

opakovaně prováděná část algoritmu

tělo cyklu

opakující se kroky uvnitř cyklu

typy cyklů: – nekonečný – s řídicí podmínkou před tělem – s řídicí podmínkou za tělem – s pevným počtem opakování


indukční iterační

38

Cykly Cyklus s podmínkou před tělem Konvence: K ukončení dojde v případě, že řídicí podmínka není splněna.

Podm + P1

Důsledek: Tělo cyklu se nemusí

Pn

vykonat ani jednou.

Cyklus s podmínkou za tělem Stejná konvence: K ukončení dojde v případě, že řídicí podmínka není splněna.

P1

Pn

Důsledek: Tělo cyklu se vykoná alespoň jednou. Počítače a programování 1

-

+

Podm 39

Příklad Start

Algoritmus pro výpočet aritmetického průměru N celých čísel. (N>=1)

Načti „počet čísel“, N Vysledek = 0 P=0 Načti a Vysledek = Vysledek + a P=P+1

+

P
Vysledek = Vysledek / N Tiskni „prumer =“, Vysledek Stop Počítače a programování 1

40

Cyklus s pevným počtem opakování - for

výraz_start

Pvýraz_stop o d m

typicky inicializace řídicí proměnné (ř.p.) ukončovací podmínka s ř.p. -

+

výraz_start; výraz_stop; výraz_iter

P 1

P 1

výraz_iter P n

Iterace pro ř.p.


41

Cyklus s pevným počtem opakování - for Algoritmus pro výpočet aritmetického průměru N celých čísel. (N>=1)

Z Načti „počet čísel“, N Vysledek = 0 L = 1 ; L<=N ; L=L+1 Načti a Vysledek = Vysledek + a

Vysledek = Vysledek / N Tiskni „prumer =“, Vysledek K Počítače a programování 1

42

Vícenásobně vnořené cykly

+

Podm 1

Podm 2

Podm 3 + Počítače a programování 1

43

START

VÝVOJOVÝ DIAGRAM PRO URČENÍ n-TÉ MOCNINY ČÍSLA

ČTI X

ČTI n

Z=0 Y=1

Z
+ Y=Y*X Z=Z+1

PIŠ Y

STOP Počítače a programování 1

44

Pole • kolekce prvků stejného datového typu prvky = normální proměnné

Př. A = [5

9 8.1

3]

• přístup k jednotlivým prvkům pomocí tzv. indexu (typicky celé nezáporné číslo) • konvence zápisu: nazev_pole (index_prvku) Př. A(3)

(má hodnotu 8,1 z předchozího příkladu)

index_prvku ……. 1 až dimenze_pole Počítače a programování 1

45

Pole Př.: mám pole s identifikátorem y, které obsahuje 6 prvků celočíselného typu: y=5 4 8 10 -5 -20 y(1), y(2), y(3), y(4), y(5), y(6) nekorektní použití: korektní použití prvků: např. y(8) y=7 • h = y(2) / 4 + (y(0) – y(5)) • y(4) = h * y(4) – y(1) • j=4 • y(j) = h * y( j - 2 ) – y(1) indexem může být celočíselná proměnná resp. jakýkoliv výraz s celočíselným výsledkem Počítače a programování 1

46

Pole Př.: Je dáno pole y, které obsahuje N celých čísel. Napište algoritmus, který spočte a vypíše počet záporných prvků tohoto pole.

Z poc = 0 L = 0 ; L
Y(L) < 0 + poc = poc + 1

Tiskni poc K


47

Vícerozměrná pole • jednorozměrné pole - vektor • prvkem pole může být jiné pole Æ vícerozměrná pole dvourozměrné pole („pole polí¨) – matice • Matlab >>A=[1 2 ; 3 4] nebo >>A= 1 2 3 4 A= 1 2 3 4 Počítače a programování 1

48

Metody řazení prvků BUBBLE SORT - bublinkové třídění Jednotlivé prvky při něm doslova probublávají tak, že výsledkem je balík setříděných dat. Principem BUBBLE SORTu je porovnávání sousedních prvků (podtrženo) a jejich případné prohození podle toho, jak chceme data třídit (vzestupně/sestupně). Probublávání se musí většinou několikrát opakovat a končí tehdy, když při průchodu celou množinou nedošlo k výměně. Seřaďte sestupně vektor a, výsledek vložte do b: a = [7 2 3 9 5 6 4] a = [max ... min] a=[7239564] a = [ 7 2 3 9 5 6 4 ] → provedena záměna a = [ 7 3 2 9 5 6 4 ] → provedena záměna …. opakuj do konce vektoru a=[7392564] Byla provedena nějaká záměna? ANO: probublej znovu stylem NE: seřazená posloupnost - výsledek Počítače a programování 1

49

BUBBLE SORT function [b]=bub_sort(a) delka=length(a); zamena=1; (libovolne nenulové číslo – proběhnutí cyklu s podmínku alespoň jednou !) while zamena ~= 0 zamena=0; for i = 1 : delka-1 if a(i)
% prohozeni prvku s indexy i a i+1

zamena=zamena+1;


50

Metody řazení prvků SELECT SORT Pracuje tak, že vyhledá ve skupině prvků minimum nebo maximum podle toho, jestli chceme třídit vzestupně nebo sestupně, a umístí jej na první místo ve skupině. Proces se opakuje, přičemž velikost tříděného úseku se zmenšuje. Seřaďte sestupně vektor a, výsledek vložte do b: a = [7 2 3 9 5 6 4] a = [max ... min] a=[7239564] max=9 → a=[723564] max=7 → a=[23564] max=6 → a=[2354] max=5 → … Počítače a programování 1

b= [9] b=[97] b=[976] b=[9765] 51

SELECT SORT function [b]=sel_sort1(a); delka=length(a); for i=1 : delka-1 for j=i+1 : delka if a(i)

function [b]=sel_sort2(a) delka=length(a); for i = 1 : delka cast_max=max(a); pom=find(a==cast_max) b(i)=cast_max; a=[b a(1:pom-1) a(pom+1:end)]; cast_max=0; end;

52

Metody řazení prvků

INSERT SORT - Též nazývána metodou přímého zakládání. Data se rozdělí na "setříděnou" a nesetříděnou část a pak se jednotlivé prvky z nesetříděné části zakládají na příslušné místo do setříděné části. (Tato metoda je nejsložitější na algoritmizaci. Složitost vyplývá z posunu více prvků najednou při zakládání do "setříděné" části). Jiné… http://sally.webzdarma.cz/c/c41.htm


53

Pravidla pro přepis vzorců každý zlomek ve tvaru p zapíšeme jako podíl p/q

q

výraz p napíšeme jako sqrt(p) obecné mocniny p q a mocniny funkcí


q

sin 2 p

p napíšeme jako p^q a p^(1/q) napíšeme jako (sin (p))^2

54

Příklady přepisu vzorců

a+b c−d (a+b)/(c-d)

c a+ d b + e2 (a+c/d)/(b+e^2) Počítače a programování 1

a+

a *b c+d (a*b)/(c+d)

b c+

d f e+ g+h

a+(b/(c+(d/(e+(f/(g+h))))))

5

b+c a+ * x+ y d +e

(a+((b+c)/(d+e))*sqrt(x+y))^(1/5) 55

Základy algoritmizace

Recommend Documents