A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Deterministický algoritmus je v informatice označení pro algoritmus, který vždy ze stejných výchozích (vstupních) podmínek svým během vytvoří stejné výsledky (je tedy předvídatelný). Každý aktuální i následující krok vykonávání algoritmu je vždy jednoznačně definován, což je rozdíl oproti nedeterministickým algoritmům, kde následující krok nemusí být vždy jednoznačně určen.
Využití determinističnosti je aktuálně předmětem studií v mnoha oborech, především pro možnost praktického a efektivního způsobu použití na dnešních běžných počítačích. Formálně je deterministický algoritmus definován jako algoritmus pro výpočet matematických funkcí, které mají konkrétní hodnotu výstupu pro daný vstup.
Formální definice
Deterministický algoritmus může být definován konečným automatem (stavovým strojem), kde jsou jednoznačně určeny podmínky přechodu mezi vnitřními stavy automatu. Každý stav popisuje stav automatu v konkrétním časovém okamžiku. Stavové automaty procházejí podle předem daných pravidel diskrétním způsobem z jednoho stavu do druhého. Na začátku je vždy automat v počátečním stavu a má dány vstupní hodnoty. Pokud je automat deterministický, jeho aktuální stav určuje skupinu stavů následujících, přičemž je dle přechodové podmínky vybrán vždy právě jeden nový stav. Je důležité mít na paměti, že stroj může být deterministický a zároveň nekonečný, to znamená, že nikdy nebude znám výsledek algoritmu. Příkladem konkrétních abstraktních deterministických strojů je Turingův stroj a deterministické konečné automaty.
Příčiny nedeterminismu
Následující faktory mohou zapříčinit vznik nedeterminismu v deterministickém algoritmu:
- pokud je vstup algoritmu neošetřený na nepřípustné hodnoty – uživatelský vstup, globální proměnná, hodnota hardwarového časovače nebo náhodná hodnota
- pokud je zpracování algoritmu závislé na časování a následné synchronizaci (při paralelním zpracování[1]) – například vice procesů postupně zapisuje do proměnné, konečný výstup je závislý na pořadí zapsání hodnot
- pokud chyba hardwaru může způsobit přechod mezi stavy nedefinovanou cestou, nebo naopak nekonečné zacyklení algoritmu
I když jsou dnešní programy zřídka kdy čistě deterministické, jsou pro člověka mnohem více pochopitelné. Proto většina programovacích jazyků nabízí možnosti, jak předejít všem výše uvedeným faktorům pro vznik nedeterminismu, kromě kontrolovaných výjimek, které ovšem programátor musí ošetřit.
Problém deterministických algoritmů
Stále jsou aktuálně známé problémy pro které je obtížné najít deterministický algoritmus, který by daný problém vyřešil. Klasickým příkladem je určení, zda je dané číslo prvočíslo. Jako algoritmy pro určení jsou dnes využívány tzv. pravděpodobnostní algoritmy. Jsou známé již od roku 1970 (Fermatův test prvočíselnosti), jsou ovšem v praxi velmi pomalé a neefektivní.
Jako další příklad lze uvést NP-úplné problémy, které zahrnují mnohé z nejdůležitějších praktických problémů. Ty lze teoreticky efektivně řešit pomocí nedeterministických Turingových strojů, ovšem konkrétní praktické (deterministické) algoritmy zatím nalezeny nebyly. V dnešní době lze najít pouze přibližné řešení.
Dalším problém deterministických algoritmů je, že v některých případech požadujeme pravý opak – výsledek zcela nepředvídatelný. Například při karetních hrách (Black Jack), kdy je míchání balíčku realizováno pomocí pseudonáhodného generátoru čísel, je možné po určité době sledování odhadnout přesně se generující řadu čísel a tím pádem i obsah celého balíčku.[2] Podobné problémy vznikají v kryptografii, kde jsou soukromé klíče často generovány pomocí tohoto generátoru. Těmto druhům problémů se lze obecně vyhnout pomocí kryptograficky bezpečného pseudo-generátoru náhodných čísel.
Reference
V tomto článku byl použit překlad textu z článku Deterministic_algorithm na anglické Wikipedii.
- ↑ Andrews, G.R.: Foundations of Multithreaded, Parallel, and Distributed Programming. Addison Wesley, 2000, ISBN 0-201-35752-6
- ↑ Gary McGraw and John Viega. Make your software behave: Playing the numbers: How to cheat in online gambling. http://www.ibm.com/developerworks/library/s-playing/#h4
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Antény
Chemické zdroje elektriny
Chladenie v elektrotechnike
Elektrická sústava automobilu
Elektrická trakcia
Elektrické prístroje
Elektrické súčiastky
Elektrické spotrebiče
Elektrické stroje
Čítanie (elektrotechnika)
Činný výkon
Štatistická dynamika
Živý vodič
Admitancia
Antiparalelné zapojenie
Asynchrónny motor
Blúdivý prúd
Bočník (elektrotechnika)
Diak (polovodičový prvok)
Displej s kvapalnými kryštálmi
Elektrická inštalácia
Elektrická rezonancia
Elektrická sila
Elektrická vodivosť
Elektrické zariadenie
Elektrický obvod
Elektrický zvonec
Elektroenergetika
Elektromer
Elektrometer
Elektromobil
Elektromotor
Elektromotorické napätie
Elektrotechnický náučný slovník
Elektrotechnika
Elektrotechnológia
Fázor
Faradayova klietka
Frekvencia (fyzika)
Graetzov mostík
Impedancia
Indukčnosť
Induktancia
Istič
Izolácia (elektrotechnika)
Izolant
Jadro vodiča
Jednobran
Jednosmerný prúd
Joulovo teplo
Katóda
Koaxiálny kábel
Kompenzácia účinníka
Konduktometria
Konektor (elektrotechnika)
Korónový výboj
Lanko (elektrotechnika)
Leptanie
Logické hradlo
Magnetická susceptibilita
Magnetizácia (veličina)
Merný elektrický odpor
Mobilné zariadenie
Napájací zdroj
Napäťový chránič
Napäťový násobič
Nortonova veta
Odpínač
Odpojovač
OLED
Olovený akumulátor
Paralelné zapojenie
Peltierov článok
Plošná hustota elektrického prúdu
Poistka (elektrotechnika)
Posuvný prúd
Prúdový chránič
Prenosové médium
Prieletový klystrón
Primárny elektrochemický článok
Reaktancia
Rekuperácia (dopravný prostriedok)
Relé
Reproduktorová výhybka
Rezistancia
Rozhranie (interface)
Sériové zapojenie
Seebeckov jav
Sekundárny elektrochemický článok
Settopbox
Skrat
Sonar
Spínač
Spínaný zdroj
Straty v mikropásikových vedeniach
Striedavý prúd
Stupeň ochrany krytom
Svetelná výbojka
Symetrizačný člen
Technická normalizácia
Tepelné relé
Tepelne vodivostný detektor
Termočlánok
Théveninova veta
Transformátor
Transformátor s fázovou reguláciou
Trojfázová sústava
Tuhá fáza (elektronika)
Tyratrón
Usmerňovač (elektrotechnika)
Uzemnenie
Uzol (vodiče)
Vírivý prúd
Výbojka
Varistor
Ventilátor
Vodič (elektrotechnika)
Voltov stĺp
Vstavaný systém
Zásuvka (elektrotechnika)
Zdroj (elektrotechnika)
Zisk antény
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk