Teile und Herrsche 1 SS11

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2011-04-07T13:16:08+00:00. Aktuelle Version

Inhaltsverzeichnis

Autoren:


Die Idee

Entwurfsmethoden für Algorithmen

Bei der systematischen Programmentwicklung und für die unmittelbare Ableitung von Aufwandsaussagen sind verschiedene Entwurfsmethoden für Algorithmen hilfreich. Zu den Entwurfsmethoden gehören zum Beispiel:

  1. Teile und Herrsche
  2. Greedy-Algorithmen
  3. dynamisches Programmieren

Teile und Herrsche

Teile und Herrsche (engl. "divide and conqer", lat. "divide et impera") ist die Entwurfsmethode für Algorithmen die wir nachfolgend genauer betrachten wollen.

Teile und Herrsche hat seinen Ursprung als Redewendung und Strategie in der Kriegsführung. Bereits um 500 v. Chr. erwähnte Sunzi, ein chinesischer General sinngemäß "Teile und Herrsche" als Stratgie der chinesischen Kriegskunst. Mit divise pour régner(teilen, um zu herrschen) wurde es als Ausspruch des frz. König Ludwig XI (*1423-1483) bekannt.


Effizienzbetrachtung von Teile und Herrsche


Quicksort

Verfahren

Funktionsorientierte Beschreibung

Effizienzbetrachtung von Quicksort


Mergesort

Verfahren

Funktionsorientierte Beschreibung

Effizienzbetrachtung von Mergesort

Quellenverzeichnis

http://de.wikipedia.org/wiki/Divide_et_impera