Rozdíly

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

--- informatika:maturita:16a [28. 02. 2020, 00.32] – Provedena stylistická a faktografická úprava, přidány dva typy pravděpodobnostních algoritmů. xbures1
+++ informatika:maturita:16a [11. 02. 2026, 09.47] (aktuální) – xwolf4
@@ Řádek 15: / Řádek 15: @@
 ===== Vlastnosti algoritmu =====
-  * **Determinovanost** (Určenost) – V každé situaci musí být naprosto zřejmé jaký krok (instrukce) se právě provádí a jaký má následovat
+  * **Determinovanost** (Určenost)
-  * **Obecnost** – Algoritmus by měl řešit typovou úlohu co nejvíce obecně, např. výpočty s využítím proměnných místo numerických konstant
+    * Binární vlastnost - Odpovídá na otázku: "Je výsledek algoritmu vždy stejný pro stejné vstupní hodnoty?"
-  * **Finitivnost** (Konečnost) – Algoritmus by měl vždy mít omezený počet kroků, po kterých skončí (výjimkou z klasického pojetí konečnosti může být cyklické opakování určitého z kroků)
+    * 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.
-  * **Resultativnost** (Výslednost) – Musí mít nějaký výstup, tím je buď řešení úlohy a nebo oznámení o nemožnosti nalezení tohoto řešení
+    * Základní kámen funkcionálního programování a jednou z podmínek takzvané [[https://en.wikipedia.org/wiki/Pure_function|"pure function"]]
-  * **Korektnost** (Správnost) – Výstup by měl být správně (platí zejména pro výpočetní algoritmy)
+  * **Obecnost**
-  * **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
+    * Popisuje pro jakou množinu vstupů algoritmus funguje.
+    * Analogií obecnosti algoritmu je definiční obor funkce.
+    * 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ů).
+  * **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 =====
@@ Řádek 30: / Řádek 42: @@
 Postup:
-  * 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.
+Krok 1: Vytvoření seznamu, obsahujícího všechna čísla v rozsahu 2 až n:
-  * Algoritmus končí pokud je z pole odebráno poslední číslo, nebo pokud je jako prvočíslo označeno číslo vyšší než odmocnina nejvyššího čísla (pak jsou všechny zbylé prvky prvočísla).
+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)
@@ Řádek 48: / Řádek 69: @@
   * 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í]]
@@ Řádek 63: / Řádek 88: @@
   * Algoritmus pak jako výstup vydá nejrychlejší cestu do požadovaného bodu B.
+Nejhorší možná časová složitost: O(V^2)
-{{:informatika:maturita:dijkstra_animation.gif?283|}}
+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:
+===== Pravděpodobnostní algoritmy: =====
 ==== Algoritmus Las Vegas ====