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
Haskell
        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)
            
        (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
asdf

Polymorphie


        overloading
             public void test(int x) { ... }
             public void test(int x, int y) { .. }
        
         overriding
   
             
            ____________                    ____________
            |Class A         | <<------------ |Class B         |
            |method( t : T )| <<------------ |method( t : T )|
            
            ____________                    ____________
            |Class A         | <<------------ |Class B         |
            |method( t : T )| <<------------ |method( t : T*)|
            
            ____________                    ____________
            |Class A         | <<------------ |Class B         |
            |method( t*: T*)| ------------>> |method( t : T )|

                    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
    }

  

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]
    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.

Folgen


ADT "Folge"
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)

Traversierung von Folgen
Durchlaufen aller Elemente und dabei mit jedem Element etwas machen (Bsp.: map, foldl, filter)

Traversierung / Iteratoren


externer Iterator


User weiß, in welcher Reihenfolge die Elemente herauskommen

interner Iterator


Nicht transparent für den User, es wird intern über die Struktur iteriert, um irgendetwas
mit mit den Elementen zu machen

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:


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:
        Bäume:

Unsortierte Folgen:



        Komplexität der Operationen:

Sortierte Folgen

:
        
        Für linear geordnete Mengen. Haben eine erweiterte Invariante (Sortierung!)
        
        Komplexität der Operationen:

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:

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:
        Kollisionsbehandlung (geschlossene Speicherung):
        
        Sondieren:
        Kollisionsbehandlung (offene Speicherung):

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: 


Operationen:

empty, append, remove, size

Repräsentationen:


Heaps



Definition: links(vollständiger, partiell geordneter Binärbaum (d.h. jeder Knotenwert ist kleiner oder gleich sein Nachfolger)

Repräsentation: 
Heap als Priority Queue:

Bäume


allgemein
(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
Varianten
    (geordneter) Baum
    ist definiert als:
    n-ärer Baum (n-Tupel von n-ären Bäumen)
    spezielle n-äre 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
Traversierung
Sortierung
Varianten
Repräsentation
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)


Graphen


Graph G(E,K) E = Menge der Ecken, K ⊆ E x E = Menge der Kanten
Weg (path) ist eine Folge von Ecken(e_o bis e_n) mit Länge 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
typische Algorithmen
Repräsentation
        → Kanten als Zahlentupel (i,j)
            Varianten:
Traversieren und Suchen
     Def.: Expansion X(w) des Graphen G=(E,K) ist 
Algorithmen
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):
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
Verweise: 

Zusammenfassung: http://www.inf.fu-berlin.de/lehre/WS09/alp3/folien/alph3-13.pdf