ALP 3 Zusammenfassung ADT - abstract data type Ein Datentyp der nur über Schnittstellen (Methoden) manipuliert werden kann. Ein direkter Zugriff auf die Daten findet nicht statt. Objekte dieses Datentyps sind sogenannte abstrakte Datenobjekte (ADO - abstract data object). Es muss gewährleistet sein, dass die ADO nicht die Kapselung durch Referenzen durchbrechen können. Vorteile: - mehr Sicherheit - größere Komfort durch Abstraktion (Datenimplemtation) - größere Flexibilität, weil Quelltext unabhängig verändert werden kann, solange die Signatur beibehalten wird. Module keene Ahnung Pakete - Pakete schaffen eigene Namensräume und vermeiden somit die Kollision von Klassennamen - bessere Strukturierung - Erlauben Abkapselung von Programmteilen Schnittstellen / Interfaces - Sichtbarkeit immer public - Attribute stets static und final und müssen mit einem Wert belegt sein Java Implementation: interface [Schnittstellenname}[] { ... Deklaration... } Java und die konfuse Parameterübergabe * Java übergibt grundsätzlich Kopien an Methoden * Wenn Objekte übergeben werden, wird eine Kopie des Zeigers auf das Objekt übergeben * Es ist also möglich Objekte zu manipulieren, nicht aber den übergebenen Pointer auf ein anderes Objekt zeigen zu lassen * Beispielaufgabe in der Probeklausur Haskell * Implementation: class Schnittstellenname Typvariablenplatzhalter where Funktionsname :: Signatur instance Schnittstellenname Typvariable where ... Funktionsimplementierung ... Beispiel data Elements t = Elements [t] deriving Show class Enum t => Queue t where add :: (Elements t) -> t -> (Elements t) pop :: (Elements t) -> (t, (Elements t)) instance Queue Integer where add (Elements x) y = Elements (x ++ [y]) pop (Elements (x:xs)) = (x, Elements xs) * keine Datenabstraktion! * Datenabstraktion mit Modulen (pro Schnittstelle 1 Modul, 1 Modul für gemeinsame Schnittstelle) module Modulname [(Exportdatentypen)] where import Modulname [,Modulname] [data Datenname Datentyp = Definition [deriving Show]] ... Modulimplementierung ... --end Modulname Typen statischer Typ: deklartierter Variablentyp (z.B. List) dynamischen Typ: aktueller Typ des Verweises (z.B. LinkedList) Software Patterns * abstract factory * Definition von Konstruktoren im Interface * wird eingesetzt bei GUI-Programmierung (für Themes) * Vorteile * Isolation von konkreten Klassen * Nachteile * neue Klassen lassen sich umständlich hinzufügen, da die abstrakte Fabrik, sowie die konkrete Implentation verändert werden muss asdf Polymorphie * Überladen (overloading) * verschiedene Signaturen (verschiedene Parameter) für Methoden/Funktionen * Überschreiben (overriding) * gleicher Methodename in der Unterklasse + gleiche Signatur * es wird jeweils zur Laufzeit die Methode des dynamischen Typs aufgerufen * Kovarianz: Rückgabetypen und Exceptionstypen müssen Untertypen der Oberklasse sein (in Java!) * Kontravarianz: Argumenttypen können Untertypen sein (in Java nicht mögliche, führt zu overloading) * Beispiele: overloading public void test(int x) { ... } public void test(int x, int y) { .. } overriding * universelle Polymorphie * Invarianz: ____________ ____________ |Class A | <<------------ |Class B | |method( t : T )| <<------------ |method( t : T )| * Kovarianz: ____________ ____________ |Class A | <<------------ |Class B | |method( t : T )| <<------------ |method( t : T*)| * Kontravarianz: ____________ ____________ |Class A | <<------------ |Class B | |method( t*: T*)| ------------>> |method( t : T )| * Generizität (parametrische Polymorphie) * Invarianz: Die Typparameter sind eindeutig. Dies erlaubt alles was man mit so einem Typparameter machen will (autoboxing, boxing, unboxing, autounboxing) * Bsp: * Kovarianz: ist die obere Schranke der Vererbungshierarchie. D.h. die Typparameter verhalten sich in der Vererbungshierarchie gleich. * Bsp: * Kontravarianz: untere Schranke in der Vererbungshierarchie der Typparameter. Dies bedeutet, dass zur Laufzeit keine Annahme ueber den uebergebenen Datentyp gemacht werden koennen. Quasi ist dann obere Schranke vom Typ Object. * Bsp: * Beispiel: class TreeSet ..... { boolean contains(Object o) // kann jeder Typ sein -> Objekt boolean containsAll(Collection c) // die Collection kann von jedem // Argumenttyp sein boolean addAll(Collection c). // beim Hinzufügen muss die Collection // Verträglich mit dem Argumenttyp der // aktuellen Instanz sein (also auch // Untertyp davon) // -> nur Lesezugriff auf c TreeSet(Comparator comp) // comperator muss von einer Oberklasse // von E sein -> nur Schreibzugriff auf comp } * Vererbung (Einschlusspolymorphie) Spezifikation von Datenstrukturen formale Spezifikation: Deklariert durch Voraussetzung (Precondition) und dem Effekt (Postcondition) und Invariante Modell: Einfache abstrakte Beschreibung der Daten so wie die Operationen auf diesen, ohne auf die eventuell komplexere Realisierung (Datenstrukur) Bezug zunehmen. Beispiel: Eine Menge von Strings wird einfach als Liste dargestellt: M = [String] * abstrakte Invariante: Eventuelle Kapazitätsbeschränkung * abstrakte Vorraussetzung (Preceondition): * abstrakter Effekt (Postcondition) Repräsentation: Die konkrete Darstellung der Daten mit Hilfe einer geeigneten Datenstrukur. Wichtig für eine effiziente, leistungsfähige Implementierung. Beispiel: Die Menge wird als Verkettete Liste, Stack, oder Queue dargestellt. * Invariante: Konkrete Invariante => abstrakte Invariante * Precondition: Abstrakter Vorr. => konkrete Vorraussetzung (es kann in der Implementierung mehr gefordert werden, aber es muss mindestens die abstrakte Vorraussetzung gelten) * Postcondition: Konkreter Effekt => abstrakten Effekt (die Implementierung darf mehr leisten, aber nicht weniger) * Abstraktionsfunktion: abs : Rep -> Modell ist also eine Funktion welche aus den konkreten Datenobjekten das zugehörige abstrakte Modell zurückgibt: Beispiel: Sei das Modell eine geordnete Liste, welche mit Hilfe eines Binärbaums implementiert wird, so ist die Abstraktionsfunktion die Funktion welche Alle Knoten des Baums zurückgibt (Traversierung) Folgen ADT "Folge" * Modell: [T] * Invariante: eventuell Längenbeschränkung * Operationen unterschiedlich: Keller | Liste (fkt.) | Schlange | Liste (imp.) ----------------------------------------------------------------- length | length | length | length, size empty | empty | empty | empty push | cons | append | append | | | insert* | | | add* top | head | front | get* pop | tail | remove | remove* | cat | | cat | | | cut* iterate | iterate | iterate | iterate ---------------------------------------------------------------- Stack | Queue | List | ArrayList | Vector (*eventuell mit Positionsangabe) * Keller/Stapel (stack) * Komplexität aller Operationen O(1) * Anwendung: Spreicherverwaltung, Auswerten von Ausdrücken, Entrekursivierung, u.v.a. * Entrekursivierung: Umwandlung Rekursion in Iteration * Schlangen * Komplexität aller Operationen O(1) * Repräsentationen * Feld zyklisch benutzt (Längenbeschränkung!) * lineares/zyklisches Geflecht einfach verkettet * Anwendungen: Ressourcenverwaltung, Baum- und Graphtraversierung, Verwaltung realer Warteschlangen, Simulation zeitdiskreter System u.v.a * Doppelkopfschlagen (double ended queues/"deques") * hinzufügen und entfernen an beiden Enden * imperative Listen * Komplexität teils O(1) teils O(n) * beliebig manipulierbare Folge mit Positionen 0,1,2... * Repräsentationen * wechselnde Felder variabler Länge * zyklisches Geflecht doppelt verkettet mit innerer Klasse * Anwendung: Repräsentation "höherer" ADT, Simulation zeitdiskreter Systeme, u.v.a Traversierung von Folgen Durchlaufen aller Elemente und dabei mit jedem Element etwas machen (Bsp.: map, foldl, filter) * Implementierung in Java mit Klasse für Funktion * Traversierung / Iteratoren externer Iterator User weiß, in welcher Reihenfolge die Elemente herauskommen * nicht wiederverwendbar * Mehrere Iteratoren gleichzeitig einsetzbar * Änderungen an der Liste kann undefinierten Effekten für den Iterator führen * flexibler Einsatz für den User * elegnate Lösung für for-Schleifen in Java: for( T elem : list ) { ... interner Iterator Nicht transparent für den User, es wird intern über die Struktur iteriert, um irgendetwas mit mit den Elementen zu machen * reguläre Funktion * sicher & komfortabel * weniger flexibel als externer * Beispiel: fold, map Relationen Modell: Menge von Tupeln (Key,Data) in Pseudo-Haskell: type Rel k d = {(k,d)} rechtseindeutig: type Rel k d = k -> d Operationen: empty, lookup, add, edit, delete, iterate Representation: * Hashing * Bitliste * binäre Suchbäume * B-Bäume (2.3-Bäume): Knoten enthalten nur Schlüssen, Daten stehen in den Blättern Mengen Modell: {T} mit Basistyp T. Wenn T linear geordnet ist, dann geordnete Menge Invariante: eventuell Umfangsbeschränkung Operationen: add, remove, contains, sowie Schnitt, Differenz, Vereinigung Repräsentation: linear: * unsortierte/sortierte Folge (Feld, linked list) * Bitfeld * Streuspeicherung (Hashing) Bäume: * Suchbäume * Heaps Unsortierte Folgen: Komplexität der Operationen: * contains: O(n) * add: O(n) für Mengen und O(1) wenn Duplikate zugelassen sind * remove: O(n) Sortierte Folgen: Für linear geordnete Mengen. Haben eine erweiterte Invariante (Sortierung!) Komplexität der Operationen: * contains: O(log n) (binäre Suche, nur für Felder) im Geflecht: O(n) * add: O(n) * remove: O(n) Bitfelder: Zur Repräsentation natürlicher Zahlen, geignet für kleine Wertebereiche. Folge von Bits oder boolean[], wobei jede Position i einen Wert x repräntiert, wobei x genau dann in der Menge enthalten ist, wenn das i-te Bit gesetzt ist. Komplexität der Operationen: * contains: O(1) * add: O(1) * remove: O(1) Streusspeicherung (Hashing): Ähnlich wie Bitfelder nur für beliebige Basistypen. Mittels einer Hashfunktion werden die Daten auf einen definierten Wertebereich abgebildet, welcher den Index im Feld angibt: h(x) = i => x = A[i] Vorteil: Alle Operationen in O(1) Hashfunktion h: T -> [0..M-1] für ein Feld der Größe M, geignet wählen: * surjektiv * gleichmäßig Streuend um Kollisionen zu minimieren. Kollisionsbehandlung (geschlossene Speicherung): Sondieren: * Nach Kollision mit h_i(x) neuer Versuch mit h_i+1(x) * Z.b. lineares Sondieren (h_i(x) = h_0(x) + ci) mod M * zufälliges sondieren, etc * Doppelhashing: zweite Hashfunktion einsetzen * => Komplexität von O(1) wenn keine Kollision auftritt Kollisionsbehandlung (offene Speicherung): * Kollision wird zu gelassen, d.h. jeder Feldeintrag der Hashtabelle kann mehre Elemente beinhalten (Bucket) * Mengenoperation wird dann als Operation auf dem jeweiligen Bucket B_h(x) ausgeführt * Bucket kann irgendwie implementiert werden, z.b. Feld oder linked List * => Komplexität hängt von der Implementierung der Buckets ab, aber immer mit Faktor 1/M ! Priority Queues und Heaps Definition: Schlange mit Entnahme des jeweils "ranghöchsten Element. Modell: type PQ r t = [(r,t)] -- Ord r (r: Priorität, t: Daten) Invariante: * In der Regel wird die Priorität als durch eine natürliche Ranzahl dargestellt, wobei kleinste Rangzahl ( 0 oder 1) höchste Priorität bedeutet * in Haskell: inv q = all(>=0)(fst(unzip q)) Operationen: empty, append, remove, size Repräsentationen: * linear als Geflecht oder Feld ( wie Modell) * Feld von Schlangen für wenige Ränge (z.b.für Scheduler in Betriebssystemen) * Heaps, ein spezieller Baum Heaps Definition: links(vollständiger, partiell geordneter Binärbaum (d.h. jeder Knotenwert ist kleiner oder gleich sein Nachfolger) Repräsentation: * linear als Feld mit Breitensuche-Anordnung der Knoten, die Wurzel hat den Index 1 * Anschaulich: Wurzel, alle knoten der ersten Ebene (von links nach rechts), alle Knoten der zweiten Ebende, usw. * Identifizierung der Knoten x durch Indexrechnung: index(x) = i ⇔ index(left(x)) = 2i ∧ index(right(x)) = 2i+1 Heap als Priority Queue: * Entfernen: kleinstes Element ist die Wurzel, es wird mit dem letzten eingefügten Element vertauscht * Hinzufügen: hinten anhängen (links unten) * Bei beiden Operationen muss anschließend die Heap-Eigenschaft wieder hergestellt werden: dies erfolgt in zwei Phasen: Bäume allgemein * Bäume bestehen aus (Unter-)Bäumen * n Knotenanzahl, h Höhe, H(n) maximale Höhe mit n Knoten, B(h) maximale Blätteranzahl bei Höhe h * n ≥ h+1 (da falls Kette : h = n-1) * N(h) = 2^(h+1)-1 * B(h) = 2^h * h = ⌈ |log2 (n+1)|) - 1⌉ * Bäume sind verzweigte Folgen. D.h. Operationen auf Bäume sind Operationen auf Folgen (freie) Bäume sind spezielle ungerichtete kreisfreie zusammenhängende Graphen G(E,K) mit E = Menge der Knoten, K ⊆ E x E Menge der Kanten (Wurzel-)Bäume (B,w) bestehen aus freien Baum B und Wurzel w. Die Endknoten werden auch Blätter des Baums genannt. Desweiteren sind die Begriffe Vater- und Kindnoten für durch eine Kante verbundene Knoten geläufig. Begriffe * Grad: Anzahl der Kinder eines Knoten (= Anzahl der nichtleeren Teilbäume eines Unterbaums) * Ebene: Stufe eines Knotens (Weglänge von der Wurzel) * Höhe : maximale Ebene eines Baumes (Ebenenanzahl - 1) * vollständiger Baum: alle Ebenen sind komlett besetzt (außer eventuell der untersten) Varianten (geordneter) Baum ist definiert als: * Folge von geordneten Bäumen * Multimenge von Bäumen n-ärer Baum (n-Tupel von n-ären Bäumen) spezielle n-äre Bäume: * n=1 Kette/Liste * n=2: Binärbaum * n>= 3: Vielwegbaum (multi way tree), ungeordnete Bäume markierte Bäume (labelled tree) Bäume die Wert in den Knoten speichern Bsp: B = { (b,m) | b ist Baum mit Eckenmenge E, m : E → T } unendliche Bäume Standardmethoden * height * nodes * leaves * left,right * add Traversierung Sortierung * Vorordnung/Präordnung (preorder) - Wurzel, linker Baum, rechter Baum * Nachordnung/Postordnung (postorder) - linker baum, rechter Baum, Wurzel * Inordnung (nur Binärbaum) (inorder) - linker Baum, Wurzel, rechter Baum Varianten * Tiefendurchlauf (depth-first traversal): Traversierung rekursiv durch Traversierung der Teilbäume * Implementierung mit Hilfe eines Stacks * Breitendurchlauf (breadth-first traversal): von der Wurzel aus eine Ebene nach der anderen durchlaufen * Implementierung mit Hilfe einer Queue Repräsentation * lineare Repräsentation * z.B. als Array in pre-,post- oder inorder * Geflecht * lineare Abbildung * viele Baumarten → viele Respräsentationen Implementierung: Java markierter Binärbaum class Node { // record type, no operations, // no data abstraction ! // data Bintree t = // Null | Node t (Bintree t)(Bintree t) Node(T val, Node l, Node r) { root = val; left = l; right = r; } final Node left; final T root; final Node right; } Haskell markierter Binärbaum data Bintree t = Empty | Node(Bintree t) t (Bintree t) Graphen Graph G(E,K) E = Menge der Ecken, K ⊆ E x E = Menge der Kanten * gerichtet - Relation K ist nicht symmetrisch * streng zusammenhängend, falls jedes Eckenpaar durch Weg (auch über ander Knoten) verbunden ist * ungerichtet - Relation K ist symmetrisch (a,b) ∈ K ↔ (b,a) ∈ K * zusammenhängend, falls jedes Eckenpaar durch Weg (auch über ander Knoten) verbunden ist * Multigraph - Eckenpaar kann durch mehrere Kanten verbunden sein * planar - Graph kann in 2-D so angeordnet werden, dass sich keine Kanten überschneiden * markiert - den Ecken und/oder Kanten ist ein Wert zugeordnet Weg (path) ist eine Folge von Ecken(e_o bis e_n) mit Länge n * einfacher Weg - alle Knoten von einander unterschiedlich (außer eventuell e_0 = e_n) Zyklus - in gerichtetem Graph, n ≥ 2, e_0 =e _n Kreis - in ungerichtetem Graph, n ≥ 3, e_0 = 3_n isolierte Ecke - Knoten ohne Kante (un-)typische Operationen * typisch: komplexe Algorithmen auf unveränderliche Graphen * untypisch: Operationen zum Erweitern, Ändern, Abfragen typische Algorithmen * Eckensuch: Breiten- und Tiefensuche * Wegsuche * existiert ein Weg von a nach b * (un)günstigster Weg * alle Wege von a nach b * Struktur * zyklisch? * zusammenhängend? * minimaler Spannbaum Repräsentation * Adjazenzmatrix * Ecken durchnummeriert (0,1,..n-1)) → Kanten als Zahlentupel (i,j) * nxn-Matrix Varianten: * mit bool'schen Werten: a_{i,j} = (i,j) ∊ K * kantenmarkierte Graphen: a_{i,j} = ∞ falls (i,j) ∊ K, ansonsten -∞ * Abstrakationfkt: * Invariante: * Adjazenzlisten * jeder Knoten hat eine eigene Adjazenzliste für die Nachfolger * Geflechte * Jeder Knoten hat eine Liste von Nachfolgern. Elemente in der Liste repräsentieren die Kanten von dem Knoten Traversieren und Suchen * precondition: von Wutzel w alle Ecken erreichbar Def.: Expansion X(w) des Graphen G=(E,K) ist * a) w selbst, wenn w keine Nachfolger hat * b) mit dem Nachfolgern {v_1, v_2,...} der ungeordnete Vielwegbaum (w,{X(v_1),X(v_2),...}) * Achtung! Vielwegbaum ist unendlich, falls G Zyklen oder Kreise enthält!) * Breitendurchlauf * Breitendurchlauf von X(w) mit Ignorierung von Unterbäumen, mit bereits besuchter Wurzel * typischerweise interner Iterator * Tiefendurchlauf * Durchlauf von X(w) in Präordnung mit Ignorieren von Unterbäumen mit bereits besuchter Wurzel * nur wenn Graph kein Baum ist! Algorithmen * Wegsuche * Weg von a nach b: Tiefensuche (Weg aufzeichnen / revidieren) * alle Wege von a nach b: * kürzester Weg von a nach b: Dijsktra * alle kürzesten Wege von a nach b: Floyd * längster Weg: topologisches Sortieren * Rundwege: * Euler-Weg * Euler-Kreis * Hamilton-Kreis * minimaler Spannbaum: Kruskal Spannbaum freier Baum mit Kanten aus einem ungerichteten, gewichteten, zusammenhängenden Graphen und allen Ecken aus diesen Graphen Ein minimaler Spannbaum ist ein Spannbaum mit minimalen Kosten (d.h. Summe der Kantengewichte) Geometrische Objekte (nicht Klausurrelevanz laut Micha) Geometrische Objekte finden ihren Einsatz bei Computergraphik, sowie als Modelle für Anwendungsprobleme (Algorithmische Geometrie) Segment-Bäume Ein Segment-Baum über X ist ein Binärbaum minimaler Höhe, dessen Blätter die Intervalle (xi, xi+1) tragen. Ein Nichtblatt trägt das Intervall (y,z), das die Vereinigung der Intervalle seiner beiden Kinder ist („Knotenintervalle“). Abtastalgorithmen Streckenschnitt-Problem Finde aus einer Menge mit horizontalen Strecken und einer Menge mit vertikalen Strecken, alle Streckenpaare die sich schneiden. Algorithmus: Abtasten der Objekte mit einer vertikalen Testgeraden (sweep line) - und zwar schrittweise, unter Berücksichtigung der wesentlichen Ereignisse (sweep event structure): * linkes Ende einer horizontalen Strecke, * rechtes Ende einer horizontalen Strecke, * vertikale Strecke. Punkt-Einschluss-Problem Finde zu gegebenen Mengen von Punkten und Rechtecken alle Paare (Punkt, Rechteck), bei denen der Punkt im Rechteck liegt Algorithmus: Plane Sweep(zwei-dimensional) mit Buchführung über die aktuellen Intervalle, die die Rechtecke auf der sweep line bilden. Rechteckschnitt-Problem Finde in einer Menge von Rechtecken alle Paare von überlappenden Rechtecken! Algorithmus: Für Rechtecke, deren Kanten sich schneiden, wird das Problem auf das Streckenschnitt-Problem zurückgeführt. Wenn ein beliebig gewählter Punkt innerhalb eines Rechtecks a in einem Rechteck b enthalten ist, dann überlappen a und b. → Punkteinschluss-Problem anwenden Allgemeine Streckenschnitte Finde aus einer Menge von Strecken, die Streckenpaare die sich schneiden. Algorithmus: Lösung mit Abtastverfahren (plane sweep): Buchführung von der Folge S aller aktuellen Strecken, die die Testgerade schneiden, linear geordnet (sweep status) gemäß den Ordinaten dieser Schnittpunkte. Divide and Conquer Arbeitsspeicherverwaltung (nicht Klausurrelevant laut Micha) Verwaltendes System | verwalteter Speicher | enthält ------------------------------------------------------------------------------------------------- Laufzeitsystem | | | Adressraum | | Codebereich | Instruktionen | Keller | lokale Variable | Halde (heap) | Objekte -------------------------------------------------------------------------------------------------- Betriebssystem | | Arbeitsspeicher | Seiten/Segmente | Externer Speicher | Blöcke typisches Layout des Adressraums eines Prozesses: ------------ oder ------------ | code | | code | ------------ ------------- | stack | | heap | ------|----- ------------ | | | | ------------ ------|------ | heap | | stack | ------------ ------------ (Stack schreib in den leeren Raum) Speicherfreigabe * explizite - Gefahr : Pointer auf schon befreite Speicherzellen * unterlassene - Speicherleck * automatische - superb * Keller - Freigabe nach Verlassen der Methode * Halde * Verweiszähler (reference counts) * Versagen bei Zyklen * start: c = 1; * Kopieren des Verweises c++; * Überschreiben eines Verweises c--; * wenn 0 löschen * * Speicherbereinigung (garbage collection) * alle vom Keller aus nicht erreichbaren Objekte werden gelöscht (nebenläufig oder wenn Halde überläuft) * 2 Phasen * mark * ausgehend vom Keller alle erreichbaren Objekte markieren (= Graph-Traversierung!) * sweep * löschen nicht markierter Objekte * Entferunung der Markierungen an anderen Objekten * in Java: * jedes Element Methode finalize() wird aufgerufen nachdem Objekt nicht mehr erreichbar ist & direkt vor Löschung des Objekts * WeakReferences schütze nicht vor Löschung * aber nützlich bei Caching * für Schlüssel schwache Verweise einfügen nicht die regulären * wenn Objekt nicht gefunden wird aus Datei nachladen * Achtung! Eintrag kann verschwinden beim Nutzen von equals(); * bei einheitlicher Speichergröße * Freispeicherliste * einrichten neuer Speicherzelle durch Entnahme des Kopfes der Freispeicherliste * wenn Freispeicherliste erschöpft → markierung erreichbarer Zellen; alle anderen in neue Freispeicherliste * unterschiedliche Speichergröße * Bitliste * Blockverkettung * First Fit * Speicherzerstückelung * Best Fit * lohnt den Aufwand nicht * Worst Fit * bringt auch nix * Buddy System * Größe der Halde ist 2^n * Best Fit mit eventuellem Splitten eines zu großen Blocks * viel Verschnitt, dafür sehr schnell * Zellenverkettung Verweise: Zusammenfassung: http://www.inf.fu-berlin.de/lehre/WS09/alp3/folien/alph3-13.pdf