Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- informatika:maturita:16a [06. 01. 2015, 14.03] – [Základní prvky algoritmů] xmrnustik
+++ informatika:maturita:16a [11. 02. 2026, 09.47] (aktuální) – xwolf4
@@ Řádek 1: / Řádek 1: @@
 ====== Algoritmizace ======
-===== Algoritmus =====
-Algoritmus je přesný popis pracovního procesu, který z měnitelných vstupních údajů dochází k žádaným výsledkům.
+===== Pojmy =====
-==== 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
-==== Základní prvky algoritmů ====
-=== Podmínky (selekce) ===
-Umožňují větvení algoritmů. Podmínky můžou mít čtyři možné formy. První forma jsou podmínky typu **if-then**, když něco, tak dělej ("Pokud máš řidičák, budeš řídit."). Druhou formou jsou podmínky typu **if-else** když něco, tak dělej, a pokud ne něco, tak dělej něco jiného ("Když máte kuřecí kůžičky, přidejte je, pokud je nemáte použijte potravinovou fólii." - převzato z kuchařky Ládi Hrušky).
-<WRAP center round tip 60%>
-Přidat ternární operátor a switch-case
-</WRAP>
-=== Cykly ===
+  * **Algoritmus** – konečná sekvence operací sloužící k řešení určitého typu úlohy
-Umožňují vícenásobné opakování části algoritmu. Cykly můžou mít také dvě možné formy. První forma jsou cykly typu **while**, dokud něco tak prováděj ("Dokud máš v košíku nákup, skládej ho na pult."). Druhá forma jsou cykly typu **do-while** prováděj dokud něco("Ohřívej vodu, dokud nezačne vařit."). Hlavní rozdíl mezi cykly typu while a do-while je ten, že cyklus typu do-while proběhne minimálně jednou, zatímco cyklus while pokud nebude hned na počátku splněna podmínka nemusí.
+  * **Program** – systematicky sestavený soubor algoritmů, zapsaný v určitém programovacím jazyce, který lze zkompilovat a spustit
-<WRAP center round tip 60%>
+  * **Programovací jazyk** – prostředek pro zápis algoritmů a tvorbu programů
-Přidat for a for-each
-</WRAP>
-==== Ukázka algoritmu ====
+===== Pravidla programovacích jazyků =====
+  * **Syntaxe** (forma) – Definuje kombinaci symbolů, které jsou považovány za správně strukturovaný kód. V každém programovacím jazyce bývá syntaxe odlišná. Jejími typickými prvky jsou např. závorky, středníky, mezery a tabulátory. Je-li syntaxe chybná, výsledný program nelze zkompilovat.
+  * **Sémantika** (význam) – Zhodnocuje význam syntakticky platných řetězců a provádí jejich výpočty. Popisuje procesy, které počítač provádí při běhu programu. Například:
+  * //int number = 1 + 1;//
+  * Dojde k inicializaci deklarované proměnné "number" – je do ní vložen výsledek součtu 1 + 1.
-**Vajíčka**
-  * **Vstupní údaje:** počet vajec, typ tuku, šunka
-  * **Výstup:** poživatelná volská oka
-  - Vezmi pánev
+===== Vlastnosti algoritmu =====
-  - POKUD je typ tuku máslo, vezmi z lednice máslo
+  * **Determinovanost** (Určenost)
-  - POKUD NENÍ, vem ze skříně olej (**if-else**)
+    * Binární vlastnost - Odpovídá na otázku: "Je výsledek algoritmu vždy stejný pro stejné vstupní hodnoty?"
-  - Dej olej na pánev
+    * Algoritmus není determinovatelný pokud má vnitřní stav (například počítá kolikrát algoritmus byl spuštěn) nebo pokud používá skutečně náhodné hodnoty.
-  - Přidej na pánev šunku
+    * Základní kámen funkcionálního programování a jednou z podmínek takzvané [[https://en.wikipedia.org/wiki/Pure_function|"pure function"]]
-  - DOKUD není šunka dozlatova, čekej (**while**)
+  * **Obecnost**
-  - Přidej vejce, DOKUD tam nejsou všechny (**do-while**)
+    * Popisuje pro jakou množinu vstupů algoritmus funguje.
-  - DOKUD vše není hotovo, čekej (**while**)
+    * Analogií obecnosti algoritmu je definiční obor funkce.
-  - Vypni plotnu
+    * Algoritmus by měl řešit typovou úlohu co nejvíce obecně, například implementace kosinové věty je obecnější než implementace pythagorovy věty (funguje pro větší množinu úhlů).
-  - Jez!
+  * **Finitivnost** (Konečnost)
+    * Binární vlastnost - Odpovídá na otázku: "Skončí algoritmus pro jakýkoliv vstup po konečně mnoha krocích?"
+  * **Resultativnost** (Výslednost)
+    * Binární vlastnost - Odpovídá jestli má pro daný vstup algoritmus nějaký výstup nebo ne.
+    * Algoritmus není resultativní pokud vrací void a neměnní vnější proměnné.
+  * **Korektnost** (Správnost)
+    * Binární vlastnost - Vydá algoritmus pro všechny vstupy správný výsledek?
+  * **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 často k sobě ve vztahu nepřímé úměry (například dynamické programování).
+    * Primárně se určuje pomocí velké O notace.
+    * Sekundárně se určuje podle praktických záležitostí (například cache miss nebo CPU branch prediction)
+{{:informatika:maturita:big_o.jpg?400|}}
+===== Známé algoritmy =====
+==== Eratosthenovo síto ====
+Algoritmus pro získání všech prvočísel od dvou po dané číslo.
+Postup:
+Krok 1: Vytvoření seznamu, obsahujícího všechna čísla v rozsahu 2 až n:
+Krok 2: První číslo ze seznamu je zapsáno jako prvočíslo do seznamu prvočísel a ze seznamu je vymazáno společně se všemi jeho násobky.
+Krok 3: Opakuj krok 2, dokud není původní seznam prázdný.
+Krok 4: Seznam prvočísel obsahuje všechna prvočísla od 2 po n
+Časová složitost: O(n log(log(n)))
+Paměťová složitost: O(1)
+[[https://www.youtube.com/watch?v=2SD2lLFj4h0&feature=player_detailpage|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.
+Zde příklad: jsou zadána dvě čísla 140 a 15.
+Postup:
+  * Nejprve zjistíme zbytek po dělení většího čísla číslem menším. (V našem případě 140 = 9 * 15 + **5**)
+  * Nyní zopakujeme první krok, ale s dělením menšího čísla zbytkem po dělení (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
+Časová složitost: O(log(min(a, b)))
+Paměťová složitost: O(1)
+[[http://www.algoritmy.net/article/44/Eukliduv-algoritmus|Podrobnější vysvětlení]]
+==== Djikstrův algoritmus ====
+Algoritmus sloužící pro výběr nejlepší trasy z bodu A do bodu B.
+Postup:
+  * Každá cesta mezi jednotlivými body dostane hodnotu, podle "náročnosti" (délka trasy, povolená rychlost, ...).
+  * Algoritmus si postupně vypočítává délku cesty z bodu A do všech sousedních bodů a z nich do dalších bodů.
+  * Pokud algoritmus najde novou cestu do již objeveného bodu, pomalejší cestu k tomuto bodu odstraní.
+  * Na konci zůstane pouze jedna nejrychlejší cesta do kažhého z bodů.
+  * Algoritmus pak jako výstup vydá nejrychlejší cestu do požadovaného bodu B.
+Nejhorší možná časová složitost: O(V^2)
+Nějhorší možná paměťová složitost: O(V + H)
+V = počet vrcholů
+H = počet hran
+{{:informatika:maturita:dijkstra_animation.gif?283|}}
+===== Pravděpodobnostní algoritmy: =====
+==== Algoritmus Las Vegas ====
+Algoritmus hledající prvek žádaného typu v množině s více typy prvků. V základní podobě algoritmu je narušen jak princip determinismu, tak princip konečnosti (není-li běhový čas algoritmu či počet opakování cyklu nijak omezen, běhová doba algoritmu se teoreticky může blížit nekonečnu ...).
+Postup:
+  * Algoritmus vybere prvek množiny s náhodně přiděleným pořadovým číslem v rámci povoleného rozsahu odpovídajícím velikosti možiny.
+  * Poté algoritmus u získaného prvku ověřuje typ, je-li typ shodný s typem hledaným, prvek vrátí jako výsledný výstup.
+  * Pokud však typ prvku neodpovídá, postup se opakuje a to tak dlouho, dokud není nalezen prvek typově odpovídající.
+==== Algoritmus Monte Carlo ====
+Algoritmus s cílem analogickým k výše zmíněnému. Je alternativou k algoritmu Las Vegas, neboť nabízí konečnost (ukončení běhu cyklu v závislosti na parametru maximálního běhového času či počtu opakování cyklu) výměnou za jistou pravděpodobnost nedosažení cíle (není-li v rámci daného času či počtu opakování nalezen prvek žádaného typu, algoritmus skončí a vrátí se "s prázdnou").
+Postup:
+  * Algoritmus vybere prvek množiny s náhodně přiděleným pořadovým číslem v rámci povoleného rozsahu odpovídajícím velikosti možiny.
+  * Poté algoritmus u získaného prvku ověřuje typ, je-li typ shodný s typem hledaným, prvek vrátí jako výsledný výstup.
+  * Pokud však typ prvku neodpovídá a zároveň není dosaženo maximálního času či počtu opakování cyklu, postup je zopakován.