Algorithmen und Datenstrukturen I.

1997-03-04 Einführung

1997-03-05 Aufwandsabschätzung

1997-03-11 Dynamische Datenstrukturen: Listen

1997-03-12 Bäume

1997-03-18

1997-04-08 Suchbäume, Quadtrees, Linearisierung von Bäumen, Stacks

1997-04-09 Hash-Tabellen, Queues

1997-04-15 Heap, Stringsuche

1997-04-16 Graphen

1997-04-22 Sortieren (Selection, Insertion, Bubble-, Merge, Heap-, Quicksort)

1997-04-23 Sortieren (Radix Exchange, Distribution Counting)

1997-04-29 Objektorientierte Programmierung

1997-04-30 OOP

1997-05-23 2. Test

Wichtige Adressen:

ad1admin#cg.tuwien.ac.at AlgoDat 1 via E-Mail

www.cg.tuwien.ac.at/~ad1admin Infos im WWW

news:at.tuwien.lva.cg.ad1 Newsgroup

(wp#cg.tuwien.ac.at Prof. Werner Purgathofer)

Übungsgruppen

mindestens 5 Treffen verpflichtend, beim 1. Treffen Anwesenheitspflicht

Anmeldung: Dienstag, 4. März 12:30 - Montag, 10. März 17:00

2 Beispiele in Turbo Pascal 6.0 (Beispielangaben beim 1. Gruppentreffen)

Vorabgabe und Hauptabgabe

2 Abschnitte, je ein Beispiel, jedes Beispiel bis zum Ende des jeweiligen Abschnitts abgeben

Zuerst Vorabgabe, 2 Wo später Hauptabgabe beim/r TutorIn

Tests: 2 notwendig. Beispieltest statt Abgabe von Beispielen möglich, allerdings viel strengeres Beurteilungsschema (aber auch nicht so schlimm).

Inhalte der Vorlesung

Listen, Bäume, Stack, Queue, Heap, Graphen, Hashtabelle, Stringsuche, Sortierverfahren, OOP

Wiederholung: Felder und Prozeduren

Mehrere gleichartige Daten können in ein Feld (array) zusammengefaßt werden und mittels einer Nummer (Index) angesprochen werden (indiziert werden):

Pascal:

    TYPE Feld=ARRAY[1..n] OF INTEGER;
    VAR a: Feld;

Matrixmultiplikation:

    FOR i:=1 TO n DO
        FOR j:= 1 TO n DO
        BEGIN

            z[i,j]:=0;

            FOR k:=1 TO n DO
                Z[i,j]:=z[i,j]+ x[i,k]*y[k,j]

Wiederholung: Verbunde (Records)

Zusammengehörige verschiedenartige Daten werden zusammengefaßt.

Beurteilung der Eignung von verschiedenen Verfahren

Aufwandsabschätzung:

Kriterien:

• Rechenzeit (hier primäres Kriterium, da kleine Projekte)
• Speicherbedarf

z.B. sequentielle Suche <=> binäre Suche in einem sortierten Array

sequentiell: Mittel: (max+1)/2 Schritte, worst case: max Schritte

binär: Mittel: (ld max) -1, worst case: ld max Schritte.

Aufwand eines Algorithmus (O):

Eine Funktion (ein Algorithmus) g(N) wird als O(f(N)) bezeichnet, wenn es Konstante c₀ und N₀ gibt, sodaß g(N)<c₀*f(N) für alle N>N₀. (Bedeutet: Es gibt eine bestimmte Zahl, ab der das eine Verfahren besser ist)

Wichtige Feststellungen für O

1. O(k*f(N))=O(f(N)): Konstante Faktoren spielen zur Berechnung des Aufwandes keine Rolle.
2. O(log_a N)=O(ld N): Egal, zu welcher Basis der Logarithmus gerechnet wird
3. O(f₁(N)+f₂(N))=O(max{f₁(N),f₂(N)}): Der Aufwand des Gesamtalgorithmus ist nur der Aufwand des langsameren Verfahrens

Beispiele: O(7 N²)=O(N²); O(4 lg²N)=O(ld²N); O(3 N² + N + 100) = O(N²); O(N + ld²N) = O(N)

Übliche O-s von Algorithmen

• O(1): konstant (optimal)
• O(ld N): logarithmisch
• O(ld² N)
• O(SQRT(N))
• O(N): linear
• ...
• O(N²)
• O(2^N): exponentiell: am schlechtesten

Beispiele:

• Einfügen, Entfernen, Suchen (ohne Abbruchbedingung) in einem bereits definierten unsortierten Array: Konstanter Aufwand
• Einfügen/Entfernen {in/aus} ein(em) sortierte{s/n} Array: O(N)
• Sortieren (Minimum-Suchen-Methode: "selection sort") eines bereits definierten Arrays: ca. O(N²)

Kurze Pause: Prof. Purgathofer erzählt (teils burgenländerfeindliche) Witze. In Zukunft sollen die Studierenden selbst aktiv werden, z.B. Jonglierkünste vorzeigen oder selbst Witze erzählen.

Zeiger (Pointer)

Im Unterschied zu einfachen Arrays "wissen" die Datensätze selbst, wo der nächste Datensatz beginnt. Zugriff auf den Datensatz bei einem Zeiger: p^ (= "Dereferenzieren").

1997-03-11 Dynamische Datenstrukturen: Listen

Löschen eines Knotens aus der Liste

Der Speicher des Elements wird freigegeben und der next-Zeiger des vorhergehenden Elements wird auf den nächsten Knoten "verbogen". Wenn die Liste nur in einer Richtung verkettet ist, muß das vorherige Element umständlich gesucht werden. Sonderfall: Anfang der Liste soll gelöscht werden: der Anfang der Liste wird "weitergeschoben".

Vertauschen zweier Elemente

1. Die Elemente sowie ihre Vorgängerelemente suchen. (=> h1, h2, v1, v2)
2. Wenn h1 noch nicht gleich v2 ist (also Hilfsposition1 noch nicht Vorgänger von Hilfsposition2 ist), den Zeiger von Vorläufer2 auf Hilfspos1 stellen.
3. Wenn h2 noch nicht gleich v1 ist, den Zeiger von Vorläufer1 auf Hilfspos2 stellen

Sortierte Listen

Beim Einfügen wird gleich die richtige Position gesucht, damit die Liste sortiert bleibt: Es wird das erste Element gesucht, das größer ist als die einzufügende Information. Vor diesem Element wird mit der bekannten Methode eingefügt. (Sonderfälle: Anfang der Liste; Ende der Liste)

Dadurch wird das Suchen durchschnittlich um die Hälfte beschleunigt, daher ist zu überlegen, ob mehr gesucht oder mehr eingefügt ausgelesen wird (Einfügen ist hier viel aufwendiger als in eine unsortierte Liste)

Doppelt verkettete Listen

Sie "funktionieren in beide Richtungen", brauchen jedoch dementsprechend mehr Speicher. Sie werden z.B. in Textverarbeitungen gerne eingesetzt, da das Einfügen, aber auch die Bewegung in beide Richtungen ziemlich leicht geht und eine Suche sowieso immer sequentiell sein muß.

Nötig ist auch ein Zeiger für das Ende der Liste.

Listen mit mehreren Sortierkriterien

Durch mehrfache Verkettungen werden für die selben Daten mehrere Sortiermöglichkeiten erreicht.

Einfügen: so wie in eine sortierte Liste, nur für jedes Sortierkriterium.

Arrays	Listen
speichersparender bei bekannter Obergrenze	Listenlänge von vornherein nicht begrenzt
schnellerer Zugriff auf Objekte mit bekanntem Index	einige Operationen einfacher
	flexibler

Freispeicherverwaltung

Wenn die Systemprozedur Dispose nicht zur Verfügung steht, muß mensch sie nachbilden. Das passiert mit einer Freispeicherliste, die vom bereits freigegebenen Speicher neuen Speicher zurückgibt, soweit das möglich ist.

1997-03-12 Bäume

Bäume bestehen aus Kanten (die eine Richtung haben) und Knoten. Sie enthalten keine "Kreise", also wieder zusammengewachsene Zweige. Begriffe: VorgängerIn, NachfolgerIn, NachbarIn. Ebene: Knoten, die die gleiche Entfernung von der Wurzel haben und nicht Geschwister sein müssen. Teilbaum: Eine Struktur, die im "echten" Baum auch enthalten ist, und deren Wurzel ein Element des "echten" Baumes ist. Endknoten = Blätter: haben keine NachfolgerInnen.

Binärer Baum

Jeder Zwischenknoten hat höchstens zwei NachfolgerInnen, üblicherweise als li(nks) und re(chts) bezeichnet.

Rekursion

Fundamentales Konzept der Informatik: eine komplizierte oder umfangreiche Aufgabe wird dadurch gelöst, daß mensch sie in einfachere oder kleinere Aufgaben gleichen Typs zerlegt, und mit deren Lösungen die Gesamtaufgabe löst.

Wichtig bei rekursiven Aufrufen:

1. die Daten sollen einfacher oder weniger werden.
2. es muß eine Abbruchbedingung für ganz einfache Daten geben, nach der das Ergebnis direkt zurückgeliefert wird.

"Divide and conquer": die Daten werden in 2 "Hälften" geteilt und für jede Hälfte die Operation ausgeführt. Sobald die Operation "einfach" ist, kann sie direkt ausgeführt werden.

Mittelbare Rekursion: Prozedur A ruft B auf, die wiederum A aufruft: Vorsicht!

Türme von Hanoi: jede beliebige Anzahl von Scheiben läßt sich umlegen, der Aufwand ist 2^N.

Erste Vorabgabe: 8. 4. 18:10

Tutor: Johannes Riemer

Stacks sind sehr gut für die Auswertung von Ausdrücken.

Hash-Tabellen speichern einen möglichst eindeutigen und in der Grundgesamtheit gleichmäßig verteilten Schlüssel, der auf die eigentlichen Daten zeigt. Voraussetzung ist eine Funktion, die aus den echten Daten auf nachvollziehbare Weise (also ohne Zufallszahlen) Hash-Daten generiert. Hash-Tabellen werden wegen des schnellen Zugriffs in Arrays (in Pascal mit fixer Größe) gespeichert.

Heap ist die linearisierte Version eines binären Baumes, bei dem jeder Knoten größer ist als seine Nachfolger.

Heapbedingung: h[i] > h[2i] und h[i] > [2i + 1]

Aufwand bei "einfacher" Stringsuche: O(N) bis O(N*M)

Aufwand bei Mismatched-Character-Algorithmus: theoretisch O(N*M), bei natürlichen Texten ca. O(N/3).

Erkenntnis von Sunday:

Wenn eine Wortposition nicht paßt und wenn der dieser Wortposition folgende Buchstabe nicht im Suchwort vorkommt, dann kann mensch um M+1 Stellen weiterrücken.

Graphen bestehen aus Knoten und Kanten.

Ein Weg zwischen zwei Konten X und Y ist eine Liste von Kanten, die X und Y miteinander verbindet.

Ein einfacher Weg enthält keine Knoten doppelt.

Ein Kreis ist ein einfacher Weg, bei dem lediglich der Anfangsknoten und der Endknoten gleich sind.

Ein kreisfreier Graph heißt Baum, wenn er zusammenhängend ist, und Wald, wenn er nicht zusammenhängend ist.

Ein Gerüst eines Graphen ist ein Teilgraph (Teilmenge der Knoten und Kanten), der alle Knoten enthält und ein Baum ist (also nicht alle Kanten enthält).

Ein Graph heißt

+ komplett: wenn alle möglichen Kanten existieren,

+ dünn: wenn sehr wenige Kanten existieren,

+ gerichtet: wen die Kanten eine Richtung haben,

+ gewichtet: wenn die Kanten Werte (Gewichte) haben.

Implementierung:

Adjazenzmatrix: eine K*K-Matrix mit logischen Werten, in der adjmatr[x,y]=TRUE, wenn eine Verbindung vorhanden ist.

Type GrMatrix = ARRAY [1..K, 1..K] OF BOOLEAN;

Brauchbar, wenn die Anzahl der Kanten nicht viel kleiner ist als die Anzahl der möglichen Kanten.

Adjazenzliste: Für jeden Knoten gibt es eine Liste mit allen durch eine Kante verbundenen Knoten.

TYPE KnoPtr = ^Kno;

Kno = RECORD

data: irgendwas;

next: KnoPtr;

end;

Speicherbedarf: O(K+L) (K: Anzahl der möglichen Verbindungen; L: Anzahl der wirklichen Verbindungen).

Sehr gut, wenn viel weniger Verbindungen existieren, als möglich wäre.

Durcharbeiten von Graphen

Depth-First-Search: Ausgehend von jedem erreichten Knoten werden alle angrenzenden Knoten besucht, die noch nicht besucht wurden. Dazu muß mensch sich merken, welche Knoten bereits besucht wurden: VAR besucht: ARRAY[1..K] OF BOOLEAN;

PROCEDURE DepthRek(no: INTEGER);

VAR hinf: KnoPtr;

BEGIN

IF NOT besucht[no] THEN

hilf:=adjliste[no];

WHILE hilf<> NIL Donnerstag

BEGIN DepthRek(hilf^.no);

hilf:=hilf^.next

END (*WHILE*)

END(*IF*)

END;

Aufwand proportional zur Anzahl der Kanten (O(L)).

• Prüfen des Graphen auf Zusammenhang: DepthRek nur für eine Konten aufrufen, wenn danach alle besucht[i]= TRUE sind, ist der Graph zusammenhängend.
• Prüfen des Graphen auf Kreise: Wenn bei einem zusammenhängenden Graphen die Bedingung IF NOT besucht[i] jemals FALSE ist, enthält er Kreise.
• Suche nach einem Gerüst: Die Menge aller Kanten eines zusammenhängenden Graphen, die nicht zu einem bereits besuchten Knoten führen, bildet ein Gerüst.

Aufgabe in der Pause: 10000, 121, 100, 31, 24, 22, 20, 17, 16, 15, 14, 13, 12, 11, 10, ... (ohne Java-fähigen Browser geht's natürlich nicht!)

Andere Möglichkeit für Depth-First-Search (mit einem Stack):

PROCEDURE Depth (no: INTEGER);

VAR hilf: KnoPtr;

BEGIN

REPEAT besucht[no]:=TRUE;

hilf:=adjliste[no];

WHILE hilf<>NIL Donnerstag BEGIN

IF NOT besucht[hilf^.no]

THEN Push(hilf^.no);

hilf:=hilf^.next; end;

REPEAT no:=Pop

UNTIL StkEmpty OR NOT besucht[no]

UNTIL StkEmpty

END;(*Depth*)

Breadth-First-Search

Nach einem Knoten werden zuerst alle unmittelbaren Nachfolger besucht, bevor deren Nachfolger besucht werden.

Selection Sort

Das kleinste Element des noch unsortierten Teiles wird gesucht und an die erste Stelle gestellt (Durch Vertauschen mit dem ersten Element). Aufwand: N².

Insertion Sort

Die Elemente werden in ein neues Array gleich in der richtigen Reihenfolge eingefügt, Aufwand N².

BubbleSort

BubbleSort arbeitet so, daß benachbarte Elemente jeweils vertauscht werden, solange das linke Element noch größer ist. Dadurch "wandern" kleine Elemente tendentiell nach links, große nach rechts. Der Aufwand ist immer N², aber BubbleSort ist bei kleinen Datenmengen (bis ca. 20 Elemente) manchmal schneller als aufwendige Verfahren.

Merge Sort

wird eingesetzt, wenn zwei sortierte Teilmengen zusammengefaßt werden. Vorgehensweise:

1. das jeweils erste Element aus den Teilmengen wird verglichen, das kleinere kopiert.
2. in der kopierten Teilmenge wird weitergeschaut, ob das nächste Element kleiner ist als das erste Element der anderen Menge.
3. usw

Dieses Verfahren (Aufwand N) funktioniert zwar nur im angesprochenen Spezialfall, aber ein beliebiges Array kann durch rekursive Aufrufe in kleinste Teile aufgeteilt werden. Dann ist der Aufwand N * ld N.

Proc MergeSort(li, re: Integer);

var Mittwoch: Integer;

Begin

if li < re then begin

mi:=(li+re) DIV 2;

MergeSort(li, mi);

MergeSort(mi+1, re);

Merge(li, mi, re);

end

end;(*MergeSort*)

HeapSort

In ein Heap (das sehr effizientes Einfügen und Entfernen des größten Elements erlaubt) werden erst einmal alle Daten eingetragen und dann rückwärts wieder ausgelesen. Der Aufwand ist N * ld N, aber es ist ein gleich großer Speicher notwendig.

QuickSort (angeblich genial)

(Hoare, 1960) Klassisches Divide & Conquer-Verfahren.

In jedem Schritt wird ein Element auf seinen endgültigen Platz gebracht. Davor stehen nur kleinere, danach nur größere.

Ausartung: Wenn zufällig immer der kleinste oder größte Datensatz erwischt wird, ist der Aufwand N²/2

Radix Exchange Sort

Basiert auf der Binärrepräsentation der Zahlen. Einsetzbar, wenn Zahlen sortiert werden und der Wertebereich bekannt ist. Der Vorteil ist, daß Zahlen nicht verglichen werden müssen, sondern gleich bekannt ist, wo sie in der Folge stehen. Aufwand theoretisch N, aber die Differenz zwischen der Obergrenze des Wertebereichs und der größten Zahl fällt stark ins Gewicht. Außerdem kann dieses Verfahren nicht ausarten.

Distribution Counting

Es existiert ein Feld, das mit seinem Indexbereich den gesamten Wertebereich (Der natürlich ziemlich klein sein sollte) der Schlüssel überdeckt. Dann werden alle Elemente einfach an "ihre" Stelle eingetragen und dort wird ein Zähler für die Anzahl der Elemente erhöht. Anschließend wird das Array für den Definitionsbereich von unten nach oben durchgelesen und die entsprechende Anzahl von Werten ins sortierte Array eingefügt.

Der Aufwand ist (N + max), d.h. bei einem großen Definitionsbereich und wenigen zu sortierenden Werten ist dieses Verfahren allen anderen deutlich unterlegen. Bei sehr großem Definitionsbereich (z.B. Long-Zahlen) ist der Speicherbedarf für praktische Anwendungen zu groß.

Entwicklung der Programmiersprachen

1. Assembler
2. Strukturierte Hochsprachen (Algol, C, Pascal...)
3. ADT(=Abstrakte Datentypen)-Sprachen (Modula2, Turbo Pascal ab 4.0...)
4. OOP-Sprachen (C++, Oberon, Turbo Pascal ab 5.5, Visual Basic ab 4.0, Java...)

Objekte

Objekte bestehen aus Daten (Eigenschaften) und Methoden (Fähigkeiten).

Kommunikation mit Objekten: Nachricht (message) + Parameter => Objekt => Reaktion (+ Rückgabewerte)

Organisation von Objekten: Klassen und Instanzen

• Klasse: Gruppe von Objekten mit gleichen Eigenschaften und Fähigkeiten
• Instanz: Ausprägung einer Klasse

Klassen

• Objekte werden hierarchisch gegliedert => baumförmige Struktur
• Objekte mit gleichen Eigenschaften und Fähigkeiten werden zu gemeinsamer Superklasse (Oberklasse) zusammengefaßt. Spezielle Ausprägungen eines Objekts werden zur Subklasse (Unterklasse).

Vererbung (inheritance)

Eigenschaften und Fähigkeiten werden den Subklassen übertragen, diese können sie aber neu implementieren.

Regeln der Vererbung

• Subklasse erbt alle Instanzvariablen und Methoden der Superklasse
• Subklasse kann neue Instanzvariablen und Methoden definieren
• Bestehende Methoden können überladen werden (overloading)
• Vererbte Instanzvariablen dürfen in der Subklasse nicht neu definiert werden

Vererbung in Pascal: TYPE SubKlasse = OBJECT(Superklasse)

Konstruktoren und Destruktoren

Konstruktor: Methode zur Initialisierung eines Objekts

Destruktor: Methode zum ordentlichen Löschen des Objekts

Schlüsselwort CONSTRUCTOR bzw. DESTRUCTOR statt PROCEDURE

Guter Stil: immer beide implementieren und aufrufen!

Polimorphismus und virtuelle Methoden

• Motivation: Spezialisierung durch Vererbung
• Typkompatibilität von Objekten: Subklasse erbt alles von Superklasse
• Subklasse dadurch zu Superklasse kompatibel
• Warum Methoden überladen?
  • Idee des Polymorphismus (Vielgestaltigkeit): eine Methode tritt in vielerlei Gestalten auf
  • selber Name der Methode in allen Klassen, je nach Klasse unterschiedliche Implementierung
  • einheitliches Interface für alle Klassen

Problem bei Polimorphismus in Pascal: Wenn mit einem Pointer auf die Superklasse gearbeitet wird, wird immer (also auch bei Subklassen) die Methode der Superklasse aufgerufen!

"Lösung": Schlüsselwort "VIRTUAL" nach Methoden, die immer neu definiert werden; immer Constructor (für die Initialisierung des Laufzeitsystems) notwendig.

Beispiel:

TYPE Haus = OBJECT

CONSTRUCTOR Bau;

FUNCTION Energie: REAL; VIRTUAL;

FUNCTION Kosten: REAL;

END;

Wohnhaus = OBJECT(Haus)

CONSTRUCTOR Bau(leute: INTEGER);

FUNCTION Energie: REAL; VIRTUAL;

END;

HausPtr = ^Haus;

WohnhausPtr = ^Wohnhaus;


CONSTRUCTOR Haus.Bau; BEGIN END;

CONSTRUCTOR Wohnhaus.Bau;

begin einwohner:=leute; END

FUNCTION Haus.Kosten;

BEGIN

Kosten:=500 + Energie * 1.5;

END;


VAR p: HausPtr;

....

p:=New(WohnhausPtr, Bau(12));

x:=p^.Kosten;

Wohnhaus.Kosten ruft Wohnhaus.Energie auf.

Rat: zuerst alles VIRTUAL definieren, und erst beim nachträglichen Optimieren ausgewählte Methoden unvirtualisieren.

Abstrakte Basisklassen

• Platzhalterklassen nahe Wurzel der Hierarchie
• nur zu Design-Zwecken
• definieren abstraktes Interface
• "halbfertig": dürfen nie instanziert werden
• Trick: irrtümliches Instanzieren generiert Laufzeitfehler

Fragen:

1. (10 Pkt.)

TYPE
    A = OBJECT
        FUNCTION D(v: INTEGER): INTEGER; VIRTUAL;
        FUNCTION E: INTEGER;
    END;(*A*)

    B = OBJECT(A)
        FUNCTION D(v: INTEGER): INTEGER; VIRTUAL;
    END;(*B*)
(...)
FUNCTION A.D;
BEGIN D := v * 2; END;

FUNCTION A.E;
BEGIN E := D(3); END;

FUNCTION B.D;
BEGIN D := v + 1; END;

Was liefert Ainstanz.E + Binstanz.E ?

Welche Funktion wird wie oft aufgerufen?

2. a. (10 Pkt.) Gegeben sind ein verbesserter BubbleSort-Algorithmus und ein Integer-Array: In eine Tabelle muß der Inhalt des Arrays nach jedem Durchlauf der inneren Schleife eingetragen werden.

2. b. (10 Pkt.) Aufwandabschätzung eines QuickSort-Algorithmus: Gegeben ist, wie lange die Sortierung eines Arrays mit 100, 400, 1000, 1500 Elementen gedauert hat, Frage: wie lange dauert es mit 2000 Elementen? (O(QuickSort = 1,386 N * ld N))

3. a. (10 Pkt.) Ein Graph ist aufgezeichnet, es muß ein Gerüst eingezeichnet werden. Ist der Graph ein Baum? zusammenhängend? kreisfrei? ein Wald? Eine Adjazenzliste zeichnen.

3. b. (10 Pkt.) Eine Funktion soll geschrieben werden, die ermittelt, ob ein gerichteter ungewichteter Graph ein Baum ist.