Informatika – Algoritmy Radim Farana Podklady předmětu Informatika pro akademický rok 2010/2011
Obsah zAlgoritmus. zVlastnosti algoritmu. zPopis algoritmu. zHodnocení algoritmů. zPříklady algoritmů.
Algoritmus zAlgoritmus je přesný předpis definující výpočtový proces vedoucí od měnitelných Muhammad ibn výchozích údajů až k žádaným Musa (vždy správným) výsledkům. Tento Al'Khwarizmi předpis se skládá z jednotlivých výpočtových kroků, které jsou zapsány v určitém pořadí. Počet výpočtových kroků musí být konečný. * 778? Baghdad + 850?
http://www.cs.jcu.edu.au/ftp/web /teaching/Subjects/cp1030/1997 /lectures/history/algorism.html
1
Vlastnosti algoritmu z determinovanost - shrnuje přesnost, srozumitelnost a jednoznačnost. V každém okamžiku řešení musí být jasné, jakou operaci má algoritmus provádět. z hromadnost (masovost) - algoritmus musí popisovat zpracování celé skupiny příbuzných hodnot. z rezultativnost - algoritmus musí vždy dospět ke správnému výsledku, a to pomocí konečného počtu kroků. z opakovatelnost - při stejných hodnotách vstupních dat musí algoritmus vždy dospět ke stejnému výsledku.
Algoritmus versus program zprogram = posloupnost příkazů, { dokumentu je se výpisem programu, { je chráněn autorským zákonem.
zalgoritmus = postup práce, { dokumentuje se zápisem algoritmu, { je možné ho patentovat.
zProgram realizuje algoritmus (algoritmy), algoritmus je jeho nutnou součástí.
Popis algoritmu zSlovní popis { pracovní postup, { strukturovaný text, zápis pomocí grafu, { pseudokód (programovací).
zGrafický zápis { vývojový diagram, { Kopenogram, NS-diagram, { strukturogram.
2
Příklad 2.3: 10 Read Cislo 20 If Cislo=0 Then Goto 90 30 Write Cislo 40 If Int(Cislo/2)*2=Cislo Then Goto 70 Příklad 2.1: Z klávesnice čteme celá čísla a vypisujeme 50 Write "liché" 60 Goto 10 je na obrazovku doplněná o informaci, 70 Write "sudé" zda je číslo sudé nebo liché. 80 Goto 10 Práce končí po vstupu čísla 0, 90 End které se nezpracovává.
Slovní popis
Příklad 2.4:
Příklad 2.2: 1 přečti číslo ze vstupu 2 když je číslo 0 jdi k bodu 9 3 vyšli číslo na výstup 4 když je číslo sudé, jdi k bodu 7 5 vyšli na výstup "liché" 6 jdi k bodu 1 7 vyšli na výstup "sudé" 8 jdi k bodu 1 9 konec
čti číslo číslo je 0 ? + konec
napiš číslo je číslo sudé ? - + napiš "liché"
napiš "sudé"
Vývojový diagram z Popis algoritmů pro FORTRAN (FORmula TRANslator) z IBM v r. 1954 z Formalizován různými normativy (ČSN 36 9030 )
John Warner Baskus * 3. 12. 1924 Philadelphia, USA http://www-gap.dcs.st-and.ac.uk/~history/ Mathematicians/Backus.html
Ing. Rudolf Pecinovský, CSc.
Kopenogram
* 17. 7. 1954, Praha http://rudolf.pecinovsky.cz/
MUDr. Jiří Kofránek, CSc.
zAutoři: Kofránek, Pecinovský a Novák zPro výukový jazyk Karel zpracování řady čísel čti číslo zpracování řady čísel
číslo není 0
čti číslo
napiš číslo
číslo není 0
jedno číslo napiš číslo číslo je sudé
číslo je sudé jedno číslo napiš "sudé"
napiš "liché"
napiš "sudé"
napiš "liché"
zpracování řady čísel
čti číslo
3
N-S diagramy zAutoři: Nassi a Schneiderman zÚspornější zápis zStále používán zPlug-in do Vizio
Isaac “ Ike“ Nassi Ben Shneiderman http://www.nassi.com
* 21. 8. 1947 http://www.cs.umd.edu/~ben/
čti číslo
číslo není nula
napiš číslo
číslo je sudé
ano
ne
napiš "sudé"
napiš "liché"
čti číslo
Diagramy aktivit UML Podpora paralelismu rozvětvení
karoserie
motor
sestavení vozu
spojení
Strukturogramy zM. A. Jackson, 1975 zZákladní struktury:
Michael Anthony Jackson * 1936 http://mcs.open.ac.uk/mj665/
{ sekvence (posloupnost operací), { selekce (větvení). { opakování – zvláštní případ sekvence.
zSnadné postupné upřesňování algoritmu zJednoznačný vztah mezi daty a algoritmem
4
Strukturogramy Vstupní soubor dat
Algoritmus zpracování
1:1
vstup
výstup
1:1 čísla
nula
začátek
*
příprava
číslo znázornění opakování čísel
tělo
čti číslo
konec
* řádek
1:1 1:1
piš číslo
/
text
vstup
/
číslo je sudé
napiš "sudé"
čti číslo
napiš "liché"
Základní struktury Pseudojazyk
Vývojový diagram
Kopenogram
Strukturogram
Programový celek (rutina, podrogram, procedura a pod.) - definice název (parametry) . . . end název
začátek
název
jeden celý strukturogram
. . .
horní pruh vybarven žlutě
konec programový celek - použití (volání) název (parametry)
název(par.)
název název(parametry) blok vybarven červeně, při rekurzívním volání žlutě
Podmíněná činnost, rozhodování Pseudojazyk
Vývojový diagram
Kopenogram
Strukturogram
Provedení konkrétní činnosti popis činosti
popis činnosti
popis činnosti
popis činnosti
blok vybarven červeně Podmíněná činnost (provádí se pouze pokud je splněna určitá podmínka) if podmínka podmíněná činnost end if
-
podmínka
podmínka podmínka
+
podmíněná činnost
činnost
činnost
horní pruh vybarven modře Rozhodování (pokud platí určená podmínka, provede se činnost 1, jinak činnost 2) if podmínka činnost 1 else činnost 2 end if
+
podmínka
-
podmínka podmínka činnost 1
činnost 1
činnost 2 činnost 1
činnost 2
činnost 2
horní pruh vybarven modře
5
Pseudojazyk
Vývojový diagram
Kopenogram
Strukturogram
Větvení (podle hodnoty výrazu se provádí určená činnost) case výraz=hodnota 1 činnost 1 case výraz=hodnota 2 činnost 2 .......
výraz
výraz = hodnota1
-
=
výraz
činn.
výraz = hodnota n +
činnost při neznámé hodnotě
činnost n
end case
výraz = hodnota1
hod.2
+ činnost1
case else
...
=
hod.1 -
činnost při neznámé hodnotě
činn.
činn.
1
2
výraz = hodnota2
činn.1
činnost při nezn. hodnotě
činn.2
při nezn. hodn.
horní pruh vybarven modře
Opakování s pevným počtem opakování for
počítadlo=začátek to konec step krok
počet opakování
počítadlo=začátek
#
činnost činnost
end for počít. > konec
počet opakování
činnost
+
horní a dolní pruh vybarveny zeleně
činnost počítadlo=počítadlo+krok
Opakování Pseudojazyk
Vývojový diagram
Kopenogram
Strukturogram
Opakování s testem na začátku (dokud platí podmínka, činnost se opakuje - pokud na začátku opakování není podmínka splněna, činnost se vůbec neprovede) podmínka while podmínka činnost end while
-
podmínka + činnost
činnost horní a dolní pruh vybarven zeleně
* podmínka činnost
Opakování s testem na konci (opakování končí, pokud je splněna podmínka - i když podmínka platí již na začátku opakování, činnost se jednou provede) repeat činnost until podmínka (v některých jazycích while činnost end while podmínka)
činnost neexistuje -
činnost podmínka
podmínka
+
Zvláštní činnosti Pseudojazyk
Vývojový diagram
Kopenogram
Strukturogram
Vstupní nebo výstupní operace Jako každá jiná činnost
popis činnosti
Jako každá jiná činnost
Jako každá jiná činnost
Přípravná činnost Jako každá jiná činnost
popis činnosti
Jako každá jiná činnost
Jako každá jiná činnost
Spojka (činnost končí v jedné části algoritmu a pokračuje v jiné části) Neexistuje
číslo
číslo
Neexistuje
Neexistuje
6
Hodnocení algoritmů zSložitost algoritmu (binární bitová). zSčítání dvou k-bitových čísel má binární bitovou složitost úměrnou délce k. zNásobení dvou k a j bitových čísel představuje Tedy celkem nejvýše (j – 1) součtů (k + j – 1) místných čísel: (j – 1)(k + j – 1) < j(k + j) < 2kj. zZkráceně: f(n) = O(g(n)), f (n ) lim pro konečnou limitu: n →∞ g (n )
Složitost algoritmů zPolynomická složitost: výpočet vyžaduje O(kd) bitových operací { sčítání d = 1, { násobení d = 2.
zNepolynomická složitost, složitost výpočtu s rostoucím n roste rychleji. { n! - O(nlog22(n)) = O(2kk2). { an
Realizace základních operací zSčítání (odečítání) binárně: 45 + 23 zdekadicky: 68 + 23
45 + 23 = 68 1 0 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 1 +2 69
0 1 1 1 1 0 0 +3 8 1
7
Násobení zNásobení postupné sčítání a rotace
1 1 0 1 0 1 1 1 1
45 x 11 = 495 1 0 1 1 1 0 1 1 0 1 1 0 0 0 0 1 1 0 1 1 0 1 1
2
3
4
0 1 0 1 1 1 1
x
1 0 1
1
1 1
5
0 1
0 1 2
1 3
5
zdekadicky: 23.45
x x x
Realizace funkcí zTaylorova řada 50000000 40000000
f ' (a) f ( x) = f (a ) + (x − a ) + f ' ' (a) (x − a )2 + ... 1! 2! 30000000 20000000 10000000
0 -10000000 0
x x2 ex =1+ + + ... 1! 2!
5
10
15
20
25
30
-20000000 -30000000 -40000000 -50000000 a(k)
Suma 1..k
problémy kumulace chyb, výpočet e-20:
⎡ ( x − 1) ( x − 1)3 (x − 1)5 + ...⎤ ln x = 2.⎢ + + ⎥ 3 5 5.( x + 1) ⎣ ( x + 1) 3.( x + 1) ⎦
8
