BIT – Schaßan – WS 02/03

Basisinformationstechnologie

HK-Medien

Teil 1, 10.SitzungWS 02/03

BIT – Schaßan – WS 02/03

Literatur zu Algorithmen und Datenstrukturen

Ottmann, T. / Widmayer, P.: Algorithmen und Datenstrukturen. 3., überarbeitete Auflage. Heidelberg, Berlin, Oxford: Spektrum Akademischer Verlag, 1996.

BIT – Schaßan – WS 02/03

Ein Programm entsteht

Ein Computerprogramm soll ein Problem lösen.Dazu muss das Problem genau beschrie-ben, spezifiziert werden.Danach muss ein Ablauf von Aktionen entworfen werden, ein sog. Algorithmus.Der Algorithmus stützt sich auf die in der Beschreibungssprache vorgegebene Strukturierung der Daten.

BIT – Schaßan – WS 02/03

Spezifikation

Eine Spezifikation ist eine vollständige, detaillierte und unzweideutige Problembeschreibung.

vollständig: alle Anforderungen und relevante Rahmenbedingungen sind angegebendetailliert: Nennung aller Hilfsmittel, insbe-sondere der zulässigen Basis-Operationenunzweideutig: Kriterien, wann eine Lösung akzeptabel ist

BIT – Schaßan – WS 02/03

Beispiel Spezifikation

"Berechne für beliebige Zahlen M und N den größten gemeinsamen Teiler ggT(M,N)."

Vollständigkeit: Welche Zahlen M und N sind zugelassen?Detailliertheit: Welche Operationen sind erlaubt?Unzweideutigkeit: Was heißt berechnen? Wie soll das Ergebnis ausgegeben werden?

BIT – Schaßan – WS 02/03

Vor- und Nachbedingungen

Formale Spezifikation geschieht mittels der Angabe von Vorbedingung P und Nachbedingung Q.P und Q sind logische Aussagen.In {P} und {Q} sind alle relevanten Eigenschaften aufgeführt, die vor Beginn bzw. nach Beendigung des Programms gelten sollen.

BIT – Schaßan – WS 02/03

Beispiel Bedingungen

Vorbedingung:{M,N ∈ ℤ und unveränderlich (=Konstanten) mit 0 < M < 32767 und 0 < N < 32767}Nachbedingung:{z = ggT(M,N), d.h. z ist Teiler von M und N und für jede andere Zahl z', die auch M und N teilt, gilt: z' ≤ z}

BIT – Schaßan – WS 02/03

Algorithmus

Definition:"Ein Algorithmus ist eine detaillierte und explizite Vorschrift zur schrittweisen Lösung eines Problems."

Die Ausführung erfolgt in einzelnen Schritten.Jeder Schritt besteht aus einer einfachen und offensichtlichen Grundaktion.Zu jedem Zeitpunkt muss eindeutig bestimmt sein, welche Schritte als nächstes auszuführen sind.

BIT – Schaßan – WS 02/03

Darstellungsweisen für Algorithmen

Ablauf-/Flussdiagramm

BIT – Schaßan – WS 02/03

Darstellungsweisen (2)

In Pascal:

BEGINx := M ;y := N ;WHILE x <> y DO

IF x > y THEN x := x-y ELSE y := y-x ;

z := x ;END.

BIT – Schaßan – WS 02/03

Darstellungsweisen (3)

In Java:

{ x = M ;y = N ;while ( x != y ) {

if ( x < y ) x = x-y ;else y = y-x ;}

z = x ;}

BIT – Schaßan – WS 02/03

Algorithmen zur Lösung von Spezifikationen

{P} A {Q}"Wenn ein Algorithmus in einer Situation gestartet wird, in der {P} gilt, wird dann, wenn er beendet ist, {Q} gelten."Spezifikation als Gleichung mit einer Unbekannten:"Gesucht ist zu der Spezifikation {P} {Q} der Algorithmus A mit {P} A {Q}."

BIT – Schaßan – WS 02/03

Terminierung

Algorithmen im strengen Sinne müssen nach endlich vielen Schritten terminieren, also beendet sein.

Manchmal ist aber gewünscht, dass ein Algorithmus (ein Programm) nicht von selbst abbricht.Es ist manchmal (aufgrund von Schleifen) nur schwer feststellbar, ob ein Algorithmus in endlicher Zeit zu einem Ende kommt.

BIT – Schaßan – WS 02/03

Formale Eigenschaften von Algorithmen

Korrektheit Aber: Man kann durch Testen die Korrektheit von Algorithmen nicht beweisen, nur deren Fehlerhaftigkeit!Effizienz

benötigter Speicherplatzbenötigte Rechenzeit

BIT – Schaßan – WS 02/03

Effizienzmessung

Möglichkeiten der Messung:mittels eines idealisierten Modellrechners als Referenzmaschine vor allem: Wachstum der Laufzeit bei steigender Komplexität des ProblemsMessung der Komplexität anhand spezifischer, charakteristischer Parameter Unterscheidung von best case, average case und worst case-Szenarien

BIT – Schaßan – WS 02/03

Vom Algorithmus zum Programm

PROGRAM ggT ;CONST M = 84 ; N = 30 ;VAR x,y,z : Integer ;BEGIN

x := M ;y := N ;WHILE x <> y DO

IF x > y THEN x := x-y ELSE y := y-x ;

z := x ;END.

BIT – Schaßan – WS 02/03

Datentypen (3, Wdh.)

Jeder Datentyp ist definiert durch die Menge der zulässigen Werte (Wertebereich) und die Menge der zulässigen Operationen.

Zwei Datentypen heißen strukturgleich, wenn sie denselben Wertebereich besitzen.

BIT – Schaßan – WS 02/03

Datentypen und ihre Operationen

Auf verschie-dene Daten-typen kann man unter-schiedliche Operationen ausführen

BIT – Schaßan – WS 02/03

Operationen auf Datentypen: Boolean

Werte: true, falseOperationen:

and, or, xor: Boolean x Boolean Booleannot: Boolean BooleanTrue, false: Boolean

Gleichungen:true or x = true

BIT – Schaßan – WS 02/03

Operationen auf Datentypen: Integer

Werte: alle ganzen ZahlenOperationen:

+ - * div mod: Integer x Integer Integer- succ pred: Integer Integer0: Integer

Gleichungen:0 + x = xsucc(pred(x)) = xpred(x) = x*y - y

BIT – Schaßan – WS 02/03

Operationen auf Datentypen: Real

Werte: alle realen ZahlenOperationen:

+ - *: Real x Real Real/:: Real x Real Real (x/y) nur definiert für y>0

- exp: Real Realsqrt:: Real Real sqrt(x) nur definiert für x≥0

ln:: Real Real ln(x) nur defniert für x>0

sin, tan,…: Real Real

BIT – Schaßan – WS 02/03

Operationen auf Datentypen: Real (2)

Gleichungen:x + ( y + z ) = ( x + y ) + zx * ( y + z ) = x*y + x*zsqrt(x) * sqrt(x) = xsin(x) / cos(x) = tan(x)…

BIT – Schaßan – WS 02/03

Bedeutung der Datenstruktur

Gut gewählte Datenstrukturen können das Programmieren vereinfachen und die Effizienz steigern.

BEGIN x := M ; y := N ; WHILE x <> y DO

IF x > y THEN x := x mod y ELSE y := y mod x ;

z := x ;END.

BIT – Schaßan – WS 02/03

Operationen auf Datentypen: Char

Werte: Alle ASCII- (bzw. Unicode-) ZeichenOperationen:

succ, pred: Char Charchr: Byte Charord: Char Byte

Gleichungen:ord(chr(n)) = nsucc(pred(n)) = n

BIT – Schaßan – WS 02/03

Operationen auf Datentypen: Strings

Werte: alle ZeichenkettenOperationen:

+: String x String String"": Stringlength: String Integerpos: String x String Integer= <>,… String x String Boolean

BIT – Schaßan – WS 02/03

Operationen auf Datentypen: Strings (2)

Gleichungen:"" + x = xlength(x+y) = length(x) + length(y)…

Aber: in Java dürfen Strings nicht verändert werden!Sie können in einen Puffer (stringBuffer) kopiert, dort verändert und in einen neuen String zurück verwandelt werden.

BIT – Schaßan – WS 02/03

Operationen auf Datentypen: Benutzerdefiniert

Benutzer können in modernen PSS Datenstrukturen konstruieren.Mögliche Werte, Operationen und Gleichungen sind dann festzulegen.Beispiel Datum:

Darstellung durch die Anzahl der vergangenen Tage seit einem "Anfangszeitpunkt"Darstellung durch drei Integers, jeweils für Tag, Monat und Jahr

BIT – Schaßan – WS 02/03

Variablen und Speicher

Je nach Art einer Variable wird unterschiedlich viel Platz im Speicher reserviert.

BIT – Schaßan – WS 02/03

Deklaration

Dazu muss eine Variable in den meisten höheren Programmiersprachen vor der ersten Benutzung deklariert werden.D.h., dem System muss mitgeteilt werden, welche Variablen zur Verfügung stehen sollen, welchen Datentyp und welchen Speicherbedarf sie haben.

BIT – Schaßan – WS 02/03

Initialisierung

Nach der Deklaration einer Variable enthält der zugewiesene Speicherplatz noch keinen oder einen falschen Wert. Es ist daher sinnvoll, jede Variable möglichst früh zu initialisieren, d.h. mit einem Ausgangswert zu versehen.

BIT – Schaßan – WS 02/03

Fehlerhafte Variablenverwendung

Bei der Verwendung von Variablen muss man vor allem auf zwei mögliche Fehlerquellen achten:

TypfehlerSeiteneffekte

BIT – Schaßan – WS 02/03

Typfehler

Typfehler treten auf, wenn Variablen unterschiedlichen Typs verknüpft werden.

Seien x,y,z : Integer r,s : Real u : Charx + 2 * ( y – z ) typkorrektchr(ord(u) + ord('A') typkorrektr * x Real typkorrektx + u Typfehlerlength(s+1) statt length(s)+1 Typfehler, da Ausdruck unsinnig, egal ob s Integer oder String ist

BIT – Schaßan – WS 02/03

Seiteneffekte

Seiteneffekte entstehen, wenn durch die Auswertung eines Ausdruckes der Inhalt der Variablen verändert wird.

(x+1) * (x+1) ersetzbar durch sqr(x+1)(x+1) - (x+1) ersetzbar durch 0In C oder Java kann man (x+1) als ++x schreiben Auftreten eines Seiteneffektes, da x inkrementiert wird, d.h.(++x) - (++x) = -1 !!!

BIT – Schaßan – WS 02/03

Zuweisungen

Eine Zuweisung besteht in der Belegung der Variablen mit konkreten Werten (=Speicherzustand) aus einer Folge elementarer Operationen (=Berechnung), die

einen Ausdruck auswerten,das Ergebnis speichern.

BIT – Schaßan – WS 02/03

Zuweisungen (2)

Auf der rechten Seite einer Zuweisung bezeichnet eine Variable einen Wert, auf der linken Seite steht sie für einen Speicherplatz.Die Zuweisung ist die einfachste Form eines Befehls, einer Anweisung einer Programmiersprache. Eine Anweisung beschreibt einen Effekt, ein Ausdruck einen Wert.

BIT – Schaßan – WS 02/03

Kontrollstrukturen

Kontrollstrukturen sind Folgen von Anweis-ungen, die gezielt und kontrolliert zu neuen komplexeren und abstrakteren Anweis-ungen zusammengesetzt worden sind.Drei grundlegende Konstrukte reichen aus, um alle Algorithmen aufzubauen:

sequentielle Komposition (Verbundanweisung)Alternativanweisungwhile-Schleife

BIT – Schaßan – WS 02/03

Sequentielle Komposition

Sequentielle Komposition ist die Hinterein-ander-Ausführung von Anweisungen.

Syntax in Pascal:BEGIN A1; A2;…; An END

Syntax in C und Java:{ A1; A2;…; An }

Semantik:A1; A2;…;An werden nacheinander ausgeführt.( ohne Sprungbefehle)

BIT – Schaßan – WS 02/03

Sequentielle Komposition Beispiel

Aufgabe: Gib Wechselgeld für einen Betrag zwischen 0 und 100 Cent. Es stehen jeweils genügend Münzen im Wert von 1, 2, 5, 10, 20, 50 Cent und 1 Euro zur Verfügung. Ziel ist es, mit möglichst wenig Münzen auszukommen.

P: { Betrag > 0 }Q: { Betrag = k1*1 + k2*2 + k3*5 + k4*10 + k5*20 + k6*50 + k7*100,mit k1+k2+k3+k4+k5+k6+k7 minimal }

BIT – Schaßan – WS 02/03

Sequentielle Komposition Beispiel (2)

BEGINrest := Betrag ;k7 := rest div 100 ;rest := rest mod100 ;k6 := rest div 50 ;rest := rest mod50 ;k5 := rest div 20 ;rest := rest mod20 ;k4 := rest div 10 ;rest := rest mod10 ;k3 := rest div 5 ;rest := rest mod5 ;k2 := rest div 2 ;rest := rest mod2 ;k1 := rest

END

BIT – Schaßan – WS 02/03

Alternativanweisung

Die Alternativanweisung erlaubt die Auswahl zwischen zwei Anweisungen A1 und A2 in Abhängigkeit von dem Ergebnis eines zuvor auszuführenden Tests.Der Test wird als boolescher Ausdruck B formuliert und heißt Bedingung, A1 heißt if-Zweig, A2 heißt else-Zweig der Anweisung.

BIT – Schaßan – WS 02/03

Alternativanweisung (2)

Syntax in Pascal:IF B THEN A1 ELSE A2

Syntax in C und Java:if (B ) A1 else A2

Semantik:Zunächst wird B ausgewertet. Ist das Ergebnis true, dann wird A1 ausgeführt, andernfalls A2.

BIT – Schaßan – WS 02/03

while-Schleife

Eine Schleife ist ein Programmteil, der wiederholt ausgeführt werden kann, je nachdem, ob eine Bedingung erfüllt ist oder nicht.

Syntax in Pascal:WHILE B DO ASyntax in C oder Java:while (B ) A

BIT – Schaßan – WS 02/03

while-Schleife (2)

Semantik:Die Bedingung B wird ausgewertet. Ist B true, wird die Anweisung A ausgeführt. Anschließend wird B erneut ausgewertet. Sollte B false sein, ist die Schleife beendet. Kurz: Solange B wahr ist, wird A ausgeführt.

BIT – Schaßan – WS 02/03

while-Schleife (3)

In der Form "while B do A" wird B vor der möglichen Ausführung von A geprüft. Die Umkehrung ist möglich, d.h. B erst zu überprüfen, nachdem A einmal ausgeführt worden ist.

Syntax in C oder Java:do { A } while (B ) ;

BIT – Schaßan – WS 02/03

Weitere Schleifenkonstrukte

In manchen Zusammenhängen mag es sinnvoll sein, die Bedingung B weder genau am Anfang noch genau am Ende zu prüfen.

Syntax in Pascal:LOOP REPEAT A1 ; A2 ; …; Ak ; IF B THEN EXIT ; … Ak+1 ; …; An

END UNTIL

BIT – Schaßan – WS 02/03

for-Schleife

Die for-Schleife ist für Fälle vorgesehen, in denen man eine bestimmte Anweisung mehrfach wiederholen will, wobei sich die Anzahl der Wiederholungen vor Beginn der Schleife bestimmen lässt.Eine Variable bezeichnet nacheinander alle Elemente des Intervalls, dessen Grenzen durch zwei Ausdrücke festgehalten sind und das aufwärts oder abwärts durchlaufen werden kann.Diese Variable heißt Laufvariable.

BIT – Schaßan – WS 02/03

for-Schleife (2)

Syntax in Pascal:FOR v := t1 TO t2 DO A ENDSyntax in Java:for { Init1, …, Initk ; test ; Inc1, …,Incn) A

{ Init1, …, Initk while (test) { A

Inc1 ; …; Incn ; }

for { ; B ; } A gleich while ( B ) A