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

von Neumann – Computer

besteht aus Rechenwerk, Steuerwerk, Speicher, Daten- und Adressbus

Speicher

  • Eingang Adressen
  • Eingang Steuersignale
  • Ein-/Ausgang Daten

Steuerwerk

  • Befehlsdaten
  • Ausgang Adressen
  • Ausgang Steuersignale Rechenwerk
  • Ausgang Speicher

Rechenwerk

  • Eingang Steuersignale
  • Ein-/Ausgang Daten

schematische Darstellung eines von Neumann Computers

IT – Lerninhalte: Definitionen I

C6ff

Zeichen – Alphabet
Element aus A., d.h. aus einer endl. Menge, die zur Darstellung von Informationen dient
Zeichenvorrat, linear geordnete Menge (siehe auch Relationen, totale Ordnung)

Code
Bijektion (eineindeutige Abbildung) zwischen Zeichen & Bitmuster

File / Datei
strukturierte Datenmenge

Interpreter – C52ff
zeilenweise Umwandlung in Maschinensprache
Sprachen mit einfacher Syntax
während der Laufzeit
mehrfache Übersetzung bspw. bei Schleifen notwendig
Abbruch bei Syntaxfehler zur Laufzeit

Compiler
Gesamtprogramm wird umgewandelt
vor der Laufzeit 1x übersetzen, daher zur LZ schneller
bei jeder Änderung neu kompilieren notwendig
–> lexikalische –> syntaktische –> semantische Prüfung –> Übersetzung –> Codererzeugung –> Objektprogramm

Java virtual machine (JVM) liest Java Bytecode und realisiert dadurch Plattformunabhängigkeit

 Zeichenvorrat – C62ff
endliche Menge unterscheidbarer, im Kontext atomarer Objekte (Bilder, Symbole,…)

Wort
Folge von Zeichen, die im Kontext als Einheit betrachtet werden

Freier Monoid, Sprache
alle darstellbaren Wörter, einschließlich dem leeren Wort

Grammatik
Regelwerk zur Definition einer Sprache L

Syntax – C60f
Form, allgemeine Grammatiken, Syntaxdiagramme, EBNF, Java Notation

Semantik
Bedeutung, natürliche Sprachen, UML