Algorithmus

Glossar
· Hauptseite · Zufälliger Artikel · Portal liste
Diskussion
· Diskussion : Algorithmus
Webkatalog
· Übersicht · Eigene Artikel · Seite vorschlagen
Aktuelles
· Seite der Woche · Newsletter · Today in History · Kreuzworträtsel
Weitere Inhalte
· Einkaufsmeile · Begriffslexikon · Multimedia
Suche
· Geschi.de · nach Jahren · Weltchronik.de · Geschichtsreferate
Interna
· Seitenneuigkeiten · Hilfe zur Seite · Impressum

Jahres-Sprung
Jahreszahl eingeben: >Chronik2000-Homepage<

Algorithmus

Stichpunkte

Allgemein
	Unter einem Algorithmus versteht man allgemein eine mehr oder weniger genau definierte Handlungsvorschrift zur LÃ¶sung eines Problems oder einer bestimmten Art von Problemen
	Im tÃ¤glichen Leben lassen sich leicht Beispiele fÃ¼r Algorithmen finden: Zum Beispiel ist ein Kochrezept ein Algorithmus â€“ zumindest dann
	ebenfalls Algorithmen gibt
	wie Braten
	RÃ¼hren
	etc.
	wenn alle Angaben genau genug sind und es fÃ¼r alle Teilaufgaben
	Auch Reparatur- und Bedienungsanleitungen oder Hilfen zum AusfÃ¼llen von Formularen sind in der Regel Algorithmen
	Ein weiteres
	etwas prÃ¤ziseres Beispiel sind Waschmaschinenprogramme
	wie der Algorithmentheorie
	Vor allem aber sind Algorithmen eine der zentralen Themen der Informatik und 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
	dass es fÃ¼r diesen intuitiv klar erscheinenden Begriff keine einheitliche prÃ¤zise Definition gibt
	Schaut man genauer hin
	stellt man fest
	Verschiedene Autoren pflegen verschiedene Definitionen
	Seine Definition ist immer noch Gegenstand der Forschung
	angepasst an die Notwendigkeiten und MÃ¶glichkeiten der realen Maschine)
	d. h. einer idealen mathematischen Maschine). Inhaltsverzeichnis showTocToggle("Anzeigen"
	"Verbergen") 1 Geschichte 1.1 Erster Computeralgorithmus 2 Formale Definition 2.1 Turingmaschinen und Algorithmusbegriff 2.1.1 Church-Turing-These 2.2 Abstract State Machines 3 Ein Beispiel: der Euklidische Algorithmus 4 Eigenschaften 4.1 Determiniertheit 4.2 Determinismus 4.3 Finitheit 4.3.1 Statische Finitheit 4.3.2 Dynamische Finitheit 4.4 Terminiertheit 5 Algorithmenanalyse 6 Beispiele 6.1 Algorithmen in der Wikipedia 6.2 Algorithmen im Alltag 7 Siehe auch 8 Literatur 9 Weblinks [Bearbeiten]
	Die Sicht reicht vom Algorithmus als abstraktes GegenstÃ¼ck zum konkret auf eine Maschine zugeschnittenen Programm (d. h. die Abstraktion erfolgt hier im Weglassen der Details der realen Maschine
	das Programm ist eine konkrete Form des Algorithmus
	dass Algorithmen gerade die Maschinenprogramme von Turingmaschinen sind (wobei hier die Abstraktion in der Verwendung der Turingmaschine an sich erfolgt
	bis hin zur Sicht
Geschichte
	Das Wort Algorithmus ist eine Abwandlung oder Verballhornung des Namens Muhammad ibn Musa al-Chwarizmi (* ca
	783
	â€ ca
	des Autors des Buchs Hisab al-dschabr wa-l-muqabala (825
	durch das die Algebra im Westen verbreitet wurde
	Regeln zur Wiederherstellung und Reduktion)
	850)
	Die lateinische Fassung beginnt mit â€žDixit Algorithmi...â€œ
	womit der Autor gemeint war
	Das Wort Algebra stammt ebenfalls (al-Jabr â€“ â€žEinrenkungâ€œ) aus dem Titel des Buches
	UrsprÃ¼nglich stand das Wort Algorism nur fÃ¼r die Regeln zur Arithmetik mit arabischen Ziffern
	Heute steht es fÃ¼r alle geregelten Prozeduren
	mit denen Probleme aller Art gelÃ¶st werden kÃ¶nnen. [Bearbeiten]
Erster Computeralgorithmus
	Der erste fÃ¼r einen Computer gedachte Algorithmus wurde 1842 von Ada Lovelace
	festgehalten
	in ihren Notizen zu Charles Babbages Analytical Engine
	Sie gilt deshalb als die erste Programmiererin
	Weil Charles Babbage seine Analytical Engine nicht vollenden konnte
	wurde Ada Lovelaces Algorithmus nie darauf implementiert. [Bearbeiten]
Formale Definition
	Die mangelnde mathematische Genauigkeit des Begriffs Algorithmus stÃ¶rte viele Mathematiker und Logiker des 19. und 20
	Jahrhunderts
	Insbesondere steht die natÃ¼rliche Sprache mit ihren UnschÃ¤rfen und WidersprÃ¼chlichkeiten der Forderung nach Eindeutigkeit und Widerspruchsfreiheit im Wege. [Bearbeiten]
Turingmaschinen und Algorithmusbegriff
	In der ersten HÃ¤lfte des 20
	Jahrhunderts wurden eine ganze Reihe von AnsÃ¤tzen entwickelt
	um zu einer genauen Definition zu kommen
	Formalisierungen des Berechenbarkeitsbegriffs sind die Turing-Maschine (Alan Turing)
	der Lambda-KalkÃ¼l (Alonzo Church)
	und Markow-Algorithmen
	rekursive Funktionen
	Chomsky-Grammatiken
	Es wurde â€“ unter maÃŸgeblicher Beteiligung von Alan Turing selbst â€“ gezeigt
	dass all diese Methoden ebenso leistungsfÃ¤hig (gleich mÃ¤chtig) sind
	und sie kÃ¶nnen umgekehrt eine Turing-Maschine emulieren. Mit Hilfe des Begriffs der Turing-Maschine kann folgende formale Definition des Begriffs formuliert werden: Eine Berechnungsvorschrift zur LÃ¶sung eines Problems heiÃŸt Algorithmus genau dann
	Sie kÃ¶nnen durch eine Turing-Maschine emuliert werden
	wenn eine zu dieser Berechnungsvorschrift Ã¤quivalente Turingmaschine existiert
	die fÃ¼r jede Eingabe stoppt
	Aus dieser Definition sind folgende Eigenschaften eines Algorithmus ableitbar: Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit). Jeder Schritt des Verfahrens muss auch tatsÃ¤chlich ausfÃ¼hrbar sein (AusfÃ¼hrbarkeit). Das Verfahren darf zu jedem Zeitpunkt nur endlich viel Speicherplatz benÃ¶tigen (Dynamische Finitheit
	siehe PlatzkomplexitÃ¤t). 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: Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern (Determiniertheit). Die nÃ¤chste anzuwendende Regel im Verfahren ist zu jedem Zeitpunkt eindeutig definiert (Determinismus). [Bearbeiten]
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 Turing-Maschine Ã¤quivalenten Formalismus heran
	insbesondere die Implementierbarkeit in einer Programmiersprache â€“ die von Church verlangte Terminiertheit ist dadurch allerdings noch nicht gegeben
	d. h. wenn eine entsprechend programmierte Turing-Maschine das Problem in endlicher Zeit lÃ¶sen kÃ¶nnte. [Bearbeiten]
	dass ein Problem berechenbar ist genau dann
	Der Begriff der Berechenbarkeit ist dadurch dann so definiert
	wenn es einen (terminierenden) Algorithmus zu dem Problem gibt
Abstract State Machines
	daher wurden andere Maschinen vorgeschlagen
	reale Probleme sind jedoch ungleich komplexer
	Turingmaschinen harmonieren sehr gut mit den ebenfalls abstrakt-mathematischen berechenbaren Funktionen
	kÃ¶nnen sie z.T. sehr mÃ¤chtige Operationen
	wie z
	Diese Maschinen weichen z.B. in der MÃ¤chtigkeit der Befehle ab
	anstatt den einfachen Operationen der Turingmaschine
	BF
	in einem Rechenschritt ausfÃ¼hrenO
	ouriertransformation
	der sie beschrÃ¤nken sich nicht auf eine Operation pro Rechenschritt
	sondern ermÃ¶glichen sehr parallele Operationen
	wie z.B. die Addition zweier Vektoren in einem Schritt. Ein Modell einer realeren Maschine ist die Sequential Abstract State Machine (seqA
	SM) (http://www.eecs.umich.edu/gasm/papers/seqthesis.html) mit folgenden Eigenschaften: Ein Algorithmus einer seqA
	dass immer terminiert werden muss
	muss aber nicht immer terminieren (sinnvolle Gegenbeispiele fÃ¼r die Forderung
	SM soll durch einen endlichen Programmtext spezifiziert werden kÃ¶nnen schrittweise ausgefÃ¼hrt werden kÃ¶nnen fÃ¼r bestimmte ZustÃ¤nde terminieren
	der fortgesetzt Primzahlen findet
	oder ein Betriebssystem) nur begrenzt viele ZustÃ¤nde pro Schritt Ã¤ndern kÃ¶nnen (Begrenzung der ParalellitÃ¤t) nur begrenzt viele ZustÃ¤nde pro Schritt inspizieren kÃ¶nnen (Begrenzung der Exploration) [Bearbeiten]
	seien der Sieb des Erastothenes
Ein Beispiel: der Euklidische Algorithmus
	der bereits um 300 v
	Der Euklidische Algorithmus
	dann fahre fort mit Schritt 1
	falls dies nicht bereits so ist) Setze A = A â€“ B Wenn A und B ungleich sind
	dient zur Ermittlung des grÃ¶ÃŸten gemeinsamen Teilers (ggT) zweier natÃ¼rlicher Zahlen A und B: Sei A die GrÃ¶ÃŸere der beiden Zahlen A und B (entsprechend vertauschen
	dann beende den Algorithmus: Diese Zahl ist der grÃ¶ÃŸte gemeinsame Teiler. Beispiel: Es soll der grÃ¶ÃŸte gemeinsame Teiler der Zahlen 14 und 8 berechnet werden
	Chr. beschrieben wurde
	wenn sie gleich sind
	Hierzu wird der euklidische Algorithmus verwendet: A B A-B 1. 14 8 6 2. 8 6 2 3. 6 2 4 4. 4 2 2 5. 2 2 gleich Das Ergebnis ist also 2. [Bearbeiten]
Eigenschaften
	so dass in anderen Bereichen oft vorausgesetzt wird
	Nichtdeterministische Algorithmen finden vor allem in der Theoretischen Informatik Anwendung
	dass es sich um einen deterministischen Algorithmus handelt
	in die absichtlich ein Zufallsfaktor eingebaut wurde
	randomisierte oder probabilistische Algorithmen
	Eine Ausnahme bilden so genannte stochastische
	Solche Algorithmen sind demnach nicht deterministisch und auch nicht determiniert
	orientieren sich aber an Erfahrungswerten
	Stochastische Algorithmen dagegen sind im Allgemeinen deterministisch
	Die verschiedenen formalen Eigenschaften in KÃ¼rze: [Bearbeiten]
Determiniertheit
	Kurz: Wenn gleiche Startwerte vorhanden sind
	muss das gleiche Ergebnis berechnet werden
	Algorithmen sind determiniert
	wenn sie bei gleichen Parametern und Startwert stets das gleiche Resultat liefern
	Das trifft zum Beispiel nicht fÃ¼r randomisierte Algorithmen zu
	bei denen das Ergebnis zu einem gewissen Grad auf Zufall beruht
	Es gilt Ã¼brigens: Jeder deterministische Algorithmus ist auch determiniert
	Nicht jeder determinierte Algorithmus ist jedoch deterministisch. [Bearbeiten]
Determinismus
	bei denen zu jedem Zeitpunkt der AusfÃ¼hrung maximal eine MÃ¶glichkeit der Programmfortsetzung besteht
	Kurz: Es darf immer nur eine MÃ¶glichkeit vorhanden sein Deterministisch heiÃŸen alle Algorithmen
	randomisierten oder probabilistischen Algorithmen
	so spricht man von stochastischen
	Gibt es mehrere MÃ¶glichkeiten der Programmfortsetzung und lassen sich diesen Wahrscheinlichkeiten zuweisen
	der aber in der Praxis kaum Verwendung findet
	In der theoretischen Informatik gibt es neben dem Determinismus auch den Nichtdeterminismus
	welche auch solche Algorithmen erfolgreich ausfÃ¼hren
	ZusÃ¤tzliche Bedeutung bekommen solche nichtdeterministische Algorithmen allerdings durch den Einsatz von Quantencomputern
	Es gilt Ã¼brigens: Jeder deterministische Algorithmus ist auch determiniert
	Nicht jeder determinierte Algorithmus ist jedoch deterministisch. [Bearbeiten]
Finitheit
	[Bearbeiten]
Statische Finitheit
	Kurz: Die Beschreibung ist endlich
	Die Beschreibung eines Algorithmus darf nicht unendlich groÃŸ sein
	Als statische Finitheit wird die Endlichkeit des Quelltextes bezeichnet
	Der Quelltext darf nur eine begrenzte Anzahl
	wenn auch bei Bedarf sehr viele Regeln enthalten. [Bearbeiten]
Dynamische Finitheit
	Kurz: FÃ¼lle an Datenstrukturen und Zwischenspeicherungen sind zu jeder Zeit endlich
	Zu jedem Zeitpunkt der AusfÃ¼hrung darf der von einem Algorithmus benÃ¶tigte Speicherbedarf nur endlich groÃŸ sein
	Andernfalls wÃ¤re der Algorithmus nicht ausfÃ¼hrbar
	Dies wird als dynamische Finitheit bezeichnet. [Bearbeiten]
Terminiertheit
	Kurz: Bricht nach endlicher Zeit kontrolliert ab
	wenn sie fÃ¼r jede mÃ¶gliche Eingabe nach einer endlichen Zahl von Schritten zu einem Ergebnis kommen
	Algorithmen sind terminierend
	Die tatsÃ¤chliche Zahl der Schritte kann dabei beliebig groÃŸ sein. Steuerungssysteme und Betriebssysteme und auch viele Programme
	erfÃ¼llen diese Eigenschaft nicht: Wenn der Benutzer keinen Befehl zum Beenden gibt
	lÃ¤uft das Programm endlos weiter
	die auf Interaktion mit dem Benutzer aufbauen
	nicht terminierende Algorithmen als rechnergestÃ¼tzte Methoden ("Computational Methods") zu bezeichnen
	Donald Knuth schlÃ¤gt in diesem Zusammenhang vor
	fÃ¼r einen Algorithmus zu bestimmen
	Es ist Ã¼brigens im allgemeinen nicht mÃ¶glich
	ob er terminiert oder nicht - siehe Halteproblem. [Bearbeiten]
Algorithmenanalyse
	Die Erforschung und Analyse von Algorithmen ist 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
	die Ergebnisse werden als asymptotische Laufzeiten angegeben
	Beispielsweise wird das Verhalten von Algorithmen bezÃ¼glich Ressourcenbedarf wie Rechenzeit und Speicherbedarf in der KomplexitÃ¤tstheorie behandelt
	oder wie viele Elemente sortiert werden mÃ¼ssen etc
	d.h. die angegebene KomplexitÃ¤t hÃ¤ngt davon ab
	deren ggT gesucht wird
	Der Ressourcenbedarf wird dabei in AbhÃ¤ngigkeit von der LÃ¤nge der Eingabe ermittelt
	wie groÃŸ die Zahlen sind
	behandelt die Berechenbarkeitstheorie. [Bearbeiten]
	d.h. ob der Algorithmus Ã¼berhaupt jemals erfolgreich beendet werden kann
	Das Verhalten bezÃ¼glich der Terminierung
Beispiele
	[Bearbeiten]
Algorithmen in der Wikipedia
	etwa den euklidischen Algorithmus und Quicksort
	In einzelnen Wikipedia-Artikeln gibt es zahlreiche Algorithmen-Beschreibungen
	Eine Ãœbersicht gibt die Liste von Algorithmen und die Kategorie Algorithmus. [Bearbeiten]
Algorithmen im Alltag
	Funktionsplan der Registrierkasse Eintasten von 17
	Instrumentalist Tonfolge Bedienung eines Handys Anrufer Bedienungsanleitung drÃ¼cke die # Taste Bau eines Radios Radiobastler Schaltplan und Montageanleitung verbinde die Basis von Transistor T1 mit dem Kollektor von T5 Kassieren im Supermarkt Kassiererin an Registrierkasse Bedienungsanleitung fÃ¼r Registrierkasse
	82 + [Bearbeiten]
	Auch im Alltag begegnen uns Algorithmen in Form von Handlungsanweisungen oder Rezepten: Prozess AusfÃ¼hrender Algorithmus Typische Anweisung Kuchenbacken BÃ¤cker Rezept nimm 1 Pfund Mehl / rolle Teig aus Spielen einer Melodie SÃ¤nger
Siehe auch
	z.B. zur Zerlegung von BrÃ¼chen in Summen von StammbrÃ¼chen Heuristik KomplexitÃ¤tsklassen MMIX (virtuelle Maschine von Donald E
	Liste von Algorithmen Ameisenalgorithmus Approximationsalgorithmus Datenstruktur Determinierter Algorithmus Deterministischer Algorithmus Entscheidungsproblem EvolutionÃ¤rer Algorithmus Genetischer Algorithmus Greedy Algorithmus "gieriger" Algorithmus
	Knuth zur Darstellung von Algorithmen) Online-Algorithmus Optimierungsproblem Paralleler Algorithmus Probabilistischer Algorithmus Prozedur (Programmierung) Randomisierter Algorithmus Sortierverfahren Stochastischer Algorithmus Suchverfahren [Bearbeiten]
Literatur
	John E
	Jeffrey D
	Hopcroft
	Rajeev Motwani
	Ullman
	EinfÃ¼hrung in die Automatentheorie
	Formale Sprachen und KomplexitÃ¤tstheorie
	Pearson Studium
	2002
	ISBN 3-8273-7020-5. Donald E
	Knuth: The Art of Computer Programming
	ISBN 0201485419 Thomas H
	Addison Wesley 1998. (Das ist der Standard in dem Bereich; Ãœbersetzung existiert nicht â€“ Juli 2000)
	Vol 1â€“3
	Ronald L
	Charles Leiserson
	Cormen
	Clifford Stein: Introduction to Algorithms
	MIT Press
	Rivest
	2nd edition 2001
	ISBN 0262531968 Deutsche Ãœbersetzung: Thomas H
	Ronald L
	Charles Leiserson
	Cormen
	ISBN 3-486-27515-1 [Bearbeiten]
	Clifford Stein: Algorithmen - Eine EinfÃ¼hrung
	2004
	Rivest
	Oldenbourg Wissenschaftsverlag
Weblinks
	Algorithmen in der Informatik (http://www.grundstudium.info/algorithmen/) Was ist ein Algorithmus? (http://www.uni-flensburg.de/mathe/zero/veranst/algorithmen/algo_abschn11/algo_abschn11.html) Dictionary of Algorithms and Data Structures (http://www.nist.gov/dads/) des NIST (englisch) Definition (http://www.bullhost.de/a/algorithmus.html) ca:Algorisme cs:Algoritmus da:Algoritme el:Î‘Î»Î³ÏŒÏ?Î¹Î¸Î¼Î¿Ï‚ en:Algorithm eo:Algoritmo es:Algoritmo et:Algoritm fi:Algoritmi fr:Algorithmique gl:Algoritmo he:×?×œ×’×•×¨×™×ª×? hu:Algoritmus it:Algoritmo ja:ã‚¢ãƒ«ã‚´ãƒªã‚ºãƒ ko:ì•Œê³ ë¦¬ì¦˜ lt:Algoritmas nl:Algoritme pl:Algorytm pt:Algoritmo ru:Ð?Ð»Ð³Ð¾Ñ€Ð¸Ñ‚Ð¼ sl:Algoritem su:Algoritma sv:Algoritm uk:Ð?Ð»Ð³Ð¾Ñ€Ð¸Ñ‚Ð¼ th:à¸à¸±à¸¥à¸?à¸à¸£à¸´à¸—à¸¶à¸¡ zh:ç®—æ³•

[X] Schliessen

Dieser Artikel basiert auf dem Artikel Algorithmus aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.

Arabische Sprache AOLPRESS Aorta AutoCAD Alessandro Volta Anwendungsprogramm Antoni van Leeuwenhoek

[Zurück ]

Inhalt Glossar:

Diese Seite einem Freund, Kollegen oder Bekannten weiterempfehlen? Hier klicken!

Allgemein

Geschichte

Erster Computeralgorithmus

Formale Definition

Turingmaschinen und Algorithmusbegriff

Church-Turing-These

Abstract State Machines

Ein Beispiel: der Euklidische Algorithmus

Eigenschaften

Determiniertheit

Determinismus

Finitheit

Statische Finitheit

Dynamische Finitheit

Terminiertheit

Algorithmenanalyse

Beispiele

Algorithmen in der Wikipedia

Algorithmen im Alltag

Siehe auch

Literatur

Weblinks