This service will soon be decomissioned on 2024-05-22. Please copy all content you still need to padlite.spline.de

SplinePad
Full screen

Server Notice:

hide

Public Pad Latest text of pad alp3 Saved Feb 5, 2018

 

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}[<Generizität>] {
        ... 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: <E>
  • Kovarianz: ist die obere Schranke der Vererbungshierarchie. D.h. die Typparameter verhalten sich in der Vererbungshierarchie gleich.
  • Bsp: <? extends A>
  • 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: <? super Integer>
  • Beispiel:
                    class  TreeSet<E> ..... {
                                                       
                    boolean contains(Object o) // kann jeder Typ sein -> Objekt
                    boolean  containsAll(Collection<?> c)   // die Collection kann von jedem 
                                                                             // Argumenttyp sein
                    boolean  addAll(Collection<? extends E> 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<?  super E> 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<E>                   |  Queue<E>  |  List<E>
                                                      | ArrayList<E>
                                                      | Vector<E>
(*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<T> = { (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<T> {     // record type, no operations,
                                        // no data abstraction !
                                       // data Bintree t =
                                      //      Null | Node t     (Bintree t)(Bintree t)
                Node(T val, Node<T> l, Node<T> r) {
                    root = val; left = l; right = r;
                }
 
                final Node<T> left;
                final T root;
                final Node<T> right;
        }
        
    Haskell
        markierter Binärbaum
            data Bintree t = Empty | Node(Bintree t) t (Bintree t)
 
 

Graphe

n

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