Post on 06-Apr-2016
transcript
Programmierungstechnik
© Günter RiedewaldDie Folien sind eine Ergänzung zur Vorlesung und nur für den internen Gebrauch konzipiert.
VorbemerkungenRolle einer Vorlesung:- Grundstruktur für Selbststudium- Ermöglichung der selbständigen
Nutzung der Literatur- Hinweis auf Probleme und
Gesamtzusammenhänge
VorbemerkungenRolle von Übungen:- Ergänzung der Vorlesung durch
umfangreichere Beispiele- Dialog von Übungsleiter und Student
zur Beseitigung von Unklarheiten- Aktive Mitarbeit als Voraussetzung
der aktiven Auseinandersetzung mit dem Stoff
VorbemerkungenVorlesungshilfsmittel:- Tafel - Schreibarbeit für beide Seiten + Hören-Sehen-Schreiben in Kombination erleichtert Verständnis und Merkfähigkeit+ Ableitungen besser darstellbar
Vorbemerkungen- Folien +- Vermittlung von mehr Stoff +- Schreibarbeit entfällt - Höherer Aufwand zur Einprägung des Stoffes
Vorbemerkungen- Multimedia - Hoher Entwicklungs- und Wartungsaufwand - Bisher kein Nachweis eines deutlich höheren Lerneffekts+ Darstellung dynamischer Vorgänge
Hier: Kombination von Tafel und Folien
VorbemerkungenLiteraturstudium:- Ausführliche Beschäftigung mit dem
Stoff- Andere Sichten- Mehrmaliges Lesen:
1. Diagonal Überblick2. Durcharbeiten gründliches Verständnis
VorbemerkungenPrüfungen:- Nachweis von Wissen und Fähigkeit
der aktiven Nutzung (Verstehen Wiedergabe Anwendung)
- Prüfungsvorbereitung führt zur Verknüpfung von Teilgebieten und mit anderen Lehrgebieten
VorbemerkungenAbschlüsse und Bedingungen:- Studiengang Informatik (Fachprüfung
Praktische Informatik):1. Sem.: schriftliche Prüfung (ca. 150 min)2. Sem.: benoteter Leistungsnachweis3. Sem.: mündliche Prüfung (ca. 20 min) über PT und SWT (Vor.: Benoteter Leistungsnachweis)
Vorbemerkungen- Studiengang IT/TI:
1. Sem.: schriftliche Prüfung (ca. 150 min)2. Sem.: mündliche Prüfung (ca. 30 min)
Vorbemerkungen- Studiengang WIN/BIN:
2. Sem.: benoteter Leistungsschein3. Sem.: mündliche Prüfung (ca. 30 min) zu PT und SWT
VorbemerkungenRolle der Theorie:- Schnelles Veralten von Wissen zu
konkreten Systemen- Langlebige und allgemeingültige
Erkenntnisse in der Theorie- Theorie als Basis (Befähigung zur)
Weiterbildung
Vorbemerkungen- Theorie als Basis der Automatisierung
von Prozessen der IV- Schnelle Einsatzbereitschaft von
Absolventen erfordert Praxiserfahrungen- Realitätsnahe Ausbildung an HS schwer
zu verwirklichen Ausbildung als Mix von Theorie und
Praxis
VorbemerkungenRolle der Theorie nach J. Nievergelt
(Informatik-Spektrum, 18(6), S. 342-344, 1995)Anwendungsmethodik ProblemlösungenSystemrealisierung ProgrammsystemeAlgorithmik ProgrammierungTheorie abstrakte math.Fakten
LiteraturAlagic’, S., Arbib, M.A.: The Design of Well-
Structured and Correct Programs, Springer-Verlag, 1978
Appelrath, H.-J., Ludewig, J.: Skriptum Informatik - eine konventionelle Einführung, B.G. Teubner Stuttgart, 1991
LiteraturBauer, F.L., Goos, G.: Informatik - eine
einführende Übersicht Heidelberger Taschenbücher, Sammlung
Informatik, Springer-Verlag, Teile 1+2, 3. Auflage, 1982, 1984, 4. Auflage 1991
Berman, K.A., Paul, J.L.: Fundamentals of Sequential and Parallel Algorithms, PWS Publishing Company, 1997
LiteraturForbrig, P.: Introduction to Programming
by Abstract Data TypeFachbuchverlag Leipzig, 2001
Goldschlager, L., Lister, A.: Informatik - Eine moderne Einführung, Hanser Verlag, Prentice-Hall International, 3. Auflage 1990
LiteraturHotz, G.: Einführung in die Informatik,
B.G. Teubner Stuttgart, 1990
Kröger, F.: Einführung in die Informatik - Algorithmenentwicklung, Springer-Lehrbuch, Springer-Verlag, 1991
LiteraturMyers, G.J.: The Art of Software Testing,
Wiley-Interscience Publication 1979oder: Methodisches Testen von
Programmen, Oldenbourg Verlag, 4. Auflage, 1991
Pomberger, G.: Softwaretechnik und Modula-2, Hanser Verlag, 1984
LiteraturSedgewick, R.: Algorithmen, Addison-Wesley
Publ. Company, 1992, 2002 2.Auflage
Sedgewick, R.: Algorithmen in JavaAddison-Wesley Publ. Comp., 2003
Sedgewick, R.: Algorithmen in C++Addison-Wesley Publ. Comp., 2002
LiteraturWeitere Literatur: z. B. von den
Autoren Broy, Gruska, Kerner, Wilhelm
Siehe auch Lehrbücher zu konkreten Programmiersprachen
Inhalt 1. Einleitung
2. Grundbegriffe3. Algorithmenentwurf und Programmentwicklung 3.1 Einleitung 3.2 Programmierungstechniken 3.3 Techniken der Algorithmenentwicklung (Iteration, Rekursion, nichtdeterministische Algorithmen, Backtracking, parallele Algorithmen)
3.4 Korrektheit, Zuverlässigkeit 3.4.1 Programmteste 3.4.2 Korrektheitsbeweise (Verifikation) 3.4.2.1 Deduktive Methode 3.4.2.2 Model Checking 3.5 Datenstrukturen 3.5.1 Einleitung 3.5.2 Mathematische Grundlagen 3.5.3 Fehlerbehandlung 3.5.4 Datenstrukturen und ihre Implementation
4. Existenz und Durchführbarkeit von Algorithmen
4.1 Berechenbarkeit, Terminiertheit, Durchführbarkeit
4.2 Komplexität 4.3 Nichtprozedurale Algorithmen
5. Ausgewählte Algorithmen 5.1 Sortierverfahren
5.1.1 Adressenorientiertes Sortieren
5.1.2 Assoziatives Sortieren
5.2 Suchverfahren5.2.1 Einleitung5.2.2 Suchalgorithmen auf der Basis von Adressberechnungen (Hashing, perfektes Hashing, digitale Suchbäume, Tries)5.2.3 Assoziatives Suchen (Suchen in geordneten Mengen)5.2.3.1 Suchverfahren5.2.3.2 Gewichtete Bäume5.2.3.3 Balancierte Bäume (gewichtsbalanciert, höhenbalanciert)
5.3 Heuristische Algorithmen5.4 Evolutionsalgorithmen
6. Funktionales Programmieren6.1 Funktionen in der Mathematik6.2 Datentypen und Programmierung
Problem 1 Anwendung 1
Problem 2 Mathe. SoftwareModell
Problem nAnwendung m
Abstraktion Spezialisierung
Datenverarbeitung: = (N, I), : D D N
Nachricht Nachricht´
Information Information´ I
d D d´ D
Spezifikation Algorithmus inmathematischer Notation
Algorithmus in höhererProgrammierung Programmiersprache
Algorithmus inÜbersetzung Maschinensprache
Flussbilder - GrundelementeVerarbeitungsblock
<Anweisungs- x := x + 1 folge> y := 0
Bedingungnein ja nein ja
x < 0
Flussbilder - GrundelementeKonnektoren
<Zahl> <Zahl> 25 25
Gerichtete Kanten
Motto
Bevor ein Zimmermann ein Haus baut, muss er einen Plan dafür erarbeiten.
Eine Hundehütte kann er jederzeit auch ohne große Vorbereitung bauen.
Schrittweise Verfeinerung – Beispiel 1
Zubereitung einerTasse Kaffee
Koche Wasser Kaffee in TasseWasser in Tasse
Wasser in Einschalten Warten bisKessel zum Kochen
Schrittweise Verfeinerung – Beispiel 2
Sortieren einer Folge F zu F´
Zerlegung SortierungMischen
in F1 und F2 von F1 zu F1´ von F1´ und von F2 zu F2´ F2´ zu F´
Schrittweise VerfeinerungBeispiel 3program ggt( (*a,b*));(*Vereinbarungen*)begin(* Eingabe a,b *)x := a; y := b;while y<>0 do
begin (* Verkleinerung von y; Änderung von x *) end ;
(* Ausgabe ggt(a,b)*)end.
StruktogrammeVerarbeitungsblock
<Anweisungen> Lies N
Block mit Bezeichnung
<Name> Maxberech
StruktogrammeReihung zweier Blöcke
Lies m, ky := m * k
Wiederholung (abweisender Zyklus)<Bedingung> x > 0 <Anwei- x := x * 1 sungen> y := y + 2
StruktogrammeWiederholung (nichtabweisender Zyklus)
<Anwei- x := x – 1sungen> y := y + 2<Bedingung> x < 0
Wiederholung (Zählzyklus)v=a,e,s i=1, 10, 2 <Anweisungen> s := s + 1
StruktogrammeWiederholung (ohne Bedingung)
<Anweisungen> Temperatur-messung
Alternative (einfach)<Bedingung> x > 0
true false true false<Anw> <Anw> z := 1 z := 0
StruktogrammeFallabfrage (mehrfache Alternative)
<Ausdruck> s
W1 W2 ... Wn -1 0 1A1 A2 ... An x := 0 y := 0 z := 0
StruktogrammeAbbruchanweisung
<Name> S1 B1B2true falseA1 S1A2S2
Beziehungen Dienstmodul - KundenmodulDatenmodulDienstmodul- Definitionsmodul: Datentypen,
Konstanten, Variablen- Implementationsmodul: leer
KundenmodulNutzung der Daten
BeziehungenDienstmodul - KundenmodulFunktionsmodulDienstmodul- Definitionsmodul: Prozedur/Funktionsköpfe- Implementationsmodul:
Prozedur/Funktionsrümpfe
KundenmodulLokale Daten und Prozedur/Funktionsaufrufe
BeziehungenDienstmodul - KundenmodulDatenkapselDienstmodul- Definitionsmodul: Prozedur/Funktionsköpfe- Implementationsmodul:
Prozedur/Funktionsrümpfe und Daten
KundenmodulProzedur/Funktionsaufrufe (keine eigenen
Daten)
BeziehungenDienstmodul - KundenmodulAbstrakter DatentypDienstmodul- Definitionsmodul:
Prozedur/Funktionsköpfe, Datentyp- Implementationsmodul: Struktur des
Datentyps, Prozedur/FunktionsrümpfeKundenmodulProzedur/Funktionsaufrufe, Daten zum
Datentyp
DEFINITION MODULE Dateimanager; (*Dateimanipulationsroutinen*) CONST Endnr = 65535; (* groesste Kontonr*) TYPE Kontonr = CARDINAL; PROCEDURE AddiereWert; (*addiert Wert des letzten Bewegungsdatensatzes zum Datensatz im
Ausgabepuffer*) PROCEDURE SchliesseDateien; (*schliesst alle Dateien*) PROCEDURE AusNeuStamm; (*schreibt Ausgabepuffer in neue Stammdatei*) PROCEDURE EinBewegung(VAR Bewnr: Kontonr); (*liefert einen Datensatz der Bewegungsdatei und seine Nummer*) ... END Dateimanager.
IMPLEMENTATION MODULE Zufall; (*Zufallszahlen nach der Kongruenzmethode*) FROM InOut IMPORT WriteString, WriteLn, WriteCard, ReadCard; CONST Modulus = 2345; Faktor = 3; Inkrement = 7227; VAR Seed: CARDINAL; PROCEDURE RandomCard(A, B: CARDINAL): CARDINAL; VAR random: REAL; BEGIN Seed := (Faktor*Seed+Inkrement) MOD Modulus; random := FLOAT(Seed)/FLOAT(Modulus); random := random*(FLOAT(B)-FLOAT(A)+1.0)+FLOAT(A); RETURN TRUNC(random) END RandomCard; BEGIN WriteString(‘Zufallszahlen’); WriteLn; WriteString(‘Startwert?’); ReadCard(Seed); WriteLn END Zufall.
DEFINITION MODULE Konserve; TYPE tName = ARRAY [0..79] OF CHAR; tWochentag = (Montag, Dienstag, Mittwoch, Donnerstag, Freitag,
Samstag, Sonntag); tMonat = (Januar, Februar, Maerz, April, Mai, Juni, Juli, August,
September, Oktober, November, Dezember); tDatum = RECORD Tag:[1..31]; Monat: tMonat; Jahr: CARDINAL END; VAR Datum: tDatum; Konto: RECORD Name: tName; Kontonr: CARDINAL; datum: tDatum; wert: RECORD mod: (soll, haben); mark: CARDINAL; pfg: CARDINAL END; END; CONST MaxCard = 65535; MaxInt = 32767; MinInt = (-32767) - 1 END Konserve.
DEFINITION MODULE Stapel; (*fuer Cardinalzahlen*) VAR Fehler: BOOLEAN; (*Fehler, falls versucht wird, ein Element von
einem leeren Stapel zu entnehmen oder ein Element auf einen vollen Stapel abzulegen*)
PROCEDURE leererStapel; (*Initialisierung eines Stapels*) PROCEDURE push(c: CARDINAL); (*Zahl auf einen Stapel*) PROCEDURE pop(VAR c: CARDINAL); (*Zahl vom Stapel*) END Stapel.
DEFINITION MODULE ADTPuffer; TYPE Puffer; PROCEDURE leere(VAR R: Puffer); PROCEDURE leer(R: Puffer): BOOLEAN; PROCEDURE voll(R: Puffer): BOOLEAN; PROCEDURE push(VAR R: Puffer; El: CARDINAL); PROCEDURE pop(VAR R: Puffer); PROCEDURE gen(VAR R: Puffer) END ADTPuffer.
IMPLEMENTATION MODULE ADTPuffer; (*Ringpuffer*) IMPORT... FROM... CONST G = 8; (* G-1 Groesse des Ringpuffers*) TYPE Puffer = POINTER TO Ring; Ring = RECORD rng: ARRAY[1..G] OF
CARDINAL; kopf, ende: [1..G] END; ... END ADTPuffer.
MODULE Ablage; ... FROM ADTPuffer IMPORT Puffer, gen,
leer, voll, push, pop; ... VAR Ordner1, Ordner2: Puffer; ... END Ablage.
OOP - Beispiel CLASS Complex(x,y);
REAL x,y; BEGIN REAL re,im;
REAL PROCEDURE RealPart;BEGIN RealPart := re; END RealPart;
REAL PROCEDURE ImaginaryPart;BEGIN ImaginaryPart := im; END ImaginaryPart;
PROCEDURE Add(y); REF (COMPLEX) y;BEGIN re := re + y.RealPart;im := im + y.ImaginaryPart; END Add;
... re := x; im := y; END COMPLEX; REF (COMPLEX) C1, C2, C3; C1 :- NEW COMPLEX(-1,1); C2 :- NEW COMPLEX(1,-1); C1.Add(C2);
OOP - Klassenhierarchie
Geometrisches ObjektFarbe, Zeichne,...
Lineares Objekt 2D-Objekt 3D-Objekt
Beispiel: Türme von Hanoi1 Turm ti: Bausteine 1 - i2... n-1n
(1) (2) (3)
ReihenberechnungEingabe x,
Anfangswerte fürSummand T undSumme S
Berechnung S, TAbbruchtest p(T,S)nicht erfüllt
erfülltAusgabe
Reihenberechnung für sin x
Eingabe x,
I:=1; T:=x; S:=0;xq:=-x*x
|T|< Ausgabe S erfülltnicht erfüllt
S:=S+T;T:=T*xq/((I+1)*(I+2));I:=I+2
Vollständige Induktion Vor.: p:N0 Boolean (Prädikat), N0 = {0,1,..} Induktionsanfang: Zu beweisen:
p(0) = WAHR (kürzer: p(0)) Induktionsvoraussetzung: Für alle n N0
ist zu beweisen: p(n) = WAHR p(n+1)= WAHR
Induktionsschluss: Für alle n N0 gilt p(n) = WAHR.
Allgemeine Induktion Vor.: p: M Boolean, M induktiv definiert Induktionsanfang: Für die Basiselemente
xM ist zu beweisen p(x) = WAHR. Induktionsvoraussetzung: Für alle
Konstruktoren C und alle Elemente x1,...,xnM ist zu beweisen: p(xi) = WAHR, i=1,...,n p(C(x1,...,xn)) = WAHR
Induktionsschluss: Für alle Elemente xM gilt p(x) = WAHR.
Struktogramm - Hornerschema
i := 1;k := a1
i= 2, n+1k := k * x + ai
Kantorovič-Baum für Polynome
a1 xa2 *+ xa3 *+ x...an+1
+
Labyrinth - Beispiel1 2 3 4 5 6 7
1234567
Polynom: a1x4 + a2x3 + a3x2 + a4x + a5
a4 x x* *
a5 a3 x+ * *a2 x+ * *a1
+ *+
Paralleles Sortieren – Beispiel
Jochen Karin Franz Bernd Sepp Jim Maria Pos
Jochen 1 0 1 1 0 1 0 4Karin 1 1 1 1 0 1 0 5Franz 0 0 1 1 0 0 0 2Bernd 0 0 0 1 0 0 0 1Sepp 1 1 1 1 1 1 1 7Jim 0 0 1 1 0 1 0 3Maria 1 1 1 1 0 1 1 6
Korrektheit
Intuitive Vorstellungen Formal spezifizierteüber Eigenschaften Eigenschaften derder Software Software
Durch SoftwarerealisierteEigenschaften
Entwicklung von „funktionstreuer“ Software Korrekte Software:
a) Anwendung korrekter Werkzeuge auf Spezifikationb) Verifikation nach Softwareentwicklungc) Softwareentwicklung gekoppelt mit Beweisverfahren
Softwareteste zur Fehlerentdeckung (auch fehlende Fälle)
Simulation bei Echtzeitsoftware
Aussage zu TestenEs gibt keinen Algorithmus, der für ein
beliebiges Programm eine solche Testdatenmenge erzeugen könnte, dass ein korrekter Test für die Testdaten auch die Korrektheit für beliebige andere Daten garantieren würde.
(Beweis durch Rekursionssatz)
TestmethodenKriterium MethodenArt des Test- Durchsicht von Test lauffähiger Program-objekts Dokumenten me durch AusführungArt der Test- statisch dynamisch (Abarbeitungausführung (Inspektion) mit Testdaten)Kenntnisse Strukturtest Funktionstest
(Strukturüber Test- (bekannte unbekannt)objekt Struktur)Komponen- Modultest (einzelner Modul)tenart Integrationstest (Modulverbindung)
Systemtest (Gesamtsystem mit BS)
Auswahl von Testdaten – Programmbeispiel
0 (A>1) (B=0)ja nein1 X:=X/A 2
3 (A=2) (X>1)ja nein4 X:=X+1 5
6
Äquivalenzmethode
Bedingung Normalfälle Fehlerfälle
Daten aus 1 (im Intervall) 2 („vor“ undIntervall „hinter“ Intervall)
Daten sind 1 (erlaubte 2 (zu kleine und zuAnzahl Anzahl) große Anzahl)
Daten einer 1 (aus Menge) 1 (nicht aus Menge)Menge
Vor- und Nachteile von Testmethoden Funktionales Testen:
+ unabhängig von der Implementation+ Entwicklung der Testfälle parallel zur Codierung- Redundanz in den Testdaten möglich, aber nicht ausschließbar- evtl. werden Programmteile nicht getestet- Definition von Überdeckungsmaßen schwierig
Vor- und Nachteile von Testmethoden - Fortsetzung Strukturelles Testen:
+ wenig Redundanz in den Testdaten+ alle Programmteile werden erreicht- Testdatenauswahl erst nach Codierung möglich- ausschließlicher Test des programmierten Verhaltens
Ein- und Ausgabeverhalten – Beispiel{x0y0} P {x=q*y+r0ry}
Programm Eigenschaften Voraussetzung: x 0, y > 0, x,y ganzzahlig
q := 0; r := x; r 0 , y > 0, x = q*y + r
WHILE r y DO r y, y > 0, r 0, x = q*y + rr := r - y; q := q + 1 r 0, y > 0, x = q*y + rOD; Nach der Schleife: x = q*y + r, 0 r < y
Korrektheit {Q} P {R} bedeutet: Wenn die Aussage Q vor der Abarbeitung des
Teilprogrammes P wahr ist und die Abarbeitung von P terminiert, dann ist die Aussage R nach der Abarbeitung wahr (partielle Korrektheit).
oder Wenn die Aussage Q vor der Abarbeitung des
Teilprogrammes P wahr ist, dann terminiert die Abarbeitung von P und die Aussage R ist wahr (totale Korrektheit).
Axiome und Schlussregeln (Auszug) Axiom für die Wertzuweisung V := E (V Variable, E Ausdruck):
{P’} V := E {P} ,wobei P’ aus P durch Ersetzen der
nichtquantifizierten Auftreten von V durch E entsteht (P’ ist die schwächste Vorbedingung)
Axiome und Schlussregeln (Auszug) Verkettungsregel
{P} A1 {Q}, {Q} A2 {R}{P} A1; A2 {R}
Regel für die while-Anweisung{PB} A {P}
{P} while B do A od {P not B}
Axiome und Schlussregeln (Auszug) Implikationsregeln
{P} S {Q}, Q R{P} S {R}
P R, {R} S {Q}{P} S {Q}
PfadformelnE F p E G p
p
p
p p
Pfadformeln (Fortsetzung)A F p A G p
p
p p p
p p p p
p p
Model Checking – Railroad (1)
X
Train Gate
A I O E
Controller
Z
Ya
l, r
e
D1 D2 D3
X, Y, Z..................clocks D1.......................distance between A and IA, I, O, E ..............sensors D2.......................distance between I and Oa, l, r, e..................signals D3.......................distance between O and EV............................speed of the train
Model Checking – Railroad (2)Train automaton
X:=0
aX<5 X>2d3=D3/V e i X=D1/V
o
d2=D2/V
0 10
3 2
Model Checking – Railroad (3)Gate automaton
Y:=0
lY>1 and Y<1Y<2 u d
r
Y:=0
0 10
3 2
Model Checking – Railroad (4)Controller automaton
Z:=0
a
Z<1 r l Z=1
e
Z:=0
0 10
3 2
Model Checking – Railroad (5)Beispiellauf (Zugautomat):
a i o e<0, 0> ----> <1, 0> ----> <2, 2.5> ----> <3, 3> ----><0, 4> 10 12.5 13 14
a i o e----> <1, 0> ----><2, 2.5> ----> <3, 3> ----> <0, 4>20 22.5 23 24
Betrachtungsebenen von Datenstrukturen Datenstrukturen als abstrakte Objekte:
Darstellung von Eigenschaften und Wirkungsweise von Operationen
Konkrete Repräsentation Implementation in höherer
Programmiersprache Implementation in Maschinensprache
Vorteile der Abstraktion Konzentration auf Wesentliches Unabhängigkeit von Repräsentation und
Programmiersprache Austauschbarkeit von Implementationen
bei gleicher Schnittstelle Wiederverwendbarkeit der
Implementationen Nutzerfreundlichkeit durch Verwendung
des Problemniveaus
Algebraische Vorgehensweise der Softwareentwicklung
Anforderungsdefinition (informal)
Formalisierung Test, Plausibilität Algebraische Spezifikation (Prototyping)
Verfeinerung Verifikation Algorithmische Spezifikation
TransformationImperatives Programm
Algebra ganzer Zahlen Trägermenge der Algebra: = {...,-2,-1,0,1,2,...} Operationen der Algebra: Addition, Subtraktion,
Multiplikation, Division, Vergleiche Funktionalität (Profil) der Operationen: _+_: x _*_: x _/_: x _-_: x _<_: x ( steht für Boolean) ...
Algebra ganzer Zahlen - FortsetzungEigenschaften der Operationen: Addition, Multiplikation: kommutativ, assoziativ,
distributiv a + b = b + a a * b = b * a (a + b) + c = a + (b + c) (a * b) * c = a * (b * c)
(a + b) * c = (a * c) + (b * c) a,b,c Subtraktion als Umkehrung zur Addition
...
ADT Ganze Zahlen (Ganz) Datensorten: INT Operationssymbole: + - pred succ 0 (für spätere Operationen Addition, Subtraktion,
Vorgänger, Nachfolger, Konstante 0) Funktionalität:_+_: INT x INT INT _-_: INT x INT INT 0 : INT Signatur (Syntax)pred: INT INTsucc: INT INT
ADT Ganze Zahlen (Ganz) - Fortsetzungpred(succ(x)) = xsucc(pred(x)) = x Termgleichungen x + 0 = x (Semantik) x + succ(y) = succ(x + y) x + pred(y) = pred(x + y)
x - 0 = x x - succ(y) = pred(x - y) x - pred(y) = succ(x - y) x + y = y + x
Algebra Ganze Binärzahlen Sorte: INT
Trägermenge: {...,-11,-10,-1,0,1,10,11,...} Operator: +
Operation: +B Addition von Binärzahlen Operator: succ
Operation: +B 1 Operator: pred
Operation: -B 1
Termalgebra Sorte: INT
Trägermenge: alle Terme Operator: +
Operation: +T „Addition“ von Termen, d.h. t1 +T t2 = t1 + t2
Operator: succOperation: succT(t) = succ(t)
Operator: predOperation: predT(t) = pred(t)
Eigenschaften von TermgleichungenNotation: - X: t1 = t2 bezeichnet eine
Termgleichung mit der Variablenmenge X - x: s bezeichnet eine Variable der
Sorte sEigenschaften: Reflexivität: X: t = t Symmetrie: X: t1 = t2 X: t1 = t2 Transitivität: X1: t1 = t2, X2: t2 = t3
X1 X2: t1 = t3
Eigenschaften von Termgleichungen - Fortsetzung Substituierbarkeit: X1 {xs}: t1 = t2, X2: t3 = t4,
xs: S, t3 Ts, t4 Ts X1 X2: t5 = t6, t5 = t1[xs/t3], t6 = t1[xs/t4]
Abstraktion: X: t1 = t2, xs: S, xs X X {xs}: t1 = t2
Konkretisierung: X {xs}: t1 = t2, t1 ...xs... t2,Menge der variablenfreien Terme der Sorte s ist nicht leer X: t1 = t2
Strukturelle InduktionVoraussetzungen: Signatur mit Sortenmenge S, p Prädikat
auf den Termen von Induktionsschritte:Basis: Beweis für p(t) = WAHR für alle nullstelligen
Operationssymbole und VariablenSchritt: Beweis für
Für alle Operationssymbole , alle Terme t1,...,tn und (t1,...,tn) gilt: p(ti) = WAHR, i = 1,...,n p((t1,...,tn)) = WAHR
Schlussfolgerung: p(t) = WAHR für alle Terme t
Definition eines abstrakten Datentyps Einführung von Sorten Einführung von Operationssymbolen Definition der Funktionalität der
Operationssymbole Definition der Eigenschaften der Operationen
(Termgleichungen, Termersetzungsregeln) Schnelles Prototyping Umsetzung (Implementation) in höhere
Programmiersprache mit Verifikation
Modulares Programmieren, objektorientiertes Programmieren und Theorie der Algebren im VergleichModulares Programmieren- Datenkapsel:
Daten – Operationen – Import/Export- Abstrakter Datentyp:
Datentyp – Operationen – Import/ExportBeschreibung durch Definitionsmodul (Schnittstelle) und Implementationsmodul
Modulares Programmieren, objektorientiertes Programmieren und Theorie der Algebren im Vergleich (Forts.)Objektorientiertes Programmieren- Objekt:
Daten (Attribute, Instanzvariablen) – Operationen (Methoden)
- Klasse (Objektbeschreibung):Datentypen – Operationen- VererbungBeschreibung durch Schnittstelle und Implementation
Modulares Programmieren, objektorientiertes Programmieren und Theorie der Algebren im Vergleich (Forts.)Theorie der Algebren- Algebra:
Trägermengen – Operationen – Import/Export
- Abstrakter Datentyp:Signatur (Sorten, Operationssymbole, Funktionalität) – Operationseigenschaften (Termgleichungen) – Import/Export
Fehlerbehandlung - BeispielDatensorte: NatOperationssymbole und ihre
Funktionalität:zero: Natsucc: Nat Natpred: Nat Natadd: Nat x Nat Natmult: Nat x Nat Nat
Fehlerbehandlung – Beispiel (Forts.) Termgleichungen: pred(succ(x)) = x add(zero, x) = x add(succ(x), y) = succ(add(x, y)) mult(zero, x) = zeromult(succ(x), y) = add(y, mult(x, y))
Fehlerbehandlung – Beispiel (Forts.)==> Ergänzung der Spezifikation:error: Nat succ(error) = error pred(error) = error add(error, x) = error add(x, error) = errormult(error, x) = errormult(x, error) = error
pred(zero) = error
Fehlerbehandlung – Beispiel (Forts.)Operationssymbole:
zero: Natsucc: Nat Natpred: Nat Natadd: Nat x Nat Naterror: Natsafe: Nat Bool
Fehlerbehandlung – Beispiel (Forts.) Termgleichungen: succ(error) = error safe(zero) = true safe(succ(x)) = safe(x) safe(error) = false pred(error) = error pred(succ(x)) = x pred(zero) = error
Fehlerbehandlung – Beispiel (Forts.) add(zero, x) = xadd(succ(x), y) = succ(add(x, y)) add(error, x) = error mult(zero, x) = if safe(x) then zero else
error fimult(succ(x), y) = add(y, mult(x, y)) mult(error) = error
Spezifikation eines ADTtype <Name> ==<Exportliste>
based on <Importliste>sorts <Namenliste>decl <Variablenliste>constructors <kanonische Operationssymbole mit Funktionalität>operations <restliche Operationssymbole mit Funktionalität>axioms <Termgleichungen>
end of type
Beispiel – ADT BOOLtype BOOL == bool, T, F, ,
based on sorts booldecl B:bool, B1:boolconstructors T: bool; F : booloperations : bool bool; __: bool x bool bool axioms T = F; (B)) = B; T B = B;F B = F; B B1 = B1 B
end of type
Beispiel – ADT BOOLAbgeleitete Operationen
B B1 = (B B1) B B1 = B B1 B B1 = (B B1) (B1 B)
Transformation arithmetischer Ausdrücke in IPN
Voraussetzungen: zu transformierender Ausdruck wird mit einem Endezeichen beendet und Operatoren haben Prioritäten
„(„ wird im Keller abgelegt „)“ entkellert alle Operatoren bis
einschließlich der zugehörigen öffnenden Klammer mit anschließender Beseitigung beider Klammern und Einfügen der Operatoren in die IPN
Transformation arithmetischer Ausdrücke in IPN (Fortsetzung)
Variablen und Konstanten gehen sofort in die IPN über
Operatoren entkellern alle Operatoren mit größerer oder gleicher Priorität und werden anschließend gekellert; die entkellerten Operatoren werden der IPN hinzugefügt
Entkellerung aller Operatoren durch Endezeichen „!“ mit Löschen des Zeichens
Transformation arithmetischer Ausdrücke in IPN (Fortsetzung)
Prioritäten:
1 2 3 4 5 = 6 + -7 / * 8 **
Abstrakter Datentyp Keller – Signatur
erelement init push element stack erstack
top pop
Keller – Eigenschaften der Operationen
a) Aus einem nichtleeren Keller kann nur das zuletzt hinzugefügte Element entfernt werden.
b) Von einem nichtleeren Keller kann nur das zuletzt hinzugefügte Element gelesen werden.
c) Im Falle eines leeren Kellers kann weder ein Element entfernt noch gelesen werden. In beiden Fällen erfolgt eine Fehlermeldung.
Kellerspezifikationtype Keller1 == stack, push, pop, top, init, erstackbased on ELEMENTsorts stackdecl e: element, s: stack;constructors init: stack;
push: element x stack stack; erstack: stack
operations pop: stack stack; top: stack element
Kellerspezifikation (Fortsetzung)axioms pop(push(e, s)) = s
top(push(e, s)) = epop(init) = erstacktop(init) = erelement
end of type
Abstrakter Datentyp Keller (erweitert) – Signatur
maxerelement init nat push over lng
= element stack erstack empty top pop bool full
Keller – Eigenschaften der neuen Operationen a) lng gibt die Anzahl der Elemente eines
Kellers an, wobei der leere Keller die Anzahl 0 hat und durch jedes in den Keller abgespeicherte Element die Anzahl um 1 vergrößert wird.
b) Ein Keller ist leer, wenn die Anzahl seiner Elemente 0 ist. Ein Keller ist gefüllt, wenn die Anzahl eine vorgegebene Größe max erreicht hat.
Keller – Eigenschaften der neuen Operationen (Fortsetzung) c) Der Initialisierungskeller ist leer. d) Die Abspeicherung eines Elements in
einen vollen Keller führt zu einem Fehler.
Kellerspezifikation (erweitert)type Keller2 == stack, push, pop, top, init, erstack,
full, empty, lng, max, overbased on NAT, BOOL, ELEMENTsorts stackdecl e:element, s:stack constructors init: stack; push: element x stack stack;
erstack: stack; over: stack
Kellerspezifikation (erweitert) - Fortsetzungoperations pop: stack stack; top: stack element; lng: stack nat; max: nat; empty: stack bool; full: stack bool; _=_: nat x nat bool
Kellerspezifikation (erweitert) - Fortsetzung
axioms push(e, s) = if full(s) then over else push(e, s) fi pop(push(e, s)) = s top(push(e, s)) = e pop(init) = erstack top(init) = erelement lng(init) = 0 lng(push(e,s)) = lng(s) + 1 empty(init) = Tempty(push(e, s)) = F full(s) = (lng(s) = max)end of type
Abstrakter Datentyp Schlange – Signatur
maxerelement init nat over insert length = element queue erqueue qempty front remove bool qfull
Schlange – Eigenschaften der Operationen Eine nur initialisierte Schlange ist leer
und hat die Länge 0. Mit jedem hinzugefügten Element wächst die Länge um 1.
Eine Schlange mit mindestens 1 Element ist nicht leer. Eine volle Schlange hat die maximale Länge erreicht. Es kann dann kein Element hinzugefügt werden.
Schlange – Eigenschaften der Operationen (Fortsetzung) Einer leeren Schlange kann kein
Element entnommen werden. Elemente werden bei einer nichtleeren
Schlange vorn weggenommen. Das Anfügen von Elementen geschieht am Ende der Schlange.
Gelesen werden kann grundsätzlich nur das erste Element und das nur bei nichtleeren Schlangen.
Schlange - Spezifikationtype Schlange == queue, front, insert, remove, init,
erqueue, over, qempty, qfull, lengthbased on NAT, BOOL, ELEMENTsorts queuedecl e:element, q:queue
constructors init: queue;
erqueue: queue; over: queue;
insert: element x queue queue
Schlange – Spezifikation (Forts.)
operations front: queue element; remove: queue queue; length: queue nat; max: nat; qempty: queue bool; qfull: queue bool; _=_: nat x nat bool
axioms length(init) = 0 length(insert(e, q)) = length(q) + 1
Schlange – Spezifikation (Forts.) qempty(init) = Tqempty(insert(e, q)) = F qfull(q) = (length(q) = max) front(init) = erelement front(insert(e, q)) = if qempty(q) then e else front(q) fi insert(e, q) = if qfull(q) then over else insert(e, q) fi remove(init) = erqueueremove(insert(e, q)) = if qempty(q) then init else insert(e, remove(q)) fiend of type
Abstrakter Datentyp Tabelle – Signaturisdef boolkey
read erelement deleteadd, update fullelement emptytable =sizeinit over ertable nat
max
Abstrakter Datentyp Tabelle – Signatur
(andere Variante – unvoll.)
element add
mentry entry table
key
Tabelle – Eigenschaften der Operationen - Eine nur initialisierte Tabelle ist leer und
hat den Umfang 0. Mit jeder Eintragung wächst ihr Umfang um 1.
- Die Aktualisierung einer leeren Tabelle ist ohne Effekt. Hingegen ist das Lesen einer Eintragung aus einer leeren Tabelle ein Fehler.
- In eine gefüllte Tabelle kann keine weitere Eintragung vorgenommen werden.
Tabelle - Spezifikationtype TABLE == key, table, read, add, update,
delete, isdef, empty, full,init, over, ertable, sizebased on NAT, ELEMENT, BOOLsorts key, tabledecl k:key, l:key,t:table,e:element,f:element
constructors init: table; over: table; ertable: table; add: table x key x element table
Tabelle – Spezifikation (Forts.)operations read: table x key element; update: table x key x element table;
delete: table x key table; __: key x key bool; isdef: table x key bool; empty: table bool; full: table bool; _=_: nat x nat bool; size: table nat; max: nat
Tabelle – Spezifikation (Forts.) axioms delete(init, k) = ertabledelete(add(t, k, e), l) = if k l then t else add(delete(t, l), k, e) fi isdef(init, k) = F isdef(add(t, k, e), l) = if k l then T else isdef(t, l) fi add(t, k, e) = if full(t) then over else if isdef(t, k) then ertable else add(t, k, e) fi fi
Tabelle – Spezifikation (Forts.) update(init, k, e) = initupdate(add(t, k, e), l, f) = if k l then add(t, k, f) else add(update(t, l, f), k, e) fi read(init, k) = erelement read(add(t, k, e), l) = if k l then e else read(t, l) fi size(init) = 0 size(add(t, k, e) = 1 + size(t) empty(t) = (size(t) = 0) full(t) = (size(t) = max)end of type
Liste – informale Beschreibung Modellierung eines Karteikastens (Folge
von Karteikarten) Kennzeichnung der bearbeiteten Karte
durch Einschub einer Spezialkarte (Markierungskarte) und damit Unterteilung der Karten in Karten des vorderen und hinteren Teils des Karteikastens
Einfügen und Entfernen von Karten stets vor der Markierungskarte
Liste – informale Beschreibung (Fortsetzung) Verschiebung der Markierungskarte um 1
Position nach vorn oder hinten oder nach ganz vorn bzw. ganz hinten
Lesen der Karte vor der Markierungskarte hinten Markierungskarte vorn
max mlist erlist over nat
erelement read init
element list = insert length delete, first, boollast, next, prev empty, full, atbeg, atend
Liste - Signatur
Liste - Operationen insert Einfügen einer Karte vor der
Markierungskarte delete Entfernen der Karte vor der
Markierungskarte read Lesen der Karte vor der
Markierungskarte init Initialisierung der Kartei (nur
Markierungskarte vorhanden)
Liste – Operationen (Forts.) first,last Setzen der Markierungskarte
auf Anfang bzw. Endenext, prev 1 Karte nach hinten bzw. vorn
length Anzahl der Karteikarten max maximale Kartenanzahl empty, full Ist der Karteikasten leer bzw.
voll? atbeg,atend Ist die Markierungskarte am
Anfang bzw. Ende des Kastens?
Liste – Eigenschaften von Operationen (Auszug) Befindet sich die Markierungskarte am
Anfang des Kastens, so ist weder Lesen noch das Entfernen einer Karte möglich. Die Anwendung der prev-Operation ist dann nicht gestattet und die first-Operation hat keine Wirkung.
Steht die Markierungskarte am Ende des Kastens, dann ist die next-Operation nicht erlaubt und die last-Operation ohne Wirkung.
Liste - Signaturänderung
element
cons seq listclist
nil
Beispiel – kanonischer Terma b & c d
Kanonischer Term – alte Formprev(prev(insert(d, insert(c, insert(b, insert(a, init))))))
Kanonischer Term – neue Formclist(cons(b, cons(a, nil)),
cons(c, cons(d, nil)))
Liste - Spezifikationtype LIST == list, read, insert, mlist, init, erlist,
over, delete, first, last, next, prev, length, empty, full, atbeg, atend
based on ELEMENT, NAT, BOOLsorts list, seqdecl e:element, f:seq, b:seq, l:list
constructors mlist: list; erlist: list; over: list; nil: seq;
Liste – Spezifikation (Forts.) cons: element x seq seq; clist: seq x seq list
operations init: list; insert: element x list list;delete: list list; first: list list; last: list list; next: list list; prev: list list;
Liste – Spezifikation (Forts.) read: list element;length: list nat;empty: list bool; full: list bool; atbeg: list bool; atend: list bool; max: nat; _=_: nat x nat bool
Liste – Spezifikation (Forts.)axioms init = clist(nil, nil)
insert(e, clist(f, b)) = if full(clist(f, b)) then over
else clist(cons(e, f), b) fi delete(clist(nil, b)) = erlistdelete(clist(cons(e, f), b)) = clist(f, b) read(clist(nil, b)) = erelementread(clist(cons(e, f), b)) = e
Liste – Spezifikation (Forts.) last(clist(f, nil)) = clist(f, nil)last(clist(f, cons(e, b))) = last(clist(cons(e, f), b)) first(clist(nil, b)) = clist(nil, b)first(clist(cons(e, f), b)) = first(clist(f, cons(e, b))) next(clist(f, nil)) = mlistnext(clist(f, cons(e, b))) = clist(cons(e, f), b) prev(clist(nil, b)) = mlist prev(clist(cons(e, f), b) = clist(f, cons(e, b)) length(init) = 0
Liste – Spezifikation (Forts.) length(clist(cons(e, f), b)) = 1 + length(clist(f, b))length(clist(nil, cons(e, b))) = 1 + length(clist(nil, b)) empty(l) = (length(l) = 0) full(l) = (length(l) = max) atbeg(clist(nil, b)) = T atbeg(clist(cons(e, f), b)) = F atend(clist(f, nil)) = T atend(clist(f, cons(e, b))) = Fend of type
BaumdurchlaufalgorithmenInorderPROCEDURE inorder(t: IN tree);IF NOT null(t) THEN BEGIN inorder(left(t));
write(root(t)); inorder(right(t)) END
FIEND inorder
BaumdurchlaufalgorithmenPräorderPROCEDURE preorder(t: IN tree);IF NOT null(t) THEN BEGIN write(root(t));
preorder(left(t)); preorder(right(t)) END
FIEND preorder
BaumdurchlaufalgorithmenPostorderPROCEDURE postorder(t: IN tree);IF NOT null(t) THEN BEGIN postorder(left(t));
postorder(right(t)); write(root(t)) END
FIEND postorder
TreesortPROCEDURE treesort(x:IN array[1..n] of Elem);{x ist die zu sortierende Folge}VAR t, q, help, tree, y, z:Elem; i:1..n;{t Gesamtbaum; help und q sind Unterbäume zur
Bestimmung der Stelle, wo ein neuer Knoten angehangen werden soll}
t := leaf(x[1]); {erstes Element wird zum Baum}FOR i:= 2 TO n DO{weitere Elemente werden in den Baum einsortiert}
BEGIN y := x[i];{einzusortierendes Element}help := t;
Treesort (Forts.)WHILE NOT null(help) DO{Abwärtshangeln im Baum}
q := help; {Merken des Ausgangsknotens} z := root(help); {Bestimmung des Elements an der Wurzel von help} IF keyof(y) < keyof(z) THEN help := left(help) ELSE help := right(help) FI {Fortsetzung im linken oder rechten Unterbaum}OD;
Treesort (Forts.)IF keyof(y) < keyof(z) THEN setleft(q, leaf(y)) ELSE setright(q, leaf(y)) FI {Anhängen eines Elements} OD; inorder(t);
{Durchlauf durch t in Inorder}END treesort
Suche in einem treesort-BaumFUNCTION find(t:IN tree; k:IN key): Boolean;VAR p:tree; found:Boolean; x:Elem;found := FALSE; p := t; WHILE (NOT null(p)) AND (NOT found) DO root(p, x); IF k = keyof(x) THEN found := true ELSE IF k < keyof(x) THEN p := left(p) ELSE p := right(p) FI FI OD; find := foundEND find
Binärbaum - Signatur max
setleft,setright nat leaf left, right noden = elem tree null, maxtree root
over, ertree, empty bool cons setroot
Binärbaum - Operationenroot liefert Element der Wurzelsetroot, setright, setleft Aktualisierung der
Baum- komponentennoden liefert Knotenanzahl eines Baumesleft (right) linker (rechter) Unterbaum wird
geliefertcons Konstruktion eines Baumes aus
Wurzelelement, linkem und rechtem Unterbaum
Binärbaum – Operationen (Forts.)leaf ein Element wird zu einem Baum,
bestehend aus einem Blatt (wird eigentlich nicht benötigt, ergibt aber kürzere Darstellungen)
null Test auf leeren Baummaxtree Test auf maximale
Knotenanzahlempty Bauminitialisierung
Binärbaum - Spezifikationtype B-TREE == tree, root, leaf, left, right, empty, cons,
over, ertree, setroot, setleft, setright, noden, null, maxtree
based on NAT, BOOL, ELEMsorts treedecl w:elem, r:tree, l:tree, e:elem, t:tree
constructors empty: tree; over: tree; ertree: tree; cons: elem x tree x tree tree;
Binärbaum – Spezifikation (Forts.)
leaf: treeoperations root: tree elem;
left: tree tree; right: tree tree; setleft: tree x tree tree; setright: tree x tree tree; setroot: tree x elem tree; null: tree bool; maxtree: tree bool;
Binärbaum – Spezifikation (Forts.)
noden: tree nat; max: nat; _=_: nat x nat bool
axioms root(empty) = erelem right(empty) = ertree left(empty) = ertree
leaf(w) = cons(w, empty, empty) root(cons(w, l, r)) = w
Binärbaum – Spezifikation (Forts.) left(cons(w, l, r)) = l right(cons(w, l, r)) = r setleft(empty, t) = ertree setright(empty, t) = ertree setroot(empty, e) = ertree setleft(cons(w, l, r), t) = cons(w, t, r) setright(cons(w, l, r), t) = cons(w, l, t) setroot(cons(w, l, r), e) = cons(e, l, r)
Binärbaum – Spezifikation (Forts.) null(t) = (noden(t) = 0) noden(empty) = 0 noden(leaf(w)) = 1noden(cons(w, l, r)) = 1 + noden(l) + noden(r) maxtree(t) = (noden(t) = max) cons(w, l, r) = if noden(cons(w, l, r)) >
max then over else cons(w, l, r) fi
end of type
Beispielbaum
T /
T1 + / T3
a T2 * a c
b c
right(T) = cons(/, leaf(a), leaf(c))left(left(T)) = left(
cons(+, leaf(a), cons(*, leaf(b), leaf(c)))) = leaf(a)
Beispielbaum – ImplementierungIndex Wert lr rr
1 / 2 4 2 + 5 3 3 * 6 7 4 / 8 9 5 a 6 b 7 c 8 a 9 c
Beispiel – FreispeicherketteIndex Wert lr rr
1 2 6 besetzter Speicher 3 4 2 5 6 7 Anfang der Frei- 7 9 speicherkette 8 9 nil
Fragen zu Algorithmen Existiert (im mathematischen Sinn) zu einer
gegebenen Aufgabe ein Lösungsalgorithmus? Welche Ressourcen benötigt er und ist er
überhaupt durchführbar (Komplexität)? Wie beeinflusst ein gegebenes
Rechnersystem die effiziente Ausführung eines Algorithmus?
In welcher Programmiersprache kann der Algorithmus am besten notiert werden?
Church-Turing-These Alle (existierenden) „vernünftigen“
Definitionen des Begriffs „Algorithmus“ sind gleichwertig. (Formale Beweise der Äquivalenz der Formalisierungen existieren.)
Jede (neue) „vernünftige“ Definition des Begriffs ist gleichwertig mit den obigen.
Bemerkungen Intuitive Vorstellungen über Algorithmen lassen
sich durch Turingmaschine, Markovalgorithmen usw. formalisieren. Ein Beweis der Äquivalenz ist allerdings nicht möglich.
Die Formalisierungen des Algorithmenbegriffs kommen ohne den Rechnerbegriff aus. Demzufolge muss ein Algorithmus prinzipiell auf jedem Rechner ausführbar sein.
Algorithmen können in Software oder Hardware umgesetzt werden.
Fermatsche VermutungStoppt der nachfolgende Algorithmus?
Eingabe n;Für a = 1, 2, 3,...
Für b = 1, 2,..., aFür c = 2, 3,..., a + b
Wenn an + bn = cn, dann gib a, b, c und n aus und stoppe.
TotalitätsproblemGibt es einen Algorithmus, der für ein
beliebiges Programm P feststellen kann, ob P für alle Eingaben D stoppt oder nicht stoppt?
ÄquivalenzproblemGibt es einen Algorithmus, der für
beliebige zwei Programme feststellen kann, ob sie die gleiche Aufgabe lösen.
Beispiel: Suchproblem Gegeben:
endliche Folge F von Elementen einer Menge SF = A1,..., An, Element a S
Gesucht: Position von a in der FolgeAlgorithmus:FUNCTION LinSu(F: IN ARRAY [1..n] OF real; a: IN
real): natural;FOR i := 1 TO n DO IF a = F[i] THEN RETURN(i) FI OD;RETURN(0)END LinSu
O/Ω/Θ-Notation g(n) = O(f(n)) bedeutet: Es existieren eine
positive Konstante M und eine Konstante n0, so dass (n n0) |g(n)| M*|f(n)|.
g(n) = (f(n)) bedeutet: Es existieren eine positive Konstante M und eine Konstante n0, so dass (n n0) |g(n)| M*|f(n)|.
g(n) = (f(n)) bedeutet: Es existieren eine positive Konstante M und eine Konstante n0, so dass (n n0) |f(n)|/M |g(n)| M*|f(n)|.
Rechenregeln für die O-Notation
f(n) = O(f(n)) O(O(f(n))) = O(f(n)) c*O(f(n)) = O(f(n))O(f(n))*O(g(n)) = O(f(n)*g(n)) O(f(n)*g(n)) = O(f(n))*O(g(n)) O(f(n)*g(n)) = f(n)*O(g(n))
Beispiel Eine Operation benötige 0,000001 sec Anzahl der Asymptotischer Zeitbedarf bei Eingabedaten Komplexität
n log2 n n n2 2n
10 0,000003 0,00001 0,0001 0,001sec sec sec sec 100 0,000007 0,0001 0,01 1014
sec sec sec Jhd. 1000 0,00001 0,001 1 sec sec sec 10000 0,000013 0,01 1,7sec sec min 100000 0,000017 0,1 2,8sec sec h
Häufig auftretende Komplexitäten(in wachsender Reihenfolge)
O(1) konstant O(log n) logarithmisch
O(n) O(n) linearO(n*log n) O(n2) quadratischO(nk), k konstant polynomialO(kn), k konstant exponentiellO(n*2n) O(n!)
Menge M mit Halbordnung (partieller Ordnung) R:
R M x M, R binäre Relation auf M, wobei gilt R ist reflexiv: (x M) (xRx) R ist transitiv: (x, y, z M)
(xRy yRz xRz) R ist antisymmetrisch: (x, y M)
(xRy yRx x = y)
R ist eine (totale) Ordnung, wenn zusätzlich gilt: (x, y M) (xRy yRx)
Sortierproblem:Gegeben: U Universum mit Ordnung R
M = {a1,..., an}, ai UGesucht: Permutation P = (p1,..., pn) von (1, ...,n), so dass apiRapi+1, i = 1,...,n-1
Beispiel:U = {0, 1, 2,...}, M = {5, 4, 8, 2} =
{a1,...,a4} P = (4, 2, 1, 3), da a4 a2 a1 a3
Grad der Unsortiertheit einer Menge:Anzahl der Inversionen der Menge
Inversion:M = {a1,..., an}(ai, aj), wobei ai > aj und i < jMaximale Anzahl: (n2 – n)/2
Beispiel:Im obigen Beispiel: (5, 4), (5, 2), (4, 2), (8,
2)
Klassifikation von Sortierverfahren:1. Nach der Art der Elemente:
- Elementsortierung- SchlüsselsortierungSchlüssel Assoziierte Information ElementArgument Wert Sortieren mit vollständiger Umspeicherung der Elemente oder nur mit Schlüsselumspeicherung (siehe auch Implementation des ADT Tabelle)
Stabile Sortierung: relative Ordnung zwischen zwei gleichen Schlüsseln bleibt erhalten
Beispiel:Eine alphabetisch geordnete Liste von Prüfungsnoten wird nach den Noten geordnet. Dann sind alle Namen zur gleichen Note immer noch in alphabetischer Reihenfolge.
2. Nach dem Speicher:- Innere Sortierverfahren: Sortieren auf dem Hauptspeicher- Externe Sortierverfahren: Sortieren von Daten auf externen Speichern unter Nutzung innerer Verfahren für kleine Datenportionen
3. Nach der Rechnerarchitektur:Sequentielles und paralleles Sortieren
4. Nach der zeitlichen Komplexität5. Nach den Methoden: adressenorientiert,
assoziativ, hybrid
Adressenorientiertes Sortieren
Adressenorientiertes SortierenGrundalgorithmus
Voraussetzung: U = {u1,..., um} Universum, M = {a1,..., an}, ai U, zu sortierende Menge Algorithmusschritte: 1) Initialisierung: Anlegen von m leeren Listen
(zugeordnet zu den Elementen des Universums) 2) Verteilung: Abarbeitung von M von links nach
rechts und Anhängen des Indexes i an die Liste j, wenn ai = uj.
3) Verkettung: Verbindung des Endes der i. Liste mit dem Anfang der (i+1). Liste ==> Indizes der Elemente der sortierten Folge bezogen auf ursprüngliche Folge
Adressenorientiertes SortierenBeispiel U = {0, 1, 2, 3, 4, 5, 6} = {u1,..., u7} M = {5, 4, 3, 4, 5, 0, 2, 1} = {a1,..., a8} Listen: Liste(Element)
1(0) 2(1) 3(2) 4(3) 5(4) 6(5) 7(6)
6 8 7 3 2 1
4 5 M sortiert: {a6, a8, a7, a3, a2, a4, a1, a5} = {0, 1, 2, 3, 4, 4, 5, 5}
Adressenorientiertes SortierenEigenschaftenKomplexität: Zeitlich:
- Typische Operationen: Einsortieren eines Elements in eine Liste (c1*n), Listen-verknüpfung (c2* (m – 1)) c3* (n + m) O(n+m) O(n)
Speicher: O(n*m) O(n)Stabilität: ja
Adressenorientiertes SortierenLexikographisches SortierenLexikographische Ordnung:U = {u1,..., un}, ui Zahlen gleicher Länge
bestehend aus den Ziffern 0, 1,..., m-1Dabei gilt: ui < uj, i < j, ui = a1...ak, uj = b1...bk l: (1 l k) (ar = br, r=1,...,l-1) (al < bl)
Eine analoge Definition gilt für Wörter.
Adressenorientiertes SortierenLexikographisches Sortieren Algorithmusschritte: 1) Initialisierung: Anlegen von m leeren Listen
(m Anzahl der Ziffern bzw. Buchstaben) 2) k Durchläufe:
i. Durchlauf: Verteilung: Zahlen (Wörter) des letzten
Durchlaufs werden gemäß i. Ziffer (Buchstaben) einer Zahl (eines Wortes) von rechts betrachtet in die Listen einsortiert
Verkettung: Verbindung des Endes der i. Liste mit dem Anfang der (i+1). Liste
Beispiel U = {affe, alf_, duo_, elch, esel, maus, tanz, tor_,
zart, zoo_} S = {zoo_, affe, tor_, maus, alf_} _ a e f l m o r s t
u zzoo_ affe maustor_alf_ alf_ zoo_ tor_ maus
affe maus affe alf_ zoo_
tor_ affe maus tor_ zoo_
alf_
Adressenorientiertes SortierenLexikographisches Sortieren
Komplexität: Zeitlich: O(k * (m + n)) O(n) Speicher: O(n * m) O(n)
Assoziatives Sortieren Prinzip: Vergleich der Elemente untereinander Grundmethode (rekursive Beschreibung):1. Analyse: Überführung des ursprünglichen
Sortierproblems in Sortierprobleme geringeren Umfangs
2. Rekursion: Lösung der kleineren Probleme gemäß 1.-3.3. Synthese: Zusammensetzung der Lösungen der
kleineren Probleme zur Lösung des Gesamtproblems
Assoziatives SortierenSortieren durch Einfügen (INSERTSORT) Algorithmus (rekursive Version): 1. Analyse: Zerlegung von M = {a1,..., an} in
M1 = {a1,..., an-1} und M2 ={an} 2. Rekursion: Sortieren von M1 nach 1. - 3. mit Ergebnis M1’ 3. Synthese: Einfügen von an an die richtige Stelle in M1’
Beispiel: Sortieren von M = {4, 5, 0, 2, 1}
Zerlegung{4, 5, 0, 2, 1}
{4, 5, 0, 2} {1} {0, 1, 2, 4, 5} {4, 5, 0} {2} {0, 2, 4, 5} {4, 5} {0} {0, 4, 5} {4} {5} {4, 5}
Einsortierung
Assoziatives SortierenSortieren durch Einfügen (INSERTSORT)Komplexität: Typische Operationen: Vergleich zweier
Elemente, Verschiebung eines Elements um 1 Platz
Zeitlich: O(n2) Speicher: O(n)
Sortieren durch Einfügen (INSERTSORT)Iterative Versionprocedure insertion(a : array of integer);var i, j, v: integer;begin
for i := 2 to N dobeginv := a[i]; j := i;while a[j – 1] > v dobegin a[j] := a[j – 1]; j := j – 1 end;a[j] := vend
end
Sortieren durch Einfügen (INSERTSORT)Iterative Version
Beispiel: a0 a1 a2 a3 a4 a5
- 4 5 0 2 1- 4- 4 5- 0 4 5- 0 2 4 5- 0 1 2 4 5
Sortieren durch Einfügen (INSERTSORT)Eigenschaften Wegen der quadratischen zeitlichen Komplexität ist
es ungeeignet für große Mengen, aber sehr wohl anwendbar für kleine.
Ist die zu sortierende Menge gut vorsortiert, dann sind auch große Mengen gut sortierbar (Annäherung an minimale Komplexität).
Es ist gut für on-line Sortierung geeignet. Der durch den Algorithmus zusätzlich benötigte
Speicherplatz ist unabhängig von der Größe der zu sortierenden Menge konstant.
Das Verfahren ist stabil.
Sortieren durch Einfügen (INSERTSORT)Verbesserungen Beginn der Suche der
Einfügungsstelle ca. von der Mitte der sortierten Menge an
Beginn des Aufbaues der sortierten Menge von der Mitte her
Sortieren durch Einfügen (INSERTSORT)VerbesserungenBeispiel: S = {4, 5, 0, 2, 1, 6}Aufbau der sortierten Menge:
4 54 5 00 4 5 20 2 4 5 10 1 2 4 5 60 1 2 4 5 6
Assoziatives SortierenSortieren durch Auswahl (SELECTSORT)Algorithmus (rekursive Version):1.M = {a1,..., an} wird zerlegt in M1 =
{a11,..., a1n-1} = M - M2 und M2 = {min(M)}
bzw. M2 = {max(M)}2.Sortieren von M1 nach den Schritten 1. -
3. mit der Ergebnismenge M1’3.M’ = M2 M1’ bzw. M’ = M1’ M2
Sortieren durch Auswahl (SELECTSORT)Rekursive VarianteBeispiel: Sortieren mit Minimum
{4, 5, 0, 2, 1}Zerlegung
{4, 5, 2, 1} {0} {0, 1, 2, 4, 5} {4, 5, 2} {1} {4, 5} {2} {5} {4} Aneinanderreihung
Sortieren durch Auswahl (SELECTSORT)Iterative VarianteBeispiel: M = {4, 5, 0, 2, 1} Schritt Sortierte Menge Restmenge 1 0 4 5 2
1 2 0 1 4 5 2 3 0 1 2 4 5 4 0 1 2 4 5 5 0 1 2 4 5
Assoziatives SortierenSortieren durch Vertauschen (BUBBLESORT)Prinzip:Vergleich von unmittelbar benachbarten
Elementen mit anschließender Vertauschung bei falscher Reihenfolge
Sortieren durch Vertauschen (BUBBLESORT)Beispiel: M = {4, 5, 0, 2, 1, 6} Vertauschungsschritte:
4 5 0 2 1 64 0 5 2 1 64 0 2 5 1 64 0 2 1 5 60 4 2 1 5 60 2 4 1 5 60 2 1 4 5 60 1 2 4 5 6
Sortieren durch Vertauschen (BUBBLESORT) Verbesserungen:1.Auslassen der Vergleiche von der Stelle
an, von der im letzten Durchlauf die letzte Vertauschung stattfand (Elemente sind bereits in richtiger Reihenfolge)
2.Vergleich mit alternierender Richtung und Verbesserung 1. (SHEAKSORT)
Sortieren durch Vertauschen (BUBBLESORT) 3. Idee von D. L. Shell (1959): i. Sortierschritt auf der Basis des
Vergleichs von Elementen, die hi Elemente voneinander entfernt liegen, wobei hi > hi+1, hk = 1
Empfehlung von Knuth: hi = 3*hi+1 + 1 (..., 40, 13, 4, 1)
Sortieren durch Vertauschen (BUBBLESORT)
Beispiel: SHELLSORT für {4, 5, 0, 2, 1, 6} Vergleich und Vertauschung mit h1 = 4 4 5 0 2 1 6 1 5 0 2 4 6
1 5 0 2 4 6
Vergleich und Vertauschung mit h2 = 2 1 5 0 2 4 6 0 5 1 2 4 6 0 2 1 5 4 6 Vergleich und Vertauschung mit h3 = 1 0 2 1 5 4 6 0 1 2 4 5 6
Assoziatives SortierenSortieren durch Mischen (MERGESORT)Algorithmus:1.M = {a1,..., an} wird zerlegt in M1 und
M2, die von gleicher Größe sein sollten2.Sortieren von M1 und M2 gemäß 1. - 3.;
Ergebnismengen M1’ und M2’3.Mischen der Mengen M1’ und M2’ zur
sortierten Menge unter Verwendung des nachfolgenden Algorithmus’
Assoziatives SortierenSortieren durch Mischen (MERGESORT)
Mischalgorithmus: Gegeben: Sortierte Mengen M1’ und M2’ Gesucht: Sortierte Menge M’ bestehend aus den
Elementen von M1’ und M2’ Schritte:Initialisierung von M’: M’ := Solange M1’ und M2’ beide nicht leer sind, führe aus: Übernahme des kleineren der beiden ersten Elemente von M1’ und M2’ nach M’ und Entfernung aus M1’ bzw. M2’. Ist M1’ oder M2’ leer, dann Übernahme der anderen
Menge nach M’.
Sortieren durch Mischen (MERGESORT)Beispiel: Zerlegung {4, 5, 0, 2, 1, 6} {4, 5, 0} {2, 1, 6}
{4, 5} {0} {2, 1} {6}
{4} {5} {2} {1}
Mischung:{0, 1, 2, 4, 5, 6}
{0, 4, 5} {1, 2, 6}
{4, 5} {0} {1, 2} {6}
Assoziatives SortierenQUICKSORTVerbesserung von MERGESORT zu QUICKSORT
(Hoare 1961):1. Auswahl eines Pivotelements P aus M = {a1,...,
an} und Zerlegung von M in zwei Mengen M1 und M2, wobei M1 alle Elemente aus M enthält, die kleiner als P sind.
2. Sortieren von M1 und M2 gemäß den Schritten 1. - 3. mit den Ergebnismengen M1’ und M2’
3. M’ = M1’ . {P} . M2’
Beispiel: M = {207, 095, 646, 198, 809, 376, 917, 534, 310}
Zerlegung{207, 095, 646, 198, 809, 376, 917, 534, 310}
{376}{207, 095, 198, 310} {646, 809, 917, 534}
{198} {646} {095} {207, 310} {534} {809, 917}
{207} {809}
{310} {917}
Verkettung
{095, 198, 207, 310, 376, 534, 646, 809, 917} {095, 198, 207, 310} {376} {534, 646,
809, 917}
{095} {198} {207, 310} {534} {646} {809, 917}
{207} {310} {809} {917}
Assoziatives SortierenSortieren durch Zählen (COUNTSORT)Prinzip: Zu jedem Element von M = {a1,..., an}
wird festgestellt, wie viel Elemente kleiner als dieses Element sind.
Die Anzahl der Elemente, die kleiner als ein gegebenes Element sind, gibt die Stellung des Elements in der sortierten Folge an.
Assoziatives SortierenSortieren durch Zählen (COUNTSORT)Beispiel:Menge M = {4, 5, 0, 1, 2, 6}Kleinere 3 4 0 1 2 5ElementeSortierte M´ = {0, 1, 2, 4, 5, 6}MengePosition 0 1 2 3 4 5
Assoziatives SortierenHeapsort
Vollständiger Binärbaum: Auf jedem Niveau, bis evtl. auf das
letzte, sind alle Knoten vorhanden. Auf dem letzten Niveau dürfen Knoten
nur am rechten Rand lückenlos fehlen.
Assoziatives SortierenHeapsortHeap:Vollständiger Binärbaum, wobei der
Schlüssel jeden Knotens größer oder gleich den Schlüsseln der Nachfolgerknoten ist.
Lineare Darstellung eines Heaps: Anordnung der Elemente in einem Vektor entsprechend Baumebenen beginnend mit der 0. Ebene
Assoziatives SortierenHeapsortBeispiel: Heap
1 917
2 809 3 646
4 534 5 550 6 613 7 412
8 320Lineare Darstellung: 917 809 646 534 550 613 412 320
Assoziatives SortierenHeapsort
Positionsbestimmung: Vorgänger zu Knoten j: Position j div 2 Direkte Nachfolger zu Knoten j:
Positionen 2*j und 2*j + 1
Assoziatives SortierenHeapsortAlgorithmus:1. Aufbau eines Heap aus den Elementen der zu
sortierenden Menge M:Wiederholung folgender Schritte beginnend mit einem 1-elementigen Heap1.1 Anfügen des nächsten Elements aus M an gegebenen Heap1.2 Überprüfung der Heapeigenschaft mit Korrektur, wenn nötig
2. Konstruktion der sortierten Menge M´:Wiederholung folgender Schritte bis zur Erreichung eines leeren Heaps:2.1 Übernahme des Wurzelelements des Heaps nach M´(von links nach rechts)2.2 Ersetzen des Wurzelelements im Heap durch letztes Heapelement (letzte Ebene, rechter Rand)3.2 Überprüfung der Heapeigenschaft mit Korrektur, wenn nötig
Beispiel: M = {550, 917, 613, 320, 809, 646, 412, 534}
1. Konstruktion des Heap
550 550
550 917 550
917Erfüllt Heapeigenschaft nicht
917 550 917
550
917 550 613 917
550 613
Heap zu M
917 809 646 534 613 412 320 917
809 646
534 550 613 412
320
2. Konstruktion der sortierten Menge M´Auslesen der Wurzel: 917Ersetzen der Wurzel durch letztes Element:
320 809 646 534 550 613 412 917
320
809 646
534 550 613 412
Überprüfung der Heapeigenschaft:
809
320 646
534 550 613 412
809
550 646
534 320 613 412
Auslesen und Ersetzen der Wurzel:
412
550 646
534 320 613
412 550 646 534 320 613 809 917
Endergebnis: M´= {320, 412, 534, 550, 613, 646, 809, 917}
Hybrides SortierenAlgorithmus:M = {a1,..., an}, amin minimales Element, amax maximales Element von MSchritte:1. Unterteilung von <amin, amax+1) in m Teilintervalle
<xi, xi+1), i=0,...,m-1, x0 = amin,xm = amax + 1
2. Verteilung der Elemente auf Intervalllisten3. Assoziatives Sortieren in den Listen und
Listenverkettung
Beispiel: M = {207, 095, 646, 198, 809, 376, 918, 534, 310, 209,
181, 595, 799, 694, 344, 522, 139} xmin = 095 xmax + 1 = 919 m = 8 Intervalle Elemente Elemente sortiert
<095, 198) 095 181 139 095 139 181 Sortierte<198, 301) 207 198 209 198 207 209 Menge<301, 404) 376 310 344 310 344 376<404, 507) <507, 610) 534 595 522 522 534 595<610, 713) 646 694 646 694<713, 816) 809 799 799 809<816, 919) 918 918
SuchverfahrenSuchproblem: Ein Suchproblem ist gegeben durch 1) die Mengen U Universum (Elemente, aus
denen der Suchraum bestehen kann), A Menge der Anfragen, X Menge der Antworten
2) und eine Beziehung zwischen den angeführten Mengen Q: A x 2U XQ(a, S) mit a A, S 2U bezeichnet eine Antwort aus X zu einer Anfrage a an einen Suchraum S aus dem Universum U.
SuchverfahrenAlgebraische FormulierungStatisches Suchproblem: Der Suchraum
wird einmal aufgebaut und bleibt dann unverändert.
Statisches Q XLexikon
init build Ainsert,delete2U U
SuchverfahrenAlgebraische FormulierungDynamisches Suchproblem: ständige
Änderung des Suchraums durch Hinzufügen und Entfernen von Elementen
Dynamisches Q XLexikoninit A
insert delete
U
SuchverfahrenOperationen:init Initialisierung des Suchraums mit
einer leeren Menge
insert Aufnahme eines Elements aus U in den Suchraum
delete Entfernung eines Elements aus dem Suchraum
build Strukturierung des Suchraums
SuchverfahrenTypische SuchproblemeZugehörigkeit eines Elements zu einer
Menge: U = A beliebige Menge (nach jedem Element des U kann in
S gefragt werden), X = {true, false}, S U true, a S Q(a, S) = false, a S S Wörterbuch mit der Anfrageoperation (Mitglied, member)
und im dynamischen Fall zusätzlich mit den Operationen insert (Einfügen) und delete (Streichen, Entfernen)
SuchverfahrenTypische SuchproblemeMinimum (Maximum) einer geordneten
Menge: U = X (potenziell jedes Element aus U
kommt in Frage), A ohne Bedeutung Q(_, S) = min S (Q(_, S) = max S), S U
Dynamischer Fall: Prioritätsschlange
SuchverfahrenTypische Suchprobleme Mehrdimensionale Suchprobleme (partial
match searching): E beliebige Menge U = Ek Menge aller k-Tupel von Elementen aus E, k 1 A = (E {*})k Menge aller k-Tupel, deren Elemente *
oder aus E sein können, * E X = 2U
Q(a, S) = {b S| j (1 j k) (aj = bj aj = *)}, S Ek Menge aller k-Tupel, deren Komponenten mit denen von
a = (a1,..., ak) übereinstimmen, wenn sie kein * sind
SuchverfahrenTypische SuchproblemeProblem des nächsten Nachbarn (Postamtproblem): A = U = E2, X = 2U, S E2
E2 zweidimensionaler Euklidischer Raum mit Metrik
Q(a, S) = {b S| (c S) ((a, b) (a, c)} (Für eine Postsendung mit gegebenem Zielort ist das nächstliegende Postamt zu bestimmen.)
SuchverfahrenKlassifizierungen Klassifizierung der Suchalgorithmen:1. Algorithmen mit Adressberechnung: Der Platz des
gesuchten Elements im Suchraum wird ausgehend vom Wert des Elements berechnet.
2. Assoziative Algorithmen: Die Positionsbestimmung geschieht durch Vergleich des gesuchten Elements mit anderen Elementen des Suchraumes, wobei im Universum eine Ordnung vorgegeben sein muss.
Weitere Klassifizierung: parallele Algorithmen,
sequentielle Algorithmen
SuchverfahrenKomplexitätsmaßeVoraussetzung: n Größe des SuchraumesP(n, k) zeitliche Komplexität der Konstruktion
der Datenstruktur (Suchstruktur), in der gesucht wird
(k-dimensionale Menge vom Umfang n)
S(n, k) Speicherkomplexität der SuchstrukturQ(n, k) zeitliche Komplexität der Realisierung einer Anfrage über der Suchstruktur
SuchverfahrenKomplexitätsmaßeU(n,k) zeitliche Komplexität jeder
Aktualisie- rungsoperation für SI(n, k) zeitliche Komplexität einer insert- Operation im dynamischen FallD(n, k) zeitliche Komplexität einer delete- Operation im dynamischen Fall
SuchverfahrenAlgorithmen mit AdressberechnungenVerwendung eines charakteristischen VektorsVoraussetzung: |U| = N, U = {1, 2,..., N},
N nicht zu groß Repräsentation von S U durch einen
charakteristischen Vektor (Bitvektor)A: array [1..N] of Boolean, wobei A[i] = true genau dann, wenn
das i. Element von U in S ist
Suchverfahren unter Verwendung eines charakteristischen VektorsBeispiel: U = {rot, blau, grün, gelb, schwarz}, S = (blau, gelb) type Farbe = ...; S: array [Farbe] of Boolean => S[blau] = true = S[gelb], S[rot] = S[grün] = S[schwarz] = false
rot blau grün gelb schwarzfalse true false true false
SuchverfahrenAlgorithmen mit AdressberechnungenHashing Voraussetzung: großes (evtl. unendliches)
Universum U und relativ kleine Menge S U, |S| m Verwendung einer Hashtabelle A[0..m-1] und
einer Hashfunktion h: U {0,..., m-1} Wenn x S, dann wird x auf A[h(x)] oder „in
der Nähe“ abgespeichert.
SuchverfahrenHashingKollission: x, y S, x y, und h(x) = h(y) Abspeicherung von x und y auf
unterschiedlichen Plätzen „in der Nähe“ von h(x); unterschiedliche Bestimmung der „Nähe“
Verkettung oder offene Adressierung
SuchverfahrenHashing1. Hashing mit VerkettungAlle Elemente von S mit der gleichenHashadresse h(x) werden zu einer Ketteverbunden, deren Anfang in A[h(x)]abgespeichert ist.
SuchverfahrenHashing mit VerkettungBeispiel: U = {0, 1, 2,...}, S = (1, 3, 4, 7, 10, 17, 21}, m = 3 Hashfunktion: h(x) = x mod 3 A 0 3 21 1 1 4 7 10 2 17
SuchverfahrenHashing2. Hashing mit offener AdressierungIdee: Zu jedem Element x U gehört eine
Folge von Tabellenpositionen h(x, i), i = 0, 1,... , auf denen sich x befinden könnte.
Mögliche Hashfunktion:
h(x, i) = [h1(x) + h2(x)*i] mod m
SuchverfahrenHashing mit offener AdressierungBeispiel: m = 7, h1(x) = x mod 7, h2(x) = 1 + (x
mod 4)S = (3, 17, 6, 9, 15, 13, 10) h(3, i) = [3 + 4*i] mod 7, i = 0 möglich Abspeicherung
von 3 auf A[3] h(17, i) = [3 + 2*i] mod 7, i = 1 möglich Abspeicherung
von 17 auf A[5] ...
0 1 2 3 4 5 613 15 9 3 10 17 6
SuchverfahrenHashing3. Perfektes Hashing Perfekte Hashfunktion:U = {0, 1,..., N - 1}, S U, h: {0, 1,..., N - 1} {0, 1,..., m-1}h heißt perfekt, wenn für alle x, y S, x y, gilt h(x) h(y).Eine Menge H von Hashfunktionen heißt (N, m, n)-perfekt, wenn es für jede Teilmenge S, |S|
= n, ein h H gibt, so dass h für S eine perfekte Hashfunktion ist.
SuchverfahrenPerfektes HashingPraktische Methode (Cormack, Horspool,
Kaiserwerth): Verwendung von zwei Tabellen:
- Tabelle D (directory)- Tabelle T (Elementetabelle)
Aufspaltung des Suchraums S in Gruppen Si, i=1,...,m, wobei gilt: x und y aus S gehören genau dann in die gleiche Gruppe, wenn ihr Hashwert gemäß primärer Hashfunktion h gleich ist
h(x,s) = a = h(y, s) bedeutet (|D| = s):hk(e,r) ist eine sekundäre Hashfunktion für das Auffinden der Elemente aus Sk im Abschnitt [, +r-1] der Tabelle T, wobei hk(x,r) = u und hk(y,r) = t , |Sk| = rTabelle D Tabelle T
a k r
+u x
+t y
+r-1
SuchverfahrenHashing4. Digitale SuchbäumeIdee: Kombination von Hashing und Suchbaum Hashwert: Binärzahl Interpretation des Hashwertes:
- Durchlaufe den Wert von links nach rechts bis zum Auffinden des Elements oder eines freien Speicherplatzes zur Elementablage- 0: gehe nach links- 1: gehe nach rechts
SuchverfahrenDigitale SuchbäumeBeispiel: S = {s1, s2, s3, s4, s5, s6}Hashfunktion:
i hs1 0010 0010 s1 s2 1001s2 1001s3 1101 0011 s5 s3 1101s4 0111 0111 s4s5 0011 s6 1111s6 1111
SuchverfahrenHashing5. Tries (Retrieval trees)Tries haben eine analoge Struktur zu den digitalen
Suchbäumen mit folgenden Änderungen:a) Die Elemente sind Blätter des Baumes.b) Als Hashwert wird die binäre Darstellung eines
Elements verwendet.c) Die Kanten im Baum sind mit 0 (linke Kante)
oder 1 (rechte Kante) bezeichnet. Der Hashwert eines Elements beschreibt dann eine Kantenfolge, die zum gesuchten Element führt.
SuchverfahrenTriesBeispiel: S = {0010, 1001, 1101, 0111, 0011, 1111}
0 1
0 1 0 1
1 1 0 0 1 0 1 1 1 1 1
s1 s5 s4 s2 s3 s6
Assoziatives SuchenVerfahrenVoraussetzungen:U linear geordnetes Universum (Menge
mit totaler Ordnung)S = (x1,..., xn) mit xi xi+1 sei im Vektor
S[1..n] abgespeichert, wobei S[i] = xi
a U in S gesuchtes Element
Grundalgorithmus:S S[1] S[unten] S[naechster]=e S[oben] S[n] Schritte:a) Vergleiche a mit einem Element e aus S.b) 1. e ist a Halt 2. a < e Suche im unteren Teil von S 3. a > e Suche im oberen Teil von SErfolgloser Abbruch, wenn bei 2. bzw. 3. der jeweilige
Bereich von S nur aus einem Element besteht und dieses Element nicht a ist.
Bestimmung des Suchabschnittes in S:1. Initialisierung: unten := 1; oben := n; naechster := aus [unten..oben] ausgewählter
Index (des Elements e);2. Solange oben > unten und a S[naechster],
führe folgende Schritte aus:Wenn a < S[naechster], dann oben := naechster - 1,sonst unten := naechster + 1.naechster := aus [unten..oben] ausgewählter Index;
3. Wenn a = S[naechster], dann wurde a gefunden, sonst ist a nicht in S.
Halt.
Der Index von e (naechster) kann durch unterschiedliche Strategien ausgewählt werden:
a) lineare Suche: naechster := untenb) binäre Suche: naechster := (oben + unten)/2 -
Intervallhalbierung(x bedeutet: kleinste ganze Zahl größer oder gleich x)
c) Interpolationssuche: zusätzlich werden S[0] und S[n + 1] eingeführtnaechster := (unten - 1) + (a - S[unten - 1])*(oben - unten + 2)/(S[oben + 1] - S[unten - 1])
Beispiel: S = (3, 8, 12, 16, 21, 27, 32), a = 12
Binäre Suche3 8 12 16 21 27 32 S
unten naechster oben erster
Suchabschnitt naechster oben zweiter
Suchabschnittunten + naechster dritter Suchabschnitt
Interpolationssuche
Zusätzliche Elemente: S[0] = 0 S[8] = 37
0 3 8 12 16 21 27 32 37S
unten naechster oben
erster Suchabschnitt
Binärer Suchbaum S = (x1,..., xn) mit xi < xi+1, i=1,...,n-1 T Binärbaum mit den Knoten v1,..., vn und
der MarkierungsfunktionLabel: {v1,..., vn } S , wobei gilt:vk sei die Wurzel eines beliebigen Unterbaums Tk von T. vi bzw. vj seien beliebige Knoten im linken bzw. rechten Unterbaum von Tk. DannLabel(vi) < Label(vk) < Label(vj)
Suchbaum mit symmetrischer Ordnung:- Markierung der inneren Knoten mit Elementen aus S.- Markierung der Blätter mit offenen Intervallen, die alle Elemente umfassen, die nicht im Suchbaum auftreten.
Beispiel: S = (3, 8, 12, 16, 21, 27, 32)
16 8 27 3 12 21 32 ( , 3) (3, 8) (16, 21) (21, 27)
(8, 12) (12, 16) (27, 32) (32, )
Algorithmus für den Zugriff zu einem Element a im Baum T:
1. Initialisierung: v := Wurzel von T;2. Solange v kein Blatt ist und Label(v)
a, wiederhole:Ist a kleiner als Label(v), dann v := linker Sohn von v,sonst v := rechter Sohn von v.
3. Wenn v ein innerer Knoten ist, dann wurde a gefunden, sonst ist a nicht im Baum vorhanden.
Algorithmus zum Einfügen eines neuen Knotens a mit xi0 < a < xi0+1 und S = (..., xi0, xi0+1,...):
1. Auffinden des Blattes mit der Markierung (xi0, xi0+1)
2. Ersetzen des Blattes durch einen Baum
a (xi0, a) (a, xi0+1)
Assoziatives SuchenGewichtete BäumeZugriffsverteilung (0, 1, 1,..., n, n):S = (x1,..., xn) mit x1 < x2 < ... < xn
i Wahrscheinlichkeit, dass das Zugriffselement a identisch mit xi istj Wahrscheinlichkeit, dass das Zugriffselement a im Intervall (xj, xj+1) liegti + j = 1
Assoziatives SuchenGewichtete BäumeTiefe eines Baumknotens v eines Baumes T:1. v sei die Wurzel von T: Tiefe(v, T) = 02. Es sei T = <w, T1,..., Tm> und v sei ein
Knoten im Teilbaum Ti:Tiefe(v, T) = 1 + Tiefe(v, Ti)T w
T1 Ti vk Tm
v
Assoziatives SuchenGewichtete Bäume
Gewichtete Pfadlänge PT eines Baumes T:PT = i*(1 + bi
T) + j*ajT
biT Tiefe des Knotens xi im Baum T
ajT Tiefe des Blattes (xj, xj+1) im Baum T
Beispiel: x3 1/8
x2 1/8 x4 0
x1 1/24 (x2, x3) (x3, x4) (x4, x5) 0 1/8 5/12
(x0, x1) (x1, x2 ) 1/6 0 PT = (1/24*3 + 1/8*2 + 1/8) + (1/6*3 + 1/8*2 + 5/12*2)
Assoziatives SuchenBalancierte Bäume1. Gewichtsbalancierte BäumeWurzelbalance eines Baumes T:Voraussetzungen:
- T hat einen linken Unterbaum Tl und einen rechten Unterbaum Tr
- |T| bedeutet die Anzahl der Blätter von TWurzelbalance: (T) = |Tl|/|T| = 1 - |Tr|/|T|
Assoziatives SuchenGewichtsbalancierte BäumeBaum T von beschränkter Balance (T BB[]):Für jeden Unterbaum T’ von T gilt (T’) 1 - .
Bedeutung der Bäume aus BB[]:Sie besitzen logarithmische Tiefe und im Mittellogarithmische mittlere Pfadlängen
(für ¼ < 1 - 21/2/2).
Beispiel: 5/14 2/5 4/9 1/2 2/3 1/2 2/5
( ) ( ) 1/2 ( ) 1/2 1/2 1/2 2/3 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1/2 ( ) ( ) ( )Für 1/3 ist der Baum aus BB[].
Operation Rotation nach links x 1 y 1 y 2 x 2 a c
b c a b 1 = 1 + (1 - 1)*22 = 1/(1 + (1 - 1)*2)
Operation Doppelrotation nach links x 1 z 1
y 2 x 2 y 3 a
z 3 d a b c d b c 1 = 1 + (1 - 1)*2*32 = 1/(1 + (1 - 1)*2*3)3 = 2*(1 - 3)/(1 - 2*3)
Assoziatives SuchenBalancierte Bäume2. Höhenbalancierte Bäume(a, b)-Baum:Voraussetzungen:
a, b ganze Zahlen, a 2, b 2*a - 1(v) Anzahl der Söhne des Knotens v
T ist ein (a, b)-Baum, wenn gilt:1. Alle Blätter von T haben die gleiche Tiefe.2. Alle Knoten v von T erfüllen die Bedingung (v) b.3. Alle Knoten v, außer der Wurzel, erfüllen die Bedingung (v)
a.4. Die Wurzel r hat die Eigenschaft (r) 2.
Abspeicherung einer Menge S als Baum T (Mehlhorn):1. Die Elemente von S werden als Blätter von T von
links nach rechts in aufsteigender Ordnung abgespeichert.
2. Jeder innere Knoten v wird mit k1(v) : k2(v) : ...: k(v)-1
markiert, ki(v) < kj(v) für i < j und ki(v), kj(v) U, wobei gilt:a) Für alle Blätter w des ersten Unterbaumes von v:Label(w) k1(v).b) Für alle Blätter des (v). Unterbaumes von v:Label(w) > k(v)-1.c) Für die Blätter w des i. Unterbaumes von v, 1 < i < (v): ki-1(v) < Label(w) ki(v).
Beispiel: (2, 4)-Baum 4 2 7 : 8 : 9 1 3 7 8 9 10
a : b : c bedeutet eine Elementeaufteilung in folgende
Bereiche a (a, b] (b, c] c <
Beispiel: Rebalancierung nach Einfügen4
2 6 : 7 : 8 : 9 1 3 6 7 8 9 10Kein (2, 4)-Baum!Rebalanciert: 4 : 7 2 6 8 : 9 1 3 6 7 8 9 10
Beispiel: Rebalancierung nach Streichen4 : 7
2 6 8 : 9 1 3 6 7 8 9 10Kein (2, 4)-Baum! Rebalanciert:4 : 8
2 7 9 1 3 7 8 9 10
KomplexitätenSortieralgorithmenVorraussetzungen: U Universum, S Sortiermenge, |U| = m (im endlichen Fall), |S| =
n Adressenorientiertes Sortieren:
- Zeit: O(n + m)- Speicher: O(n * m)
Lexikographisches Sortieren (k Stellenanzahl der sortierten Wörter, m Anzahl unterschiedlicher Zeichen):- Zeit: O(k * (m + n))- Speicher: O(n * m)
Insersort, Selectsort, Bubblesort:- Zeit: O(n2)- Speicher: O(n)
Mergesort:- Zeit: O(n * log2 n)- Speicher: O(n) (2 * n)
Quicksort:- Zeit: O(n2) , durchschnittlich ca. (n * log2 n)- Speicher: O(n)
Countsort:- Zeit: O(n2) - Speicher: O(n) (3 * n)
Hybrides Sortieren:- Zeit: O(n * log2 n), durchschnittlich ca. (n)- Speicher: O(n) (2 * n)
Heapsort:- Zeit: O(n * log2 n)- Speicher: O(n)
Shellsort:Zeit: O(n1,5) (hängt entscheidend von den gewählten Abständen ab und ist schwer ermittelbar)
Ausgewählte KomplexitätenSuchverfahrenVorraussetzungen: U Universum, S Suchraum, |S| = n, m Anzahl möglicher Eintragungen in einer
Hashtabelle
Charakteristischer Vektor: Anfrage und Aktualisierung O(1)
Hashing mit Verkettung: Anfrage, Einfügen, Löschen im schlechtesten Fall (n)
Hashing mit offener Adressierung: durchschnittliche Suchzeit bei Belegungsfaktor =n/m ca. (1/)*log2 (1/(1-))
Digitale Suchbäume: O(l) mit l Anzahl der Bit, aber durchschnittlich ca. (log2 n)
Tries: O(l) mit l Länge des Hashwertes Binäre Suche: Anfrage O(log2 n), Einfügen und
Löschen O(n) Binärer Suchbaum: O(T) mit T Tiefe des
Suchbaums Interpolationssuche: O(n) , durchschnittlich
ca. (log2 log2 n) BB[], (1/4, 1 – 21/2/2]: O(log2 n) (a, b)-Baum: Suche, Einfügen, Löschen O(log2
n)
EvolutionsalgorithmenCharakterisierung: Such- und Optimierungsstrategien nach dem
Vorbild der Evolution in der Natur Ingenieurtechnisch ist Evolution
- ein Suchprozess im Raum genetischer Informationen bzw. Erbanlagen- mit dem Ziel des Findens bester Erbanlagen
Verwendung schwacher Strategien (nicht problemabhängig; keine spezielle Bewertung)
Durchlauf durch den Suchraum:Bestimmung des nächsten Suchpunktes ausgehend von durchlaufenen
Suchpunkten und aktuellem Suchpunkt unter Nutzung von Bewertungskriterien
Durchlaufstrategien: Feste Strategien Wissensbasierte Strategien
Evolutionsalgorithmen: Genetische Algorithmen Genetische Programmierung Evolutionsstrategien Evolutionäre Programmierung
Anwendungen: Ältere Anwendungen:
1967 Entwicklung von Spielstrategien, Mustererkennung, Simulation lebender Zellen, 1975 Optimierung der Form von Kühlrippen, 1975 Gewichtsoptimierung eines Stabtragwerkes
Neuere Anwendungen: Data Mining, automatische Programmerzeugung, Berechnung optimaler Linsenformen, Strukturevolution neuronaler Netze
Genetische AlgorithmenGenetische Algorithmen bilden eine
Analogie zur natürlichen Auswahl und Evolution. Charakterisierung:1. Wahl eines geeigneten Kodierungsmechanismus’ für Problemlösungen als „Chromosomen“ (i.d.R. Bitvektoren für Individuen)2. Mechanismus zur Erzeugung der initialen Lösungspopulation (Generation 0)
Genetische Algorithmen (Fortsetzung)
3. Wiederholung nachfolgender Schritte bis zum Erreichen einer zufriedenstellenden Bewertung oder einer Abbruchbedingung:
Bewertung der aktuellen Population gemäß Bewertungs- oder Fitnessfunktion
(Bewertung: Nähe zum Optimum; Fitness: Wahrscheinlichkeit des Überlebens und der Teilnahme an der Reproduktion Abbruch oder Fortsetzung mit nächstem Punkt)
Genetische Algorithmen (Fortsetzung) - Selektion von Subpopulationen gemäß Heiratsschema und Erzeugung von Nachkommen der aktuellen Generation mittels Rekombination - Mutation der Nachkommen - Bestimmung der neuen Generation gemäß Ersetzungsschema - Aktualisierung der Abbruchbedingung
Beispiel: Problem des HandelsreisendenNaiver Lösungsprozess: Bestimmung aller möglichenRouten ((n-1)!) und Auswahl der kürzesten praktischnicht durchführbarLösung durch genetischen Algorithmus: 1. Kodierung der Routen: a) graphisch: Städte als Knoten, Reisestrecken als
bewertete KantenBeispiel:
C
B D E
A F
b) Vektor, dessen Komponenten den direkten Städteverbindungen entsprechen:1 Verbindung vorhanden0 Verbindung nicht vorhandenProbleme:
geschlossene Wegstrecken sind schlecht erkennbar
schwere Realisierbarkeit vernünftiger Rekombinations- und Mutationsoperatoren
c) Vektor S mit k Komponenten (Indizes 0,1,...,k-1), k Anzahl der Städte: Jedem Element aus {0,1,...,k-1} entspricht eine Stadt. Die Vektorkomponenten führen die besuchten Städte kodiert und in der Besuchsreihenfolge an.
Beispiel:Zuordnung: A 0, B 1, C 2, D 3,
E 4, F 5S für obigen Weg: (0, 1, 3, 2, 4, 5)
2. Festlegung von Bewertungs- und Abbruchkriterien
3. Festlegung von Rekombinations- und Auswahlstrategien
Beispiele: Rekombinationsstrategien Kreuzung: Eltern Kinder
0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 1 0 0
Mutation: Löschen - Nachschieben -
Einsetzen8 7 1 0 6 3 4 9 5 2 8 7 0 6 3 4 9 5 2 1
Genetische ProgrammierungGenetische Programmierung kann als
genetische Algorithmen auf abstrakten Syntaxbäumen von Programmen betrachtet werden
Ziel: Es sollen Programme erzeugt werden, die bestimmten Kriterien genügen
Vorgehensweise: siehe genetische Algorithmen
Genetische Programmierung (Fortsetzung)
Beispiel:Programm in LISP-Notation:(MUL (ADD X (DIV Y 1.5)) (SUB Z 0.3))
Y/1.5 Z - 0.3X + Y/1.5
(X + Y/1.5) * (Z - 0.3)
Genetische Programmierung (Fortsetzung)Abstrakter Syntaxbaum:
MUL
ADD SUB
X DIV Z 0.3
Y 1.5
Algorithmusschritte:1. Erzeugung einer initialen
Programmpopulation2. Wiederholung folgender Schritte bis zum
Erreichen von Abbruchkriterien:a) Bewertung der aktuellen Population
Abbruch bzw. Fortsetzung mit b)b) Erzeugung neuer Programme durch übliche
genetische Operationen (z.B. Austausch von Baumteilen, Ersetzen von Baumteilen), die auch typgesteuert sein können
c) Bestimmung der neuen Generation
Programm- population Programm- Eltern- test auswahl
Neue Programme
EvolutionsstrategienZiel: Verbesserung von Verhalten durch Evolution
Population: Vektoren reeller Zahlen Vektorkomponenten entsprechen
Verhaltensmerkmalen
Vorgehensweise: analog zu genetischen Algorithmen
Evolutionäre Programmierung
Keine Beschränkungen für Populationen!
Erzeugung neuer Populationen durch Mutation
Komponenten prozeduraler (imperativer) Programmiersprachen (1) Ausdrucksmittel zur Darstellung des
Steuerungsflusses (Iteration, Sequenz, Alternative, Parallelität)
Prozedurabstraktion (Zusammenfassung von Anweisungsfolgen zu einer, evtl. parametrisierten, Programmeinheit, die an verschiedenen Programmstellen aufgerufen werden kann)
Komponenten prozeduraler (imperativer) Programmiersprachen (2) Programmvariablen als Modell für Speicherplätze: - Charakterisierung durch Name (Bezeichnung im Programm), Referenz (Adresse des zugeordneten
Speicherplatzes), Wert (Inhalt des zugeordneten Speicherplatzes), Typ (Art des Inhaltes des zugeordneten
Speicherplatzes)
Komponenten prozeduraler (imperativer) Programmiersprachen (3)- Möglichkeit der Wertänderung - unterschiedliche Arten der
Parametervermittlung (z.B. Referenzaufrufe, Werteaufrufe)
- Nebeneffekte (side effect) von Prozeduren bei Wertänderung von nichtlokalen Variablen
Komponenten prozeduraler (imperativer) Programmiersprachen (4)- Möglichkeit der Mehrfachreferenz (Aliasnamen)- Sprachkonzepte zur Speicherverwaltung (z.B. Erzeugung und Beseitigung von Speicherplatz)- Lebensdauer und Gültigkeitsbereiche Lebensdauer: Dauer der Existenz eines Objekts; z.B.
während der Existenz eines Prozedurkörpers existieren
alle dort deklarierten Variablen.Gültigkeitsbereich: gibt Zugriffsmöglichkeiten zum Objekt an
Komponenten prozeduraler (imperativer) Programmiersprachen (5) Datentypkonzept: Datentyphierarchie alle elementar strukturiert
aufzählbar nicht aufzählbar rekursiv endliche kartesisches Vereinigung (Zeiger) Abbildung Produkt (union) (Array) (Record) Typkontrollen, Typäquivalenz
Komponenten funktionaler Sprachen
Menge einfacher Datenobjekte (z.B. Listen) Menge vordefinierter elementarer Funktionen (z.B.
zur Listenbearbeitung) Regeln zur Komposition von Funktionen (z.B.
Verkettung) Bezeichnungsregeln für Funktionen im
Zusammenhang mit Deklarationen Anwendungsoperator für Funktionen
(Funktionsaufruf)
Beispiel% Sortierfunktion
DEF sort([]) = []DEF sort([a|R]) = a insert sort(R)% [a|R] bezeichnet eine Liste mit dem Kopfelement% a und der nachfolgenden Restliste R% EinfuegefunktionDEF x insert [] = [x]DEF x insert [a|R] = IF x a THEN [x|[a|R]]
ELSE [a|(x insert R)] FI
Sortieren von {17, 5, 7, 1}sort([17|[5, 7, 1]]) 7 insert sort([1])
17 insert sort([5, 7, 1]) sort([1|])
sort([5|7, 1]) 1 insert sort([])
5 insert sort([7, 1]) 1 insert []
sort([7|1])[1]
Sortieren von {17, 5, 7, 1} (Fortsetzung)
7 insert [1] = 7 insert [1|] 17 insert [1, 5,7]
[1|7 insert []] [1|17 insert [5, 7]]
[1|[7]] = [1, 7] [1|[5|17 insert [7]]]5 insert [1, 7] [1|[5|[7|17 insert []]]][1|5 insert [7]] [1|[5|[7|[17]]]] =[1|[5|7 insert []]] = [1, 5, 7] [1, 5, 7, 17]
Sprachelemente von Prolog Klausel (Hornklausel): A B1,...,Bq. q 0, A,
B1,...,Bq Atome Bedeutung: x1,...,xk (B1’ ... Bq’) A’
x1,...,xk alle Variablen der Klausel A’, B1’,...,Bq’ Aussagen, entstanden aus A, B1,...,Bq
Fakt: A. verkürzte Form von A . Atom: p(t1,..., tn), p n-stelliges
Prädikatsymbol, t1,..., tn Terme
Sprachelemente von Prolog (Fortsetzung)
Programm: P = <p, f, r, g> p endliche Menge von Prädikatsymbolen f endliche Menge von Funktionssymbolen r endliche Menge von Klauseln unter
Verwendung von p und f g Anfrageklausel der Form
goal B1,...,Bq. oder ?- B1,...,Bq.
Beispielinsertsort([], []).%Die leere Liste sortiert ergibt wiederum die% leere Liste.insertsort([A|R], S) :-
insertsort(R, SR), insert(A, SR, S).%Ist eine Liste nicht leer, so wird erst die% Restliste sortiert und anschliessend das%Kopfelement in die sortierte Restliste auf% den richtigen Platz eingefuegt.
Beispiel (Fortsetzung)insert(X, [A|R], [A|S]) :-
gt(X, A), !, insert(X, R, S).%Ist das einzufuegende Element X groesser als% das Kopfelement der Liste, so muss es in die% Restliste R eingefuegt werden.insert(X, S, [X|S]).%Ist das einzufuegende Element X kleiner oder%gleich dem Kopfelement, so wird es als neues%Kopfelement verwendet und die alte Liste S% bildet die neue Restliste.
Beispiel (Fortsetzung)Anfrage?- insertsort([17, 5, 7, 1], S).
SystemantwortyesS = [1, 5, 7, 17]
Logische Programmierung mit Einschränkungen (Constraint logic programming) - Beispiel
%Zusammenstellung einer kalorienarmen Mahlzeitlightmeal(Vorspeise, Hauptmahlzeit, Nachspeise):-
I > 0, J > 0, K > 0, I + J + K <= 10,%Die gesamte Mahlzeit darf nicht mehr als 10%Kalorien enthalten.
vor(Vorspeise, I), haupt(Hauptmahlzeit, J),nach(Nachspeise, K).
%Erster Parameter ist Speise, zweiter ist Kalorien
Beispiel (Fortsetzung)%Vorspeisenvor(rettich, 1). vor(nudeln, 6).%Hauptmahlzeithaupt(H, I) :- fleisch(H, I).haupt(H, I) :- fisch(H, I).fleisch(bulette, 6). fleisch(schwein, 7).fisch(seezunge, 2). fisch(thun, 4).
%Nachspeisenach(obst, 2). nach(eis, 6).
Beispiel (Fortsetzung)
Anfrage?- lightmeal(V, H, N).
Antwort des SystemsV = rettich, H = bulette, N = obst.
Funktionales ProgrammierenFunktionen in der MathematikDefinition (Funktion, Abbildung): D und W
seien Mengen und f eine binäre, linkseindeutige Relation f D x W. Dann heißt f Funktion mit dem Definitionsbereich D und dem Wertebereich W. f bildet den Argumentwert x D auf den Resultatswert y W genau dann ab, wenn (x, y) f (Notation: f(x) = y. f(x) bezeichnet demzufolge die Anwendung von f auf x.).
D W ist der Typ (Funktionalität, Profil) von f.f heißt partiell (total), wenn die Projektion von fauf D eine Teilmenge von D (die Menge D) ist,d.h. 1(f) D (1(f) = D).
Definition (Totalisierung einer partiellen Funktion): Essei f eine partielle Funktion mit dem DefinitionsbereichD und dem Wertebereich W. Außerdem gelte D = D {} und W = W {}. Dann ist f einetotale Funktion mit dem Definitionsbereich D sowiedem Wertebereich W und
y, f(x) = y, x Df(x) = , f(x) ist nicht definiert, x D , x =
Funktionales Programmieren-TermeDefinition (-Terme): -Terme sind1. Variablen, Konstanten , Funktionssymbole2. Terme der Form v.l (-Abstraktion) mit
der Variablen v und dem -Term l; v heißt gebundene Variable in l.
3. Terme der Form (m n) (-Applikation) mit den -Termen m und n. m steht in Funktionsposition und n in Argumentposition.
Beispiele (Infixnotation statt Präfixnotation):
(x. 1 + x) ((x. 1 + x) 2) 1 + 2 3 (x. ((y. ((x. x * y) 2)) x) x + y)
2 * y 2 * x2 * (x + y)
Konversionen ( Reduktion, Abstraktion): 1. Alpha-Konversion: (x. E) E[y/x]
(Einsetzen von y anstelle von x in E; Umbenennung von Variablen )
2. Beta-Konversion: ((x. E) F) E[F/x] Die Reduktion ist analog zum Ersetzen
formaler Parameter durch aktuelle Parameter bei Prozeduraufrufen imperativer Sprachen. Zu beachten sind Namenskonflikte, die durch den Ersetzungsprozess entstehen können.
3. Eta-Konversion: (x. (E x)) E
Problem der Reihenfolge der Auswertung bei -Reduktion:
1. Erst Auswertung von F und dann Einsetzen für x – applikative oder strikte Auswertung (eager evaluation)
2. Erst Einsetzen von F für x und anschließend Auswertung – normalisierende Auswertung (normal-order evaluation);Auswertung erfolgt nur, wenn sie benötigt wird – verzögerte Auswertung (lazy evaluation)
Beispiel: (((b1. (b2. IF b1 THEN b2 ELSE FALSE FI)) n
0) t/n 0.5) n sei 0: Strikte Auswertung: Im zweiten
Argumentterm tritt eine Division durch 0 auf und somit kann dieser Term nicht ausgewertet werden.
Verzögerte Auswertung: IF n 0 THEN t/n 0.5 ELSE FALSE FI FALSE Diesmal wird der Term nicht benötigt und
daher nicht berechnet.
Funktionale ProgrammierungDatentypenElementare Datentypen: z.B. int, real,
bool, string
Zusammengesetzte Datentypen: z.B. Tupel (Untermengen kartesischer Produkte), Verbunde (Tupel mit Selektoren), Listen (Tupel mit Elementen vom gleichen Typ), Funktionstypen
Ausgewählte Programmkonstrukte: Wertedefinition
val Identifikator = AusdruckDem Identifikator wird der Ausdruck als Bedeutung zugeordnet.
Funktionsabstraktionfun (Identifikator:Typ) Ausdruck
Dies entspricht dem -Term Identifikator.Ausdruck, wobei der Identifikator (Variable)
zusätzlich einen Typ bekommen hat.
- Funktionsdefinition
val Name der Funktion = Funktionsabstraktionoderfun Name der Funktion(Identifikator:Typ) = Ausdruck, wobei
Identifikator, Typ und Ausdruck aus der Funktionsabstraktion stammen.
Beispiele: ypvereinbarung für Binärbäume mit real-
Zahlen als Markierungen:datatype tree = nil| tree of (real * tree * tree)(Typgleichung: tree = unit + (real x tree x tree) )Musterbasierte Funktionsdefinition: Summe der real-Zahlen des Baumesfun sum(nil) = 0.0 | sum(tree(N, L, R)) = N + sum(L) + sum(R)
1.0
-3.5 7.7
-5.7 5.7 8.0
sum(tree(1.0, tree(-3.5, tree(-5.7, nil, nil), nil), tree(7.7, tree(5.7, nil, nil), tree(8.0,
nil, nil)))) = 13.2
Einsortieren einer int-Zahl in einen Binärbaum mit int-Zahlen als Markierungen:
datatype tree = nil| node of (tree * int * tree)fun insert(newitem, nil) = node(nil, newitem, nil) | insert(newitem, node(left, olditem, right)) =if newitem = olditem then node(insert(newitem, left), olditem, right) else node(left, olditem, insert(newitem, right))
Typvereinigung von line, triangle und circle zu Figure
datatype Figure = line of (point * point) | triangle of (point * point *
point) | circle of (point * real)
(Typgleichung: Figure = line + triangle + circle mit line = point x point, triangle = point x point x point,
circle = point x real)
Parametrisierte Datentypen:z.B.
type pair = * definiert Paare von Elementen eines
beliebigen Typs .
DatentypenListentyp datatype list = nil| cons of ( * list)
fun hd(l: list) =case l of nil ... (*Fehler*)
|cons(h,t) hand tl(l: list) =
case l of nil ... (*Fehler*)|cons(h,t) t
and length(l: list) =case l of nil 0
|cons(h,t) 1 + length(t)
Eine Liste ist eine Folge von Elementen des gleichen Typs.
Definiert sind Funktionen zur Bestimmung des Listenkopfs (hd), des Listenrests (tl) und ihrer Länge (length).
(Typgleichung: -list = unit + ( x -list) )
Notation: cons(h, t) oder h::t bezeichnen eine Liste mit dem Kopf h und dem Rest t.
ListentypOperationenBeispiele: Summe der Elemente einer Liste ganzer Zahlenfun sum(nil) = 0
|sum(n::ns) = n + sum(ns) Produkt der Elemente einer Liste ganzer Zahlen fun product(nil) = 1 | product(n::ns) = n * product(ns) Liste der ganzen Zahlen von m bis n ([m, n])fun op through(m,n) =
if m n then nil else m:: (m + 1 through n)op bedeutet, der folgende Operator kann als Infixoperator verwendet werden.
Currying im Beispiel:Definition der Berechnung von bn
1. Variante (gewöhnlich):fun power(n, b) = if n=0 then 1.0 else b*power(n-1, b)Funktionalität: nat x integer integer2. Variante (Currying):fun powerc(n) (b) = if n = 0 then 1.0 else b * powerc(n - 1) ( b)Funktionalität: nat (integer integer)Wenn val sqr = powerc(2) , dann liefert sqr das Quadrat zu einer integer-Zahl.
Funktion als Argument im Beispiel: 1. Variante:
fun twice(f: ) = fun (x: ) f(f(x))Funktionalität: () ()
twice hat als Parameter eine Funktion und liefert selbst wieder eine Funktion. Daher könnte die vierte Potenz so definiert werden: val fourth = twice(sqr)
2. Variante:Definition der Verkettung zweier Funktionen:fun op (f: , g: ) = fun (x:) f(g(x))Funktionalität: () x () ()fun twice(f:) = f f
ListentypAllgemeine Operationen Filteroperationen: Alle Elemente einer Liste, die
eine gegebene Eigenschaft besitzen (ausgedrückt durch ein Prädikat p), sollen in eine neue Liste übernommen werden.filter p [] = [] x:: filter p xs, wenn p xfilter p (x::xs) = filter p xs, sonstFunktionalität: ( bool) (-list -list)Beispiel: filter(odd) beseitigt alle geraden Zahlen aus einer Liste ganzer Zahlen
Abbildung: Auf jedes Element einer Liste wird die gleiche Funktion angewendet.map f [] = []map f (x::xs) = f x:: map f xsFunktionalität: () (-list -list)
Beispiel: map(sqr) liefert auf eine integer-Liste angewendet eine Liste der Quadrateder Listenelemente bzw. map(odd) liefert eine Liste logischer Werte in Abhängigkeit davon, ob ein Listenelement ungerade (true) oder gerade (false) war.
Faltung: Diesen Operator gibt es als rechte und linke Faltung. Die Faltung bedeutet, dass alle Elemente einer Liste ausgehend von einem wählbaren Startwert durch eine zweistellige Operation verknüpft werden, z.B. durch Addition.faltr f a [x1,...,xn] = f x1 (f x2 (...(f xn a)...))f ist eine zweistellige Operation und a ist der Startwert. Die Anwendung von f geschieht von rechts.Funktionalität: () []
Rechte Faltung in der Sprache ML:fun reduce(binaryop, unity) =
let fun f(nil) = unity|f(x::xs) = binaryop(x, f(xs))
in fend
Definition der Summe bzw. des Produkts
der Elemente einer Liste von integer-Zahlen:
reduce(op +, 0) bzw. reduce(op *, 1)
Potenziell unendlich lange Listen und verzögerte AuswertungBeispiel: näherungsweise Berechnung der
Quadratwurzel durch yn+1 = (yn + x/yn)/2Lösungsidee: Berechnung der Elemente der unendlichen
Folge gemäß Formel Abbruch der Berechnung der Folge, wenn
sich zwei aufeinander folgende Elemente um nicht mehr als unterscheiden
Berechnung der Listenelemente:fun approxsqrts(x) = let fun from(approx) = approx:: from(0.5 * (approx + x/approx))in from(1.0)end
Überprüfung der Abbruchbedingung für die ersten beiden Elemente einer Liste:fun absolute(eps) (approx1::approx2::approxs) = if abs(approx1 - approx2) = eps then approx2else absolute(eps) (approx2::approxs)
Kombination der obigen Funktionen zur Lösungsfunktion:val sqrt = absolute(0.0001)approxsqrts Listenelemente werden durch approxsqrts nur solange berechnet, wie sie für den Test absolute(0.0001) benötigt werden.
Andere Vorgehensweise (nicht in ML-Notation):
Verbesserung eines Näherungswertes y gemäß Formel (für x ist die Quadratwurzel zu berechnen):
verbessern x y = (y + x/y)/2 Überprüfung der Abbruchbedingung für
zwei Werte x und y: erfüllt x y = abs(y^2 - x) eps
Berechnung eines Funktionswertes der Funktion f mit dem Argument x in Abhängigkeit von der Bedingung p:
x, wenn p xbis p f x = bis p f(f x), sonst
Kombination obiger Funktionen:wurzel x y = bis (erfüllt x) (verbessern x) y
Beispiele: Sortierfunktionen in der Sprache OPAL
OPAL-QUICKSORTDEF sort() == DEF sort(a::R) == LET Small == (_ a) RMedium == a:: (_= a) RLarge == (_ a) RIN sort(Small) :: Medium :: sort(Large) liefert zu einer Liste alle Elemente, die eine bestimmte Bedingung erfüllen, in Formeiner Liste. vertritt die leere Liste.
OPAL-INSERTSORTDEF sort() == DEF sort(a :: R) == a insert sort(R)FUN insert: x seq[] seq[]DEF x insert == x :: DEF x insert (a :: R) == IF x a THEN x :: (a :: R) ELSE a :: (x insert R) FI