Algorithmus

Zum Forum
Passwort vergessen? Noch keinen Account?

lexikon

Hauptseite

Zufälliger Artikel

Diskussion

Diskussion : Algorithmus

Links

Forum

Portale

Reisen

Versicherung

Inhaltsverzeichnis

Hauptmenü

Home

Bildung

Wissen

--------------------------

Reisen

Lexikon

Versicherung

Suchen

News

Treffpunkt

Chat

Forum

Suche

Schnellsuche

Sitemap

Kontakt

Impressum

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
	etc.
	wenn alle Angaben genau genug sind und es fÃ¼r alle Teilaufgaben
	wie Braten
	ebenfalls Algorithmen gibt
	RÃ¼hren
	Im tÃ¤glichen Leben lassen sich leicht Beispiele fÃ¼r Algorithmen finden: Zum Beispiel ist ein Kochrezept ein Algorithmus â€“ zumindest dann
	Auch Reparatur- und Bedienungsanleitungen oder Hilfen zum AusfÃ¼llen von Formularen sind in der Regel Algorithmen
	Ein weiteres
	etwas prÃ¤ziseres Beispiel sind Waschmaschinenprogramme
	Vor allem aber sind Algorithmen eine der zentralen Themen der Informatik und Gegenstand einiger Spezialgebiete der Theoretischen Informatik
	der KomplexitÃ¤tstheorie und der Berechenbarkeitstheorie
	wie der Algorithmentheorie
	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
	d. h. einer idealen mathematischen Maschine). Inhaltsverzeichnis showTocToggle("Anzeigen"
	dass Algorithmen gerade die Maschinenprogramme von Turingmaschinen sind (wobei hier die Abstraktion in der Verwendung der Turingmaschine an sich erfolgt
	bis hin zur Sicht
	das Programm ist eine konkrete Form des Algorithmus
	angepasst an die Notwendigkeiten und MÃ¶glichkeiten der realen Maschine)
	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
	"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]
Geschichte
	Das Wort Algorithmus ist eine Abwandlung oder Verballhornung des Namens Muhammad ibn Musa al-Chwarizmi (* ca
	783
	â€ ca
	850)
	Regeln zur Wiederherstellung und Reduktion)
	durch das die Algebra im Westen verbreitet wurde
	des Autors des Buchs Hisab al-dschabr wa-l-muqabala (825
	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
	mit denen Probleme aller Art gelÃ¶st werden kÃ¶nnen. [Bearbeiten]
	Heute steht es fÃ¼r alle geregelten Prozeduren
Erster Computeralgorithmus
	in ihren Notizen zu Charles Babbages Analytical Engine
	festgehalten
	Der erste fÃ¼r einen Computer gedachte Algorithmus wurde 1842 von Ada Lovelace
	Sie gilt deshalb als die erste Programmiererin
	wurde Ada Lovelaces Algorithmus nie darauf implementiert. [Bearbeiten]
	Weil Charles Babbage seine Analytical Engine nicht vollenden konnte
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
	um zu einer genauen Definition zu kommen
	Jahrhunderts wurden eine ganze Reihe von AnsÃ¤tzen entwickelt
	rekursive Funktionen
	und Markow-Algorithmen
	Formalisierungen des Berechenbarkeitsbegriffs sind die Turing-Maschine (Alan Turing)
	Chomsky-Grammatiken
	der Lambda-KalkÃ¼l (Alonzo Church)
	dass all diese Methoden ebenso leistungsfÃ¤hig (gleich mÃ¤chtig) sind
	Es wurde â€“ unter maÃŸgeblicher Beteiligung von Alan Turing selbst â€“ gezeigt
	wenn eine zu dieser Berechnungsvorschrift Ã¤quivalente Turingmaschine existiert
	die fÃ¼r jede Eingabe stoppt
	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
	siehe PlatzkomplexitÃ¤t). Das Verfahren darf nur endlich viele Schritte benÃ¶tigen (Terminierung
	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 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
	dass ein Problem berechenbar ist genau dann
	d. h. wenn eine entsprechend programmierte Turing-Maschine das Problem in endlicher Zeit lÃ¶sen kÃ¶nnte. [Bearbeiten]
	wenn es einen (terminierenden) Algorithmus zu dem Problem gibt
	Der Begriff der Berechenbarkeit ist dadurch dann so definiert
Abstract State Machines
	Turingmaschinen harmonieren sehr gut mit den ebenfalls abstrakt-mathematischen berechenbaren Funktionen
	daher wurden andere Maschinen vorgeschlagen
	reale Probleme sind jedoch ungleich komplexer
	anstatt den einfachen Operationen der Turingmaschine
	Diese Maschinen weichen z.B. in der MÃ¤chtigkeit der Befehle ab
	wie z
	kÃ¶nnen sie z.T. sehr mÃ¤chtige Operationen
	BF
	in einem Rechenschritt ausfÃ¼hrenO
	ouriertransformation
	sondern ermÃ¶glichen sehr parallele Operationen
	der sie beschrÃ¤nken sich nicht auf eine Operation pro Rechenschritt
	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
	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]
	dass immer terminiert werden muss
	der fortgesetzt Primzahlen findet
	SM 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
	seien der Sieb des Erastothenes
Ein Beispiel: der Euklidische Algorithmus
	der bereits um 300 v
	Der Euklidische Algorithmus
	Chr. beschrieben wurde
	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
	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
	wenn sie gleich sind
	dann fahre fort mit Schritt 1
	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
	Nichtdeterministische Algorithmen finden vor allem in der Theoretischen Informatik Anwendung
	dass es sich um einen deterministischen Algorithmus handelt
	so dass in anderen Bereichen oft vorausgesetzt wird
	Eine Ausnahme bilden so genannte stochastische
	randomisierte oder probabilistische Algorithmen
	in die absichtlich ein Zufallsfaktor eingebaut wurde
	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
	muss das gleiche Ergebnis berechnet werden
	Kurz: Wenn gleiche Startwerte vorhanden sind
	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
	Gibt es mehrere MÃ¶glichkeiten der Programmfortsetzung und lassen sich diesen Wahrscheinlichkeiten zuweisen
	so spricht man von stochastischen
	randomisierten oder probabilistischen Algorithmen
	In der theoretischen Informatik gibt es neben dem Determinismus auch den Nichtdeterminismus
	der aber in der Praxis kaum Verwendung findet
	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
	erfÃ¼llen diese Eigenschaft nicht: Wenn der Benutzer keinen Befehl zum Beenden gibt
	Die tatsÃ¤chliche Zahl der Schritte kann dabei beliebig groÃŸ sein. Steuerungssysteme und Betriebssysteme und auch viele Programme
	die auf Interaktion mit dem Benutzer aufbauen
	lÃ¤uft das Programm endlos weiter
	Donald Knuth schlÃ¤gt in diesem Zusammenhang vor
	nicht terminierende Algorithmen als rechnergestÃ¼tzte Methoden ("Computational Methods") zu bezeichnen
	Es ist Ã¼brigens im allgemeinen nicht mÃ¶glich
	fÃ¼r einen Algorithmus zu bestimmen
	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
	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
	d.h. die angegebene KomplexitÃ¤t hÃ¤ngt davon ab
	oder wie viele Elemente sortiert werden mÃ¼ssen etc
	Der Ressourcenbedarf wird dabei in AbhÃ¤ngigkeit von der LÃ¤nge der Eingabe ermittelt
	deren ggT gesucht wird
	wie groÃŸ die Zahlen sind
	d.h. ob der Algorithmus Ã¼berhaupt jemals erfolgreich beendet werden kann
	behandelt die Berechenbarkeitstheorie. [Bearbeiten]
	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
	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
	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
	Funktionsplan der Registrierkasse Eintasten von 17
	82 + [Bearbeiten]
Siehe auch
	Liste von Algorithmen Ameisenalgorithmus Approximationsalgorithmus Datenstruktur Determinierter Algorithmus Deterministischer Algorithmus Entscheidungsproblem EvolutionÃ¤rer Algorithmus Genetischer Algorithmus Greedy Algorithmus "gieriger" Algorithmus
	z.B. zur Zerlegung von BrÃ¼chen in Summen von StammbrÃ¼chen Heuristik KomplexitÃ¤tsklassen MMIX (virtuelle Maschine von Donald E
	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
	Formale Sprachen und KomplexitÃ¤tstheorie
	EinfÃ¼hrung in die Automatentheorie
	Pearson Studium
	2002
	ISBN 3-8273-7020-5. Donald E
	Addison Wesley 1998. (Das ist der Standard in dem Bereich; Ãœbersetzung existiert nicht â€“ Juli 2000)
	Vol 1â€“3
	ISBN 0201485419 Thomas H
	Knuth: The Art of Computer Programming
	Cormen
	Charles Leiserson
	Ronald L
	Rivest
	2nd edition 2001
	MIT Press
	Clifford Stein: Introduction to Algorithms
	ISBN 0262531968 Deutsche Ãœbersetzung: Thomas H
	Charles Leiserson
	Cormen
	Ronald L
	Clifford Stein: Algorithmen - Eine EinfÃ¼hrung
	ISBN 3-486-27515-1 [Bearbeiten]
	Rivest
	Oldenbourg Wissenschaftsverlag
	2004
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 Lexikon:

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