Embed Size (px)
Citation preview
Algorithmen & Datenstrukturen
Prof. Dr. Wolfgang Schramm
ALGORITHMEN-‐ PARADIGMEN
4. Kapitel
1
Übersicht
1. Einführung 2. Algorithmen 3. EigenschaFen von
Programmiersprachen 4. Algorithmenparadigmen 5. Suchen & SorNeren 6. Hashing 7. Komplexität von Algorithmen 8. Abstrakte Datentypen (ADT) 9. Listen 10. Bäume 11. Graphen
2
Lernziele des Kapitels
¨ Sie verstehen was ein Algorithmenparadigma ist.
¨ Sie lernen verschiedene Algorithmenparadigmen kennenlernen und können diese jeweils in eine Anwendung umsetzen.
2
3
Inhalt
o Paradigma (Begriff) o WichNge Algorithmenparadigmen
¤ applikaNve (funkNonale), ¤ imperaNve, ¤ objektorienNerte, ¤ logische.
4
Paradigma, Algorithmenparadigma, Programmierparadigma
o Paradigma (in der WissenschaFstheorie) = Denkmuster, welches das
wissenschaFliche Weltbild einer Zeit prägt.
o Algorithmenparadigma = Denkmuster/Denkmodell, das die Formulierung und
den Entwurf von Algorithmen (und damit letztendlich auch den von Programmier-‐
sprachen) grundlegend prägt.
o Programmierparadigma (Programmiersprache vs. Algorithmus !) n Ein Programmierparadigma legt das einer Programmiersprache zugrundeliegende Prinzip fest.
n Programmierparadigmen entsprechen Algorithmenparadigmen bzw. setzen diese um.
n I.d.R. folgt eine Programmiersprache mehreren Programmierparadigmen, es gibt jedoch ebenso i.d.R. ein „herausragendes“.
5
WichNge Algorithmenparadigmen
o Grundlegende: ¤ applikaNve (funkNonale), ¤ ImperaNve.
o … weitere: ¤ objektorienNerte, ¤ logische, ¤ geneNsche, ¤ parallele, ¤ neuronale, ¤ agentenorienNerte.
Algorithmen
6
ApplikaNve Algorithmen
o ApplikaNve Algorithmen ...
sind eine Verallgemeinerung der FunkNonsauswertung mathemaNsch noNerter FunkNonen. In ihnen spielt Rekursion eine wesentliche Rolle.
ApplikaNver Algorithmus = Liste von FunkNonsdefiniNonen.
Eine FunkNon muss nicht für alle Eingaben definiert sein, insbesondere führt eine nicht terminierende Berechnung zu einem undefinierten Ergebnis (die FunkNon heißt dann parNelle FunkNon).
Beispiele:
FakultätsfunkDon
x! = x * (x-‐1) * (x-‐2) .... 2 * 1 für x > 0 -‐ mathemaNsche DefiniNon
fac(x) = if x ≤ 0 then 1 else x * fac(x-‐1) -‐ applikaNver Algorithmus
„Lazy evaluation“
Rekursion
„if“ ist eine Funktion! if (a, b, c)
sieht jedoch sehr ungewohnt aus.
7
ApplikaNve Algorithmen – DefiniNon (informell) 1/3
o DefiniNon Term (vom Typ int): n Ein „üblicher“ arithmeNscher Ausdruck mit Zahlen und Unbekannten. n Ein Ausdruck der Form if A then B else C fi (B, C vom Typ int). n Eine FunkNon vom Typ int. n Es gelten „übliche“ Vereinfachungsregeln (Auswertung).
¤ Andere Typen analog.
o DefiniNon FunkNon → Es sind v1, …, vn UnbesNmmte vom Typ t1, …, tn, sowie
T(v1, …, vn) ein Term mit dem Ergebnistyp tT, dann heißt f (v1, …, vn) = T (v1, …, vn) eine FunkNon vom Typ tT.
Formale Parameter
Funktionsausdruck
8
ApplikaNve Algorithmen – DefiniNon (informell) 2/3
o DefiniNon applikaNver Algorithmus ¤ Ein applikaNver Algorithmus ist eine Liste von FunkNonsdefiniNonen
f1 (v11, …, v1n1) = T1 (v11, …, v1n1) … fm (v11, …, v1nm) = Tm (v11, …, v1nm)
¤ Die Auswertung der ersten FunkNon f1 ist die Bedeutung des
Algorithmus.
o Anmerkung ¤ Es gibt keine Variablen, keine Zuweisung. ¤ Wesentlich: Rekursion.
Beispiele: Lisp
Scheme
9
ApplikaNve Algorithmen – DefiniNon (informell) 3/3
o DefiniNon parNelle FunkNon ¤ Eine FunkNon heißt parNell,
wenn sie für einige Eingabewerte nicht definiert ist.
o Anmerkung ¤ Eine FunkNon ist nicht definiert, wenn sie
n nicht terminiert oder n einen Fehler liefert.
10
ApplikaNve Algorithmen -‐ Beispiel
Euklid‘scher Algorithmus zur BesNmmung des größten gemeinsamen Teilers zweier natürlicher Zahlen (die sind immer > 0).
ggT(x,x) = x -‐ mathemaNsche Gesetzmäßigkeiten
ggT(x,y) = ggT(y,x)
ggT(x,y) = ggT(x,y-‐x) für x < y
ggT(x,y) = if (x ≤ 0 ) or (y ≤ 0) then
ggT(x,y)
else if x = y then -‐ applikaNver Algorithmus
x
else if x > y then
ggT(y,x)
else
ggT(x, y-‐x)
fi;
11
Diskussion
• Nehmen wir an, dass wir einen Rechner haben, der nur die AddiNon beherrscht. Wie können wir trotzdem eine MulNplikaNon realisieren?
• Stellen Sie dazu mathemaNsche Regeln auf.
• Setzen Sie die Regeln um in einen applikaNven Algorithmus.
12
ApplikaNve Algorithmen -‐ Aufgabe
o Nehmen wir an, dass wir einen Rechner haben, der nur die AddiNon beherrscht. Wie können wir trotzdem eine MulNplikaNon realisieren?
o Stellen Sie dazu mathemaNsche Regeln auf.
o Setzen Sie die Regeln um in einen applikaNven Algorithmus.
mos (a, b) = mos (b, a) - mathematische Definition
mos (a, 0) = 0
mos (a, b) = mos (a, b-1) + a für b > 0
= mos (a, b+1) – a für b < 0
13
ImperaNve Algorithmen
o ImperaNve Algorithmen ...
basieren auf einem einfachen Maschinenmodell mit änderbaren Werten. Hier werden primär Schleifen und AlternaNven als Kontrollbausteine eingesetzt.
Der Algorithmus wird ausgeführt auf einem „üblichen“ Rechner, d.h. n Es gibt Variable, die einen Wert speichern können. n Es gibt Anweisungen, die einen Wert ändern können.
o Anmerkung ¤ Basiert auf der von-‐Neumann-‐Architektur.
14
ImperaNve Algorithmen -‐ Beispiel
Beispiel fac (x: int): var y: int; y := 1; while x > 1 do y := y*x; x := x-1; od; output y;
(2, 6) (1, 6)
Zustand (x, y)
(3, -) (3, -) (3, 1)
(3, 3) (2, 3)
Aufruf: fac (3)
Ausgabe: 6
15
ImperaNve Algorithmen – DefiniNonen 1/3
o DefiniNon Variable ¤ Eine Variable hat einen Namen und einen – veränderlichen – Wert. ¤ Der Wert kann durch eine Zuweisung eines Terms geändert werden.
o DefiniNon Zustand ¤ Der Zustand eines Rechners zu einem besNmmten Zeitpunkt ist die
Zuordnung von Werten zu allen Variablen.
o Anmerkung ¤ Ein Term bei der imperaNven Algorithmen enthält Variable stax
Unbekannte.
16
ImperaNve Algorithmen – DefiniNonen 2/3
o DefiniNon transformierter Zustand ¤ Ein transformierter Zustand Zneu ist der neue sich ergebende Zustand
nach der Durchführung einer Zuweisung in einem alten Zustand Zalt. ¤ Für den transformierten Zustand gilt:
n Der Wert einer Variabeln V im Zustand Zneu ist n der gleiche wie in Zalt, falls die Zuweisung die Variable
nicht betroffen hat. n der Wert des Terms der Zuweisung, falls die Zuweisung an
diese Variable ausgeführt wurde.
17
ImperaNve Algorithmen – DefiniNonen 3/3
o DefiniNon Anweisung (informell) ¤ Eine Anweisung ist ein Algorithmus-‐Baustein mit ent-‐sprechenden
Zustandsänderungen.
o DefiniNon imperaNver Algorithmus ¤ Ein imperaNver Algorithmus ist eine Anweisung. ¤ Die Ausführung eines imperaNven Algorithmus ist eine Folge von
Zuständen, wobei jeder Zustand der transformierte Zustand seines Vorgängers ist.
¤ Die Bedeutung (SemanNk) des Algorithmus ist gegeben durch den letzten Zustand.
Beispiele: C
Fortran
18
ImperaNve Algorithmen – prozedurale Programmierung
o Anmerkung ¤ Anweisung
n Ein Programm ist i.d.R. keine elementare OperaNon, sondern eine Folge (Sequenz) von OperaNonen.
n WichNges Strukturierungsmixel: Prozeduren
(à imperaNve oder prozedurale Programmierung) ¤ Bedeutung
n OF nur Wert der Ausgabevariablen.
19
Diskussion
¨ Schreiben Sie den Euklidischen Algorithmus in imperaNver Form.
20
ImperaNve Algorithmen -‐ Beispiel
Berechnung der Fakultät: fac: var x, y: int;
y := 1; while x > 1 y := y*x; x := x-‐1; od; output y;
Euklid‘scher Algorithmus (ggT) – eine mögliche Lösung: ggT: var x, y: int;
input x,y; while x ≠ y while x > y x := x-‐y; od; while x < y y := y-‐x; od; od; output x;
21
ObjektorienNerte Programmierung 1/2
v Idee
¤ Es gibt eine Menge von Objekten (Einheit von Daten und FunkNonen).
¤ Ein Objekt hat einen Zustand.
¤ Die Objekte kommunizieren.
¤ Es gibt ein ausgezeichnetes Start-‐Objekt.
¤ Die Ausführung ergibt eine Folge von verteilten Zuständen.
Beispiele: C++ Java
Smalltalk
22
ObjektorienNerte Programmierung 2/2
o Beispiel
Kapselung: Implementierung
unsichtbar
Math
+fac (int i):int
Polymorphie à Daten Dynamische Bindung à Methoden
Object
+equals
Vererbung
23
Logische Algorithmen 1/2
v Idee ¤ Es gibt eine Menge Formeln. ¤ Es gibt eine Menge logischen Fakten und Regeln
(Fakt = Formel mit Konstanten). ¤ Es gibt eine Anfrage:
n Formel mit Konstanten: Formel verifizieren. n Formel mit Variablen: Belegung für Variable suchen.
o Beispiel ¤ Fakten: Sohn (Peter, Rainer); Sohn (Rainer, Walter) ¤ Regeln: Sohn (a, b) ∧ Sohn (b, c) à Enkel (a, c) ¤ Anfrage: Sohn (Peter, Walter)? ⇒ false
Enkel (Peter, a)? ⇒ a = Walter
24
Logische Algorithmen 2/2
o Auswertung ¤ Backtracking (vereinfacht)
n Gegeben: Anfrage ohne bzw. mit einer Variablen. n Vorgehen:
1. Wähle den ersten Fakt. 2. Teste den gewählten Fakt,
d.h. wird die Anfrage durch Einsetzen wahr? 3. Falls ja à ferDg (true bzw. Belegung)
(mit erneutem Aufruf nächste Belegung finden). 4. Falls nein à wähle den nächsten Fakt;
weiter mit 2. 5. Falls kein Fakt mehr verfügbar
à ferDg (false bzw. keine Lösung).
25
Noch Fragen?
25
