Bestandteile des Anfangs- und Endzustands

Vorsicht bei globalen Variablen – side effects.

Eingangs-, Ausgangs- und Übergangsgröße

Übergangsgrößen werden geändert  Eingangsgrößen werden benutzt

Ausgangsgrößen werden erzeugt    irrelevant, hat in der Spezifikation nichts zu suchen

Dateien als Bestandteile der Schnittstelle
Dateiname
Pfad
Format
Dateistruktur
Satzaaufbau
Feldinhalte: Datentypen, Wertebereiche, Bedeutung

Zustands- und Überführungsschema
Eingabe -> f -> Ausgabe
salopp Eingabe + Funktion = Ausgabe
Aus zwei Teilen ergibt sich der dritte.

Zustandsschema:
statisch
gegebene Eingabe und gewünstche Ausgabe
Wie scheint nicht auf; abstrakt; Implementierer erfüllt Lücke;
schwierig zu spezifizieren (alle zustände sind anzugeben);
z.B: p,q e ℝ; ges.: x…..
wenn Anfangs- und Endzustand gut formal beschrieben werden können; es nur wenige Wege zum ZIeel gibt.

Überführungsschema:
gegebene Eingabe und auszuführende Funktion
dynamisch; Ausgabe ergibt sich aus Funktion
Beschreibt den Weg
oft genauer
Sonderfälle leichter zu erkennen
Gibt Hinweise auf den Lösungsweg
Gefahr der Überspezifikation; Beschränkt Implementierer; kann bessere Lösungswege vereiteln
Beispiel: Lösungsformel quadratische Gleichung
wenn Aktion wichtiger als Ergebnis

In der Praxis oft vermischung der 2 Formen

Abstraktionsgard:

verbal ——————————- formal
Ungangssprache unscharf                mathematische Ausdrücken präzise
mehrdeutig                                         eindeutig, widerspruchsfrei
verständlich                               schwer verständlic
(Hausverstand) (Experten)
ausschweifend knapp

Beispiel
oder: umgangsprachlich (exklusiv), mathematisch(inklusiv)
bei Wind und Regen oder Schnee

Algorithmen mit Gedächtnis
weichen von klassischer Definition ab

Trennung in zwei Funktionen
1. Berechnung des Ergebnisses
2. Berechung des Folgezustands (Zustandsüberführungsfunktion)

Mealy vs Morreautomaten

Wie wird der Anfangszustand eingestellt?

Wie wird der Zustand von Aufruf zu Aufruf gerettet?

statische vs. dynamische Variablen
dynamisch: bei Prozedureintritt erzeugt, danch undefiniert
statisch: bei Porgammstart erzeugt; von Prozeduren unabhängig

lokal vs globale Variablen
lokal: nur in der aktuellen Prozedur bekannt
global: überall bekannt

Dynamische Voribalen sind immer lokal
Globale Variablen sind immer statisch
Lokale Varablen können auch statisch sein.

Lokale statischen Variablen in Jana:
A(….) {
static int x = 0 // Wertzuweisung passiert nur einmal
…
}

Zustandsgrößen in realen Progarmmierprachen (in Jana-Notation dargestellt)
in C, C++ wie in JANA

in Java: außerhalb des Algorithmus in der Klasse
ein privates Gedächtnis nur für einen Algorithmus in Java nicht möglic

(6) Ideal in objektorientierten Sprachen

Algorithemn mit Gedächtnis haben “side effects”
Wirkung Größen, die nicht in der PArameterleste aufscheinen
Reihenfolge der Aufrufe können eine Rolle spielen

if (A()&&B() || !A()&&!B()) {…}
problematisch wenn A() od. B() mit Gedächtnis sind und Zustand wechseln
sicherheitshalber in Variable zwischenspeichern

Komplexität

Komplexität =? Aufwand
Auffasungen in der Informatik: Laufzeit, Seicher, Struktur Komplexität
Hier: Laufzeitkomplexität Laufzeit t = f(n)
n: Problemgröße

n
eine ganze Zahl, charakterisiert den Umfang der Aufgabe
typisch: Menge zu verarbeitender Daten (z.B Länge eines Textes oder Feldes)
bei numerischen Aufgaben auch:
Stellenanzahl von Zahlen

Komplexität eines gegebenen Algorithmus
Wie verhält sich die Laufzeit des Algorithmus in Abhängigkeit von der Problemgröße?
Auch zum Verglich mehrerer Algorithmen:
Welcher ist (für welche Problemgrößen)schneller?

Komplexität eines Problems
Gibt es eine Schranke die nicht unterboten weredn kann?

Laufzeitanalyse
Grobanalyse; Feinanalyse
Grazanalyse ist von Sprache und Maschine unabhängig

Abstraktionsschichten

Black Box: von Außen, z.B in der Zukunft zu entwickelnn
Grobstruktur: Lösungsidee
Detail: für Algorithmusanalyse

Black Box
Beispiel Median (sort wird nicht erklärt)

Grobstruktur
sort(liste n) {
for (i=l…n-l) {
Suche das kleineste Element listen[k] in liste [i:n]
Vertausche liste[k] mit liste[i]
}
}
kommt Lösung näher
Veranschaulicht das Verfahren, lässt Implementierungsdetails aus.

Detailsicht
Ausforulierung der informell gehaltenen Teile:
sort(liste n) {
for (i=l..n-l) {
k=i
for (j=i+l…n) {
if (liste[j] < liste [k]) { k = j}
}
liste[k]<-> liste [i] // <-> Vertauschungsauktion
}
}

Welche Abstraktionsschicht für welchen Zwech?

Common Mistake: zu viel Detail am Anfang
Grundregel: so abstrakt wie möglich denken, nicht mehr Details als nötig

Black Box: Betonung des Schnittstellenaspekts; wie soll der Algorithmus benutzt werden; Vision

Grobstruktur: für die ersten Enwurfsschitte; erklären;

Detail: genauer Ablauf, Sprach- oder Maschinendetails

Bestandteile von Algorithmen
Was sind unsere Atome?

for vs while
for- und while-schleife sind sematisch äquivalent.

Semantische Äquivalenz

for- und while-Schleife heißen semantisch äquivalent wenn gleiche Anfangs und Folgezustände.

ZFA -> FS -> ZFE und ZWA -> WS -> ZWE gilt:
………….

switch/case = Kaskade von if
if-Kaskade langsamer
trotzdem semantisch Äquivalent; nur Wirkung zählt

Benötigte Bausteine
1. Elementaraktion

Aktion kann sein:
Zweisung: x = ausdruck
E/A-Anweisung: read(war eof); write(wert)
Ausfruf: sort(liste n)
nichts: {} leere Anweisung

2. Sequenz
Schritte

3. Binäre Verzweigung
Bedingung, ja nein, kommt am Ende wieder zusammen, neinzweige dürfen leer sein

4. Abweisschleife
while Schleife; eso lange Bedingung erfüllt ist, Inhalt 0 oder mehrmals ausgeführt.

D-Diagramm (D nach Dijkstra)
die oben gennanten 4 Bausteine reichen um alle Algorithmen zu formulieren -> Ablaufdiagramme heißen D-Diagramme.

Gegensatz: Spaghetti-Struktur (Sprungmarken)

Beweis (nach Knuth)
Zerlegung in Blöcke, Nummerierung, state,
while sate != 0 – swictch case state 1, state 2 state 3,
jana hat kein break

Eigenschaften
nur noch eine Schleife
einzelne Fälle enthalten nur noch Sequenzen (eventuell binäre Verzweigung am Ende)
Funktiontiert für jeden Algorithmus
Für Praxis nicht geeignet, notfalls für C-Programm mit goto -> Java

?andere Formen: Codeverdopplung

Beispiel: n+1/2 Schleife

while (true) { //endlos
Lesen
if (Ende) {break}
Verarbeiten
}
Codeverdopplung:

Lesen
while (!Ende) {
Verarbeiten
Lesen
}
Unangenehm: schwer zu warten; unlogisch

Schaltervarible:

nochDaten = true
while (nochDaten) {
Lesen
nochDaten =! Ende
if (nochDaten) {Verarbeiten}
}
unangenehm: 2 Prüfungen für nochDaten

Spezifikation

Zweck
Schnittstellenbeschreibung
Aufgabenbeschreibung
….

Spezifikation

Spezifikation | Entwurf Implementierung Test (40 Entwurf, 20 Implementierung, 40 Test)
Dokumentation

mit Lösungsideen  anfangen, verennen dokumentieren, testen dokumentieren ausbessern dokumentieren

Spezifikationsdokument (Vertrag)

Was soll eigentlich eentwickelt werden?
Worauf ist zu achten?
Was kann vorausgesetzt werden?
Was gilt als richtig, was als falsch?

Der Begriff “Spezifikation”
Salopp: Aufgabenstellung
Dokument: Anfordungsdefinition, Pflichtenheft
juristisches Doukment
von Vertragspartnern gemeinsam verfasst (Auftraggeber, Entwickler)

Spezifikation          Implementierung
Aufgabe – Lösung
WAS? – WIE?
von außen – von innen
Black box – Details
Schnittstellen – Algorithmen

Eigenschaften guter Spezifikation
einfach: kein Farchjargon
eindeutig: verdammt schwierig
vollständig:kein Interpretationsspielraum in wesentlichen Punkten
minimal: kei “Wie” behandeln

Funktionale Anforderungen: Was
NichtFunktionale Anforderungen: Qualitätskriterien

funktionale Anforderungen
Was?
Ausgabe…
bla….

Teile Schnittstellenbeschreibung
Aufrufschnittstelle
Parameter
Systemzustand
Dateien
Geräte
Systemumgebung: welche Klassen dürfen nicht benützt werden?
Benutzerschnittstelle

Programm vs Prozedur
Programm: selbständig ablauffähig; Anwendersicht
Prozedur: bestandteil, nicht ablauffähig;

Schnittstellen von Prozeduren
Aufruf -> Parameter ->Prozedur (liefert Daten zurück)??
Variablen ??l
Dateien <-> Prozedur??
Systemumgeben <-> Prozedur??
…

Prozedur
Aufgabe: stichwortartige Beschreibung (eine Zeile, kurz, pregnant)
Aufruf: Name, Parameter, Funktionswert
Eingangsgrößen: Eingangsparameter mit ihren Datentypen und ihre Bedeutung
Ausgangsgrößen: Ausgangsparameter wie Eingangsgößen
Funktion: wie steheln Eingang und Ausgangsrößen in verbindung
Fehler: was tun bei Fehler?

Folgerungen
ZA muss zur Lösung reichen
Der Algorithums darf sonst nichts ändern
keine Annahmen (ausserhalb der Spezifikation)
idealerweise Sicherheitsprüfung