Algoritmizace

Pojmy

Algoritmus - přesný abstraktní postup určený pro vyřešení dané úlohy

Program - konkrétní řešení algoritmu v daném programovacím jazyce

Programovací jazyk - prostředek pro zápis algoritmů

Pravidla programovacích jazyků

Dělíme na:

Syntaktická - způsob jakým máme program zapisovat (klíčová slova(= názvy konstrukcí a proměnných), středníky na konci řádků, pojmenování proměnných,…), při porušení syntaktických pravidel nejde program zkompilovat

Sémantická - způsob jakým budou implementovány jednotlivá klíčová slova (pokud je tam if tak je to podmínka,…)

Vlastnosti algoritmus

Determinovanost - 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, pro stejné vstupní data musí mít stejný výstup

Obecnost - algoritmus by neměl řešit jeden konkrétní problém (například 5 x 5), ale měl by nabízet obecné řešení daného problému (například X x Y)

Finitivnost - algoritmus by měl vždy mít omezený počet kroků, po kterých skončí

Resultativnost - musí mít nějaký výstup

Korektnost - výstup by měl být správně

Efektivita - děláí se na paměťovou efektivitu (náročnost na paměť) a výpočetní efektivitu (náročnost na výpočet), tyto dvě vlastnosti jsou většinou k sobě ve vztahu nepřímé úměry

Známé algoritmy

Erastotenovo síto

Algoritmus pro získání všech prvočísel od dvou po dané číslo. Vytvoříme si pole všech čísel obsažených v daném rozsahu. Postupujeme postupně přes všechna čísla rozsahu a odebíráme z něj čísla, která jsou násobky těchto čísel.

Ukázka erastotenova síta na číslech od 2 do 120

Euklidův algoritmus

Algoritmus pro výpočet největšího společného dělitele (dále jen NSD) dvou čísel.

Nejlépe se to asi ukáže na příkladu. Máme zadaná dvě čísla 140 a 15. Postup:

Nejprve podělíme větší číslo číslem menším. (V našem případě 140 = 9 * 15 + 5)

„Z titulu toho“(Vojtěchu ), že obě strany rovnice by měly být dělitelny NSD a zároveň číslo 15 musí být také dělitelné NSD těchto dvou čísel, tak musí platit, že i zbytek po dělení musí být dělitelný NSD, tím pádem NSD 140 a 15 musí být zároveň NSD 15 a zbytku (tedy 5) a to vede k tomu, že aplikujeme znovu první krok

Po aplikaci prvního kroku na čísla 15 a 5 nám vyjde 15 = 3 * 5 + 0

Vyšel nám zbytek 0, takže NSD je rovno 5, pokud by nám nevyšel zbytek 0 aplikovali bychom znovu krok jedna

Djikstrův algoritmus

Algoritmus sloužící pro vybrání nejlepší trasy z bodu A do bodu B. Funguje tak, že každá cesta mezi jednotlivými body dostane hodnotu, podle „náročnosti“(může být délky trasy, povolená rychlost,…). Pro výpočet trasy se jednotlivé cesty sčítají, aby a trasa s nejnižším součtem se vybere jako finální.