Beschreiben Sie den Zusammenhang Algorithmus - Datenstruktur!

3 Abstraktionsebenen: 1) Mathematik 2) Algorithmik, 3) Programmierung, 1) Funktion, 2) Algorithmus, 3) Prozedur / Funktion, 0) ADT (Abstrakter Datentyp), 1) Algebra (konkreter Datentyp), 2) Datenstruktur, 3) Typ / Modul / Klasse, Spezifikation - Implementierung

1

Unterscheiden Sie die 3 Abstraktions-ebenen für Algorithmen!

mathematische Ebene (was wird berechnet), algorithmische Ebene (wie wird es berechnet, umgangssprachliche Skizze), Abstraktion, unabhängig von Programmiersprache, programmier-sprachliche Ebene

2 / 3

Beschreiben Sie Notations-Konstrukte für die Beschreibung von Algorithmen!

Notationen für Kontrollstrukturen: if - then - fi, if - then - else - fi , for - do - od, while - do - od, andere Möglich-keiten: if - then - endif, oder if (<Be-dingung>) {<Anweisungen>},

4 / 5

Welche Qualitätskriterien gibt es für Algorithmen?

Korrektheit, einfach zu verstehen, ein-fach zu implementieren, Laufzeit, Platzbedarf

6

Lassen sich diese Kriterien immer gleichgut erfüllen?

nein, Abwägung (trade-off)

6

Wie läßt sich die Laufzeit eines Algo-rithmus abschätzen / bestimmen?

Elementaroperationen zählen, Algorith-musverhalten durch Funktion darstel-len: Anzahl der Elementaroperationen, Komplexität der Eingabe

6

Was sind Elementaroperationen, was sind keine? Grenzen Sie ab!

ja: Zuweisung, Vergleich, Arithmetische Operation, Arrayzugriff | nein: Schleifen, Prozeduraufruf (insbes. Rekursion)

7

Nennen Sie 2 Maschinenmodelle zur Berechnung der Komplexität von Algo-rithmen!

Turingmaschine, RAM (Random-Access-Maschine): [Programm- und Datenspeicher, kleiner Satz von Ins-truktionen, Register, Akkumulator, Ope-rand, Programmzähler, Elementarope-ration = RAM-Instruktion, Kostenmaß 1, sehr große Zahlen, logarithmisches Kostenmaß]

7

Was ist der unterschied zwischen RAM und realRAM?

realRAM, vollständige reelle Zahl in einer Speicherzelle, trigonometrische Funktionen und Wurzelziehen auch Kostenmaß 1, für geometrische Algorith-men

8

Werden zur Laufzeitbestimmung eines Algorithmus wirklich alle Elementarope-rationen gezählt?

nein, Abstraktionsschritte:

9

Nennen Sie die unterschiedlichen Ab-straktionsschritte!

1) keine Unterscheidung der Elementar-operationen

2) Menge aller Eingaben aufgeteilt in Komplexitätsklassen (Laufzeit T(n) bei Eingabe der Größe n)

3) Abstraktion innerhalb der Komplexi-tätsklasse, Spezialfälle: best case, worst case, average case, Häufigkeit der Eingaben, gewichtetes Mittel, häufig nur worst-case-Analyse

4) Weglassen der multiplikativen und additiven Konstanten, O-Notation

9 - 12

Was versteht man unter der Ordnung einer Funktion / eines Algorithmus (O-Notation)?

f = O(g) [präzise: f Î O(g)]: f wächst höchstens so schnell wie g, O(g) ist die Menge aller Funktionen f für die f = O(g) gilt, Grenzwert (limes) von f(n) / g(n) existiert, O-Notation vergröbernde Be-trachtung von Funktionen: eliminiert Konstanten, bildet obere Schranken

12 / 13

Wie wird die O-Notation für die worst-case Abschätzung der Laufzeit von Algorithmen eingesetzt?

Laufzeit jeder Elementarop. = O(1), Laufzeit von Konstanten Folgen von EO's = O(1), Sequenz: Addition von O-Notationen, dominante Funktion, Schlei-fe, jeder Durchlauf andere Laufzeit: auf-summieren, Anzahl Schleifendurchläufe abhängig / unabhängig von n, bedingte Anweisung: aufsummieren, ggf. verein-fachen, Prozeduren & Subalgorithmen gesondert berechnen

14 / 15

Beschreiben sie die verschiedenen Ordnungen der O-Notation und dafür typische Algorithmen!

O(1) konstant, O(log n) logarithmisch, Suchen auf einer Menge, O(n) linear, Bearbeiten jedes Elementes einer Men-ge, O(n log n), gute Sortierverfahren, O(n log² n), ..., O(n²) quadratisch, pri-mitive Sortierverfahren, O(n^k) polyno-miell, ..., O(2ⁿ) exponentiell, Backtrak-king-Algorithmen

16 / 17

Wie funktioniert "binäres Suchen"?

nur in sortiertem Array, rekursiver Algo-rithmus: 1) Mitte des Teilarrays bestim-men, 2) Suchwert mit Wert der Mitte ver-gleichen, 3) true: Abbruch, false: rekur-siver Aufruf mit mit halbiertem Teilarray

18

Wie wird die Laufzeit eines rekursiven Algorithmus berechnet?

Rekursionsgleichung [z.B.: T(0)=a, T(n)=b + T(n/2), a=Laufzeit ohne rekur-siven Aufruf, b=Laufzeit bis zum rekursi-ven Aufruf, n=Arraygröße], O(log n)

19

Wie ist die allgemeine O-Notation defi-niert?

f = W(g), falls g = O(f), "f wächst mindes-tens so schnell wie g", f = Q(g), falls f = O(g) & g = O(f), "f und g wachsen in gleicher Größenordnung", f = o(g), falls Folge (f(n)/g(n)) = Nullfolge, "f wächst langsamer als g", f = w(g), falls g = o(f), "f wächst schneller als g"

20

Wie wird die Komplexität eines Prob-lems charakterisiert?

W-Notation, untere Schranke für Funk-tionswachstum, Laufzeit aller Algorith-men eines Problems

21

Wann ist ein Algorithmus "optimal"?

optimaler Algorithmus: obere Schranke = untere Schranke

21

Eine Zahlenfolge s1,...,sn sei in einem Array der länge n dargestellt. Beschrei-ben Sie rekursive Algorithmen (a) mit Rekursionstiefe O(n), (b) mit Rekur-sionstiefe O(log n), die die Summe dieser Zahlen berechnen!

1A2

Wann kann ein Algorithmus mit einer Laufzeit von O(n³) besser sein als einer mit Laufzeit O(n²)? Erläutern Sie die Problematik!

kleine Eingabemengen: schlechter Al-gorithmus ggf. besser, sehr große Kon-stanten | große Eingabemengen: nur Algorithmen der O(n) oder O(n log n), exponentielle Algorithmen O(2ⁿ) nur bei sehr kleinen Eingabemengen (z.B. <20)

23

Was ist eine Algebra (ein Datentyp)?

1) mehrsortige (heterogene) Algebra: System, bestehend aus Objektklassen mit darauf ausführbaren Operationen

2) universale Algebra: nur eine Objekt-klasse

24

Wie beschreibt man eine Algebra?

Signatur, Objektmengen Sorten (sorts), Operationen (ops) incl. Opera-tionsargumente und Ergebnis-Objekttyp, nur Syntax, keine Semantik, Träger-menge, Funktionen

24 / 25

Nennen sie mögliche Vorgehensweisen zur Algebren-Beschreibung?

2 Möglichkeiten: 1) Spezifikation als Al-gebra, direkt Trägermengen und Funktionen angeben (mathematische Notation), Charakteristik muss erkenn-bar sein, 2) Spezifikaiton als abstrakter Datentyp, Trägermengen und Operatio-nen anhand interessierender Aspekte charakterisieren, Gesetze (axioms): Gleichungen über Ausdrücke, implizit all-quantifiziert

25 / 26

Welchen Zusammenhang gibt es zwischen abstrakten Datentypen und Algebren?

Modell: Algebra, die Signatur und Gesetze eines ADT erfüllt, polymorpher Datentyp: mehrere Modelle, monomor-pher Datentyp: nur ein Modell (Modell ist dann isomorph)

26

Nennen sie Vor- und Nachteile der Spezifikation von abstrakten Datenty-pen!

Vorteile: Datentyp nur soweit festlegen wie erforderlich, größere Implementie-rungsfreiheit, polymorphe Datentypen, präzise formale Gesetz-Beschreibungs-sprache (Entwurfswerkzeuge)

Nachteile: komplexe Anwendungen - große Gesetz-Anzahl, intuitive Bedeu-tung oft schlecht erkennbar, Charakteri-sierung mit Gesetzen schwierig, Voll-ständigkeit, Widerspruchsfreiheit

26 / 27

Wie wird eine Algebra / ADT in eine Datenstruktur umgesetzt (algorithmi-sche Ebene)?

Festlegen des logischen Speicherme-diums (z.B. Array, Record, Liste, Que-ue, Stack...) und ggf. Hilfstypen/-varia-blen, Operationen werden Algorithmen

28

Welche Sprachkonstrukte gibt es in den verschiedenen Programmiersprachen zur Implementierung eines Datentyps?

Klassen (SIMULA, SMALLTALK, Java), Module (Modula-2), Packages (ADA), Records (Pascal),...

29

Welche Arten von Modulen gibt es in Modula-2, und welche Aufgaben haben sie?

definition module (für Benutzer sichtbar, entspricht Algebra-Signatur), implementation module (für Benutzer verborgen, entspricht Trägermengen und Funktionen einer Algebra)

30

Was ist ein Algorithmus?

Verfahren zur Lösung eines Problems, Zuordnung: Ergebnis zu Element einer Klasse von Probleminstanzen (mögliche Eingaben), Schritte, klar und eindeutig beschrieben, mit endlichem Aufwand in endlicher Zeit ausführbar (anders: math. Funktion!), soll für jede Eingabe termi-nieren (nicht immer möglich!)

32

Was ist eine Signatur?

Paar (S, S), S = Menge von Sorten, S = Menge von Operationen / Vereinigungs-menge S_w,s in einer Mengenfamilie { S_w,s | w Î S*, s Î S}

33

Was ist eine mehrsortige (heterogene) Algebra?

System von Mengen und Operationen, gegeben durch Signatur (S, S), Träger-menge A_s für jedes s Î S und Funktion f_s für jedes s Î S

34

Was ist ein abstrakter Datentyp?

Signatur (S, S), Gleichungen (Axiome)

34

Was ist eine Datenstruktur?

Implementierung eines Datentyps auf algorithmischer Ebene, Datentypen nutzen andere Datentypen, vollständig wenn alle benutzten Datentypen imple-mentiert, Hierarchie, alle Implementie-rungen gestützt auf elementare Daten-typen einer Programmiersprache

34

Ist ein Array ausschließlich als Datenstruktur anzusehen?

eigenständiger Datentyp (aus Anwen-dersicht), programmiersprachliches Werkzeug mit fester Implementierung

39

Nennen Sie wesentliche Werkzeuge zur Konstruktion von Datenstrukturen!

Arrays (reihen variabel viele Objekte eines Typs aneinander, Zugriff in O(1) Zeit), Records (Objekte verschiedenen Typs zu neuem Objekt zusammenfas-sen, auf Komponenten-Objekte zugreifen), Zeiger (Objekte referenzie-ren), Konzepte zur Bildung von Typen: 1) atomare Typen, 2) Typkonstruktoren / strukturierte Typen, 3) Zeigertypen

39

Was sind "atomare Typen"?

atomare Datentypen, (z.B.: integer, real, boolean, char, ... ), Operationen, (z.B.: +, -, *, /, div, mod, and, or, not, =, <, >, ... ), unterstellte Ordnung (z.B. bei char: ASCII-Alphabet), Wert eines ato-maren Typs: 1 Speicherwort, Byte o. Bit

40

Was sind Aufzählungstypen?

vom Programmierer definiert, [z.B.: type Wochentag = (Mo, Di, Mi,...)], Operatio-nen: Nachfolger (SUCCessor), Vor-gänger (PREDecessor), meist Abbil-dung auf IN

41

Was sind Unterbereichstypen?

Beschränkung eines Standardtyps auf bestimmten Wertebereich, z.B.: type T = [min..max], Fehlzuweisungen vom Com-piler oder vom Laufzeitsystem entdeckt

41

Welche Aufgabe haben Typkonstruk-toren / Strukturierte Typen ?

wesentliche Konstruktoren: Array, Record, [Aneinanderreihen der Reprä-sentationen (Bytefolgen, Speicherblök-ke)der zusammenges. Objekte], von geringerer Bedeutung: Set

42

Was ist ein Array?

Felder von Werten, fester Grundtyp, zugriff über Index, Index = Unterbereich von integer, wesentliche Operation: Selektion (Index liefert Grundtyp), Wertebereich: homogenes, kartesi-sches Produkt des Grundtyp-Wertebe-reichs, Adressierung: [Position 1. Ele-ment + (Index - 1) * Elementgröße], Zugriff in O(1) Zeit, auch mehrdimensio-nal, Kontrollstruktur: for-Schleife

42 / 43

Was ist ein Record?

Datentyp aus gegebener Menge ver-schiedener Datentypen, wesentliche Operation: Selektion, Wertebereich: heterogenes, kartesisches Produkt der Grundtyp-Wertebereiche, Adressie-rung: Grundtypen-Größen bekannt, für jeden Sektor: offset berechnen, Kompo-nentenzugriff in O(1) Zeit, Kontroll-struktur: with-Anweisung: with - do - od

45 / 46

Was ist ein Set?

Datentyp, deren Werte = Mengen von Werten eines Grundtyps, [type T = set of T₀], nur atomarer Grundtyp mit kleiner Kardinalität, Operationen: Durchschnitt, Vereinigung, Differenz, Elementtest, Wertebereich: Potenzmenge des Grundtyps, Adressierung: Bitvektor über wenige Speicherwörter, schnelle Operationen, O(1) Zeit

47

Welche Aufgabe haben Zeigertypen / Zeigervariablen?

andere Typen: (statisch, Größe & Struk-tur nicht änderbar), Zeiger (Pointer), Konstruktion dynamischer Datenstruk-turen, Verweis auf Objektrepräsentation, Adresse, Wertebereich (dynamisch): Menge aller Adressen von Objekten des Grundtyps, spezieller Wert: nil, neue Variable = Speicherplatzreservierung, Zeigervariable ® Adresse, Operatio-nen: Zuweisung, Vergleich, Dereferen-zierung, Nachteile: Struktur nur zur Laufzeit änderbar, ungewolltes "Abkop-peln" der Objekte von der Struktur | Gar-bage Collection: Freigabe von Variablen, ggf. vom Benutzer (dispose-Anweisung)

49

Nennen und charakterisieren Sie die Ihnen bekannten grundlegenden Datentypen!

1) Listen (einfach / doppelt verkettet), 2) Stacks (LIFO), 3) Queues (FIFO), 4) Abbildungen (Abstraktion eines Arrays) und 5) Bäume (binäre Bäume, Suchbäu-me, AVL-Bäume, ...)

53

Erläuter sie den Begriff "Sequenz"!

Oberbegriff für Folgen / Listen, endliche Folge von Objekten, Ordnung definiert, Vorgänger, Nachvolger, Duplikate erlaubt, einelementige / leere Sequenz, Konkatenationsoperator

53

Welche zwei Listen-Modelle werden im Kurs vorgestellt?

1) Listen mit Operationen: first (erstes Element), rest (alle Elemente außer das Erste), append (Element vorne hinzu-fügen), concat (2 Listen verketten), empty, isempty (jede Datenstruktur!)

2) Listen mit expliziten Positionen, Positionen durch Zeigerwerte realisiert, Position "p0" vor der Liste, Operationen: concat, insert (Einfügen an bestimmter Position), delete (Entfernen) find (liefert Position des 1. gesuchten Elementes), retrieve (Ausgabe des Elementes einer best. Pos.) | Operationen zur Zeiger-manipulation: front (p0, vor dem 1. Ele-ment), last (letztes Element), bol (bool: begin of list), eol (bool: end of list), next, previous

54

Welche Gemeinsamkeiten haben die beiden Modelle?

Datentypen parametrisiert mit Element-typ und Funktionstyp, Typkonstruktor list(elem), Positionen nur durch nachse-hen in Liste, Einfügen / Entfernen: Posi-tionen der Folgeelemente bleiben gültig

55 - 57

Wie kann eine Liste implementiert werden?

1) Doppelt verkettete Liste, Zeiger auf Nachfolger- (succ) und Vorgänger- (pred) Element, Listenkopf-(pred) zeigt auf letztes Element, Einfüge- und Entferne-Operationen, Elemente können verloren gehen, bei "concat" wird 1 Lis-tenkopf freigegeben

2) Einfach verkettete Liste, nur Zeiger auf Nachfolger, weniger Speicherplatz, grundsätzl. Zeiger auf Vorgänger (unter-stützt delete), 1 Zeiger auf (vor-)letztes Element (unterstützt "last" und "concat"), Positionszeiger unter Änderungen insta-bil, bei "delete" 3 Fälle: a) p = einziges Element, b) p = letztes Element, c) p = nicht letztes Element

3) Sequentielle Darstellung im Array, Listenelemente in aufeinanderfolgende Zellen, ungenutzes Stück, Zeiger durch Adressen im Array (Array-Indizes) erset-zen, Vorteile: einfach, keine expliziten Zeiger nötig, Nachteile: aufwändiges Einfügen und Entfernen, instabile Posi-tionszeiger, vorher festgelegte Maximal-größe (Speicherplatzverschwendung, unflexibel)

4) Einfach oder doppelt verkettete Liste im Array, gleichartige Elemente, viele Listen in einem Array möglich, Programmierer verwaltet freie Zellen (sonst Laufzeitsystem), ggf auch freie Zellen verketten, Zelle 0 = nil-Pointer, Nachteile: festgelegte Maximal-grösse, Vorteile: Laufzeit- und Betriebssystem-aufrufe werden vermieden ("new" und "dispose" sehr schnell), komplette Struk-tur kann extern gespeichert werden

58 - 62

62 - 65

66

Beurteilen Sie die Implementierungen von Listen nach dem Platzbedarf und der Laufzeit ihrer Operationen!

Zeit: doppelt verkettete Listen: find O(n) alle anderen O(1), einfach verkettete Listen (mit Last-Zeiger): previous und delete (im Einzelfall) O(n), alle anderen O(1), Platz: explizit verkettete Strukturen: O(n)

69

Was ist ein Stack?

Stack (Stapel) Spezialfälle von Listen, Operationen: top (= first), pop (= rest), push (= append), (Standardbeispiel für ADT), beliebteste Implementierung: sequentielle Darstellung im Array, ver-schieben von Elementen unnötig, LIFO-Struktur (last in first out), Anwendungsgebiete: Bearbeitung von Klammerstrukturen, z.B.: arithmetische Ausdrücke, geschachtelte Prozedurauf-rufe (Aktivierungs-Records, je Prozedur-inkarnation speichern: Rück-sprungadresse, Parameter, lokale Varia-blen), Simulation rekursiver Prozeduren

70 - 74

Wie können rekursive Prozeduren simmuliert werden (wenn die Program-miersprache dieses Konstrukt nicht anbietet)?

1) Sprungmarken einfügen (am Anfang des Programms, hinter jedem rekursiven Aufruf)

2) Stack definieren (Elemente: Parame-tersatz, lokale Variablen, Sprungmarke / Rücksprungadresse)

3) vor 1. Sprungmarke leeren Stack ini-tialisieren

4) rekursive Aufrufe durch folgende Aktonen ersetzen: a) Parameterwerte, Variablen und Sprungmarke auf Stack legen, b) Parametern neue Werte zuwei-sen, c) zu Sprungmarke 1 gehen

5) bei Programmende Stack prüfen und ggf. zu Folgemarke zurückkehren

74 - 77

Was sind Queues?

Queue ((Warte)-Schlange), spezielle Liste, Elemente an einem Ende ange-fügt, am anderen entnommen, FIFO-Struktur (first in first out), Operatio-nen: front (= first), enqueue (= "rear append"), dequeue (= rest), beliebte Implementierung: sequentielle Darstellung im Array, zyklisch, Anwen-dungsgebiete: Warteschlangen (Pro-zesse, Nachrichten, Druckaufträge...) in Betriebssystemen, ...

77 - 79

Was ist unter einer Abbildung - im Sinne von Datenstrukturen - zu verstehen?

Zuordnung, Element des Argument-wertebereichs (domain), Element des Zielwertebereichs (range), 2 Möglich-keiten: 1) prozedurale Auswertung, 2) Speicherung (Datentyp: "mapping"), spezieller Wert "^" (undefiniert), Implementierungen: direkt in Array (wenn Domain-Typ endlich und skalar), sonst in Listen

79 / 80

Was sind binäre Bäume?

Definition 3.5: [leerer Baum = binärer Baum, wenn x = Knoten und T1, T2 = binäre Bäume, dann Tripel (T1, x, T2) = binärer Baum], Wurzel, linker Teilbaum, rechter Teilbaum, Blatt, innerer Knoten

Anwendungsbereich: hierarchische Beziehungen zwischen Objekten, Klammerstrukturen (z.B. arithmetische Ausdrücke), Knoten, Kanten (Relation auf Knotenmenge), Vater, (maximal 2) Söhne (Kinder), Brüder (Geschwister), Pfad, Vorfahren (ancestors), Nachfah-ren (descendants), Pfadlänge = Kan-tenanzahl, Baumhöhe = längste Pfad-länge, Knotentiefe = Pfadlänge Wurzel - Knoten, bin. Baum mit n Knoten: maxi-male Höhe: n - 1 = O(n), minimale Hö-he: ëlog nû = O(log n), vollständiger bin. Baum: maximale Knotenzahl bei Höhe h, rekursive Strukturen, Zeigerstrukturen, verkettete Strukturen

80 - 86

Auf welche Arten kann man eine lineare Ordnung auf die Knoten eines Baumes definieren?

inorder ((l, x, r)) = ino.(l) <x> ino.(r)

preorder ((l, x, r)) = <x> preo.(l), preo.(r)

posto. ((l, x, r)) = posto.(l), posto.(r) <x>

86

Welche Implementierungsmöglichkeiten bieten sich für binäre Bäume an?

Implementierung mit Zeigern, Array-Einbettung, Array-Inidizes = Zeiger oder ohne explizite Zeiger: Index (p) = i, In-dex (p.left) = 2i, Index (p.right) = 2i+1

87 - 89

Wie unterscheiden sich binäre Bäume von allgemeinen Bäumen

Definition 3.12: [einzelner Knoten x = Baum, wenn x = Knoten und T1, ..., Tk = Bäume, dann (k+1)-Tupel (x, T1, ..., Tk) = Baum], beliebige Anzahl von Söhnen, Grad eines Knotens = Sohnanzahl, Grad eines Baumes = maximaler Kno-tengrad, Wald = Menge von Bäumen mit disjunkten Knotenmengen, Baum mit n Knoten:, maximale Höhe: n - 1 = O(n), minimale Höhe: ëlog_d nû = O(log_d n), Implementierung: über Arrays (Voraussetzung: maximaler Grad d, sons[i] = Zeiger auf i-ten Sohn im Array speichern, schlecht, wenn Knotengrad stark variiert), über Binärbäume, Zeiger auf linkesten Sohn und rechten Bruder, Nachteil: nur indirekter Zugriff über Geschwister, Vorteil: keine Speicherplatzverschwendung

89 - 92

Welche Datentypen zur Mengendar-stellung kennen Sie?

Mengen mit Durchschnitt, Vereini-gung und Differenz: a) Bitvektor, b) Ungeordnete Liste c) geordnete Liste Mengen mit INSERT, DELETE, MEM-BER: Dictionaries: a) Hashtables (has-hing), b) binäre Suchbäume, c) AVL-Bäume, d) B-Bäume, e) Priority Queue

97

Wie lassen sich Mengendarstellungen implementieren, die die Operationen Durchschnitt, Vereinigung und Differenz unterstützen?

nötige Operationen: empty, insert, enumerate (Auflisten aller Elemente), union (Vereinigung), intersection (Durchschnitt), difference, Implemen-tierungen (Annahme: linear geordneter Grundwertebereich):

Bitvektor: kleiner, endlicher Wertebe-reich (Universum N), Implementierung: Array [1..N] mit boolschen Variablen, Komplexität: insert: O(1), empty, enumerate: O(N), union, intersection, difference: O(N), Platzbedarf = O(N)

Ungeordnete Liste: Menge = Liste der Elemente, nicht effizient, Komplexität: union, intersection, difference: O(m*n) (bei 2 Listen m und n), insert: O(n),...

Geordnete Liste: allgemein beste Darstellung, Mengen wesentlich kleiner als Universum, Komplexität abhängig von Mengengröße, Komplexität: empty: O(1), insert: O(n), union, intersection, difference (paralleler Durchlauf): O(n+m), enumerate: O(n)

98

99

Was sind Dictionaries?

häufigst benötigter Operationen-Satz: insert, delete, member, dictionary (Wörterbuch), Operationen: insert, delete, member, (empty, isempty) ein-fache Implementierungen: 1) Sequen-tiell geordnete Liste im Array [insert, de-lete: O(n), member: O(log n), Platzbe-darf O(N)], 2) Ungeordnete Liste [insert O(1), insert ohne Duplikate O(n), delete, member O(n), Platzbedarf O(n)], 3) Ge-ordnete Liste [insert, delete member: O(n), Platzbedarf: O(n)], 4) Bitvektor [kleines Universum, insert, delete, member: O(1), Platzbedarf: O(N)]

99 - 101

Wie lassen sich Dictionaries optimaler Implementieren?

Hashing, Binäre Suchbäume, AVL-Bäume

101

Was versteht man unter Hashing?

Hashing: aus Wert des Mengenelemen-tes seine Speicheradresse berechnen, Speicher = Menge von Behältern (buckets), Schlüssel bei komplexer innerer Struktur (Records), Hashfunk-tion (Schlüsseltransformation) totale Ab-bildung h:D ® {0, ...,m-1}, D = Schlüs-sel-Wertebereich, Hashfunktion sollte: surjektiv sein, Schlüssel gleichmäßig auf Behälter verteilen, effizient zu berechnen sein, einfache Hashfunktion: Zahlenwert der Binärdarstellung mod Behälterzahl, Kollision

102 / 103

Wie unterscheiden sich offenes und geschlossenes Hashing voneinander?

offenes Hashing: je Behälter beliebig erweiterbare Liste von Schlüsseln (se-parate chaining), Array mit Zeigern ver-waltet Behälter, durchschnittliche Listen-länge = n/m, bei gleichmäßiger Vertei-lung: insert, delete, member: O(1+n/m) = O(1), worst case je O(n), Platzbedarf: O(n+m), Listen zu groß: reorganisieren

geschlossenes Hashing: je Behälter konstante Schlüsselzahl b, Überlauf (overflow), Kollisionen praktisch unver-meidlich, Zahl der Einträge begrenzt durch Tabelle m*b, wenn b = 1, Elemen-te direkt als Array-Komponenten gespei-chert, spezielle Werte: "empty" und "deleted" oder zusätzliche Record-Kom-ponente, Auslastung über 80 % kritisch, für sehr "dynamische" Anwendungen nicht geeignet

104 - 106

Welche Methoden zur Kollisionsbe-handlung werden beim geschlossenen Hashing eingesetzt?

offene Adressierung (rehashing), mehrere Hashfunktionen h₀, h₁, h₂, ..., , Kollisionsstrategien: 1) Lineares Sondieren, Tendenz, lange Ketten zu bilden, 2) Quadratisches Sondieren, ggf. abwechselnd + i², - i², keine Verbesse-rung für Primärkollisionen, vermeidet Clusterbildung bei Sekundärkollisionen 3) Doppel-Hashing, zwei voneinander unabhängige Hashfunktionen h und h', Folge von Hashfunktionen: h_i(x) = (h(x) + h'(x) * i²), nahezu ideal, beweisbar voneinander unabhängige Hashfunk-tionen (Doppelkollisionswahrschein-lichkeit 1/m²) schwer zu finden, Praxis: intuitive Unabhängigkeit

106 - 108

Beschreiben Sie 2 Methoden für Hashfunktionen!

1) Divisionsmethode: einfachste Hash-funktion, h(k) = k mod m, m = maximale Anzahl von Einträgen, Nachteil: aufein-anderfolgende Zahlen k, k+1, k+2 werden auf aufeinanderfolgende Zellen abgebildet

2) Mittel-Quadrat-Methode: [k = Ziffern-folge k_r, k_r-1, ..., k₁, k² = Ziffernfolge s_2r, s_2r-1, ..., s₁, Block von mittleren Ziffern als Adresse h(k)], Vorteil: Streuung auf-einanderfolgender Werte, bei Zeichen-ketten zuerst Buchstabencodes aufsum-mieren

109 / 110

Was sind Binäre Suchbäume?

Mengen-Elemente in binärem Baum Definition 4.4: [Knotenmarkierung = Ab-bildung m:T ® D für geordneten Werte-bereich D], Definition 4.5: [Binärer Suchbaum = wenn jedes Element im linken Teilbaum kleiner als dessen Wurzel...], inorder-Durchlauf liefert Elemente sortiert, Operationen insert und member einfach zu implementieren, bei delete innere Knoten und Blätter unterscheiden, degenerierter Baum bei sortierter Eingabereihenfolge, für alle 3 Operationen: worst case-Verhalten O(n), avg. case in "zufälligem" Baum O(log n), viele Updates - linkslastig (wenn beim Entfernen eines inneren Knotens immer der Nachfolger an dessen stelle rückt!), Löschprozedur sollte ggf. zufällig zw. Nachfolger und Vorgänger wählen!

111 - 120

Was sind AVL-Bäume?

AVL-Baum eine von verschiedenen Arten balancierter Suchbäume, Struk-turinvariante unter Updates aufrechter-halten, Definition 4.8: [AVL-Baum = binärer Suchbaum, für jeden Knoten gilt: Höhenunterschied der 2 Teilbäume £ 1], nach Einfügen oder Löschen ggf. Reba-lancierphase, jeweils einfache Rota-tion wenn äußerer Teilbaum am tiefsten, Doppelrotation, wenn innerer Teilbaum am tiefsten, beim Löschen ggf. auch Vorgängerteilbäume rebalancieren, Implementierung: wie binärer Such-baum zuzügl. Komponente "height" für jeden Knoten, Prozedur: balance(p) = height (p.left) - height(p.right), minimale Knotenanzahl bei Höhe h: N(h) = Fibo-naci_h+3-1 Laufzeit für alle 3 Ops. auch im worst case: O(log n), Platz O(n)

121 - 132

Was ist ein externer Algorithmus bzw. eine externe Datenstruktur?

externer Algorithmus: zur Verarbeitung einer Objektmenge O(n) wird nur O(1) interner Speicherplatz benötigt

externe Datenstruktur (Speicherstruk-tur): vollständig auf Hintergrundspeicher dargestellt, Gründe: persistente Spei-cherung der Daten, große Datenmenge

132

Was ist die Besonderheit beim "Externen Suchen"? (Was ist beim suchen auf externen Datenstrukturen zu beachten?)

Lesen / Schreiben eines Bytes nicht we-sentlich billiger als 1kByte, Einteilung in Blöcke (Seiten), Blockgröße zwischen 512 und 8192 Bytes (1/2 K bis 8 K), Kostenmaß für Laufzeit eines ext. Algorithmus (Anzahl der Seitenzugriffe), Platzbedarf (Anzahl belegter Seiten), Speicherplatzausnutzung (seiteninter-ne Fragmentierung), Problem: Finden von Datensätzen mit möglichst wenigen Seitenzugriffen

132 - 133

Was versteht man unter einem "B-Baum"?

Speicherseiten als Knoten eines Such-baums, Bäume mit hohem Verzwei-gungsgrad: allgemeiner Suchbaum, Definition 4.12 Vielweg-Suchbäume, B-Baum spezielle Form, Definition 4.13: [B-Bäume Ordnung m, Eigenschaften: 1) Schlüsselanzahl jedes Knotens zwischen m und 2m, bei Wurzel zwischen 1 und 2m, 2) Alle Pfadlängen Wurzel - Blatt sind gleich, 3) Jeder innere Knoten mit s Schlüsseln hat s+1 Söhne], #Knoten, #Schlüssel, Höhe = O(log_(m+1) n), Implementierung: je Knoten 3 Komponenten: used [1..2m], keys (array[1..2m]of keytype), sons (array[0..2m]of logischeSeitennummern)

133 - 137

Was ist beim Einfügen bzw. Löschen in einem B-Baum zu beachten?

Overflow (Knoten mit 2m+1 Schlüs-seln), Underflow (Knoten mit m-1 Schlüsseln), Overflow-Behandlung: Knoten in 2 Teile mit 1...m und m+2...2m+1, m+1 neuer Schlüssel im Vaterknoten (bei Wurzel: neue Wurzel), ggf. Vaterknoten teilen..., Underflow-Behandlung: 1) Knoten wird mit Schlüs-seln aus Nachbarknoten ausgeglichen (ballance) oder 2) mit diesem ver-schmolzen (merge), verliert Wurzel dabei letzten Schlüssel, wird verschmol-zener Knoten zur Wurzel, Komplexität aller Dictionary-Operationen: O(log_(m+1) n) Zeit, O(n) Platz, Speicherausnutzung mind. 50 % (außer Wurzel), Haupt-Anwendungsgebiet: Datenbanksys-teme [in Blättern Datensätze, in inneren Knoten nur Schlüssel, Zeichenketten ab-gekürzt, Over- und Underflow-Kriterium: Füllungsgrad der Seite], interne balan-cierte Baumstruktur [Verzweigungs-grad minimal wählen, Ordnung 1, 2-3-Bäume, Operationen in O(log n) Zeit, O(n) Platz]

137 - 143

Was versteht man unter "Priority-Queues"?

Warteschlangen mit Priorität, Anwen-dungsgebiet: Prozessverwaltung in Betriebssystemen, Operationen: insert (Einfügen mit Prioritätswert), deletemin (Entnehmen des Elementes mit gering-stem Prioritätswert), mehrere Objekte mit gleicher Priorität möglich, Multimen-gen (Multisets, Bags), Funktionen mit mehreren möglichen Ergebnissen, Implementierung: modifizierte AVL-Bäume, (einfacher) partiell geordnete Bäume: [knotenmarkierter binärer Baum, Wurzel enthält Minimum des Teilbaums, Heap (Haufen), Folge der Knotenmar-kierungen monoton steigend]

143 - 145

Erläutern Sie die Besonderheit eines links-vollständigen partiell geordneten Baumes!

links-vollständig: alle Ebenen sind voll besetzt, Ausnahme: letzte Ebene Knoten so weit links wie möglich, Implementie-rung der Operationen: insert [Knoten erzeugen, in unterste Ebene einfügen, Wert ggf. mit Vaterknoten tauschen...] deletemin [Wurzeleintrag auslesen, letzte Position löschen (Wert in Wurzel), solange Wurzelwert < Sohnwert, mit dem kleineren Sohnwert tauschen...], Vorteile: einfach, praktisch sehr effi-zient, Komplexität: beide Operationen in O(log n) Zeit, Platz O(n)

145 - 147

Beschreiben sie das allgemeine "Sortierproblem"!

Folge unsortierter Records, key-Kompo-nente eines linear geordn. Datentyps, Permutation der Folge, gleicher Schlüs-selwert in mehreren Records möglich

153

Wonach kann man Sortieralgorithmen klassifizieren?

intern/extern, alle Records gleichzeitig im Hauptspeicher oder nicht, metho-disch, 1) Sortieren durch Einfügen, 2) ...durch Auswählen, 3) Divide-and-Con-quer, 4) Fachverteilen, nach Effizienz (Laufzeit), einfache Verfahren: O(n²), gute Methoden O(n log n), average- und worst-case-Verhalten, nach Im-plementierung, im Array oder nicht, Platzverbrauch, in situ, allgemeine/ein-geschränkte Verfahren, Manche Me-thoden nur bei Records mit speziellen Eigenschaften, stabil/instabil, Reihen-folge von Sätzen mit gleichen Schlüssel-werten

153

Nennen und beschreiben Sie einfache Sortierverfahren!

SelectionSort (Sortieren durch Auswäh-len), Minimum entnehmen & an neue Liste anfügen, oder Minimum mit 1., 2. ...Element vertauschen, Comparisons O(n²), Exchanges O(n)

InsertionSort (Sortieren durch Einfügen), erstes Element entnehmen & in neuer Liste an richtiger Stelle einfü-gen, oder zusätzliches Feld s[0] mit ab-solut kleinstem Schlüssel & 2., 3. ...Ele-ment mit größeren Werten davor vertau-schen, Comparis.& Movements je O(n²)

BubbleSort, vertauschen benachbarter Elemente bei falscher Reihenfolge, Comparisons & Exchanges je O(n²)

für alle gilt: "direktes" Auswählen oder Einfügen (vollständig im Array realisiert), Laufzeit jeweils O(n²) für worst- und average-case

154 - 157

Was ist unter der Divide-and-Conquer-Methode (DAC-Paradigma) zu verstehen?

wenn Objektmenge klein genug: Prob-lem direkt lösen, sonst: Divide: Menge in möglichst gleich große Teilmengen zer-legen, Conquer: Problem rekursiv für je-de Teilmenge lösen, Merge: aus Lösun-gen für Teilmengen Gesamtlösung be-rechnen, Satz 5.1: [balancierter DAC-Algorithmus (Teilmengen etwa gleich groß), wenn Divide- und Merge-Schritt je O(1): Laufzeit O(n), wenn Divide- und Merge-Schritt je O(n): Laufz. O(n log n)]

157

Welche Divide-and-Conquer-Methoden kennen Sie?

Mergesort, Quicksort

157

Beschreiben Sie das Mergesort-Verfah-ren und dessen Laufzeitverhalten!

Mergesort (Sortieren durch Verschmel-zen), eher externes Sortierverfahren, nicht in situ, Verfahren: 1) teile Liste in 2 gleich große Teillisten, 2) widerhole dies rekursiv bis alle Teillisten Größe = 1, 3) verschmelze alle Teillisten in sor-tierter Reihenfolge, Laufzeit: average- und worst-case O(n log n)

157

Nach welchem Verfahren arbeitet der Quicksort-Algorithmus?

Quicksort, im Durchschnitt schnellstes Verfahren überhaupt, Verfahren: 1) Wähle beliebigen Schlüsselwert x aus Liste, 2) berechne Teilfolgen mit a) Elementen < x und b) Elementen ³ x, 3) widerhole rekrusiv bis Teillistengröße = 1, 4) hänge sort. Teillisten aneinander

Implementierung in Listen / im Array, Divide-Schritt: W(n), Merge-Schritt bes-tenfalls O(1), Problem: nicht sicher balancierte Aufteilung im Divide-Schritt, wird in jedem Divide-Schritt das Mini-mum gewählt, terminiert Quicksort nicht (!), Konsequenz: alle Schlüssel gleich - nichts zu sortieren, x darf nicht minimal sein, Laufzeit: average-case O(n log n) (Beweis S. 165/166), Satz 5.2: worst-case O(n²) (bei Aufteilung 1 / n-1), Implementierung im Array: Pro-zedur "findx"sucht im Teilarray nach zwei unterschiedlichen Schlüsseln, gibt größeren aus, Prozedur "partition" läßt 2 Zeiger aufeinander zu wandern und Werte < x mit Werten ³ x vertauschen, Nachteil: "findx" bei sortierter Eingabe schlecht, besser x per Zufallsgenerator, zusätzl. Platzbedarf (Rekursionsstack): worst case O(n), modifiziert O(log n)

158

Welche Verbesserung gegenüber Quicksort bietet "Clever Quicksort"?

Clever-Quicksort wählt als Split-Ele-ment das mittlere aus 3 zufällig ausge-wählten Elementen, eher balanciert, Ver-gleich-Anzahl nur 18,8 % über opt. Wert

167

Wie lassen sich die Sortieralgorithmen Auswählen und Einfügen verfeinern?

1) Minimum aus partiell geordnetem Baum (in O(log n) Zeit) auswählen (Heapsort), 2) Einfügen in geordnete Folge per AVL-Baum (Baumsortieren), (Inorder-Durchlauf liefert sortierte Ergeb-nisfolge), beide Verfahren worst-case-Laufzeit O(n log n), Baumsortieren aufgrund benötigter "komplexer dynami-scher Datenstrukturen" wenig interes-sant, dennoch asymptotisch optimal

168

Beschreiben Sie die Methode des Standard-Heapsort!

partiell geordneter Baum im Array effi-zient implementierbar, in situ, bestes bekann-tes Sortierverfahren mit O(n log n) Laufzeit im worst-case, Grund-idee: 1) n Elemente in Heap einfügen (O(n log n) Zeit), 2) n-mal das Minimum aus dem Heap entnehmen (O(n log n) Zeit), Definition 5.4: Teilheap, (ën/2û +1 bis n = Teilheap), Implementierung: i von ën/2û bis 1 einsinken lassen, Proze-dur "reheap": [(min. {S[2j], S[2j+1]}) (j = i) mit dem j-Element vertauschen falls S[j] > (min. {S[2j], S[2j+1]}), weiter mit j = 2j,...], jede Ebene 2 Schlüsselvergleiche, maximal 2*log n Vergleiche = O(log n) ("reheap" trifft 2 Entscheidungen: wel-cher Pfad?, muß aktuelles Element noch weiter einsin-ken?), Prozedur "Heap-Sort": [1) Aufruf von "reheap(i, n)" für i = ën/2û bis 1, 2) vertauschen von S[1] & S[i] und "reheap (1, i-1)" für i = n bis 2, Komplexität: Schleife 1 wird n/2-mal durchl. (insg. O(n)), Schleife 2 wird n-1-mal durchlau-fen (je O(log n)), daher Gesamtlaufzeit O(n log n) im worst-case, benötigt man nur k kleinste Ele-mente, O(n + k log n) Zeit möglich

168 - 172

Grenzen sie den Algorithmus "Bottom-Up-Heapsort" vom Standard-Heapsort ab!

Bottom-Up-Heapsort trennt die beiden Entscheidungen der "reheap"-Prozedur: 1) Durchlaufe Heap "top-down" (vom einsinkenden Element e bis zum Array-Ende) und finde Pfad, auf dem e liegen bleiben muß, 2) Durchlaufe Zielpfad von hinten nach vorne ("bottom-up") bis j-Schlüssel < i-Schlüssel (Pos. q), 3) entnimm e, schiebe alle Elemente ab Pos. q um eine Position nach oben und füge e auf Pos. q ein.

Vorteil gegenüber Standard-Heapsort: Schleife 2 bricht i. d. R. nach 1-2 Durch-läufen ab, reduzierte Vergleiche-An-zahl, Fazit: Bottom-Up-Heapsort bei n ³ 400 besser als Standard-Quicksort, bei n ³ 16000 besser als Clever-Quicksort, daneben: gutes worst-case-Verhalten (O(n log n))

172 - 174

Warum ist W(n log n) eine untere Schranke für Sortierverfahren?

jeden Schlüsselwert einmal betrachten - untere Schranke in jedem Fall W(n), allgemeines Verfahren: beliebige Men-ge von linear geordneten Werten, einzi-ge Möglichkeit: Vergleich (<, £), ab-strakter Datentyp: nur eine Vergleichs-möglichkeit, Schlüsselvergleichsverfah-ren, beliebiger Algorithmus A: Ablauf hängt nur von Vergleichsergebnissen ab, Verhalten von A für sämtliche Fol-gen, Entscheidungsbaum (Menge aller möglichen Abläufe von A), A muß sämt-liche n! Permutationen über Entschei-dungsbaum (ohne redundante Verglei-che für Folge der Länge n = n! Blätter = 2*n!-1 Knoten) ansteuern, für worst-ca-se-Berchenung balancierter Entschei-dungsbaum, da längster Pfad minimal, untere Schranke für jeden Schlüssel-vergleichs-Sortieralgorithmus W(n log n)

174 - 178

Was versteht man unter "Sortieren durch Fachverteilen? Stellen Sie 2 Sortierverfahren vor!

Einschränkungen für Schlüsselwerte, neben Vergleichen auch andere Opera-tionen, Möglichkeit schneller als O(n log n) zu sortieren: z.B. O(n), Bucket-sort, Radixsort

178

Wie funktioniert Bucketsort?

Voraussetzungen: keytype = 0..m-1 und Duplikate erlaubt, Menge von Behäl-tern (Buckets) B₀, ..., B_m-1, Bucket = Lis-te von Records, Buckets durch Array verwaltet (ähnlich offenes Hashing), Al-gorithmus: 1) von 0 bis m-1 alle Buckets entleeren, 2) von 1 bis n jedes Element in Bucket_Schlüssel einfügen (Duplikate führen zu Listen), 3) von Bucket 0 bis m-1 alle Elemente als Ergebnisfolge ausgeben, Komplexität: O(m + n) Zeit, für m = O(n), gilt: O(n)

178

Erläutern sie den Radixsort-Algorith-mus!

Verallgemeinerung von Bucketsort: keytype = 0..n^k-1, (Bucketsort hätte Laufzeit O(n^k), mehrere Phasen (k*n Durchläufe), wichtig: Records werden ans Ende einer Bucket-Liste angefügt!, Schlüsselwerte als Ziffernfolgen zur Basis m, Sortieren in jeder Phase nach einer Ziffer: Radixsortieren, Wertebereiche der Ziffern müssen nicht gleich sein, z.B.: Datum, k als Konstan-te auffassen, dann Laufzeit O(n), sonst O(k*n), besonders gut wenn Schlüssel = Zeichenkette fester, geringer Länge

179

Was für ein Sortierverfahren würden Sie vorschlagen, wenn bekannt ist, dass die Eingabefolge zum größten Teil sortiert vorliegt und nur an deren Ende einige wenige unsortierte Werte angehängt sind? Begründen Sie!

sequentieller Durchlauf, unsortierte Werte isolieren, unsortierte Werte intern sortieren (z.B. mit Quicksort), anschließend Merge-Lauf (verschmelzen der sortierten mit der zuvor unsortierten Folge) Laufzeit: O(n), wenn man den in-ternen Sortieralgorithmus der kleinen Folge vernachlässigt

4-A5

Was ist ein Graph?

Menge von Objekten zusammen mit einer Beziehung (Relation), Objekte = Knoten, Beziehungen = Kanten, ge-richtete Kante (Pfeil), Spezialfall: sym-metrische Beziehung = ungerichtete Kante, gerichtete/ungerichtete Graphen

185

Was ist ein gerichteter Graph?

Definition 6.1: gerichteter Graph, Digraph (directed graph), Paar G = (V, E), V (endliche nichtleere Knotenmen-ge), E Í V x V Menge von Kanten, Kan-te (v, w) = Pfeil von v nach w, inzident, Knoten v und w benachbart (adjazent), Grad eines Knotens (Gesamtzahl ein- und ausgehender Kanten), Eingangs-grad, Ausgangsgrad, Pfad (Folge von durch Kanten verbundene Knoten), Pfadlänge (Kantenanzahl), einfacher Pfad (alle Knoten paarweise verschie-den), Zyklus (1. und letzter Knoten identisch), Pfad der Länge 0 (einzelner Knoten), Teilgraph, stark verbunden (strongly connected) wenn Pfad von v nach w und umgekehrt, starke Kompo-nente (Teilgraph mit maximaler Knoten-zahl, alle Knoten paarweise stark ver-bunden), markierte Graphen (weitere Informationen zu Knoten und/oder Kan-ten), Kosten, Kosten eines Pfades (Summe der Kantenkosten)

186 - 188

Wie läßt sich ein Graph im Speicher darstellen?

verschiedene Datenstrukturen, die beiden wichtigsten:

a) Adjazenzmatrix (boolesche n x n-Matrix A mit A_ij = true falls (i, j) Î E, false sonst), true/false = 1/0, oder markierte Adjazenzmatrix (true = Kantenbeschrif-tung, false = Sonderzeichen), Vorteil: feststellen ob Kante (v, w) vorhanden in Laufzeit O(1), Nachteil: Platzbedarf O(n²), finden aller Nachfolger in O(n) Zeit, Initialisierung der Matrix in Q(n²) Zeit

b) Adjazenzlisten, für jeden Knoten Lis-te aller (Nachfolger-)Nachbarn, Listen in Array der Länge n = |V| verwaltet, mar-kierte Graphen - Listenelemente mit mehreren Einträgen, Vorteil: geringer Platzbedarf O(n + e) mit (n = |V|, e = |E|), erreichen aller k Nachfolger eines Knotens in O(k) Zeit, Nachteil: Test ob v und w benachbart, nicht in O(1) Zeit möglich, zur Vorgänger-Suche ggf. inverse Adjazenzlisten verwalten

188 - 191

Wie lassen sich systematisch alle Knoten eines Graphen aufsuchen? Welche Fälle sind zu unterscheiden?

1) Wurzelgraph: (alle Knoten von Wurzel aus erreichbar), Tiefen- und Breiten-durchlauf, Baum: "Expansion von G in r" (i.a. unendlich falls G Zyklen enthält), Definition 6.7: [Expansion X(v): hat v keine Nachfolger, besteht X(v) nur aus v, jeder Nachfolger von v ist Sohn von v...], Tiefendurchlauf (depth-first-traversal) entspricht Preorder-Durchlauf der Expansion, Abbruch in bereits besuchtem Knoten, Breitendurchlauf (breadth-first-traversal), Besuch der Knoten ebenenweise, erst Pfad der Län-ge 1, dann 2, ..., Abbruch bei bereits be-suchtem Knoten, depth-first- / breadth-first-Spannbaum

2) allgemeiner Graph: bei Durchlauf können unbesuchte Knoten verbleiben, neuer Durchlauf in unbesuchtem Knoten, spannende Wälder, Imple-mentierung: zusätzliches Array: "visi-ted", Algorithmus Tiefendurchlauf: dfs(v): [wenn v noch nicht besucht, dann 1) v als besucht markieren, 2) dfs auf allen Nach-folgern von v aufrufen], Algorithmus Breitendurchlauf: bfs(v): mit Queue für Knoten-Nachfolger: [1) er-zeuge Queue q für v, 2) markiere v als besucht, 3) solange q nicht leer: a) entnehme w aus q und b) verarbeite w: für alle Nachfolger x von w: wenn x noch nicht besucht, markiere alle x als be-sucht und füge x in q ein, Laufzeit für Tiefen- und Breitendurchlauf je O(n + e)

191 - 196

Was versteht man unter einem "gerichteten azyklischen Graphen"?

DAG (directed acyclic graph), z.B. Operatorbaum für Arithmetische Ausdrücke, in denen gemeinsame Teilausdrücke nur einmal vorkommen

196

Wie kann in einem Graphen der kürzeste Weg von einem Knoten v nach Knoten w berechnet werden?

Erläutern Sie den Algorithmus von Dijkstra zu diesem Problem!

Voraussetzungen: Kanten mit Kosten markiert, "single source shortest path"-Problem, Idee: Startknoten, Teil-graph (bereits erkundeter Teil von G.) wachsen lassen, je 2 Arten von Knoten und Kanten: Grüne Knoten (alle Kanten zu Nachbarknoten bereits betrachtet, Nachbarknoten liegen im Teilgraphen), Gelbe Knoten (ausgehende Kanten noch nicht betrachtet, Rand des Teilgra-phen), Rote Kanten (Baum des kürzes-ten Weges), in jedem Knoten des Teil-graphen kürzester Abstand zu v verwal-tet, Ablauf: gelber Knoten mit minima-lem Abstand zu v wird grün, noch nicht betrachtete Nachfolgerknoten werden gelb, für erneut erreichte gelbe Knoten wird kürzester Pfad korri-giert..., termi-niert Algorithmus, sind alle von v aus erreichbaren Knoten grün, ungefärbte Knoten sind von v nicht erreichbar, Lemma 6.12: für jeden Knoten roter Pfad minimal zu allen gelb-roten Pfaden, Lemma 6.13: Grüner Knoten: roter Pfad ist kürzester im Graphen, Satz 6.14: Algorithmus von Dijkstra berechnet kür-zeste Pfade zu allen von v erreichbaren Knoten

196 - 202

Wie läßt sich der Dijkstra-Algorithmus implementieren?

1) mit Kosten-Adjazenzmatrix, zusätz-lich Arrays dist (Distanzen zu v), father (Vaterknoten der über rote Kante erreichbar ist), grün (true wenn Knoten grün), Teilschritte: a) in Array dist nach gelbem Knoten mit minimalem Abstand suchen O(n), b) Zeile cost (w, -) der Ma-trix durchlaufen & für alle Nachfolger von w Abstand und Vater korrigieren O(n), n-mal Teilschritte durchführen: Laufzeit O(n²), Nachteile: ineffizient wenn n nicht sehr klein, oder e nicht ca. n² ist

2) mit Adjazenzlisten mit Kostenein-trägen und als Heap dargestellter Priority Queue, zusätzlich Arrays dist, father und heap-adress, grüne und gelbe Knoten haben Einträge in dist und father, gelbe Knoten mit Abstand vom Ausgangsknoten in Priority Queue (als Heap), Queue-Einträge und Knoten dop-pelt miteinander verkettet (Heap-Eintr. hat Knotennummer, Knoten hat Position im Heap), Teilschritte: 1) Entnimm gelben Knoten w mit minimalem Abstand aus Priority Queue O(log n), 2) Finde in Adjazenzliste m Nachfolger von w O(m), a) neue gelbe Nachfolger - in Priority Queue einfügen O(log n), b) alte gelbe Nachfolger - ggf. Priority Queue Eintrag korrigieren (zu finden über heapadress, wandert im Heap nach oben) O(log n), und Heap-Adressen ändern O(1), Aufwand für a) + b) = O(m log n), über alle Schritte ist Aufwand für 1) und 2) je O(e log n) mit (e = |E|) also insgesamt O(e log n), Platzbedarf O(n + e)

202 / 203