IT – Graphentheorie

Definition

G = ( V, E ) → gerichteter Graph (Digraph) ↔

  • V ≠ Ø – Knotenmenge
    v ∈ V – Knoten / Vertex
  • E ⊆ V²  – Kantenmenge
    e = { u, v } ∈ E – Kante
    u – Quelle, v – Ziel der Kante
  • e = ( u, v ) ∈ E mit u = v – Schlinge

G = ( V, E )  → ungerichteter Graph ↔

  • V ≠ Ø – Knotenmenge
  • E ⊆ V²  – Kantenmenge
  • 2 Knoten heißen benachbart ↔ { u, v }  ∈ E

allgemein:

  • bestehen aus Knoten und sie verbindende Kanten
  • Kanten mit Orientierung: gerichtete Graphen
  • Kanten ohne Orientierung: ungerichtete Graphen

Kantenzug ( walk ) – Länge n von v0 nach vn

  • für alle i ∈ { 0, … , n – 1 } gilt: { vi, vi+1 }  ∈ E
  • gerichtet: v0 Startknoten, vn Endknoten von k
  • ungerichtet: vo, vn Endknoten von k
  • v1, … , vn-1 – innere Knoten von k
  • v 0 = vngeschlossener Kantenzug ( closed walk )

Weg ( trail )

  • k ist ein Kantenzug
  • für alle  i, j ∈ { 0, … , n – 1 } mit i ≠ j gilt:  { vi, vi+1 } ≠ { vj, vj+1 }
  • keine Kante doppelt, ggfs. Kreuzungen

Einfacher Weg oder Pfad ( path )

  • k ist ein Weg
  • für alle i, j ∈ { 0, … , n } mit  i ≠ j gilt: vi ≠ vj
  • keine Knoten doppelt, keine Kreuzungen

Kreis ( closed trail ) 

  • k ist ein Weg
  • v0 = vn
  • Graph ohne Kreis = kreisfrei
  • erster und letzter Knoten sind gleich, ggfs. Kreuzungen

Einfacher Kreis ( cycle )

  • k‘ ist ein einfacher Weg
  • v0 = vn
  • Graph ohne Zyklus = azyklisch
  • erster und letzter Knoten gleich, keine Kreuzungen

 Zusammenhängend ( connected )

  •  für alle u, v  ∈ V, u  ≠ v gilt:
  • Kantenzug k = ( vo , … , vn )  ∈ Vn+1 
  • mit vo = u und  vn = v

weiteres unter Bäume (ungerichteter, azyklischer, zusammenhängender Graph)

IT – Bäume

Allgemeines

  • Kante, die von Knoten A nach Knoten B geht
  • A – Vater ( Vorgänger, parent )
  • B – Sohn ( Kind, child )
  • Zwei Knoten vom selben Vater – Brüder ( siblings, Geschwister )
  • Grad eines Knotens – Anzahl direkter Nachfolger
  • Grad eines Baumes – max. Knotengrad aller Knoten
  • Blätter – Knoten vom Grad 0
  • innere Knoten Grad > 0
  • jeder Knoten hat genau 1 Vorgänger
  • Stufe eines Knotens – Pfadlänge von der Wurzel
    Wurzel – Stufe 0
    Knoten – Stufe des direkten Vorgängers K + 1
  • Höhe h – max. Stufen der Baumknoten + 1
  • Gewicht w – Anzahl aller Blätter
  • Menge mehrerer Bäume – Wald

Wurzel W
Blätter G, B, A, L, Q, F, I
Innere Knoten G, B, W
Höhe max. Stufe + 1, h = 4

Binärbaum

  • endliche Menge von Elementen
  • ist entweder leer oder hat ausgezeichnetes Element (Wurzel)
  • außerdem
    • übrige Elemente in 2 disjunkte Untermengen zerlegbar
    • Untermengen sind selbst Binärbäume

 

Binärbäume mit disjunkten Untermengen

 

links iO – rechts nicht iO, da B weder als linkes noch als rechtes Kind erkennbar ist

 

Untermengen sind nicht disjunkt
B und C haben gleiche Untermenge E

 

 

Spezielle Binärbäume

  • ähnlich – selbe Struktur
  • äquivalent – selbe Struktur und selbe Information
  • vollständig
    • jeder Knoten der Stufe h-1 ist ein Blatt
    • jeder Knoten der Stufe < h-1 hat nicht leere linke und rechte Unterbäume
  • max. Anzahl Knoten auf Stufe k ist 2k ( 0 ≤ k ≤ h – 1 )
  • max. Anzahl Knoten bei Höhe h ist 2h– 1 ( h ≥ 1 )
  • strikt – jeder innere Knoten besitzt nicht-leere linke & rechte Unterbäume
  • ausgeglichen, wenn für alle k ≥ 0 gilt:
    • jedes Blatt ist auf Stufe k oder k + 1
    • jeder Knoten auf Stufe < k hat nicht-leere linke & rechte Unterbäume
  • fast vollständig, wenn für für alle k ≥ 0 gilt:
    • jedes Blatt ist auf Stufe k oder k + 1
    • jeder Knoten auf Stufe < k hat nicht-leere linke & rechte Unterbäume
    • falls innerer Knoten Nachfolger (nicht direkter Nachfolger) auf Stufe k + 1 besitzt,
      dann ist linker Unterbaum vollständig mit Blättern Stufe k + 1

 

strikt
ausgeglichen

 

ausgeglichen

 

strikt
ausgeglichen
fast vollständig

 

IT – Suchverfahren

Suche in ungeordneten linearen Listen

Sequentielle Suche

  • durchlaufe Liste sequentiell bis Schlüssel gefunden oder Listenende erreicht ist
  • linearer Suchaufwand: O(n)

Suche in geordneten linearen Listen

Sequentielle Suche

  • durchlaufe Liste  (aufsteigend) solange Suchschlüssel größer aktueller Schlüssel und Listenende nicht erreicht
  • linearer Suchaufwand: O(n)

Binäre Suche

  • V1
    • Intervallunterteilung bis Intervallgröße = 1
    • Aufwand: O(log²n)
    • kein Abbruch, selbst wenn Schlüssel gefunden wird
  • V2
    • Divide & Conquer
    • auf Pos. bezogen mittlere Element suchen und mit Schlüssel vergleichen
    • anschließend ggfs. Teilbereich weiter durchsuchen
    • zmin = 1 (sofortiger Fund)
    • zmax = h (Höhe des Baumes) –> Herleitung für Examen!!! (folgt)
    • Aufwand worst-case: O(logn)

 Sprungsuche / Intervallsuche

  • sortierter Datenbestand in Sprüngen überqueren
  • Abschnitt lokalisieren
  • einfache Sprungsuche
    • konstante Sprungweite
    • sequentielle Suche im Sprungbereich
  • binäre
    • konstante Sprungweite
    • binäre Suche im Sprungbereich
  • Aufwand: O(√n) = O(n^½) – zwischen sequentieller und binärer Suche

IT – Stack / Queue

Stack

  • Kellerspeicher, Stapel, LIFO (Last In First Out)
  • Liste, bei der alle Änderungen (Einfügen, Löschen) nur am Ende Top vorgenommen werden
  • Funktionen:
    • Create – erzeugt leeren Stack
    • Init – initialisiert Stack als leeren Stack
    • Push – fügt neues Element hinzu
    • Pop – entfent aktuelles Element
    • Top – zeigt aktuelles Element an
    • Empty – fragt ab, ob Stack leer ist

FIFO

  • Schlange, Queue, Warteschlange, FIFO ( First In First Out)
  • Funktionen:
    • Create – erzeugt leere Schlange
    • Init – initialisiert Schlange als leere Schlange
    • Enqueue – fügt Element ans Ende der Schlange hinzu
    • Dequeue – entfernt Element; das am längsten in der Schlange verweilt
    • Front – zeigt 1. Element
    • Empty – prüft ob Schlange leer ist

 

Zoo Neuwied

Oben erwähnter Zoo erwartet tatsächlich, dass man vor Veröffentlichung der Bilder eine Genehmigung einholt… das macht nicht mal der Kölner Zoo.

IT – Vererbung / Polymorphismus

Spezialisierung

  • allgemeinere Klasse wird verfeinert
  • ist-ein(e) – Beziehung
  • Bsp. Student ist eine Person (Spezialisierung)
  • kann zu einer Oberklasse mehrere Unterklassen liefern  (disjunkt oder überlappend)

Generalisierung

  • spezielle Klasse wird verallgemeinert
  • invers ist-ein(e)-Beziehung
  • Bsp. Kugel, Würfel sind geometrische Körper (Generalisierung)

Vererbung

  • gemeinsame Eigenschaften (Attribute) und Methoden werden von der Oberklasse an Unterklasse weitergegeben –> vererbt
  • transitiv –> Unterklasse B erbt von Oberklasse A  und Unterklasse C erbt von B (und A, da b von A erbt)
  • im UML durch Pfeilspitzen gekennzeichnet
  • Bsp. Kombi ist ein spezieller PKW, PKW ist ein spezielles Fahrzeug
  • Unterklasse kann geerbte Attribut verdecken oder überschreiben

Polymorphismus

Aufruf einer überschriebenen Methode einer Oberklasse aus der Unterklasse

Bsp. Graphikobjekt hat zeichnen()-Methode, ebenso die Unterklassen Kreis und Rechteck – allerdings in überschriebener Form, da diese spezialisierte Versionen benötigen und die allgemeine zeichnen()-Methode nicht so nutzen können

IT – Objekte und Klassen

Objekte

  • jedes Objekt hat Zustand, Verhalten, Identität
  • viele Objekte gleicher Art möglich
  • daher Gruppierung in Klassen bei gleicher Datenstrutktur und gleichem Verhalten
  • Instanz einer Klasse
  • Kapselung von Zustand und Verhalten (Geheimhaltungsprinzip)
  •  Zugriff auf Attritbute ausschließlich über Methoden (s.o.)

Relationen

  •  Assoziationen
    • strukturelle Beziehungen zwischen den Objekten
    • spez. Aggregation
      • besteht-aus/ist-Teil-von-Relation
      • Bsp. Auto hat Reifen, Türen, Motor, etc.
      • Bez. Raute – leer und halbvoll
    • [Name],Leserichtung Pfeilspitze,
    • [Rolle] kann Kardinalität haben
      • 1 – genau 1
      • 0..2 – zwischen 0 und 2
      • * 0 oder mehr
      • 1,2,3,6 – 1 XOR 2 XOR 3 XOR 6
      • 1,2,6..* – 1 XOR 2 XOR min. 6
  • Spezialisierung / Generalisierung

 Klasse

  • neuer Referenztyp
  • eindeutiger Name / Identifier
  • ggfs. Oberklasse / Super
  • ggfs. Interfaces
  • Erzeugung einer neuen Instanz über new
  • kann mehrer Konstruktoren unterschiedlicher Signatur haben

Konstruktoren

  • public, protected , private
  • kein Rückgabetyp/-wert
  • expliziter Aufruf nur aus einem anderen K. über this oder super
  • Name identisch mit Klassenname
  • falls kein K. daklariert ist, wird Standardk. ohne Params verwendet

Zugriffskontrolle

+ public – für alle zugreifbar

– private – nur für eigene Klasse zugreifbar

# protected – nur für inheratiance  & package zugreifbar (Unterklassen, andere Klassen im gleichen Paket)

 Klassenattribute

  • in UML durch Unterstreichen gekennzeichnet
  • in Java durch static deklariert

IT – UML

Wofür?

  • graphische Visualisierung
  • Spezifizierung
  • Konstruktion
  • Dokumentation
  • Sprachstandard

Klassendiagramm

schematisch, statistisch; Menge von Klassen und ihre Relationen

Bsp. Stuhl, Tisch

Objektdiagramm

tatsächlich, existent; Menge von Objekten und ihre Relationen, Momentaufnahme der Instanzen von Objekten

Bsp. blauer Stuhl

IT – Komplexitäten

Eigenschaften eines Programms

  • Effizienz
  • Korrektheit
  • Zuverlässigkeit
  • Robustheit

Zeitkomplexität: Aufwand an Rechenzeit (in Schritten gemessen)

Unterscheidung:

  • worst-case
  • best-case
  • average-case

Beschreibung:

  • exakt: Zählfunktion T: N -> N; n ∈ N
  • asymptotisch: Angabe einer Vgl.größe (Komplexitätsklasse)

Speicherplatzkomplexität: Umfang des zu reservierenden Speicherplatzes

Komplexitätsklassen

obere Schranke

O(f(n)) := { g: N -> N | ∃c ∈ R, c >0: ∃ n0 ∈ N: ∀n >= n0: g(n) ≤ c * f(n)}

untere Schranke

Ω(f(n)) := { g: N -> N | ∃c ∈ R, c >0: ∃ n0 ∈ N: ∀n >= n0: g(n) ≥ c * f(n)}

 

O( 1 ) – konstant

O( log2n ) – logarithmisch – Bsp. binäre Suche

O( n ) – linear – Bsp. sequentielle Suche

O( n * log2n ) – n log n – Bsp. gute Sortierverfahren

O( n² ) – quadratisch

O( n³ ) – kubisch

O( 2^n ) – exponentiell

 

Faustregeln

  • Fallunterscheidung: Kosten der Anweisung + Kosten der teuersten Alternative
  • Schleife: Zahl der Durchläufe * Kosten der teuersten Durchführung
  • Rekursion: Anzahl der Aufrufe * Kosten der teuersten Durchführung
  • Vergleich versch. Operationen: Kosten der einzelnen Operationen bestimmen

IT – Java

  • Datentypen (Elementare D., ADT, oder Referenztyp)
  • Literale
  • Variablen verschiedener Referenzstufen
  • Ausdrücke & Operatoren
  • Typkonversion (implizit, explizit (cast))
  • Anweisungen (Ausdruck, Deklaration, Kontrollfluss)
  • Höhere Datentypen (Felder, Arrays)
  • Unterprogramme
  • Parameterübergabe (call by value, call by reference)