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 - Algorithmus

voir la définition de Wikipedia

   Publicité ▼

locutions

-A*-Algorithmus • A3 (Algorithmus) • A8 (Algorithmus) • Aho-Corasick-Algorithmus • Algorithmus von Borůvka • Algorithmus von Cohen-Sutherland • Algorithmus von Cristian • Algorithmus von Edmonds und Karp • Algorithmus von Floyd und Warshall • Algorithmus von Gilmore • Algorithmus von Hierholzer • Algorithmus von Hopcroft und Tarjan • Algorithmus von Peterson • Algorithmus von Prim • Algorithmus von Sutherland-Hodgman • Algorithmus von Tarjan • Algorithmus von Tarjan zur Bestimmung eines minimalen Spannbaumes • Algorithmus von Tarjan zur Bestimmung starker Zusammenhangskomponenten • Anubis (Algorithmus) • BCJR-Algorithmus • BLAST-Algorithmus • Baeza-Yates-Gonnet-Algorithmus • Barnes-Hut-Algorithmus • Baum-Welch-Algorithmus • Bellman-Ford-Algorithmus • Berkeley-Algorithmus • Booth-Algorithmus • Boyer-Moore-Algorithmus • Bucket-Algorithmus • Bucket-Algorithmus (Begriffsklärung) • CART (Algorithmus) • CAST (Algorithmus) • Cache-Algorithmus • Camellia (Algorithmus) • Canny-Algorithmus • Cayley-Purser-Algorithmus • Chainmail (Algorithmus) • Cocke-Younger-Kasami-Algorithmus • Common-Scrambling-Algorithmus • D*-Algorithmus • Dekker-Algorithmus • Depth-Sort-Algorithmus • Determiniertheit (Algorithmus) • Determinismus (Algorithmus) • Dijkstra-Algorithmus • Dinic' Algorithmus • Dinic-Algorithmus • Dinics Algorithmus • Douglas-Peucker-Algorithmus • EM-Algorithmus • Echo-Algorithmus • Epidemischer Algorithmus • Evolutionärer Algorithmus • FASTA-Algorithmus • FOX (Algorithmus) • Felzenszwalb-Huttenlocher-Algorithmus • Flooding-Algorithmus • Floyd-Steinberg-Algorithmus • Gauß-Jordan-Algorithmus • Genetischer Algorithmus • Genom (genetischer Algorithmus) • Goertzel-Algorithmus • Gottes Algorithmus • Greedy-Algorithmus • Haloed-Line-Algorithmus • Hase-Igel-Algorithmus • Hilltop-Algorithmus • Hybrid-Monte-Carlo-Algorithmus • Index-Calculus-Algorithmus • Jenks-Caspall-Algorithmus • K-Means-Algorithmus • Karplus-Strong-Algorithmus • Knuth-Morris-Pratt-Algorithmus • LMS-Algorithmus • LZX-Algorithmus • Las-Vegas-Algorithmus • Leaky-Bucket-Algorithmus • Lempel-Ziv-Markow-Algorithmus • Lempel-Ziv-Stac-Algorithmus • Lempel-Ziv-Storer-Szymanski-Algorithmus • Lempel-Ziv-Welch-Algorithmus • Levenberg-Marquardt-Algorithmus • Linearer Algorithmus • Luhn-Algorithmus • Maekawa-Algorithmus • Magenta (Algorithmus) • Markow-Algorithmus • Memetischer Algorithmus • Minimax-Algorithmus • Mittelwert-Algorithmus • Monte-Carlo-Algorithmus • Mutation (genetischer Algorithmus) • NULL-Algorithmus • Nagle-Algorithmus • Neighbor-Joining-Algorithmus • Online-Algorithmus • Paralleler Algorithmus • Porter-Stemmer-Algorithmus • Primal-Dual-Active-Set-Algorithmus • Push-Relabel-Algorithmus • RANDIN-Algorithmus • RANSAC-Algorithmus • Rabbit (Algorithmus) • Rabin-Karp-Algorithmus • Randomisierter Algorithmus • Rekombination (genetischer Algorithmus) • Relief-Algorithmus • Rete-Algorithmus • Ricart-Agrawala-Algorithmus • Roberts-Algorithmus • SEAL (Algorithmus) • SEED (Algorithmus) • Sankoff-Algorithmus • Scanline-Algorithmus • Selektion (genetischer Algorithmus) • Smith-Waterman-Algorithmus • Steinscher Algorithmus • String-Matching-Algorithmus • Taildrop-Algorithmus • Token-Bucket-Algorithmus • Tomasulo-Algorithmus • Toom-Cook-Algorithmus • Viterbi-Algorithmus • Vogel-Strauß-Algorithmus • WLD-Algorithmus • Warnock-Algorithmus • Waterman-Smith-Beyer-Algorithmus • Weiler-Atherton-Algorithmus • Whirlpool (Algorithmus) • Wolff-Algorithmus • Yarrow (Algorithmus) • Zassenhaus-Algorithmus

dictionnaire analogique


   Publicité ▼

Wikipedia

Algorithmus

                   
  Al-Chwarizmi, der Namensgeber des Algorithmus, auf einer sowjetischen Briefmarke anlässlich seines 1200-jährigen Geburtsjubiläums.

Ein Algorithmus ist eine aus endlich vielen Schritten bestehende eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen.

Inhaltsverzeichnis

  Wortgeschichte

  Seite aus einer lateinischen Übersetzung (Cambridger Manuskript), beginnend mit „Dixit algorizmi“

Das Wort Algorithmus ist eine Abwandlung oder Verballhornung des Namens von Muhammed al-Chwarizmi (etwa 783–850), dessen arabisches Lehrbuch Über das Rechnen mit indischen Ziffern (um 825) in der mittelalterlichen lateinischen Übersetzung mit den Worten Dixit Algorismi (Algorismi hat gesagt) beginnt. Im Mittelalter wurde daraus lateinisch algorismus (mit Varianten wie alchorismus, algoarismus, altfranzösisch algorisme, argorisme, mittel-englisch augrim, augrym) als Bezeichnung für die Kunst des Rechnens mit den arabischen Ziffern und als Titel für Schriften über diese Kunst.

Die lateinischen Autoren pflegten zu erklären, dass das Wort algorismus aus dem Namen des Erfinders dieser Kunst, eines Philosophen namens Algus, und dem griechischen Wort rismus (arithmós) für Zahl zusammengesetzt sei. Dabei wurde Algus von einigen als Araber, von anderen als Grieche oder zumindest griechisch schreibender Autor, gelegentlich auch als „König von Kastilien“ (Johannes von Norfolk) betrachtet. In der volkssprachlichen Tradition erscheint dieser „Meister Algus“ dann zuweilen in einer Reihe mit großen antiken Denkern wie Platon, Aristoteles und Euklid, so im altfranzösischen Roman de la Rose, während das altitalienische Gedicht Il Fiore ihn sogar als Erbauer des Schiffes Argo ausgibt, mit dem Jason sich auf die Suche nach dem Goldenen Vlies begab.

Durch Gräzisierung der Schreibweise des vermeintlich griechischen Wortbestandteiles rismus hat sich dann in der lateinischen Wissenschaftssprache die Schreibung algorithmus ergeben; in dieser Form hat sich das Wort später als Fachterminus für geregelte Prozeduren zur Lösung definierter Probleme eingebürgert.

  Informatik und Mathematik

Algorithmen sind eines der zentralen Themen der Informatik und Mathematik. Sie sind Gegenstand einiger Spezialgebiete der Theoretischen Informatik, der Komplexitätstheorie und der Berechenbarkeitstheorie. In Form von Computerprogrammen und elektronischen Schaltkreisen steuern sie Computer und andere Maschinen.

  Algorithmus und Programme

Für Algorithmen gibt es unterschiedliche formale Repräsentationen. Diese reichen vom Algorithmus als abstraktem Gegenstück zum konkret auf eine Maschine zugeschnittenen Programm (das heißt, die Abstraktion erfolgt hier im Weglassen der Details der realen Maschine, das Programm ist eine konkrete Form des Algorithmus, angepasst an die Notwendigkeiten und Möglichkeiten der realen Maschine) bis zur Ansicht, Algorithmen seien gerade die Maschinenprogramme von Turingmaschinen (wobei hier die Abstraktion in der Verwendung der Turingmaschine an sich erfolgt, das heißt, einer idealen mathematischen Maschine).

Algorithmen können in Programmablaufplänen nach DIN 66001 oder ISO 5807 grafisch dargestellt werden.

  Erster Computeralgorithmus

Der erste für einen Computer gedachte Algorithmus (zur Berechnung von Bernoullizahlen) wurde 1843 von Ada Lovelace in ihren Notizen zu Charles Babbages Analytical Engine festgehalten. Sie gilt deshalb als die erste Programmiererin. Weil Charles Babbage seine Analytical Engine nicht vollenden konnte, wurde Ada Lovelaces Algorithmus nie darauf implementiert.

  Heutige Situation

  Prinzipbild des Rete-Algorithmus für Expertensystem, publiziert 1979, frei

Algorithmen für Computer sind heute so vielfältig wie die Anwendungen, die sie ermöglichen sollen. Vom elektronischen Steuergerät für den Einsatz in KFZ über die Rechtschreib- und Satzbau-Kontrolle in einer Textverarbeitung bis hin zur Analyse von Aktienmärkten finden sich tausende von mehr oder minder tauglich arbeitenden Algorithmen. Als Ideen und Grundsätze, die einem Computerprogramm zugrunde liegen, wird Algorithmen in der Regel urheberrechtlicher Schutz versagt.[1] Je nach nationaler Ausgestaltung der Immaterialgüterrechte sind Algorithmen der Informatik jedoch dem Patentschutz zugänglich, so dass urheberrechtlich freie individuelle Werke, als Ergebnis eigener geistiger Schöpfung, wirtschaftlich trotzdem nicht immer frei verwertet werden können. Dies betrifft oder betraf z. B. Algorithmen, die auf der Mathematik der Hough-Transformation (Jahrzehnte alt, aber mehrfach aktualisiertes Konzept mit Neu-Anmeldung) aufbauen, Programme, die das Bildformat GIF lesen und schreiben wollten oder auch Programme im Bereich der Audio- und Video-Verarbeitung, da die zugehörigen Algorithmen, wie sie in den zugehörigen Codecs umgesetzt sind, oftmals nicht frei verfügbar sind. Die entsprechenden Einsparpotentiale für alle Anwender weltweit (für den Rete-Algorithmus wurde einst 1 Million USD auf DEC XCON genannt) dürften heute problemlos die Grenze von einer Milliarde USD im Jahr um ein zigfaches überschreiten.

  Definition

  Turingmaschinen und Algorithmusbegriff

Die mangelnde mathematische Genauigkeit des Begriffs Algorithmus störte viele Mathematiker und Logiker des 19. und 20. Jahrhunderts, weswegen in der ersten Hälfte des 20. Jahrhunderts eine ganze Reihe von Ansätzen entwickelt wurde, die zu einer genauen Definition führen sollten. Formalisierungen des Berechenbarkeitsbegriffs sind die Turingmaschine (Alan Turing), Registermaschinen, der Lambda-Kalkül (Alonzo Church), rekursive Funktionen, Chomsky-Grammatiken und Markow-Algorithmen.

Es wurde – unter maßgeblicher Beteiligung von Alan Turing selbst – gezeigt, dass all diese Methoden gleich leistungsfähig (gleich mächtig) sind. Sie können durch eine Turingmaschine emuliert werden, und sie können umgekehrt eine Turingmaschine emulieren.

Mit Hilfe des Begriffs der Turingmaschine kann folgende formale Definition des Begriffs formuliert werden:

Eine Berechnungsvorschrift zur Lösung eines Problems heißt genau dann Algorithmus, wenn eine zu dieser Berechnungsvorschrift äquivalente Turingmaschine existiert, die für jede Eingabe, die eine Lösung besitzt, stoppt.

Aus dieser Definition sind folgende Eigenschaften eines Algorithmus ableitbar:

  1. Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit).
  2. Jeder Schritt des Verfahrens muss tatsächlich ausführbar sein (Ausführbarkeit).
  3. Das Verfahren darf zu jedem Zeitpunkt nur endlich viel Speicherplatz benötigen (Dynamische Finitheit, siehe Platzkomplexität).
  4. Das Verfahren darf nur endlich viele Schritte benötigen (Terminierung, siehe auch Zeitkomplexität).

Darüber hinaus wird der Begriff Algorithmus in praktischen Bereichen oft auf die folgenden Eigenschaften eingeschränkt:

  1. Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern (Determiniertheit).
  2. Die nächste anzuwendende Regel im Verfahren ist zu jedem Zeitpunkt eindeutig definiert (Determinismus).

  Church-Turing-These

Die Church-Turing-These lautet: „Jedes intuitiv berechenbare Problem kann durch eine Turingmaschine gelöst werden.“ Als formales Kriterium für einen Algorithmus zieht man die Implementierbarkeit in einem beliebigen, zu einer Turingmaschine äquivalenten Formalismus heran, insbesondere die Implementierbarkeit in einer Programmiersprache – die von Church verlangte Terminiertheit ist dadurch allerdings noch nicht gegeben.

Der Begriff der Berechenbarkeit ist dadurch dann so definiert, dass ein Problem genau dann berechenbar ist, wenn es einen (terminierenden) Algorithmus zu dem Problem gibt, das heißt, wenn eine entsprechend programmierte Turingmaschine das Problem in endlicher Zeit lösen könnte.

  Abstrakte Automaten

Turingmaschinen harmonieren gut mit den ebenfalls abstrakt-mathematischen berechenbaren Funktionen, reale Probleme sind jedoch ungleich komplexer, daher wurden andere Maschinen vorgeschlagen.

Diese Maschinen weichen etwa in der Mächtigkeit der Befehle ab; statt der einfachen Operationen der Turingmaschine können sie teilweise mächtige Operationen, wie etwa Fourier-Transformationen, in einem Rechenschritt ausführen.

Oder sie beschränken sich nicht auf eine Operation pro Rechenschritt, sondern ermöglichen parallele Operationen, wie etwa die Addition zweier Vektoren in einem Schritt.

Ein Modell einer realeren Maschine ist die Sequential Abstract State Machine (seq. ASM)[2] mit folgenden Eigenschaften:

Ein Algorithmus einer seq. ASM soll

  • durch einen endlichen Programmtext spezifiziert werden können
  • schrittweise ausgeführt werden können
  • für bestimmte Zustände terminieren, muss aber nicht immer terminieren (sinnvolle Gegenbeispiele für die Forderung, dass immer terminiert werden muss, wären etwa ein Programm, das fortgesetzt Primzahlen findet, oder ein Betriebssystem)
  • nur begrenzt viele Zustände pro Schritt ändern können (Begrenzung der Parallelität)
  • nur begrenzt viele Zustände pro Schritt inspizieren können (Begrenzung der Exploration).

  Eigenschaften

  Determiniertheit

Ein Algorithmus ist determiniert, wenn dieser bei jeder Ausführung mit gleichen Startbedingungen und Eingaben gleiche Ergebnisse liefert.

  Determinismus

Ein Algorithmus ist deterministisch, wenn zu jedem Zeitpunkt der Algorithmusausführung der nächste Handlungsschritt eindeutig definiert ist. Beispiele für deterministische Algorithmen sind Bubblesort und der euklidische Algorithmus. Dabei gilt, dass jeder deterministische Algorithmus determiniert, während aber nicht jeder determinierte Algorithmus deterministisch ist. So ist Quicksort mit zufälliger Wahl des Pivotelements ein Beispiel für einen determinierten, aber nicht deterministischen Algorithmus, da sein Ergebnis bei gleicher Eingabe und eindeutiger Sortierung immer dasselbe ist, der Weg dorthin jedoch zufällig erfolgt.

In der theoretischen Informatik gibt es neben dem Determinismus auch den Nichtdeterminismus, der aber mit keiner realen Maschine (auch nicht mit Quantencomputern) direkt umgesetzt werden kann.

  Finitheit

  Statische Finitheit

Die Beschreibung des Algorithmus besitzt eine endliche Länge, der Quelltext muss also aus einer begrenzten Anzahl von Zeilen bestehen.

  Dynamische Finitheit

Ein Algorithmus darf zu jedem Zeitpunkt seiner Ausführung nur begrenzt viel Speicherplatz benötigen.

  Terminiertheit

Terminiertheit heißt: Ein Algorithmus hält nach endlich vielen Schritten an (bricht kontrolliert ab). Dies gilt für jede mögliche Eingabe. Würde ein Algorithmus nicht terminieren (und somit zu keinem Ergebnis kommen), wäre die Folge eine so genannte Endlosschleife.

Für diese Eigenschaft gibt es jedoch Ausnahmen: Steuerungssysteme, Betriebssysteme und viele weitere Programme, die auf Interaktion mit dem Benutzer aufbauen. Solange der Benutzer keinen Befehl zum Beenden eingibt, laufen diese Programme beabsichtigt endlos weiter. Donald Knuth schlägt in diesem Zusammenhang vor, nicht terminierende Algorithmen als rechnergestützte Methoden (Computational Methods) zu bezeichnen.

Darüber hinaus ist die Terminierung eines Algorithmus (das Halteproblem) nicht entscheidbar. Das heißt, das Problem, festzustellen, ob ein Algorithmus mit einer beliebigen Eingabe terminiert, ist nicht durch einen Algorithmus lösbar.

  Effektivität

Der Effekt jeder Anweisung eines Algorithmus muss eindeutig festgelegt sein.

  Beispiele für Eigenschaften von Algorithmen

Einfache Grundoperation: „Öffne die Flasche Wein“ hierbei wird das Wissen um das Öffnen vorausgesetzt.

Sequentieller Algorithmus: „Bier auf Wein, lass das sein“ beiden Operationen ist eine Reihenfolge vorgegeben und diese sollte nicht verändert werden.

Nebenläufiger Algorithmus: „Schnaps und Bier“ Die Reihenfolge ist nicht vorgegeben und kann auch gleichzeitig erfolgen.

Parallele Ausführung: „Mit Sekt anstoßen“ Dies kann nur gleichzeitig (parallel) ausgeführt werden und nicht hintereinander (sequentiell).

Nichtdeterministischer/nichtdeterminierter Algorithmus: „Bier oder Wasser“ Das Ergebnis unterscheidet sich, je nach dem welches man wählt.

  Algorithmenanalyse

Die Erforschung und Analyse von Algorithmen ist eine Hauptaufgabe der Informatik, und wird meist theoretisch (ohne konkrete Umsetzung in eine Programmiersprache) durchgeführt. Sie ähnelt somit dem Vorgehen in anderen mathematischen Gebieten, in denen die Analyse eher auf die zugrunde liegenden Konzepte als auf konkrete Umsetzungen ausgerichtet ist. Algorithmen werden zur Analyse in eine stark formalisierte Form gebracht und mit den Mitteln der formalen Semantik untersucht.

Die Analyse unterteilt sich in verschiedene Teilgebiete. Beispielsweise wird das Verhalten von Algorithmen bezüglich Ressourcenbedarf wie Rechenzeit und Speicherbedarf in der Komplexitätstheorie behandelt; die Ergebnisse werden als asymptotische Laufzeiten angegeben. Der Ressourcenbedarf wird dabei in Abhängigkeit von der Länge der Eingabe ermittelt, das heißt, die angegebene Komplexität hängt davon ab, wie groß die Zahlen sind, deren größter gemeinsamer Teiler gesucht wird, oder wie viele Elemente sortiert werden müssen etc.

Das Verhalten bezüglich der Terminierung, ob also der Algorithmus überhaupt jemals erfolgreich beendet werden kann, behandelt die Berechenbarkeitstheorie.

  Typen und Beispiele

  Die Lösung für das Spiel Türme von Hanoi mit drei Spielsteinen - ein einfacher Algorithmus

Der älteste bekannte nicht-triviale Algorithmus ist der euklidische Algorithmus. Spezielle Algorithmus-Typen sind der randomisierte Algorithmus (mit Zufallskomponente), der Approximationsalgorithmus (als Annäherungsverfahren), der genetische Algorithmus (mit evolutionärer Komponente) und der Greedy-Algorithmus.

Eine weitere Übersicht gibt die Liste von Algorithmen und die Kategorie Algorithmus.

  Literatur

  Weblinks

  Fußnoten

  1. Deutschland: § 69a Abs. (2) UrhG
  2. Sequential Abstract State Machine (seq. ASM)
   
               

 

Toutes les traductions de Algorithmus


Contenu de sensagent

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

  • Definition
  • Synonym

   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.

 

2825 visiteurs en ligne

calculé en 0,062s

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 :