1

Algorithmen und DatenstrukturenInformatik B1

(DAI, Physik, Mathematik BSc, Kommedia)

Wolfram Luther

Peter Hertling

Wintersemester 2007/08

2

Übersicht

1. Einführung2. Grundelemente von Programmiersprachen3. Speicherverfahren4. Sortierverfahren 15. Von Datenstrukturen zu abstrakten Datentypen6. Suchbäume und weitere Sortierverfahren7. Ausgewählte Algorithmen8. Graphenalgorithmen9. ....... (Geometrische Algorithmen, FFT, .....)

Skriptum im Netz: InfoB1WS08 Pass: binTree

3

Kapitel 1: Einführung

1.1 Grundbegriffe 1.2 Phasen oder Ebenen der Programmentwicklung 1.3 Beispiele

1.3.1 Teilstring-Prüfung 1.3.2 String-Invertierung 1.3.3 Multiplikation von Dezimalzahlen

1.4 Die O-Notation

4

Abelson & Sussman (1985): We are about to study the idea of a computational process. Computational processes are abstract beings that inhabit computers. As they evolve, processes manipulate other abstract things called data. The evolution of a process is directed by a pattern of rules called a program. People create programs to direct processes. ... The computational process, in a correctly working computer, executes programs precisely and accurately.  ...  In programming, we deal with two kinds of objects: procedures and data. Informally, data is "stuff" that represents objects we want to manipulate, and procedures are descriptions of the rules for manipulating the data. Thus, any powerful programming language should be able to describe primitive data and primitive procedures and should have methods for combining and abstracting procedures and data.

1.1 Grundbegriffe

5

Grundbegriffe 2

Ottmann (1987, Vorlesungsskriptum): In der Informatik unterscheidet man üblicherweise zwischen Verfahren zur Lösung von Problemen und ihrer Implementation in einer bestimmten Programmiersprache auf bestimmten Rechnern. Man nennt die Verfahren Algorithmen. ... Die Entwicklung und Untersuchung von Algorithmen zur Lösung vielfältiger Probleme gehört zu den wichtigsten Aufgaben der Informatik. Die meisten Algorithmen erfordern jeweils geeignete Methoden zur Strukturierung der von den Algorithmen manipulierten Daten. Algorithmen und Datenstrukturen gehören also zusammen. Die richtige Wahl von Algorithmen und Datenstrukturen ist ein wichtiger Schritt zur Lösung eines Problems mit Hilfe von Computern.

6

Anforderungen an Programme:

• Korrektheit • Terminierung • Effizienz (Laufzeitverhalten und Speicherbedarf) • Wartbarkeit (Verständlichkeit, Lesbarkeit,

Übersichtlichkeit und Änderbarkeit) • Benutzungs"freundlichkeit" (bei interaktiven

Programmen) • Anwendungsflexibilität (Kombinierbarkeit mit

anderen Programmen)

7

Anforderungen...

Korrektheit und Terminierung

müssen auf jeden Fall sichergestellt sein.

Bei Effizienz, Wartbarkeit, Benutzungs-freundlichkeit und Anwendungsflexibilität gibt es oft einen Trade-off.

8

1.2 Phasen der Programmentwicklung

9

Harel 1987

10

1.3 Beispiele1.3.1 Teilstring-Prüfung Problem: Ist eine bestimmte Zeichenkette z in einem

gegebenen Text T enthalten?

Zu entwickeln:• Datenstruktur (entfällt hier, da Datentyp string vorhanden).• Algorithmus• ImplementationDann zu prüfen und zu analysieren:• Korrektheit (des Algorithmus)• Effizienz (des Algorithmus)

11

Operationen: ohne1(String) -> String, anf1(String) -> char

algorithmus präfix(p, s: String) -> Boolean { wenn (p leer) dann { ausgabe wahr; exit };   wenn (s leer) dann { ausgabe falsch; exit };   wenn anf1(p) = anf1(s)     dann ausgabe präfix(ohne1(p),ohne1(s))     sonst ausgabe falsch }

algorithmus TeilString(z, T: String) -> Boolean { res := falsch ;   solange (T nicht leer) und (res=falsch)      führe_aus { wenn präfix(z,T) dann res := wahr                           sonst T := ohne1(T) };   ausgabe res }

Effizienz: Zeitaufwand <= c |z| |T| Schritte (c eine Konstante)

Algorithmus

12

import java.io.*; import java.util.*; import java.awt.*;

public class TeilString {

private static String butFirst(String s) { return s.substring(1,s.length()); }

private static boolean emptyString(String s) { return s.equals(""); }

private static boolean TeilString(String z, String T) { boolean res = false; while ( res == false && ! emptyString(T) ) { System.out.println(z+" ; "+T); if ( T.startsWith(z) ) res = true; else T = butFirst(T); } return res; }

Implementation: Teilstringprüfung in Java 1

13

Teilstringprüfung in Java 2

public static void main(String[] args) { String z = args[0]; String MyText = "Java ist gar nicht so uebel!"; String Ergebnis; if ( TeilString(z,MyText) ) Ergebnis = "enthalten"; else Ergebnis = "nicht enthalten"; System.out.println("Text: "+MyText); System.out.println("String "+z+" ist in Text

"+Ergebnis+"."); }

14

1.3.2    String-Invertierung Algorithmus (als Flussdiagramm, aus Harel, S. 105):

15

Die Korrektheit wird durch Nachweisen der ``Assertions‘‘ (voriges Diagramm) gezeigt.

Invariante ALGORITHMICS

16

1.3.3    Multiplikation von natürlichen Zahlen

Problem:

Effiziente Multiplikation von Dezimalzahlen.

Datenstrukturen und Grundoperationen:

Integer mit Addition, Subtraktion, div, mod, Vergleichen

Algorithmen: zwei Beispiele

Effizienzanalyse

17

Multiplikation von DezimalzahlenErster Algorithmus: Dekrementieren

18

Multiplikation von DezimalzahlenZweiter Algorithmus: Halbierungsmethode

19

Effizienzanalyse

Wir zählen die Operationen: Größenvergleich (v), Summe (s), Differenz (s), Zuweisung (z),Test mod 2 (b), Ganzzahldivision durch 2 (b), Verdopplung (b).

• Dekrementieren: 2z + (2z + 2s + v)*x = c1 + c2*x

• Halbierungsmethode:

3z + (a(x)*(z+s) + 3b+2z)*([log2 x] + 1) + v*([log2 x] + 2)

= c1 + c2*[log x]

Hierbei ist 0 < a(x) ≤ 1, und ([log2 x] +1) ist die Länge der Binärdarstellung von x (falls x > 0).

20

1.4    Die O-Notation

Dient zur Beschreibung des Größenwachstums einer Zahlenfunktion; additive und multiplikative Konstanten werden dabei vernachlässigt.

• f = O(g)   genau dann, wenn es ein no aus N und ein c aus R+ gibt, so dass für alle n no gilt: f(n) c • g(n)

(``f wächst höchstens so schnell wie g´´).

Beispiel: f(n) = 8n+2, g(n)= 3n. Dann f = O(g).

Beweis: z.B. mit c = 3 und no = 2.

Beispiel: f = O(1) f = O(n) f= O(n2) f = O(2n)

21

• f = O(g)   genau dann, wenn es ein no aus N und ein c aus R+ gibt, so dass für alle n no gilt: f(n) c • g(n)

(``f wächst höchstens so schnell wie g´´).

• f = (g)  genau dann, wenn g = O(f). (``f wächst mindestens so schnell wie g´´).

• f = (g)  genau dann, wenn f = O(g)  und g = O(f). (``f wächst genauso schnell wie g´´).

• f = o(g)  genau dann, wenn für alle c aus R+ ein no aus N existiert, so dass für alle n no gilt: f(n) < c • g(n).

(``f wächst langsamer als g´´).

22

Satz

Seien     f: N Ro

+  und     g: N R+.Es existiere L := lim_n f(n) / g(n)    (ggf. ist L gleich unendlich). Dann gilt: (i)    g = O(f)    falls L = .(ii)    f = (g)     falls L > 0 und L endlich. (iii)    f = o(g)    falls L = 0.

Man kann einen schwächeren Satz für die Voraussetzung L = limsup n f(n) / g(n) formulieren.

23

Beispiele

Beispiel: f(n)=3n2 + 7n , g(n)= n log 2(n).

lim n f(n)/g(n) = , also f = (g).

Natürlich auch lim n g(n)/f(n) = 0, also g= O(f) und g=o(f).

24

•     Falls h = O(g) und f = O(g+h), so gilt f = O(g). •     Falls c > 0 und f = O(c•g), so gilt f = O(g).

Beispiel:

mit f = O(0.3 n2 + n•log(n))

gilt auch f = O(n2).

Einige Regeln (zur Vereinfachung von O-Termen)

25

Klassifizierung einiger Standardalgorithmen:

Klasse Repräsentanten

O(1) konstant

O(log n) logarithmisch Suchen auf einem Baum von Objekten

O(n) linear Bearbeitung jedes Elements einer Liste

O(n log n) linear-logarithmisch

effiziente Sortierver-

fahren (z.B. HeapSort) O(n2) quadratisch "naive" Sortierverf.

O(nk) polynomiell

O(2n) exponentiell Backtracking-Algorithmen

26

Kapitel 2:  Grundelemente von Programmiersprachen2.1   Syntaktische Elemente 2.2   Typsysteme 2.2.1  Einfache Datentypen 2.2.2  Zusammengesetzte Datentypen 2.2.3  Rekursive Datentypen 2.3   Kontrollstrukturen 2.4   Rekursion 2.4.1  Klassifikation und Beispiele 2.4.2  Umwandlung rekursiver in iterative Verfahren 2.5   Verzweigte Rekursion und Backtracking-Verfahren 2.5.1  Türme von Hanoi 2.5.2  Erzeugung fraktaler Muster durch Turtle-Programme 2.5.3  Backtracking: Hofstadters MU-Puzzle

27

2.1    Syntaktische Elemente

Grundelemente:

• Blöcke (Gültigkeitsbereiche von Vereinbarungen, z.B. der Rumpf einer Funktionsdefinition)

• zusammengesetzte Anweisungen (Schleifen, bedingte Verzweigungen)

• einfache Anweisungen (Zuweisungen, Prozeduraufrufe)

• Ausdrücke (Bedingungen, Terme) • Bezeichner (von Konstanten, Variablen,

Prozeduren/Funktionen) • Konstanten (Zahlen, Zeichenketten)

28

Die syntaktische Struktur eines Programmstücks ergibt sich eindeutig aus einer statischen Analyse (des Programmtextes).

Beschreibung der syntaktischen Strukturen durch kontextfreie Grammatiken (z.B. in Backus-Naur-Form) oder durch Syntax-Diagramme.

29

Beispiel: <ParListe> ::= '(' <ParDeklaration> ')' <ParDeklaration>::= <ParKomp> |

<ParKomp> ';'<ParDeklaration>

<ParKomp> ::= 'var' <Par> ':' <TypBez> |

<Par> ':' <TypBez>

<Par> ::= <ParBez> | <ParBez> ',' <Par>

30

Syntaxdiagramme

31

Term

32

2.2    Typsysteme

Elemente von Typsystemen:• Werte (Belegungen von Variablen, Komponenten von

Ausdrücken, Ausprägungen von Übergabeparametern) • Typen (Mengen von Werten, die unter entsprechenden

Operationen abgeschlossen sind, z.B. ganze Zahlen, true/false, Namen der Monate)

• Ausdrücke (Programmsegmente, die zu Werten evaluiert werden können, z.B. die rechte Seite einer Zuweisung)

• Typkonstruktoren (programmiersprachliche Konstrukte zur Definition neuer (zusammengesetzter) Datentypen)

33

• Statische Typisierung: (Pascal, Modula und Java) Der Typ jeder Variablen und jedes Übergabeparameters

wird im Programm explizit definiert. Die Typprüfung wird zur Übersetzungszeit durchgeführt.

• Dynamische Typisierung: (z.B. Prolog, Lisp, Logo). Variablen und Parameter sind nicht typisiert - wohl aber

deren aktuelle Werte. Ein Wert kann ggf. potentiell unterschiedliche Typen "bedienen" (z.B. kann eine Ziffer als Integer oder Character interpretiert werden). Die Typüberprüfung findet zur Laufzeit statt.

Formen der Typisierung

34

Einige einfache Datentypen

Vordefinierte

Truth-Value = {true, false}

Integer = {..., -2, -1, 0, +1, +2, +3, ...}

Real = {..., -1.0, ..., 0.0, ..., 1.0, ...}

Character = {'a', ..., 'z', 'A', ..., 'Z', ...}

Aufzählungstyp

type Tag = {montag, dienstag, mittwoch, donnerstag, freitag, samstag, sonntag}

35

Elementare Datentypen in Java

36

Typkonvertierungen in Java

• boolean kann nicht in einen numerischen Typ überführt werden.

• Die numerischen Typen bilden eine lineare Ordnung (byte -> short -> int -> long -> float -> double). In dieser Reihe kann ein Wert "niederen" Typs implizit in einen Wert höheren Typs überführt werden. Beispiel:   int n; ... ; float x = n; ...

• Die Überführung eines höheren in einen niederen Typ erfordert einen sog. cast.

• Beispiel:   float x; ... ; x = (float) Math.sin(...); ...                 (da sin einen Wert vom Typ double liefert.)

37

Typumwandlungen in Java

• Mittels der statischen Methode (Funktion) String.valueOf(x) aus der Klasse String können Werte x von einem beliebigen elementaren Typ in einen String überführt werden.

• Die statische Methode Integer.parseInt(String s) aus der Klasse Integer überführt einen String s in einen int-Wert (falls nicht möglich: exception).

• Zu jedem elementaren Typ gibt es eine zugeordnete

Objektklasse (Wrapper-Klasse, Konvertierung erforderlich!). Auf dieser Ebene sind weitere - einheitlichere - Konvertierungsmöglichkeiten definiert.

38

Beispiele

Beispiel: int i = 5; int j = 2; float x = i / j;

ergibt den Wert 2.0 für x.

int i = 5; int j = 2; float x = i / (float) j; ergibt den Wert 2.5 für x.

39

2.2.2    Zusammengesetzte Datentypen

• werden erst im Programm durch Verwendung von Typ-Konstruktoren (record, set, array, ...) definiert.

• Java kennt hiervon nur den Array-Konstruktor;

40

• Verbundtyp (record) in Pascal: allgemeine Form:        

record I1 : T1; ... ; In : Tn end          {Ik: Feldname, Tk: Feldtyp}

• Beispiel: type TelEintrag = record Name:string[20];

Nr : string[12] end

• Wertemenge des hierdurch konstruierten Typs: kartesisches Produkt T1 ... Tn

• Kardinalität: # (T1 ... Tn ) = # (T1 )•....• # (Tn )

41

Explizite Definition von Abbildungen durch Arrays (Java):

Schema: Sei m : I T, wobei I eine endliche Indexmenge,

T der Typ der Werte (Bildmenge) sei.

Für endliche T ergibt sich die Kardinalität: # ( I T ) = # ( T ) # ( I )

Der Ansatz kann iteriert werden, d.h. T kann selbst schon ein Array sein.

42

Beispiel: Labyrinth in Pascal

type dim_x = [1 .. n] ; dim_y = [1 .. m] ; Labyrinth = array dim_x, dim_y of boolean ; var Lab: Labyrinth ;

procedure wand(i: dim_x, j: dim_y): boolean ; begin wand := Lab[i,j] end {wand} ;

Beispiel: Labyrinth in Java ... int Lab[][] = new int[n][m] ; ... /* Initialisierung erfolgt z.B. in Konstruktor-Methode der Klasse */ public boolean wand(int i, int j) { return Lab[i][j] ; }

43

2.2.3    Rekursive Datentypen

Ein Datentyp heißt rekursiv, wenn in seiner Typdefinition der Typ selbst wieder vorkommt; d.h. Werte dieses Typs können wiederum Werte des gleichen Typs als Komponenten enthalten.

Beispiel: Liste von Zahlen: ListofInteger := {nil} + (Integer ListofInteger) Vereinbarung in Pascal: type List = ^ListElem; ListElem = record wert : Integer; nachf : List end;