Lovefilm fetzt

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.

„Lovefilm fetzt“ weiterlesen

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

 

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 – 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