A2.1 Divide & Conquer

Autor: Urs Battaglia

Sehr häufig hat man im Leben Probleme zu lösen, die zu unüberschaubar und gross sind, um sie in einem Ansatz zu lösen. Vielmehr teilen wir das Gesamtproblem auf in mehrere, handhabbare Stücke, die wir lösen. Die Teillösungen werden danach nur noch zusammengefasst.
Dieses Prinzip wird auch in der Informatik sehr stark verwendet: Ein Programm zerlegt die gestellte Aufgabe zunächst in mehrere kleinere Einheiten, genannt Teilprobleme und weist danach andere Programme an, diese zu lösen. Dabei ist sehr wichtig, dass die Teilprobleme unabhängig voneinander gelöst werden können, sonst müssten die Programme miteinander kommunizieren, unter Umständen auf Lösungen voneinander warten, was den Aufwand wiederum sehr erhöht.

1. Bei Divide & Conquer Algorithmen geht es in erster Linie nicht um das Unterteilen eines Problems wie dies Beispielsweise das EVA-Prinzip (P0 Basics: EVA-Prinzip, Codierung von Ein- und Ausgabewerten) tut. Ziel ist eine rekursive Rückführung auf kleinere, sehr ähnliche Probleme, bis es am Ende einfach (trivial) lösbar wird.
2. Divide & Conquer Algorithmen teilen meist nicht das Problem sondern die Daten auf. Das Problem bleibt das selbe, aber auf mehrere kleinere Datensätze verteilt.
3. Ziel ist immer eine schnellere (weniger Rechenzyklen) Lösbarkeit eines Problems.

1. Ich kenne die Merkmale und Vorteile von Divide & Conquer Algorithmen und kann diese an Beispielen erläutern.
2. Ich erkenne anhand von Fluss- oder Nassi-Shneiderman-Diagrammen einen Divide & Conquer Algorithmus und kann diesen erklären.
3. Ich kann einfache Probleme mit Hilfe eines Divide & Conquer Algorithmus lösen und diesen als Fluss- oder Nassi-Shneidermann-Diagramm aufschreiben.
4. Ich kann für einen gegeben Algorithmus erklären, weshalb er das Problem schneller löst.

• Turm von Hanoi
• Sortieralgorithmen, z.B. Quicksort
• Suche in sortierter Liste
  • Spezialfall von D&C — JH
• Vergleich von Daten (z.B. Unterschriften)
• Diskrete Fourier Transformation (Komprimierung von JPG)
• Probleme aus der Mathematik
  • Potenzieren von Zahlen
  • Berechnung von Fibonacci-Zahlen
  • Matrixmultiplikation
  • Algorithmen aus der Numerik und des parallelen Rechnens

• A0 Algorithms
• A2 Rekursion
• P0 Basics: EVA-Prinzip, Codierung von Ein- und Ausgabewerten
• P3 Closures: Methoden, Prozeduren und Funktionen

• Introduction to Algorithms - Divide and Conquer
• Leitprogramm "Greedy" und "Divide & Conquer"

• Auch die Informatik lernt von der Politik. — Paul Miotti 2008/06/24
• Lösen einer Probleminstanz durch lösen von Teilprobleminstanzen des selben Problems und zusammenführen der Resultate — JH
• Problematik der mehrfachen Berechnung von gleichen Teilproblemen — JH