Pojem algoritmus a jeho základní vlastnosti

Vyšší odborná škola, Obchodní akademie a Střední odborná škola EKONOM, o. p. s. Litoměřice, Palackého 730/1

DUM Téma: Úvod do algoritmů - výklad Varianta: A

Algoritmy

DUM III/2-T1-1-1 PRG-01A-var1

Střední škola

Rok: 2012 – 2013

Zpracoval: Mgr. Pavel Hrubý

VÝKLAD

Pojem algoritmus a jeho základní vlastnosti Obsah Algoritmus ............................................................................................................................................... 2 Vlastnosti algoritmu ............................................................................................................................ 3 Konečnost (finitnost) ....................................................................................................................... 3 Obecnost (hromadnost, masovost, univerzálnost) ......................................................................... 3 Determinovanost ............................................................................................................................. 3 Výstup (resultativnost) .................................................................................................................... 3 Elementárnost ................................................................................................................................. 3 Algoritmizace ....................................................................................................................................... 3 Analýza úlohy .................................................................................................................................. 4 Vytvoření algoritmu úlohy ............................................................................................................... 4 Sestavení programu......................................................................................................................... 4 Odladění programu ......................................................................................................................... 4 Příklady algoritmů ............................................................................................................................... 4 Algoritmus zatloukání hřebíků ........................................................................................................ 4 Algoritmus přechodu křižovatky, řízené semaforem ...................................................................... 5 Zdroje a odkazy: .............................................................................................................................. 5

Operační program CZ.1.07 Vzděláním pro konkurenceschopnost Registrační číslo projektu CZ.1.07/1.5.00/34.0553 Název projektu Elektronická podpora zkvalitnění výuky Projekt je realizován v rámci Operačního programu Vzdělávání pro konkurence schopnost, který je spolufinancován z Evropského sociálního fondu a ze státního rozpočtu České republiky DUM-III2-T1-1-01_vyklad_1-uvod_do_algoritmu.docx stránka 1


Algoritmus Algoritmus je přesný návod či postup, kterým lze vyřešit daný typ úlohy. Pojem algoritmu se nejčastěji objevuje při programování, kdy se jím myslí teoretický princip řešení problému (oproti přesnému zápisu v konkrétním programovacím jazyce). Obecně se ale algoritmus může objevit v jakémkoli jiném vědeckém odvětví. Jako jistý druh algoritmu se může chápat i např. kuchařský recept. V užším smyslu se slovem algoritmus rozumí takové postupy, které splňují některé silnější požadavky:     

konečnost (finitnost) obecnost (hromadnost, masovost, univerzálnost) determinovanost výstup (resultativnost) elementárnost

Algoritmy vznikaly už dávno před zkonstruováním prvních počítačů. Samotné slovo "algoritmus" vzniklo ze jména perského matematika, který žil v 9. století a jmenoval se Mohammed al-Khowarizmí (v latinském přepise Algoritmus). Zabýval se především pravidly pro aritmetické operace s čísly. Například Eukleidův algoritmus pro výpočet největšího společného dělitele dvou přirozených čísel pochází už z 4. až 3. století před naším letopočtem. Algoritmy můžeme zapisovat buď v přirozeném jazyce nebo v některém z vyšších programovacích jazyků a nebo přímo ve strojovém kódu počítače či strojovém kódu hypotetického počítače, kterým je například Turingův stroj. Pokud chcete hlouběji pochopit, co to vlastně algoritmus je a udělat si pořádek v pojmech kolem algoritmů, je nutné se nejdříve věnovat trošce nezbytné teorie.



Vlastnosti algoritmu Konečnost (finitnost) Každý algoritmus musí skončit v konečném počtu kroků. Tento počet kroků může být libovolně velký (podle rozsahu a hodnot vstupních údajů), ale pro každý jednotlivý vstup musí být konečný. Postupy, které tuto podmínku nesplňují, se mohou nazývat výpočetní metody. Speciálním příkladem nekonečné výpočetní metody je reaktivní proces, který průběžně reaguje s okolním prostředím. Někteří autoři však mezi algoritmy zahrnují i takovéto postupy. Obecnost (hromadnost, masovost, univerzálnost) Algoritmus neřeší jeden konkrétní problém (např. „jak spočítat 3×7“), ale obecnou třídu obdobných problémů (např. „jak spočítat součin dvou celých čísel“), má širokou množinu možných vstupů. Determinovanost Každý krok algoritmu musí být jednoznačně a přesně definován; v každé situaci musí být naprosto zřejmé, co a jak se má provést, jak má provádění algoritmu pokračovat, takže pro stejné vstupy dostaneme pokaždé stejné výsledky. Protože běžný jazyk obvykle neposkytuje naprostou přesnost a jednoznačnost vyjadřování, byly pro zápis algoritmů navrženy programovací jazyky, ve kterých má každý příkaz jasně definovaný význam. Vyjádření výpočetní metody v programovacím jazyce se nazývá program. Některé algoritmy ale determinované nejsou, pravděpodobnostní algoritmy v sobě mají zahrnutu náhodu. Výstup (resultativnost) Algoritmus má alespoň jeden výstup, veličinu, která je v požadovaném vztahu k zadaným vstupům, a tím tvoří odpověď na problém, který algoritmus řeší (algoritmus vede od zpracování hodnot k výstupu) Elementárnost Algoritmus se skládá z konečného počtu jednoduchých (elementárních) kroků.

Algoritmizace Algoritmizace je postup při tvorbě programu pro počítač, kterým lze prostřednictvím algoritmu řešit nějaký problém. Algoritmizaci lze rozdělit do několika etap: 1. 2. 3. 4. 5. 6.

Formulace problému Analýza úlohy Vytvoření algoritmu Sestavení programu Odladění programu Formulace problému

V této etapě je třeba přesně formulovat požadavky, určit výchozí hodnoty, požadované výsledky, jejich formu a přesnost řešení.



Analýza úlohy Při analýze úlohy si ověříme, zda je úloha řešitelná a uděláme si první představu o jejím řešení. Dále zjistíme, zda výchozí hodnoty jsou k řešení postačující a zda má úloha více řešení. Podle charakteru úlohy vybereme nejvhodnější řešení. Vytvoření algoritmu úlohy Sestavíme jednoznačný sled jednotlivých operací, které je třeba provést, aby byla úloha správně vyřešena. Algoritmus přesně popisuje postup zpracování daného úkolu, nedává však odpověď na daný problém, ale pouze postup, jak ji získat. Sestavení programu Na základě algoritmu řešené úlohy sestavíme program (zdrojový text) v konkrétním programovacím jazyce. Ze zdrojového textu se pomocí překladače do strojového kódu vytvoří spustitelný program. Dá se tedy říci, že dobře provedená analýza úlohy a algoritmizace daného problému je základním předpokladem sestavení programu pro počítač. Odladění programu Cílem odladění je odstranění chyb z programu. Nejčastější chyby jsou chyby v zápise, tzv. syntaktické - ty odhalí překladač. Závažnější jsou logické chyby, vyplývající z nesprávně navrženého algoritmu, nebo chyby, vzniklé špatným předpokladem v etapě formulace nebo analýzy úlohy - ty se projeví nesprávnou činností programu nebo špatnými výsledky - při odstraňování těchto chyb může pomoci ladící program (debugger) umožňující sledování aktuálního stavu proměnných a krokování. Teprve po odstranění všech druhů chyb můžeme program použít k praktickému řešení úloh.

Příklady algoritmů Algoritmus zatloukání hřebíků Formulace problému: Zatluč hřebík do desky.

Analýza úlohy:

Vstupní údaje: Výstupní údaje: Analýza:

Sestavení algoritmu

Slovní popis:

kladivo, hřebík, deska hřebík zatlučen do desky tlouct tak dlouho, dokud není hřebík zatlučen až po hlavičku 1. Vezmi kladivo a hřebík 2. Přilož hřebík k desce 3. Uhoď kladivem na hlavičku 4. Je hřebík zatlučen? 5. ANO - pokračuj bodem 5 6. NE - vrať se na bod 3 7. Ukonči činnost a odlož kladivo



Algoritmus přechodu křižovatky, řízené semaforem Formulace problému: Přejdi na druhou stranu ulice.

Analýza úlohy:

Sestavení algoritmu

Vstupní údaje: Výstupní údaje: Analýza: Slovní popis:

přechod, semafor pozice na druhé straně ulice přes přechod se nechodí na červenou 1. Dojdi až k semaforu 2. Svítí na semaforu červená? 3. ANO - čekej, vrať se na bod 2 4. NE - pokračuj bodem 3 5. Přejdi přes přechod

Zdroje a odkazy: Wikipedie: Otevřená encyklopedie: Algoritmus [online]. c2012 [citováno 7. 8. 2012]. Dostupný z WWW: DIVIŠ, Josef. Algoritmus. SPŠE Mohelnice; [online]. c2012 [citováno 7. 8. 2012]. Dostupný z WWW: < http://www.spsemoh.cz/vyuka/algor/> MIČKA, Pavel.. Algoritmy.net. [online]. c2012 [citováno 7. 8. 2012]. Dostupný z WWW: http://www.algoritmy.net/ WRÓBLEWSKI, Piotr. Algoritmy : Datové struktury a programovací techniky. Brno : Computer press, 2004. 351 s. ISBN 80-251-0343-9.


Pojem algoritmus a jeho základní vlastnosti

Recommend Documents