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