Mon compte

connexion

inscription

   Publicité ▼


 » 
allemand anglais arabe bulgare chinois coréen croate danois espagnol espéranto estonien finnois français grec hébreu hindi hongrois islandais indonésien italien japonais letton lituanien malgache néerlandais norvégien persan polonais portugais roumain russe serbe slovaque slovène suédois tchèque thai turc vietnamien
allemand anglais arabe bulgare chinois coréen croate danois espagnol espéranto estonien finnois français grec hébreu hindi hongrois islandais indonésien italien japonais letton lituanien malgache néerlandais norvégien persan polonais portugais roumain russe serbe slovaque slovène suédois tchèque thai turc vietnamien

définition - algoritmus

voir la définition de Wikipedia

   Publicité ▼

locutions

-Algoritmus Aho-Corasick • Algoritmus Cocke-Younger-Kasami • Algoritmus de Casteljau • Algoritmus k-nejbližších sousedů • Algoritmus pro výpočet dne v týdnu • Bellman-Fordův algoritmus • Bellmanův-Fordův algoritmus • Boothův algoritmus • Borůvkův algoritmus • Coppersmith-Winogradův algoritmus • Coppersmithův-Winogradův algoritmus • Coppersmith–Winogradův algoritmus • Deterministický algoritmus • Dijkstrův algoritmus • Dinicův algoritmus • Edmonds-Karpův algoritmus • Edmondsův-Karpův algoritmus • Euklidův algoritmus • Floyd-Warshallův algoritmus • Floydův-Warshallův algoritmus • Ford-Fulkersonův značkovací algoritmus • Fordův-Fulkersonův algoritmus • Genetický algoritmus • Goldbergův algoritmus • Hladový algoritmus • In-place algoritmus • Jarníkův algoritmus • Kruskalův algoritmus • Minimax (algoritmus) • Nedeterministický algoritmus • Pštrosí algoritmus • Rozděl a panuj (algoritmus) • Shunting-yard (algoritmus) • Simplexový algoritmus • Strassenův algoritmus • Variace (algoritmus) • Řadicí algoritmus

dictionnaire analogique

   Publicité ▼

Wikipedia

Algoritmus

                   

Algoritmus je přesný návod či postup, kterým lze vyřešit daný typ úlohy. Pojem algoritmu se nejčastěji objevuje při programování, kdy se jím myslí teoretický princip řešení problému (oproti přesnému zápisu v konkrétním programovacím jazyce). Obecně se ale algoritmus může objevit v jakémkoli jiném vědeckém odvětví. Jako jistý druh algoritmu se může chápat i např. kuchařský recept. V užším smyslu se slovem algoritmus rozumí takové postupy, které splňují některé silnější požadavky:

Obsah

  Vlastnosti algoritmů

Konečnost (finitnost) 
Každý algoritmus musí skončit v konečném počtu kroků. Tento počet kroků může být libovolně velký (podle rozsahu a hodnot vstupních údajů), ale pro každý jednotlivý vstup musí být konečný. Postupy, které tuto podmínku nesplňují, se mohou nazývat výpočetní metody. Speciálním příkladem nekonečné výpočetní metody je reaktivní proces, který průběžně reaguje s okolním prostředím. Někteří autoři však mezi algoritmy zahrnují i takovéto postupy.
Obecnost (hromadnost, masovost, univerzálnost) 
Algoritmus neřeší jeden konkrétní problém (např. „jak spočítat 3×7“), ale obecnou třídu obdobných problémů (např. „jak spočítat součin dvou celých čísel“), má širokou množinu možných vstupů.
Determinovanost 
Každý krok algoritmu musí být jednoznačně a přesně definován; 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, takže pro stejné vstupy dostaneme pokaždé stejné výsledky. Protože běžný jazyk obvykle neposkytuje naprostou přesnost a jednoznačnost vyjadřování, byly pro zápis algoritmů navrženy programovací jazyky, ve kterých má každý příkaz jasně definovaný význam. Vyjádření výpočetní metody v programovacím jazyce se nazývá program. Některé algoritmy ale determinované nejsou, pravděpodobnostní algoritmy v sobě mají zahrnutu náhodu.
Výstup (resultativnost) 
Algoritmus má alespoň jeden výstup, veličinu, která je v požadovaném vztahu k zadaným vstupům, a tím tvoří odpověď na problém, který algoritmus řeší (algoritmus vede od zpracování hodnot k výstupu)
Elementárnost 
Algoritmus se skládá z konečného počtu jednoduchých (elementárních) kroků.

V praxi jsou proto předmětem zájmu hlavně takové algoritmy, které jsou v nějakém smyslu kvalitní. Takové algoritmy splňují různá kritéria, měřená např. počtem kroků potřebných pro běh algoritmu, jednoduchost, efektivitu či eleganci. Problematikou efektivity algoritmů, tzn. metodami, jak z několika známých algoritmů řešících konkrétní problém vybrat ten nejlepší, se zabývají odvětví informatiky nazývané algoritmická analýza a teorie složitosti.

  Metody návrhu

Algoritmus se navrhuje několika možnými způsoby:

  • Shora dolů – postup řešení rozkládáme na jednodušší operace, až dospějeme k elementárním krokům.
  • Zdola nahoru – z elementárních kroků vytváříme prostředky, které nakonec umožní zvládnout požadovaný problém.
  • Kombinace obou – obvyklý postup shora dolů doplníme "částečným krokem" zdola nahoru tím, že se například použijí knihovny funkcí, vyšší programovací jazyk nebo systém pro vytváření programů (CASE).

Nejužívanější metody návrhů algoritmů jsou následující:

  Rozděl a panuj

Související informace naleznete v článku Rozděl a panuj.

Klasický případ aplikace postupu odshora dolů. Algoritmy typu rozděl a panuj dělí problém na menší podproblémy, na něž se rekurzivně aplikují (až po triviální podproblémy, které lze vyřešit přímo), po čemž se dílčí řešení vhodným způsobem sloučí.

Zpracovává se množina V složená z n údajů. Tato množinu se rozdělí na k disjunktních podmnožin, které se zpracují každá zvlášť. Získané dílčí výsledky se pak spojíme odvodí se z nich řešení pro celou množinu V.

Klasickým případem je binární vyhledávání, nebo quicksort.

  Hladový algoritmus

Související informace naleznete v článku Hladový algoritmus.

Velice přímočarý přístup k řešení určité třídy optimalizačních úloh.

Zpracovává se množina V složená z n údajů. Úkolem je najít podmnožinu W množiny V, která vyhovuje určitým podmínkám a přitom optimalizuje předepsanou účelovou funkci. Jakákoliv množina W, vyhovující daným podmínkám, se nazývá přípustné řešení. Přípustné řešení, pro které nabývá účelová funkce optimální hodnoty, se nazývá optimální řešení.

Hladový algoritmus se skládá z kroků, které budou procházet jednotlivé prvky z V, a v každém kroku rozhodne, zda se daný prvek hodí do optimálního řešení. Prvky V bude vybírat v pořadí určeném jistou výběrovou procedurou. Výběrová procedura bude založená na nějaké optimalizační míře – funkci, která může být odvozena od účelové funkce. V každém kroku ale musíme dostat přípustné řešení. Jakmile je učiněno takové rozhodnutí, už není dále revidováno. Příkladem je třeba hledání nejkratší cesty grafu.

  Dynamické programování

Související informace naleznete v článku Dynamické programování.

Dynamické programování funguje obdobně jako hladový algoritmus, ale negeneruje se pouze jedna posloupnost. Zkoumají se všechny posloupnosti, které by mohly být optimální a vylučují se ty, které optimální nebudou. Používají se dílčí výsledky, které byly získané již dříve během výpočtu.

Nejjednodušší a nejméně účinnou je metoda hrubé síly – vygenerují se všechny možné posloupnosti a pak se vybere ta nejlepší. Za pomoci dynamického programování se automaticky negenerují ty možnosti, které určitě nejsou optimální.
Opírá se o princip optimality: Optimální posloupnost rozhodnutí má tu vlastnost, že ať je počáteční stav a rozhodnutí jakékoliv, musí být všechna následující rozhodnutí optimální vzhledem k výsledkům rozhodnutí prvního.

Typickým příkladem využití dynamického programování jsou grafové úlohy a a jejich příslušné grafové algoritmy.

  Hledání s návratem (backtracking)

Související informace naleznete v článku Backtracking.

Hledání s návratem založené na prohledávání stavového stromu problému. Též se nazývá metoda pokusů a oprav, metoda zpětného sledování, metoda prohledávání do hloubky.

Metodu je možné použít v případě, že řešením je vektor (x1,...,xn) jehož jednotlivé složky vybíráme z množiny Si, xiSi. Zpravidla je třeba najít n-tici, která optimalizuje nějakou účelovou funkci P(x1,...,xn). Můžou se ale také hledat všechny n-tice, které tuto podmínku splňují. Metoda vytváří n-tice jednu složku po druhé. Přitom používá účelovou funkci (nebo nějakou vhodnou pomocnou funkci) a pro každou nově vytvořenou složku testuje, zda by taková n-tice vůbec mohla být optimální nebo splňovat dané podmínky. Jestliže pro nějaké xi žádaný vektor (x1,...,xi) nemůže být optimální, není třeba už žádný takový vektor testovat a vezmeme další možnou hodnotu i-té složky. Pokud jsou vyčerpány všechny hodnoty i-té složky, vrátí se metoda zpět o jeden krok a zkouší další možnou hodnotu xi-1.

Příkladem je třeba problém osmi dam, nebo chůze koně celou šachovnicí.

  Algoritmická složitost

Je třeba poznamenat, že abstraktní kritérium konečnosti je pro praktické použití ještě příliš slabé. V praxi je třeba zajistit, aby algoritmus skončil „v rozumném“ čase. Za rozumný čas lze v praxi považovat takový čas, který nám umožní smysluplně využít výsledek.

Např. existuje jednoduchý algoritmus, který dokáže určit, zda v dané šachové pozici může hráč na tahu vynutit vítězství a zároveň dokáže určit nejlepší možný tah. Tento algoritmus se však nedá použít, protože by na svou činnost potřeboval ohromné množství času, jakkoli je toto množství konečné. Mimoto by takový algoritmus spotřeboval ohromné množství paměti, což je další praktický zřetel, který se uplatňuje při volbě algoritmu. I když průměrná počítačová paměť stále narůstá, pro některé algoritmy jí nebude nikdy dost.

Pro vyčíslení výpočetní složitosti algoritmů v závislosti na velikosti vstupních dat se používá asymptotický zápis závislosti výpočetního času na rozsahu úlohy (typicky na počtu vstupních údajů). Například O(log N) znamená, že počet kroků algoritmu závisí logaritmicky na velikosti vstupních dat. Pokud u takového algoritmu zdvojnásobíme rozsah vstupních údajů, doba výpočtu se zvýší o jednu jednotku času, pokud bude vstupních dat čtyřikrát více, doba výpočtu se prodlouží o dvě jednotky času, a tak dále. To je třeba případ nalezení jednoho prvku o určité hodnotě v seznamu prvků seřazeném podle hodnoty (např. nalezení jména v telefonním seznamu).

  Druhy algoritmů

Algoritmy můžeme klasifikovat různými způsoby. Mezi důležité druhy algoritmů patří:

  • Rekurzivní algoritmy, které využívají (volají) samy sebe.
  • Pravděpodobnostní algoritmy (někdy též probabilistické) provádějí některá rozhodnutí náhodně či pseudonáhodně.
  • V případě, že máme k dispozici více počítačů, můžeme úlohu mezi ně rozdělit, což nám umožní ji vyřešit rychleji; tomuto cíli se věnují paralelní algoritmy.
  • Genetické algoritmy pracují na základě napodobování biologických evolučních procesů, postupným „pěstováním“ nejlepších řešení pomocí mutací a křížení. V genetickém programování se tento postup aplikuje přímo na algoritmy (resp. programy), které jsou zde chápány jako možná řešení daného problému.
  • Heuristický algoritmus si za cíl neklade nalézt přesné řešení, ale pouze nějaké vhodné přiblížení; používá se v situacích, kdy dostupné zdroje (např. čas) nepostačují na využití exaktních algoritmů (nebo pokud nejsou žádné vhodné exaktní algoritmy vůbec známy).

Přitom jeden algoritmus může patřit zároveň do více skupin; například může být zároveň rekurzivní a genetický.

  Některé známé algoritmy

  Etymologie

Slovo algoritmus pochází ze jména významného perského matematika žijícího v první polovině 9. století (cca 780840), kterým byl Abū ʻAbd Allāh Muhammad ibn Mūsā al-Chwārizmī (أبو عبد الله محمد بن موسى الخوارزمي) (doslova „Otec Abdulláha, Mohameda, syn Mojžíšův, pocházející z města Chwārizm (Chórézm)“; tento kraj se nachází jižně od Aralského moře). Tento učenec ve svém díle prakticky vytvořil systém arabských číslic a základy algebry (konkrétně metody řešení lineárních a kvadratických rovnic), jejíž název pochází přímo z titulu tohoto díla (Kitūb al-jabr waāl-muqūbala). Jeho jméno bylo do latiny převedeno jako algorismus, a původně znamenalo „provádění aritmetiky pomocí arabských číslic“; abacisté počítali pomocí abaku, algoristé pomocí algorismů.

Postupem času se kvůli neznalosti původu slova jeho podoba měnila, záměnou arabského kořene s kořenem řeckého slova αριθμός (arithmos) se z algorismu stal algorithmus. (Později bylo v některých jazycích včetně češtiny th změněno na t, v katalánštině se vrátilo s.) Toto slovo se používalo jako označení různých matematických postupů, např. v 18. století označoval latinský termín algorithmus infitesimalis „metodu výpočtů s využitím nekonečně malých veličin, vynalezenou Leibnizem“. Slovo algoritmus v dnešním významu se používá až zhruba od 20. století.

  Reference

  1. heslo Algorithmus. Ottův slovník naučný I, p. 857
  2. Donald E. Knuth: The Art of Computer Programming, Vol 1–3, Addison Wesley 1998. ISBN 0-201-48541-9. Klasické dílo oboru, definitivní příručka.
  3. Gaston H. Gonnet, Ricardo Baeza-Yates: Zdrojové texty programů v Handbook of Algorithms and Data Structures.
  4. Dictionary of Algorithms and Data Structures. „Slovník algoritmů, technik, datových struktur, typických problémů a příslušných definic.“

   
               

 

Toutes les traductions de algoritmus


Contenu de sensagent

  • définitions
  • synonymes
  • antonymes
  • encyclopédie

  • definice
  • synonymum

   Publicité ▼

dictionnaire et traducteur pour sites web

Alexandria

Une fenêtre (pop-into) d'information (contenu principal de Sensagent) est invoquée un double-clic sur n'importe quel mot de votre page web. LA fenêtre fournit des explications et des traductions contextuelles, c'est-à-dire sans obliger votre visiteur à quitter votre page web !

Essayer ici, télécharger le code;

SensagentBox

Avec la boîte de recherches Sensagent, les visiteurs de votre site peuvent également accéder à une information de référence pertinente parmi plus de 5 millions de pages web indexées sur Sensagent.com. Vous pouvez Choisir la taille qui convient le mieux à votre site et adapter la charte graphique.

Solution commerce électronique

Augmenter le contenu de votre site

Ajouter de nouveaux contenus Add à votre site depuis Sensagent par XML.

Parcourir les produits et les annonces

Obtenir des informations en XML pour filtrer le meilleur contenu.

Indexer des images et définir des méta-données

Fixer la signification de chaque méta-donnée (multilingue).


Renseignements suite à un email de description de votre projet.

Jeux de lettres

Les jeux de lettre français sont :
○   Anagrammes
○   jokers, mots-croisés
○   Lettris
○   Boggle.

Lettris

Lettris est un jeu de lettres gravitationnelles proche de Tetris. Chaque lettre qui apparaît descend ; il faut placer les lettres de telle manière que des mots se forment (gauche, droit, haut et bas) et que de la place soit libérée.

boggle

Il s'agit en 3 minutes de trouver le plus grand nombre de mots possibles de trois lettres et plus dans une grille de 16 lettres. Il est aussi possible de jouer avec la grille de 25 cases. Les lettres doivent être adjacentes et les mots les plus longs sont les meilleurs. Participer au concours et enregistrer votre nom dans la liste de meilleurs joueurs ! Jouer

Dictionnaire de la langue française
Principales Références

La plupart des définitions du français sont proposées par SenseGates et comportent un approfondissement avec Littré et plusieurs auteurs techniques spécialisés.
Le dictionnaire des synonymes est surtout dérivé du dictionnaire intégral (TID).
L'encyclopédie française bénéficie de la licence Wikipedia (GNU).

Copyright

Les jeux de lettres anagramme, mot-croisé, joker, Lettris et Boggle sont proposés par Memodata.
Le service web Alexandria est motorisé par Memodata pour faciliter les recherches sur Ebay.
La SensagentBox est offerte par sensAgent.

Traduction

Changer la langue cible pour obtenir des traductions.
Astuce: parcourir les champs sémantiques du dictionnaire analogique en plusieurs langues pour mieux apprendre avec sensagent.

 

3801 visiteurs en ligne

calculé en 0,078s

Je voudrais signaler :
section :
une faute d'orthographe ou de grammaire
un contenu abusif (raciste, pornographique, diffamatoire)
une violation de copyright
une erreur
un manque
autre
merci de préciser :