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)

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

IT – Softwareentwicklung: Phasenmodell & Schneckenmodell

Phasenmodell

Problem führt über Anforderungsanalyse zur Anforderungsspezifikation.

Es folgt der Systementwurf, der zur Systementwurfsspezifikation führt.

Der Detailentwurf endet in der Detailentwurfsspezifikation.

In der abschließenden Codierung und Inetgration wird dann das ausführbare Programm erarbeitet.

Schneckenmodell

Beginnt beim Problem und durchläuft dann nacheinander in immer größeren Kreisen die Phasen Anforderung – Systementwurf – Detailentwurf und Codierung.
Die größeren Kreisen stellen dabei den intensiveren Arbeitseinsatz und die längere Verweildauer dar.

IT – Grammatiken & Notationen

Chomsky-Grammatik

4-Tupel G = ( N , T , P , S )

N – endliche Menge Zeichen, Nichtterminalsymbole

T – endliche Menge Zeichen, disjunkt N, Terminalsymbole

S ∈ N – Startsymbol

P – endliche Menge Regeln der Form (p, q) ∈ ( N ∪ T ) *

 Syntaxdiagramme

N Rechteck

T langrunder Kreis

gerichtete Pfeile verbinden die einzelnen graphischen Elemente

Grundtypen:

  • Sequenz
  • Option
  • Alternative
  • Wiederholung

EBNF

erweiterte Backus Naur – Form

besteht aus:

  • einer Startregel
  • sonstigen Regeln
  • Terminal- und Nicht-Terminalsymbolen

T – nicht speziell gekennzeichnet

N – in <> eingeschlossen

P – Form: rechte Seite = linke Seite

  • linke Seite: genau ein N
  • rechte Seite: T, N, Alternativen, geklammerte Ausdrücke
  • Klammerarten:
    • ( ) Gruppierung
    • [ ] Option
    • { } n-fach (auch 0 mal)