Rozdíly

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

--- informatika:maturita:16a [12. 03. 2019, 08.24] – [Djikstrův algoritmus] xbenes2
+++ informatika:maturita:16a [26. 05. 2020, 13.21] (aktuální) – [Eratosthenovo síto] xdostal
@@ Řádek 3: / Řádek 3: @@
 ===== Pojmy =====
-  * **Algoritmus** - přesný postup, kterým lze vyřešit určitou úlohu
+  * **Algoritmus** – konečná sekvence operací sloužící k řešení určitého typu úlohy
-  * **Program** - zápis algoritmu v určitém programovacím jazyce (je spustitelný počítačem)
+  * **Program** – systematicky sestavený soubor algoritmů, zapsaný v určitém programovacím jazyce, který lze zkompilovat a spustit
-  * **Programovací jazyk** - prostředek pro zápis algoritmů a tvorbu programů
+  * **Programovací jazyk** – prostředek pro zápis algoritmů a tvorbu programů
 ===== Pravidla programovacích jazyků =====
-  * **Syntaxe** (forma) - Definuje kombinaci symbolů, které jsou považovány za správně strukturovaný kód v konkrétním jazyce (např. středník na konci řádku, řetězec v uvozovkách, použití různých typů závorek). Při porušení syntaktických pravidel nejde program zkompilovat.
+  * **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é provádí počítač při vykonávání programu (např. a = 1 + 1 - dojde k sečtení dvou čísel a výsledek bude uložen do proměnné s názvem "a").
+  * **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.
-===== Vlastnosti algoritmus =====
+===== Vlastnosti algoritmu =====
-  * **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í být stejný výstup
+  * **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
-  * **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)
+  * **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
-  * **Finitivnost** - algoritmus by měl vždy mít omezený počet kroků, po kterých skončí
+  * **Finitivnost** (Konečnost) – U algoritmu musí být možné určit po jaké době skončí, či musí být myslitelné naplnění podmínky pro jeho ukončení
-  * **Resultativnost** - musí mít nějaký výstup, který je řešením daného úkolu
+  * **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í
-  * **Korektnost** - výstup by měl být správně
+  * **Korektnost** (Správnost) – Výstup by měl být správně (platí zejména pro výpočetní algoritmy)
-  * **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
+  * **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
@@ Řádek 25: / Řádek 27: @@
 ==== Eratosthenovo 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. 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).
+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
 [[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.
-Nejlépe se to asi ukáže na příkladu. Máme zadaná dvě čísla 140 a 15.
+Zde příklad: jsou zadána dvě čísla 140 a 15.
 Postup:
@@ Řádek 41: / Řádek 55: @@
 [[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. Funguje tak, že 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 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 požadovaného bodu.
+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.
 {{: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.