Mathematik Informatik Philosophie Diverses Kontatkt FAQ
Benutzername:
Passwort:
 Home > News
Freitag, 24. März 2017 09:04 
Artikel zur Kategorie: Informatik

11 Artikel (3 Seiten, 5 Artikel pro Seite)

zu Seite: 2 1 2 3


Das Paradigma 'Divide and Conquer' am Beispiel des Quicksort-Algorithmus (Informatik)
mehr... (8046 mehr Zeichen) Druckoptimierte Version Diesen Artikel an einen Freund senden 5523 mal gelesen
Teile und herrsche (lateinisch: divide et impera) ist angeblich ein Ausspruch des französischen Königs Ludwigs XI.

'Teile und herrsche' steht für das Prinzip, die eigenen Gegner gegeneinander auszuspielen und deren Uneinigkeit zum eigenen Zwecke und Nutzen zu verwenden. Alles also nach dem Motto: Wenn zwei sich streiten freut sich der Dritte.

In der Informatik bezeichnet man eine bedeutende Problemlösungsstrategie mit dem englischen Analogon 'Divide and Conquer'. Auch hier wird (das gestellte Problem) geteilt und in gewisser Art und Weise anschließend (über das 'besiegte' Problem) geherrscht. Allerdings enden an dieser Stelle die Gemeinsamkeiten auch schon.

Das 'Divide and Conquer'-Prinzip versucht ein gestelltes Problem P der Größe n in zwei Teilprobleme P1 und P2 zu zerlegen (divide-Schritt). Diese Teilung führt man solange durch, bis die Problemlösung trivial, offensichtlich oder zumind. wesentlich vereinfacht wird. Die eigentliche Aufgabe besteht also letztlich darin, die Lösungen der Teilprobleme P1 und P2 zu einer -umfassenden- Lösung des Gesamtproblems zusammenzufassen (conquer-Schritt).

Ein Paradebeispiel für das Paradigma des 'Divide and Conquer' ist der im Durchschnitt schnellste Sortieralgorithmus überhaupt: Der Quicksort!

Das folgende Bild (Quelle: FH Flensburg) illustriert die Vorgehensweise eines Quicksorts angewendet auf eine (abbrechende) Folge aus dem Körper IF2={0,1}.
Im ersten Schritt wird die zu sortierende Folge a in zwei Teilfolgen b und c zerlegt, so dass alle Elemente der ersten Teilfolge b kleiner oder gleich allen Elementen der zweiten Teilfolge c sind (divide).

Geschrieben von Alexander am Dienstag, 10. Januar 2006 mehr...


11 Artikel (3 Seiten, 5 Artikel pro Seite)

zu Seite: 2 1 2 3


Umfrage
Ganz klar, das schönste Ressort der Mathematik ist die

Zahlentheorie
(Lineare) Algebra
Topologie, Maßtheorie, Integrationstheorie
Statistik, Wahrscheinlichkeitstheorie, Stochastik
Analysis, Funktionalanalysis
Funktionentheorie
Kombinatorik, Graphentheorie
Diskrete Mathematik
Lineare Optimierung

Ergebnisse
Stimmen: 660
Kommentare: 0
Umfragen

Login
Benutzername:

Passwort:



Alle Logos und Warenzeichen auf dieser Seite sind Eigentum der jeweiligen Besitzer und Lizenzhalter.
Im übrigen gilt Haftungsausschluss. Weitere Details finden Sie im Impressum.
Die Inhalte dieser Seite sind als RSS/RDF-Quelle verfügbar.
Die Artikel sind geistiges Eigentum des/der jeweiligen Autoren,
alles andere © 2004 - 2017 by mathematik-netz.de

Seitenerstellung in 0.0738 Sekunden, mit 52 Datenbank-Abfragen