Seminář z IVT Algoritmizace Slovanské gymnázium Olomouc Tomáš Kühr
Algoritmizace - o čem to je?
Zatím jsme se zabývali především tím, jak určitý postup zapsat v konkrétním programovacím jazyce (např. C#)
Neméně důležité je ale tento postup řešení vymyslet
Případně vymyslet “nejlepší” možný postup
nejrychlejší
nejméně náročný na paměť
dávající nejpřesnější výsledek
zaručeně správný
nebo jakoukoli vhodnou kombinaci výše uvedeného
2
Algoritmus
V širším smyslu se jedná o návod nebo postup.
V užším smyslu: Algoritmus je posloupnost instrukcí pro řešení daného problému.
Tato definice je však značně nepřesná:
Co je instrukce?
Co je problém?
Co je jeho řešení?
Existuje i matematicky přesná definice, ale tím se nebudeme zabývat
3
Algoritmus - upřesnění
Běžně nám ale stačí následující upřesnění:
Instrukce je jednoznačný a srozumitelný pokyn, který může člověk nebo počítač mechanicky (tj. bez dalšího přemýšlení) vykonávat
Problém je zadám otázkou/úkolem a množinou možných zadání (vstupů) (např. “Je číslo na vstupu prvočíslo?” + množina všech přirozených čísel)
Řešení problému algoritmem spočívá v postupném provádění instrukci
Jako řešení problému se také označuje výstup tohoto procesu (pokud nějaký výsledek existuje)
Takto specifikovaný pojem algoritmu odpovídá počítačovým programům
4
Příklady problémů
Slovo problém používáme i v jiných situacích:
Problém zaparkování auta (Odpovídá naší definici; vstup: poloha auta a překážek v okolí; výstup: není; instrukce: otoč volantem o X stupňů, sešlápni plynový pedál, …)
Problém vyřešení kvadratické rovnice ax2 + bx + c (Odpovídá definici; vstup: 3 reálná čísla a, b, c; výstup: reálná čísla x1 a x2; aritmetické instrukce, přiřazení)
Problém přípravy svíčkové s knedlíkem (Neodpovídá naší definici - není jasné, co je dostatečně dobrá svíčková; také recepty většinou nejsou dostatečně jednoznačné - můžeme jídlo pokazit)
Izraelsko-Palestinský problém (neodpovídá definici)
Problém, jak žít smysluplný život (neodpovídá definici)
5
Příklad algoritmu
Řešení kvadratické rovnice
Vstup: reálná čísla a, b, c
Výstup: reálná čísla x1, x2 (nebo informace, že nemá řešení)
Instrukce: 1.
Vypočítej diskriminant D pomocí vzorce 𝐷 = 𝑏2 − 4𝑎𝑐.
2.
Pokud je D kladné, pak vypočítej kořen 𝑥1 =
3.
Pokud je D nula, pak existuje dvojnásobný kořen 𝑥1 = 𝑥2 =
4.
Pokud je D záporné, pak rovnice nemá reálné kořeny.
5.
Vrať kořeny x1 a x2.
−𝑏− 𝐷 2𝑎
a kořen 𝑥2 =
−𝑏+ 𝐷 . 2𝑎
−𝑏 . 2𝑎
6
Základní vlastnosti algoritmů
Jednoduchost (elementárnost) = Algoritmus se skládá z jednoduchých (elementárních) kroků.
Jednoznačnost (determinovanost) = Kroky algoritmu jsou zcela jednoznačné a po každém kroku je jasně dáno, kterým krokem bude algoritmus pokračovat.
Konečnost (finitnost) = Algoritmus vždy skončí po konečném počtu kroků.
Obecnost (hromadnost, univerzálnost) = Algoritmus neřeší jeden konkrétní problém, ale obecnější třídu problémů. (Vstupy algoritmu je možné měnit.)
Výstup (resultativnost) = Algoritmus má nějaký výsledek. Výsledkem může být i informace, že rovnice nemá řešení (viz předchozí příklad)-
7
Možnosti popisu algoritmů
Existuje velké množství možností, jak algoritmus popsat
Některé již známe:
Slovní popis v přirozeném jazyce (např. češtině)
Výhody: snadno srozumitelné laikům
Nevýhody: zdlouhavé, často nejednoznačné a méně přehledné
Popis v nějakém programovacím jazyce (např. C#)
Výhody: naprosto přesné, lze přímo přeložit a program používat
Nevýhody: dlouhé, obsahuje nepodstatné detaily
Další (pro nás zatím neznámé) možnosti:
Pseudokód (viz dále)
Vývojové diagramy
...
8
Pseudokód
Programovacím jazykům blízký způsob zápisu algoritmů
Neřeší ale spousty nepodstatných detailů
Výhody:
Stručný, úsporný způsob zápisu
Přehledný a srozumitelný i neprogramátorům (matematikům, fyzikům, ...)
Lze snadno převést do téměř libovolného programovacího jazyka
Nevýhody:
Horší čitelnost pro netechnické profese
Je vždy potřeba přepsat do konkrétního programovacího jazyka 9
Instrukce pseudokódu
V instrukcích pseudokódu se typicky vyskytují
Proměnné (budu psát kurzívou)
Operátory (+, −, *, /, mod, and, or, not, ≠, =, <, >, ≥, ≤, ←,
Větvení (if ... then ... else ...)
Cykly (while ... do ... , for ... to ... do ... )
, [ ], …)
Příklad pseudokódu (algoritmus nalezení největšího společného dělitele): Vypocet-NSD(cislo1, cislo2) 1 while cislo2>0 2 do zbytek ← cislo1 mod cislo2 3 cislo1 ← cislo2 4 cislo2 ← zbytek 5 return cislo1 10
C# vs. pseudokód static int[] delitele(int cislo) { bool[] delitelnost = new bool[cislo + 1]; int[] vysledek; int pocetDelitelu = 0; for (int delitel = 1; delitel <= cislo; delitel++) { if (cislo % delitel == 0){ delitelnost[delitel] = true; pocetDelitelu++; } else { delitelnost[delitel] = false; } } vysledek = new int[pocetDelitelu]; for (int i = 1, i2 = 0; i<=cislo; i++) { if (delitelnost[i]) { vysledek[i2] = i; i2++ } } return vysledek; }
delitele(cislo) 1 for delitel←1 to cislo 2 do if cislo mod delitel = 0 3 then 4 delitelnost[delitel]←PRAVDA 5 pocetDelitelu←pocetDelitelu+1 6 else 7 delitelnost[delitel]←NEPRAVDA 8 i2←0 9 for i←1 to cislo 10 do if delitelnost[i] 11 then 12 vysledek[i2]←i 13 i2 ← i2+1 14 return vysledek;
11
Sčítání dvou celých čísel – slovní popis
Vstup: an-1an-2...a1a0, bn-1bn-2...b1b0, kde ai a bi jsou čísla z {0, 1, …, 9}
Výstup: cncn-1...c1c0, kde ci jsou také čísla z {0, 1, …, 9} a platí, že součet čísel daných číslicemi na vstupu ai a bi odpovídá číslu, které je dáno číslicemi ci
Kroky algoritmu: 1.
Je-li a0+b0 < 10, nastav hodnotu c0 na a0+b0 a t na 0, jinak nastav c0 na a0+b0−10 a t na 1.
2.
Je-li a1+b1+t < 10, nastav hodnotu c1 na a1+b1+t a t na 0, jinak nastav c1 na a1+b1+t−10 a t na 1.
3.
... Je-li an-1+bn-1+t < 10, nastav hodnotu cn-1 na an-1+bn-1+t a t na 0, jinak nastav cn-1 na an-1+bn-1+t−10 a t na 1. Nastav cn na t.
12
Sčítání dvou celých čísel – lepší slovní popis
Vstup: pole číslic a[n] a b[n] odpovídající vstupním číslům čteným od konce
Výstup: pole číslic c[n+1] odpovídající výsledku čtenému od konce
Kroky algoritmu: 1.
Nastav t na 0.
2.
Pro hodnoty i od 0 do n − 1 prováděj postupně: Je-li a[i] + b[i] + t < 10, nastav c[i] na a[i] + b[i] + t a t na 0, jinak nastav c[i] na a[i] + b[i] + t − 10 a t na 1;
3.
Nastav c[n] na t.
13
Sčítání dvou celých čísel – pseudokód
Vstup: pole číslic a[n] a b[n] odpovídající vstupním číslům čteným od konce
Výstup: pole číslic c[n+1] odpovídající výsledku čtenému od konce
Pseudokód algoritmu: Scitani-Cisel(a[0..n 1 t ← 0 2 for i ← 0 to n − 3 do c[i] ← (a[i] 4 t ← (a[i] + 5 c[n] ← t 6 return c
− 1], b[0..n − 1]) 1 + b[i] + t) mod 10 b[i] + t)/10
14
Sčítání dvou celých čísel – C#
Vstup: pole číslic a[n] a b[n] odpovídající vstupním číslům čteným od konce
Výstup: pole číslic c[n+1] odpovídající výsledku čtenému od konce
Kód funkce: static int[] ScitaniCisel(int[] a, int[] b) { int t = 0; int n = a.Length; int[] c = new int[n + 1]; for (int i = 0; i < n; i++) { c[i] = (a[i]+b[i]+t) % 10; t = (a[i] + b[i] + t) / 10; } c[n] = t; return c; }
15
Správnost algoritmu
Správnost algoritmu není obvykle snadné ověřit
Často se spokojíme s testováním algoritmu
pro rozumně zvolené množství
rozumně zvolených vstupů (běžné vstupní hodnoty, hraniční hodnoty i zakázané vstupy)
Matematický důkaz správnosti algoritmů
Většinou velmi náročný
Používá se pro kritické systémy (letadla, jaderné elektrárny, ...)
Správnost algoritmu/programu nelze dokázat algoritmicky (tj. pomocí softwaru)
16
Složitost algoritmu
Vlastnost algoritmů určující množství zdrojů potřebných pro jejich běh
časová složitost (počet operací, využitý procesorový čas)
paměťová složitost (velikost potřebné paměti)
Podle složitosti můžeme algoritmy porovnávat
Časová složitost se uvádí ve tvaru funkce, která velikosti vstupu přiřadí počet operací provedených algoritmem
Při práci se složitostmi algoritmů obvykle zanedbáváme méně podstatné rozdíly (bereme jen nejrychleji rostoucí výraz a ignorujeme i jeho konstantní násobky) Logaritmická složitost Lineární složitost Linearithmetic complexity Kvadratická složitost
Exponenciální složitost
log n
3log5(n+5), log4(n2-5n+10), log105n + log3(6n-2)
n
5n, 3n-2,10n+6, 5n+log105n
n∙log n
2n∙log105n, 3(n-5)∙log4(n2-5n+10),10n∙log5n + 12n - 6log105n
n2
17 6n2+5n-log72n, (n-2)(n+5), 12n2-5n+10
2n, 3n2-3n+4, 10n+n2-5
Ukázka analýzy algoritmu
Vstup: pole číslic a[n] a b[n] Výstup: pole číslic c[n+1]
Pseudokód algoritmu: Scitani-Cisel(a[0..n 1 t ← 0 2 for i ← 0 to n − 3 do c[i] ← (a[i] 4 t ← (a[i] + 5 c[n] ← t 6 return c
− 1], b[0..n − 1])
1 + b[i] + t) mod 10 b[i] + t)/10
Na vstupu jsou čísla s n ciframi, můžeme tedy použít n jako velikost vstupu (podobného výsledku dosáhneme, i pokud uvažujeme velikost vstupu jako 2n)
Na řádku 1 je vždy 1 operace, cyklus na řádku 2 proběhne n-krát a obsahuje přiřazení do i a řádky 3 (4 operace) a 4 (5 operací), na řádku 5 máme 1 operaci a return na řádku 6 může být také chápán jako operace. 18
Celkově máme složitost algoritmu 10n+3
Cvičení - návrh a analýza algoritmu
Pro následující problémy: a)
Vyhledání maximálního čísla v posloupnosti čísel
b)
Určení, zda je číslo prvočíslem
c)
Rozklad čísla na součin prvočísel
d)
Násobení 2 libovolně velkých čísel
Popište problém co nejpřesněji, včetně formátu vstupů a výstupů
Zapište algoritmus jejich řešení slovně
Zapište algoritmus jejich řešení pomocí pseudokódu
Pokuste se určit/odhadnout časovou složitost algoritmů 19
