Nejlepší odpověď
Na tuto otázku neexistuje žádná odpověď.
Pojďme najít odpověď na toto prohlášení o problému:
Ot. Jak zjistit, že jakýkoli algoritmus funguje lépe?
A. Nejběžnější způsoby porovnání algoritmů:
1) Časová složitost
2) Prostorová složitost
3) Kvalita řešení (nemusí použitelné, pokud navrhuje přesně vyřešit problém). Toto může být obrovským faktorem, pokud mluvíme o aproximačních algoritmech.
4) Snadná implementace / přizpůsobení algoritmu. Některé algoritmy mohou mít spoustu režijních nákladů na správnou implementaci. Někdy existují vhodnější algoritmy pro vaši aplikaci. Například v paralelních výpočtech bude většina považovat Bellman-Ford za užitečnější než Dijkstrův algoritmus díky způsobu, jakým Bellman-Ford funguje.
Čas a složitost však nejsou * vždy * požadovaná funkce pro maximalizaci; Uvedu dva příklady.
Jedním z nich je „numerická stabilita“ , což je vlastnost algoritmů v lineární algebře i v diferenciálních rovnicích. Na algoritmy, které jsou numericky stabilnější, vynaložíme více algoritmického času i větší složitost algoritmu. V lineární algebře je nestabilita obecně způsobena, když algoritmus narazí na čísla příliš blízká nule nebo nekonečnu nebo oběma, protože může dojít ke ztrátě rozlišení čísel. Obecně to způsobí velmi nepatrně odlišná čísla, jen několik navzájem odlišných epsilon (kde epsilon je nejmenší číslo, které lze přidat k jednomu na stroji a získat výsledek! = 1), což způsobí velké rozdíly v odpověď. Například například vynaložíme spoustu času a prostoru na složitost „otočením“ faktorizace LU, abychom získali stabilní algoritmus; bez otočení LU není stabilní. Podobně máme algoritmy, které nedělají nic jiného než matice „condition“, aby se zabránilo nestabilitě.
Druhým příkladem je „robustnost“ v jeho technický statistický význam. Robustnost znamená míru nebo algoritmus, který * není * citlivý na odlehlé hodnoty. Takže například když na řadu bodů vložím čáru nejmenších čtverců, čáru lze silně zkosit o jednu extrémně velkou hodnotu. I když mám 99 párů čísel, které tvoří dokonalou 45stupňovou linii, pokud přidám jediný odlehlý pár, u kterého je hodnota Y stokrát vyšší, než by „měla“ padnout na stejnou linii, bude osazená linie vážně vychýlila se ze 45 stupňů. Algoritmus se „vzdá“ dokonalého přizpůsobení 99 bodům, aby lépe reprezentoval jeden odlehlý bod. To * není * robustní.
Robustní přístup nejmenších čtverců je namísto hledání řádku, který minimalizuje součet čtvercových chyb vytvořených pomocí tohoto řádku, najít řádek, který minimalizuje * medián * čtvercové chyby vytvořené použitím tohoto řádku. V tomto příkladu je tato čára čára 45 stupňů a medián čtvercových chyb je nula a odlehlý bod (a ve skutečnosti až 98 dalších šílených odlehlých hodnot) by byl zcela ignorován. Byla by nalezena 45stupňová čára.
Podobné robustní algoritmy existují pro přizpůsobení statistických křivek, hledání tvarů atd. Jsou však časově nákladné, někdy vážně. Časové náklady však stojí za to, protože robustní statistiky jsou účinně imunní vůči „šumu“ signálů, kde přístupy s nejmenší čtvercovou chybou nejsou. Skutečný svět je plný jak šumu, tak extrémních hodnot, z nichž některé jsou způsobeny chybou člověka nebo stroje, zejména v pixelových obrazech nebo vzorkovaném zvuku. Za takových okolností může časově nákladnější robustní algoritmus najít signály v hlučném prostředí, kde rychlejší algoritmy vytvářejí odpovědi tak poškozené zvukem, že jsou k ničemu nebo dokonce nebezpečné, pokud jsou přijaty.
V některých případech čas a prostorová složitost nejsou zdaleka tak důležité jako nalezení odpovědi, která nejpravděpodobněji modeluje skutečný signál navzdory šumu a degradaci signálu.
Odpověď
Algoritmy vznikly v matematice jako „recepty“ pro provádění výpočtu založeného na funkcích, které lze sledovat mechanicky. Ve funkčním matematickém světonázoru musí být všechny vstupy specifikovány na začátku výpočtu, který probíhá uzavřeným způsobem. Pojem algoritmus je ze své podstaty neformální, protože popis algoritmu není omezen na jediný jazyk nebo formalismus.
Snad nejstarším příkladem je Euklidův algoritmus pro hledání společných dělitelů. Algoritmy zachycují, co to znamená, aby byl výpočet „efektivní“. Stejně jako matematické vzorce, i algoritmy nám říkají, jak vypočítat hodnotu; na rozdíl od nich mohou algoritmy zahrnovat to, čemu nyní říkáme smyčky nebo větve.
Role algoritmu: Vzhledem k určité konečné vstupní hodnotě x popisuje algoritmus kroky pro efektivní transformaci na výstupní hodnotu y, kde y je f (x) pro nějakou rekurzivní funkci f.
Algoritmy přijali první počítačoví vědci v padesátých letech minulého století, kteří vytvořili spojení mezi algoritmy a Turingovými stroji (TM, formální model výpočtu datovaný do roku 1936), čímž se srovnávala jejich expresivita.
Knuth výslovně uvedl, že algoritmy jsou uzavřeny; jakmile je výpočet zahájen, nepřijme se žádný nový vstup: „Algoritmus má nula nebo více vstupů, tj. veličin, které jsou mu dány původně před zahájením algoritmu.“ Rozlišoval algoritmy od libovolného výpočtu, který může zahrnovat I / O. Jedním z příkladů problému, který není algoritmický, je následující instrukce z receptu: „házejte lehce, dokud se směs nerozdrtí.“ Tento problém není algoritmický, protože je nemožné, aby počítač věděl, jak dlouho se má mixovat; to může záviset na jedné externí dynamicky se měnící podmínce, jako je vlhkost, kterou nelze předem s jistotou předpovědět.
I když neexistuje přesná shoda ohledně algoritmů, Knuthova diskuse o algoritmech zůstává definitivní.
Prvním programovacím jazykem vysoké úrovně vyvinutým výslovně pro specifikaci algoritmů byl ALGOL (ALGOrithmic Language). Představeno na konci 50. let a zdokonaleno v 60. letech 20. století sloužilo jako standard pro publikování algoritmů. V souladu s konceptualizací algoritmů založenou na funkcích, ALGOL neposkytl žádné konstrukce pro vstup a výstup, vzhledem k těmto operacím mimo obavy algoritmů. (Není překvapením, že tato absence bránila přijetí ALGOL průmyslem pro komerční aplikace.)
V šedesátých letech došlo k rozmnožování vysokoškolských programů počítačové vědy (CS). Podle Asociace pro výpočetní techniku (ACM) se počet programů CS v USA zvýšil z 11 v roce 1964 na 92 v roce 1968. Tento nárůst byl doprovázen intenzivní činností směřující k nastolení legitimity této nové disciplíny v očích akademiků společenství. ACM hrála v této činnosti ústřední roli. V roce 1965 vysvětlila ospravedlnění a popis CS jako disciplíny, která sloužila jako základ pro doporučení z roku 1968 pro vysokoškolské programy CS.
V popisu CSM ACM byla identifikována efektivní transformace informací jako ústřední téma: “ Počítačová věda se zabývá informacemi v téměř stejném smyslu jako fyzika energií … Počítačový vědec se zajímá o objevení pragmatických prostředků, kterými lze informace transformovat. “ Tento popis staví algoritmy do středu výpočetní techniky, protože jsou „recepty“ pro provádění těchto účinných transformací vstupů na výstupy. Ve skutečnosti společnost ACM v následující větě své zprávy výslovně zaměřila na algoritmy:
„Tento zájem vede k zkoumání efektivních způsobů reprezentace informací, efektivních algoritmů pro transformaci informací, efektivních jazyků pro vyjádření algoritmy … a efektivní způsoby, jak toho dosáhnout za rozumnou cenu. “
Mít centrální algoritmický zájem, obdobný zájmu o energii ve fyzice, pomohl etablovat CS jako legitimní akademickou disciplínu na stejné úrovni jako fyzika. Algoritmy dodnes zůstávají v počítačové vědě ústřední.
Koexistence neformálního (založeného na algoritmech) a formálního (založeného na TM) přístupu k definování řešitelných problémů přetrvává dodnes a lze jej nalézt v všechny moderní učebnice algoritmů nebo vypočítatelnosti. To se ukázalo jako velmi výhodné pro počítačové vědce, protože nám umožnilo neformálně popsat algoritmický výpočet pomocí „pseudokódu“ s vědomím, že lze postavit ekvivalentní Turingův stroj.
– Problém je řešitelný, pokud ho lze specifikovaný algoritmem. – Problém je řešitelný, pokud pro něj existuje Turingův stroj.
Rozhodnutí teoretiků a pedagogů z 60. let umístit algoritmy do středu CS se jasně odrazilo v raných vysokoškolských učebnicích. Neexistovala však žádná explicitní standardní definice algoritmu a různé učebnice se rozhodly tento pojem definovat odlišně. Zatímco některé učebnice, jako je ta od Knutha, dávaly pozor, aby výslovně omezily algoritmy na ty, které počítají funkce, a jsou tedy ekvivalentní s Turingovými stroji, většina knih o teorii ponechala toto omezení implicitní, ale nevyslovené.
Časný příklad je učebnice Hopcrofta a Ullmana z roku 1969, jejichž pozdější vydání se používají dodnes: „Procedura je konečný sled pokynů, které lze provádět mechanicky, například počítačový program …Postup, který se vždy ukončí, se nazývá algoritmus. “
Tento popis algoritmu výslovně nevylučuje nefunkční výpočet, jako je příprava jídla. Jejich příklady různých problémů však objasňují, že uvažovali pouze o výpočtu založeném na funkcích. Ve skutečnosti pro své příklady použili ALGOL, který ani nenabízel žádné konstrukce pro vstup a výstup.
Od konce 60. let již programovací jazyky na vysoké úrovni používané v praxi a vyučované v programech CS již nebyly. vázán algoritmickými omezeními raného ALGOLU. Mohli byste psát programy, které interagovaly s jejich prostředím průběžně během výpočtu, jako jsou operační systémy, grafická uživatelská rozhraní nebo automatická vozidla a další roboti.
V reakci na to současné učebnice programování, jako je Rice a Rice (1969) výslovně rozšířil pojem algoritmů tak, aby zahrnoval nefunkční problémy. Tento přístup, odrážející centrálnost algoritmů, aniž by se omezoval na výpočet funkcí, se stal typickým pro učebnice jiných než teorie. Předmětem těchto učebnic je spíše metodika programování než teorie výpočtu a matematické principy, které jsou základem našich modelů výpočtu, byly kvůli praktičnosti odloženy stranou.
Na první pohled je definice algoritmu v Rice a Rice a dalších podobných učebnicích se nijak neliší od Hopcrofta a Ullmana: „Algoritmus je recept, soubor instrukcí nebo specifikace procesu, jak něco udělat. Že něco obvykle řeší nějaký problém. “ Jejich příklady vypočítatelných problémů však již nejsou založeny na funkcích a připouštějí jen ten druh výpočtu, který Knuth odmítl. Dva takové příklady, které lze údajně vyřešit algoritmem, jsou výroba bramborové vodky a plnění příkopu pískem; Knuth by je oba odmítl.
Tyto učebnice neuváděly pro své „algoritmy“ žádné nároky na ekvivalenci TM. Studenti však nebyli informováni o tom, že se tento pojem algoritmů liší od Knuthova, a že se tím rozšířil soubor problémů považovaných za vypočítatelné. Spojením širší a praktičtější konceptualizace algoritmů (a tedy i vypočítatelných problémů) s teoriemi, které tvrdí, že TM lze vypočítat velmi vypočítatelný problém, osnovy CS zaměřené na algoritmy zanechaly u studentů mylný dojem, že by tato širší sada problémů mohla vyřeší také TM.
Zatímco praktičtí počítačoví vědci již dávno následovali příklad Rice a Rice a rozšířili koncept algoritmů nad rámec výpočtu funkcí, teoretická informatika si zachovala matematický světonázor, který rámuje výpočet na základě funkcí a podle toho vymezuje naši představu o výpočetním problému. To platí alespoň na vysokoškolské úrovni. Výsledkem je dichotomie, kdy komunita počítačových věd myslí na algoritmy jako na synonymum obecného pojmu výpočtu („co dělají počítače“), ale zároveň na ekvivalent Turingových strojů.
Myslel jsem si Musel jsem napsat tuto dlouhou odpověď, abych lidi upozornil na tuto dichotomii. Jak jsem řekl na začátku, pojem algoritmu je neformální. Můžeme to považovat za ekvivalent výpočtu funkcí (nebo Turing Machines) nebo o tom, pro co můžete napsat program, včetně interaktivních programů v reálném čase, jako jsou operační systémy nebo automatické automobily. Ale tyto dvě definice nejsou rovnocenné, a to navzdory běžné záměně opaku.