Algoritmus
Obsah lekce:
- Algoritmus
- Vlastnosti algoritmu
- Příklady algoritmů
- Počítačový program
- Zápis algoritmů
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). Je to předpis, podle kterého počítač (procesor) provádí výpočty realizující požadované řešení daného problému. Jako jistý druh algoritmu se může chápat i např. kuchyňský recept.
Pokud bychom měli zpřesnit pojem algoritmus pro naši potřebu, pak lze říct, že algoritmus je předpis, jak řešit určitý problém. Jinými slovy přesně definovaná konečná posloupnost kroků, která umožní, pro přípustné hodnoty vstupních dat (vstupní informce), nalézt v konečném počtu kroků korektní výstupní data (výsledek). Pokud bychom chtěli být opravdu přesní, tak algoritmus bychom definovali jako "proceduru realizovatelnou Turingovým strojem." Není však v našich možnostech toto nyní objasňovat neboť je to již látka řešená zpravidla až v rámci vysoké školy.
- 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ý.
- 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. 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.
- Vstup (univerzálnost) - Vstupy mají definované množiny hodnot, jichž mohou nabývat. Algoritmus lze použít celou množinu vstupních dat. Algoritmus obvykle pracuje s nějakými vstupy, veličinami, které jsou mu předány před započetím jeho provádění, nebo v průběhu jeho činnosti.
- Výstup (rezultativnost) - 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 - rezultativnost)
- Obecnost (hromadnost, masovost) - 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“).
- Efektivita - Obecně požadujeme, aby algoritmus byl efektivní, v tom smyslu, že požadujeme, aby každá operace požadovaná algoritmem, byla dostatečně jednoduchá na to, aby mohla být alespoň v principu provedena v konečném čase pouze s použitím tužky a papíru (tj. byla elementární).
V praxi jsou proto předmětem zájmu hlavně takové algoritmy, které jsou v nějakém smyslu kvalitní. Takové algoritmy splňují různá kritéria, měřená např. počtem kroků potřebných pro běh algoritmu, nebo jednoduchost či elegance algoritmu. Problematikou efektivity algoritmů, tzn. metodami, jak z několika známých algoritmů řešících konkrétní problém vybrat ten nejlepší, se zabývají odvětví informatiky nazývané algoritmická analýza a teorie složitosti.
Část textu o algoritmu a jeho vlastnostech byla převzata z Wikipedie (http://cs.wikipedia.org/wiki/Algoritmus).
Počítačový program
Počítačový program (dále jen program) je z hlediska informatiky popis postupu operací, které realizují zadanou úlohu. Zápis algoritmu v některém z programovacích jazyků nazýváme program. Program zpravidla vytváří (zapisuje) programátor. Jako příklad uvedeme jednoduchý program, který nechá uživatele zadat dvě čísla a a b a vypíše na obrazovku jejich součet.
Algoritmus realizovaný tímto programem by bylo možné v přirozeném jazyce vyjádřit například takto:
- Zadej číslo a.
- Zadej číslo b.
- Zobraz na obrazovku součet a+b.
Program SectiDveCisla;
var a,b:integer;
begin
readln(a);
readln(b);
writeln(a+b);
end.
import java.util.Scanner;
public class InputExp {
public static void main(String[] args) {
int a,b;
Scanner in = new Scanner(System.in);
a = in.nextInt();
b = in.nextInt();
in.close();
System.out.println(a+b);
}
}
Psaní programu má svá pravidla, ale přehlednosti zdrojového kódu programu můžeme pomoci tím, jak jej napíšeme. Předchozí ukázku programu přepíšeme například takto:
import java.util.Scanner;
public class InputExp {
public static void main(String[] args) {
int a,b;
Scanner in = new Scanner(System.in);
a = in.nextInt();
b = in.nextInt();
in.close();
System.out.println(a+b);
}
}
Je vidět, že byť třeba programu nerozumíme, tak je pro nás daleko čitelnější.
Zápis algoritmů
Algoritmy je možno zapisovat mnoha způsoby. Na jednoduchém algoritmu pro součet dvou zadaných čísel ukážeme některé z nich:
A) Slovním vyjádřením (obdoba kuchyňského receptu):
- Zadej číslo a.
- Zadej číslo b.
- Zobraz na obrazovku součet a+b.
B) Pomocí diagramu (jednoduchý nákres, schéma, vývojový diagram, strukturogram, apod.) znázorňujícího postup řešení:
C) V programovacím jazyce:
Program SectiDveCisla;
var a,b:integer;
begin
readln(a);
readln(b);
writeln(a+b);
end.
#include "stdafx.h"
int _tmain(int argc, _TCHAR* argv[])
{
int a, b;
scanf("%d", &a);
scanf("%d", &b);
printf("%d",a+b);
return 0;
}
Další čtení
- http://cs.wikipedia.org/wiki/Algoritmus
- http://cs.wikipedia.org/wiki/The_Art_of_Computer_Programming monografie The Art of Computer Programming
- http://cs.wikipedia.org/wiki/Po%C4%8D%C3%ADta%C4%8Dov%C3%BD_program
- http://www.fi.muni.cz/~tomp/java/ucebnice/resources.html - stránka Tomáše Pitnera s odkazy na stránky s problematikou jazyka Java
- http://cs.wikipedia.org/wiki/Turingův_stroj
- http://cs.wikipedia.org/wiki/Church-Turingova_teze aneb odpověd na otázku "Proč je každý myslitelný algoritmus vyjádřitelný Turingovým strojem?".
Otázky
- Co rozumíte pod pojmem algoritmus?
- Jaké základní vlastnosti by měl splňovat algoritmus? Pokuste se jednotlivé vlastnosti uvést na příkladech.
- Co si představujete pod pojmem počítačový program?
- Je možné pomocí jinak strukturovaného zápisu programu zlepšit jeho čitelnost? Ilustrujte na příkladu.