Das hatte ich ganz vergessen… seit über 4 Jahren raubten mir Studium und jetzt das Anschlusstudium die Zeit um in Ruhe einen guten Film zu schauen. Für mehr als TV hatte es die letzten Jahre nicht gereicht. Aber jetzt – mit Mann und Sohn und Studium und Vollzeitjob und Training für den nächsten Wettkampf – habe ich keine Zeit mehr für schlechte Filme.
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 = vn – geschlossener 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
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
- Beziehungen zwischen allg. und spez. Klassen
- nutzt Vererbung
- –> siehe Vererbung/Inheritance
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 – 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)
IT – Algorithmen
Def. genaue, endl. Beschreibung eines allgemeinen Verfahrens, nutzt elementare, ausführbare Schritte
statt 3 + 4 –> a + b
Effektivität
jeder einzelne Schritt ausführbar
Effizienz
Leistungsfähigkeit, geringer Aufwand
Korrektheit
partiell: jedes Ergebnis entspricht der Ausgabespezifikation sofern die Eingaben der Eingabespez. entsprechen, nicht zwingend anhaltend
total: partiell korrekt, terminiert nach endl. vielen Schritten, nach jeder Eingabe, die der Eingabespez. entspricht
Terminierung
Algorihtmus, der bei den Eingabespez. entsprechenden Eingaben nach endlich vielen Schritten abbricht.
Determinismus
weiterer Ablauf des Algorihtmus ist zu jedem Zeitpunkt eindeutig bestimmt, Ablauf nur von Eingaben abhängig
Determiniertheit
liefert immer gleiche Ausgaben bei den Eingabespez. entsprechenden Eingaben