Halbaddierer in der Simulation

Der Halbaddierer hat 2 Eingänge und 2 Ausgänge (s und c für "sum" und "carry"). Der Ausgang s wird 1, wenn einer der Eingänge 1 ist, aber nicht beide. Innen muss es also ein OR-Gatter und ein AND-Gatter geben sowie einen Inverter für das AND-Gatter. Außerdem noch ein AND-Gatter, das auch 1 ergeben muss, damit am Ausgang 1 steht. Dieses zweite AND-Gatter prüft die Voraussetzung, dass OR vorliegt sowie die Invertierung vom ersten AND. Dazu gibt es intern 2 Hilfsdrähte.

Digitale Schaltkreise

Die Simulation besteht aus Drähten und Schaltelementen. Drähte können die Werte 0 und 1 annehmen. Drähte werden durch einen Konstruktor erzeugt und können mit Namen versehen werden. Schaltelemente bestehen dann aus passend vielen Drähten.

Klassendiagramm in Alloys Sprache umwandeln

Hier wird pro Klasse eine Signatur (sig) angegeben. In die Signatur kommen alle Attribute mit Namen, Menge und Typ. Bei Attributen ist die Menge immer one. Außerdem hinein kommen die Beschriftungen und Ziele der Assoziationen (Verbindungslinien). Vererbung wird auch hier mit extends ausgedrückt.

Wichtig sind auch noch die facts. Ein fact hat einen Namen. Er nimmt eine bestimmte Menge einer Signatur als Ausgangspunkt und eine bestimmte Menge einer anderen als Bezugspunkt. Dann wird gesagt, in welcher Menge ein bestimmtes Verhältnis zwischen beiden existiert. Bei dem Verhältnis wird Bezug genommen auf die Eigenschaften der facts.




Das Klassendiagramm

Im Klassendiagramm bekommen die Klassen (= Oberbegriffe) Kästen mit den Attributen (Eigenschaften) und Methoden (das, was sie machen können). Die Kästen können untereinander verbunden werden. Die Verbindungen können beschriftet werden, um sie weiter zu spezifizieren. Verbunden werden sie, wenn eine Klasse mit den Objekten der anderen Klasse etwas macht.
Bei den Attributen werden Name und Typ angegeben. Bei den Methoden Name, Argumente plus Typ und Rückgabetyp.

Verhaltensmodellierung und Interaktionsmodellierung

Verhaltensmodellierung betrifft das Verhalten des Objekts an sich. Interaktionsmodellierung betrifft die Interaktionen zwischen Objekten.

Strukturelle Aspekte des Systems in der Modellierung

Zu den strukturellen Aspekten des Systems gehören:


  • Klassen
  • Attribute
  • Vererbungsstrukturen
  • Pakete

Konfigurationsmanagement

Eine Konfiguration ist eine Zusammenstellung von Einheiten zu einem System. Das Konfigurationsmanagement besteht aus:


  1. Dateimanagement: Welches sind die Konfigurationseinheiten?
  2. Versionsmanagement: Was, wenn sich Konfigurationseinheit ändert?
  3. Änderungsmanagement: Wann darf sich Konfiguration/Konfigurationseinheit ändern?
  4. Build Management: Wie wird aus Konfigurationseinheiten ein Produkt?

Qualitätssicherung bei Software

Bei der Qualitätssicherung in Bezug auf Software unterscheidet man analytische und konstruktive Qualitätssicherung. Die analytische Qualitätssicherung bezieht sich darauf, Fehler in der Software zu finden. Die konstruktive Qualitätssicherung hat zum Thema, die Fehler schon im Voraus zu vermeiden.

Extreme Programming (XP)

Extreme Programming ist gekennzeichnet durch:


  • Agilität
  • Teamwork
  • Konzentration auf das Ziel
  • Tests von Anfang an
  • Weniger Halten an Formales
  • Einbeziehung des Kunden von Anfang an

Komplexität bei der Softwareentwicklung

Komplexität ist alles, was das Entwickeln schwieriger macht. Zum Beispiel:


  • Großes Team
  • Alleinarbeit
  • Sprachbarrieren
  • Besondere Fachkenntnisse erforderlich
  • Verantwortung
  • Größe des Projekts
  • Qualitätsstandard
  • usw.

Prinzipien der Softwareentwicklung

Wenn es darum geht, welche Grundsätze bei der Entwicklung neuer Software gelten, dann gibt es folgende:


  1. Abstraktion: Verallgemeinerung; Entfernung von realer Welt
  2. Strukturierung
  3. Modularisierung
  4. Kapselung: Zugriffsrechte
  5. Separation of Concerns: Aufteilung der Aufgabenbereiche
  6. Inkrementalität: Alles Stück für Stück
  7. Grundlichkeit und Formalität
  8. Änderbarkeit

Arten von Softwarefehlern

Die Arten von Softwarefehlern sind:


  • Allgemeine Programmierfehler
  • Anforderungsprofilfehler
  • Fehlbedienungen nicht abgefangen
  • Testfehler

Die Warteschlange

Eine Warteschlange besteht aus zwei veränderbaren Listen. Diese Listen sind als solche ebenfalls veränderbar (=ganz austauschbar). Die eine Liste ist der Zeiger auf den Listenanfang und die andere der Zeiger auf das Listenende.

Die Warteschlange wird dann erstellt, indem für die Listen ein bestimmter Inhalt gespeichert wird.

Eine Liste ändern

Eine Liste wird geändert, indem etwas für den Fall ausgegeben wird, dass die Liste leer ist und für den Fall, das nicht, das erste Element irgendwie geändert wird und mit dem Listenkonstruktor cons vorne an den erneuten Aufruf der Funktion für den Rest der Liste angehängt wird. Auf diese Weise ist jedes Element der Liste einmal das erste Element und wird entsprechend geändert.

Iterative Berechnung

Bei der iterativen Berechnung zum Beispiel der Summe der Zahlen von 0 bis n wird eine Hilfsfunktion aufgerufen mit einem Startwert, einem Start-Zählerstand und eventuellen Hilfswerten.

Die Hilfsfunktion selbst gibt dann das Ergebnis aus, wenn der Zähler einen bestimmten Wert erreicht hat (wird mit if abgefragt). Ansonsten ruft sich die Hilfsfunktion selbst wieder auf mit neuem Wert und neuem Zählerstand und gegebenenfalls auch neuen Hilfswerten (die man für einige Berechnungen benötigt).

Die Zahlen von 0 bis n rekursiv zusammenrechnen

Dies funktioniert, indem mensch die eine Grenze abfängt (mit if) und dann die andere Grenze je nach Vorgabe verbindet mit einem erneuten Aufruf der Funktion für den Folgewert.

Feststellen, was ein Aufruf ausgibt (Substitutionsmodell)

Um festzustellen, was ein Aufruf einer Funktion ausgibt, fängt man bei dem Aufruf an und ersetzt schrittweise die einzelnen Dinge durch die ihnen zugeordneten Werte. Dies geht so lange, bis nur noch Dinge übrig bleiben, die nicht mehr durch gespeicherte Werte ersetzt werden können. Das ist dann die Ausgabe des Aufrufs.

Eine Grammatik für Palindrome mit der EBNF

Erstmal wird ein Buchstabe definiert mit dem Namen letter und als Alternativen eben die Buchstaben von a bis z. Diese müssen nicht ausgeschrieben werden, sondern es sind auch drei Punkte dazwischen möglich.

Das Palindrom selbst ist dann entweder gar nichts oder eines (=> eckige Klammern) von den Alternativen letter oder a pali a bis z Pali z (auch hier sind wieder drei Punkte dazwischen möglich).

Wenn ein konkretes Palindrom gemacht werden soll, ist Ausgangspunkt eben ein pali. Das wird dann in einer Folge von Pfeilen aufgelöst durch Ersetzung.

EBNF - Backus-Naur-Form (Grammatik)

Begriffe:


  • Syntax: Welche Programme sind formal zulässig?
  • Grammatiken: Beschreibung der zulässigen Strukturen für die Syntax
  • Nichtterminalsymbol: Linke Seite
  • Terminalsymbol
  • Ableitungsschritt: Ersetzung des Nichtterminalsymbols durch festgelegte Symbole
  • Startsymbol: Erstes Nichtterminalsymbol
  • Satz
  • Sprache: Menge aller ableitbaren Sätze
  • Regelalternativen: Mehrere Regeln mit gleichem Nichtterminalsymbol zusammengefasst durch senkrechten Strich
  • Optionale Wiederholung: Geschweifte Klammern -> Folge muss nicht, kann aber beliebig oft vorkommen
  • Optionales Vorkommen: Eckige Klammern -> Kann einmal oder gar nicht vorkommen
  • Gruppierungen: Alternativen innerhalb von Symbolfolgen. Durch runde Klammern.

Umgebungsmodell für Scheme für Fortgeschrittene

  • Eine veränderbare Liste wird als normale Liste dargestellt (Kästen mit cons inkl first und rest oder empty)
  • Bei der Veränderung einer veränderbaren Liste können die die Kästen verbindenden Pfeile ausgestrichen und neu gesetzt werden

Eine veränderbare Liste in Scheme machen

Erstmal wird ein Record für eine nicht-leere Liste erzeugt. Diese enthält ein veränderbares erstes Element und eine veränderbare Restliste. Dabei handelt es sich um einen parametrisierten Record.

Anschließend wird die veränderbare Liste an sich implementiert. Das geht über die Definition von mlist-of. Diese bekommt ein lambda (sort) und es wird signature mixed aufgerufen. Das mixed besteht dann aus einer empty-list und aus einer nicht-leeren veränderbaren Liste, die ihrerseits dadurch entsteht, dass deren Signaturkonstruktor mit sort und einer mlist-of sort aufgerufen wird.

Allgemein zur Technik der Nachrichtenweitergabe

Die übergebenen Werte werden hier mittels set! verändert.

Ungültige Eingaben werden mit einer violation abgefangen.

Ein Feld erzeugen mit der Technik der Nachrichtenweitergabe

Der Konstruktor des Feldes benötigt die Größe und das initiale Element. Intern werden dann mehrere Funktionen implementiert (mit letrec).

Zunächst wird das Feld als Liste erzeugt, indem die entsprechende Funktion aufgerufen wird (sie wird außerhalb implementiert) und das Ergebnis dem internen Namen zugeordnet wird.

Mit diesem Feld können dann verschiedene Dinge gemacht werden. Die Größe des Feldes wird ausgegeben, indem einfach n aus der Eingabe ausgegeben wird. Alle anderen Funktionen werden außerhalb implementiert und dann einfach aufgerufen. Zudem gibt es auch hier innerhalb von letrec eine dispatch-Funktion, die den Funktionsnamen die Ergebnisse der Stringvergleiche zuordnet. Diese wird auch aufgerufen.

Auch hier gibt es Schnittstellenoperationen, die jeweils ein fertiges Feld bekommen und dann dieses mit dem gewünschten String aufrufen und gegebenenfalls dann auch noch weitere Aufrufe machen.

Eine Funktion, die die Wahrscheinlichkeit von etwas bestimmt

Zunächst muss eine Hilfsfunktion implementiert werden, die feststellt, ob eine zufällige Zahl (mit random zu erzeugen) ein bestimmtes Erfordernis erfüllt oder nicht und dafür true oder false ausgibt.

Dann eine zweite Hilfsfunktion, die als interne Funktion (mit letrec geht das) eine Funktion speichert, die die Zahl der verbleibenden Versuche und die Zahl der erfolgreichen Versuche bekommt. In einer cond-Verzweigung wird das Ergebnis ausgegeben, wenn nur noch 0 Versuche verbleiben (das Ergebnis ist die Zahl der erfolgreichen Versuche geteilt durch die Gesamtzahl der Versuche). Ansonsten wird die Zahl der erfolgreichen Versuche im erneuten Aufruf hochgezählt, wenn die obige Hilfsfunktion true zurückgibt und die Zahl der verbleibenden Versuche runtergezählt. Bei false wird nur runtergezählt. Diese Funktion wird dann intern aufgerufen mit dem angegebenen Startwert und 0 für die erfolgreichen Versuche.

Die Oberfunktion dann bekommt die Zahl der Versuche und ruft die Prüf-Funktion (also die zweite Hilfsfunktion) auf mit der angegebenen Versuchszahl und der ersten Hilfsfunktion (dem Experiment).

Als Experiment kann zum Beispiel geprüft werden, ob eine zufällige Zahl im Einheitskreis liegt.

Eine Funktion implementieren, die einen veränderbaren Datentyp bekommt und diesen verändert

Eine solche Funktion bekommt einen fertigen veränderbaren Record und einen Wert des benötigten Typs. Dann wird begin aufgerufen, damit die Reihenfolge für die Veränderungen feststeht. Anschließend wird der Mutator aufgerufen, der eben den Record und den Wert bekommt. Anschließend wird der neue Wert ausgegeben durch Aufruf des Selektors (das ist der Rückgabetyp der Funktion dann. Ansonsten wird unspecific zurückgegeben).

Wenn etwas nicht geht, macht man eine Verzweigung und ruft violation auf.

Sollen solche Funktionen in einer Oberfunktion zusammengefasst werden, muss man auch begin verwenden wegen der Reihenfolge.

Einen veränderbaren zusammengesetzten Datentyp machen

Einen veränderbaren zusammengesetzten Datentyp macht man wie ein normales Record. Der Unterschied ist nur, dass es heißt: define-record-procedures-2. Zudem werden die Selektoren eingeklammert und bekommen neben dem Namen auch einen eigenen Mutator, der seinerseits set-name-sn! heißt.

Bei den Signaturen ist es so, dass sie grundsätzlich gleich bleiben und nur noch zusätzliche für die Mutatoren hinzukommen. Diese bekommen den Ausgangsdatentyp und den benötigten Typ für den Selektor und geben unspecific aus.

Fold-list in Scheme

Die Funktion fold-list bekommt ein Element, eine Funktion und eine Liste. Wenn die Liste leer ist, wird das eine Element ausgegeben. Ansonsten wird die Funktion angewendet aus das erste Element in der Liste und den erneuten Funktionsaufruf für fold-List mit dem Rest der Liste.

Die Elemente der Liste können mit 0,+,l addiert werden.

Eine Funktion kann auf alle Elemente der Liste angewendet werden (map-list), indem fold-list aufgerufen wird mit empty, (lambda (x xds) (cons (f x) xs) und l.

Alle Zahlen zwischen zwei Grenzen zusammenrechnen

Um die Zahlen zwischen zwei Grenzen zusammenzurechnen, wird das neutrale Element ausgegeben, wenn die Zahl der linken Grenze größer ist als die der rechten. Ansonsten wird die aktuelle Zahl der linken Grenze mit dem passenden Operator verknüpft mit dem erneuten Funktionsaufruf mit der nachfolgenden Zahl für die linke Grenze.

Wenn nur die graden/ungraden Zahlen verwendet werden sollen, wird das mit dem Prädikat even? abgefragt.

Wenn es dann darum geht, eine allgemeine Funktion zu implementieren, die als Basis verwendet werden kann, wird die Grenze mit dem neutralen Element beibehalten. Als Eingabe gibt es neben den beiden Grenzen aber noch zwei Funktionen, die auch einfach als Variablen dargestellt werden können. Die erste Funktion wird dann für die aktuelle linke Grenze aufgerufen, die verknüpft werden soll. Die zweite dann im erneuten Funktionsaufruf, um den Nachfolger für die Zahl der linken Grenze zu bestimmen. Statt der linken Grenze steht im erneuten Aufruf also der Funktionsaufruf mit der linken Grenze.

Die Eingaben für die Parameter-Funktionen haben das übliche lambda-Aussehen mit Parameter(n) und Rumpf. Kompliziertere Funktionen können auch ausgelagert definiert und dann einfach ausgerufen werden. Die Übergabe muss also nicht als komplettes lambda-Konstrukt erfolgen.

In der Signatur haben die Parameter-Funktionen (also die Funktionen, die beim Aufruf der Oberfunktion übergeben werden) das typische Aussehen mit zwei Klammern und einem Pfeil in der Mitte, der von der Eingabe zur Ausgabe führt.

Feststellen, ob ein Baum ein Suchbaum (geordneter Binärbaum) ist

Zunächst müssen Minimum und Maximum zurückgegeben werden können. Dafür benötigt es zwei Funktionen. Wenn der Baum leer ist, gibt es sowas nicht und damit eine violation. Wenn der passende Teilbaum leer ist, dann ist das Minimum/Maximum der Eintrag am Knoten. Wenn nicht, dann ruft sich die Funktion selbst wieder auf mit dem passenden Teilbaum.

Die eigentliche Funktion gibt einen booleschen Wert zurück. Wenn der Baum leer ist, dann true. Wenn beide Teilbäume leer sind, dann auch. Wenn nur einer der Teilbäume leer ist (hierfür 2 cond-Verzweigungen), dann muss das Wurzelelement größer bzw kleiner sein als das Minimum bzw Maximum des Teilbaumes und die Funktion muss für den Teilbaum erneut aufgerufen werden (dass alles mit and verknüpft). Wenn keiner der Teilbäume leer ist, müssen 4 Voraussetzungen erfüllt sein, die durch and verknüpft sind und aus der Kumulation dessen bestehen, was oben steht.


Einen Huffmanbaum malen und eine Nachricht damit codieren

Gegeben ist eine Nachricht. Da werden zunächst die Zeichen (Buchstaben) gezählt und in einer Menge als Paare aus Zeichen und Häufigkeit aufsteigend nach der Häufigkeit angeordnet.

Dann nimmt man die zwei jeweils nach der Häufigkeit kleinsten Paare und packt sie zusammen. Es entsteht wieder ein Paar, wobei die Zeichen nun eine Menge sind und die Häufigkeit die Summe aus den Einzelhäufigkeiten ist. Die Zeichnung geht dann von unten nach oben. Ganz oben hat man dann die Gesamthäufigkeit und die Menge aller vorhandenen Zeichen.

Dann kriegen alle linken Äste eine 0 und alle rechten eine 1.

Die Codierung geht dann, indem man pro Buchstabe/Zeichen oben anfängt und die Nullen und Einsen auf dem Weg von oben nach unten notiert.


Einen geordneten Binärbaum spiegeln

Um einen geordneten Binärbaum zu spiegeln, muss bei Eingabe eines leeren Baumes (empty) ebenfalls empty ausgegeben werden. Ansonsten wird der Konstruktor (make-node) aufgerufen mit vertauschten Teilbäumen, wobei für diese ebenfalls die Funktion aufgerufen wird (weil sie ja ihrerseits wieder Ausgangspunkte für Teilbäume sind).

Die Testfälle umfassen den leeren Baum (empty) sowie alles mit make-node.

Implementierung des geordneten Binärbaums in Scheme

Für einen geordneten Binärbaum wird in Scheme erst ein normales Record für den Knoten erstellt (node). Dieses enthält als Selektoren den node-entry sowie node-left und node-right.

Der Baum selbst ist ein gemischter Datentyp aus einer empty-list und einem node (signature - mixed).

Danach kommen erst die Signaturen. Das deshalb, weil der Konstruktor den Baum an sich als Eingabe braucht (bei den Teilbäumen) und die Selektoren der Teilbäume einen Baum ausgeben sollen.

Parametrisiertes Record

Neben dem normalen Record gibt es auch den parametrics-Record. Das Schema ist:

(define-record-procedures-parametric name name-of
  make-name name?
  (name-s1 name-s2 name-s3 ... name-sn))

Die Signaturen dazu umfassen den Konstruktor, das Prädikat und die Selektoren. Die Besonderheit hier ist, dass der Signatorkonstruktor (name-of) in die Signaturen eingebaut wird. Dies beim Konstruktor als Endprodukt mit den Eingaben und bei den Selektoren als Ausgangspunkt.


Der Signaturkonstruktor kann dann verwendet werden, um einen konkreten Typ des Records festzulegen, wenn die Komponenten (Selektoren) variabel sind. Dies geht auch mit define, lambda und signature. Bei lambda wird dann der gewünschte Typ entgegengenommen und die Definition erfolgt über die Kombi aus Signaturkonstruktor und Variable, die über lambda festgelegt wird.

Geordnete Binärbäume in Scheme

Geordnete Binärbäume werden als Mengen mit add-set gemacht, wobei der Ausgangspunkt ein empty-set ist. Alles, was kleiner ist, kommt nach links und alles größere nach rechts.

Wenn man die Zahlen von 1 bis 7 hat und einen Baum der Höhe 2 haben möchte, fängt man in der Mitte (also bei 4) an und fügt die 4 an empty-set an. Dann nimmt man die zweitkleinere Zahl nach 4 - also die 2. Dann die beiden Ränder der 2 (die damit ebenfalls mittig ist) - also 1 und 3.
Die andere Seite ab 4 geht nach dem gleichen Schema. Also die Mitte - 6 - und dann 5 und 7.

Baum als Liste in Scheme

Bäume werden als Listen in Scheme implementiert. Ein list ist ein Knoten. Gelesen wird von links nach rechts.

Funktionen für Listen allgemein

Das Schema sieht immer so aus, dass eine Fallunterscheidung getroffen wird. Bei dieser wird mit if erst geprüft, ob die Liste leer ist. Wird eine neue Liste ausgegeben, ist meist die Folge, dass empty ausgegeben wird. Soll dagegen keine Liste entstehen, muss da etwas anderes ausgegeben werden.

Wenn die Liste nicht leer ist, wird das erste Element irgendwie verändert und dann entweder mit cons oder einer anderen Operation (wenn keine neue Liste ausgegeben werden soll) mit dem erneuten Aufruf für den Rest der Liste verknüpft.

Wenn die Funktion, die das erste Element (und damit alle Elemente in der Liste) verändert, komplexer ist, wird sie ausgelagert und eigens implementiert und dann eben nur aufgerufen für das erste Element.

Eine Funktion, die auf gemischten Datentypen arbeitet

Die Funktion bekommt einen Wert des "Obertyps" und trifft dann eine Fallunterscheidung. Bei dieser werden die Prädikate der Untertypen aufgerufen und, falls sich bei der Prüfung true ergibt, die entsprechenden Einzelfunktionen aufgerufen. Diese Einzelfunktionen werden dann für die Untertypen speziell implementiert.

Gemischten Datentyp erzeugen in Scheme

Eventuell vorher die normalen Records machen. Dann den gemischten Datentyp erzeugen mit signature und mixed.

Eine Liste von Records aus zwei Listen erzeugen

Wenn die erste Liste leer ist, entsteht auch eine leere Liste. Ansonsten wird der Listenkonstrukor aufgerufen und auf diese Weise der Aufruf des Konstruktors für die beiden ersten Elemente und der erneute Funktionsaufruf mit den Restlisten verbunden.

Einen Record erzeugen

Das Schema ist:

(define-record-procedures name
   make-name name?
   (name-s1 name-s2 ... name-sn))

Außerdem kommen noch die Signaturen dazu für den Konstruktor, das Prädikat und alle Selektoren. Dabei ist der Konstruktor quasi die Umkehrung für die Selektoren. Der neu definierte Typ wird dabei verwendet.

In Scheme eine Liste von Listen zu einer Liste zusammenfügen

Wenn die Liste leer ist, wird eine leere Liste ausgegeben. Wenn nicht, dann wird eine Zusammenfüge-Funktion aufgerufen für das erste Element der Liste und den erneuten Funktionsaufruf für den Rest der Liste.

Die "Zusammenfügefunktion" bekommt zwei Listen. Wenn die erste leer ist, wird die zweite ausgegeben. Wenn nicht, dann wird das erste Element der ersten Liste angefügt an den erneuten Funktionsaufruf mit dem Rest der ersten Liste und der zweiten Liste.

Baumiteration

Eine baumrekursive Funktion kann auch iterativ berechnet werden. Die Grenze wird in der Hauptfunktion abgefangen. Wenn sie nicht gegeben ist, wird die Hilfsfunktion aufgerufen. Diese benötigt die Startwerte für die verwendeten Vorgänger (also die Funktionsaufrufe innerhalb der Funktion) sowie eine Zählstelle (n und eventuell auch z mit Startwert 1).

Ausgegeben wird dann der Wert einer der Vorgängerstellen, wenn n runtergezählt einen Wert erreicht hat oder auch wenn n gleich z ist, wenn man z verwendet (z wird dann hochgezählt). Bei den Selbstaufrufen der Funktion werden die Vorgängerstellen verschoben beziehungsweise nach der angegebenen Formel neu berechnet.

Annäherung an einen Wert durch Wiederholung

Wenn ein Wert durch Annäherung mit einer Formel ermittelt werden soll, dann wird - iterativ - eine Hilfsfunktion mit dem gewünschten Grenzwert sowie dem Ausgangswert und den benötigten Variablen aufgerufen. In der Hilfsfunktion wird dann mittels if-Abfrage geprüft, ob der Grenzwert erreicht ist (die benötigte Funktion kann gegebenenfalls ausgelagert werden). Wenn ja, wird die auf der Stelle des Ausgangswerts berechnete Zahl ausgegeben. Wenn nein, ruft sich die Hilfsfunktion selbst wieder auf mit einem neuen Wert für die Ausgabestelle. Die Berechnung des neuen Wertes kann, wenn die Funktion komplizierter ist, ebenfalls ausgelagert werden.

Beispiele hierfür sind die Berechnung der Quadrat- und der Kubikwurzel nach dem Newton-Verfahren.

Programmiertechnik

Wenn innerhalb einer einzelnen Funktion eine andere Funktion mehrmals aufgerufen wird, dann wird diese andere Funktion ausgelagert und erstmal für sich implementiert. Dann kann sie tatsächlich mehrmals aufgerufen werden.

Laufzeit und Speicherverbrauch

Bei rekursiven Funktionen sind Laufzeit und Speicherverbrauch O(n).

Bei iterativen Funktionen ist die Laufzeit O(n) und der Speicherverbrauch O(1).

Iterativ

Eine iterative Berechnung für eine Zahlenkette erfolgt über eine Hilfsfunktion, die mit dem Startwert (0 für Addition und 1 für Multiplikation) und der aktuellen Zahl (n) aufgerufen wird. In der Hilfsfunktion wird dann über eine if-Abfrage geprüft, ob n (gleichzeitig ein Zähler) gleich 0 ist. Dann wird das Ergebnis ausgegeben. Ansonsten ruft die Funktion sich selbst auf mit dem erniedrigten Wert von n und der neu und wie gewünscht berechneten Ergebnisstelle.

Baumrekursion

Wenn etwas baumrekursiv berechnet werden soll, wird der Startpunkt (die Startpunkte) über eine if-Abfrage abgefangen. Ansonsten berechnet sich der Wert der Zahl je nachdem, wie vorgegeben, aus mehreren Aufrufen der Funktion selbst.

Das kleinste gemeinsame Vielfache zweiter Zahlen

Um das kleinste gemeinsame Vielfache zweier Zahlen zu ermitteln, gibt es zwei Methoden. Die erste besteht darin, eine Hilfsfunktion aufzurufen mit 2x der ersten und 2x der zweiten Zahl.
Die erste und die dritte Stelle werden dann miteinander verglichen. Wenn sie gleich sind, ist die eine Zahl das LCM. Wenn nicht, wird die kleinere von beiden einmal erhöht und damit die Funktion erneut aufgerufen.

Die andere Methode besteht darin, die größere der beiden Zahlen zu ermitteln und die Hilfsfunktion mit 2x dieser Zahl und der anderen Zahl aufzurufen. Wenn sich diese Zahl ohne Rest durch die andere teilen lässt, ist diese das LCM. Wenn nicht, wird sie einmal erhöht und dann wird wieder die Teilbarkeit geprüft.

Rekursiv

Um rekursiv eine Zahlenkette zusammenzurechnen, wird der Schlusspunkt der Zahlenkette mit if abgefangen und ausgegeben. Ansonsten wird die aktuelle Zahl (n) mit dem gewünschten Operator verknüpft mit einem erneuten Aufruf der Funktion mit der gewünschten nächsten Zahl, die aus n ermittelt wird.

Das Substitutionsmodell in Scheme

  • Der Name einer Funktion wird durch die Definition der Funktion ersetzt
  • Ein lambda-Ausdruck und die angegebenen Werte für die Parameter wird durch den konkreten Rechenausdruck ersetzt
  • Eine boolesche (Un-)Gleichung wird durch #t oder #f ersetzt
  • Eine Verzweigung wird durch den durch #t oder #f ermittelten Zweig ersetzt
  • Rechenvorschriften werden ausgerechnet

Die veränderbare Warteschlange in Scheme

Eine veränderbare Warteschlange besteht aus zwei Verweisen auf den Anfang und das Ende der eigentlichen Warteschlange. Diese beiden Verweise sind ihrerseits veränderbare Listen eines bestimmten Typs. Die Warteschlange wird dann nochmal extra implementiert und besteht aus den beiden Verweisen.

Die veränderbare Liste in Scheme

Eine veränderbare Liste ist entweder eine leere Liste oder eine nicht-leere veränderbare Liste. Diese wiederum besteht aus einem veränderbaren Element eines bestimmten Typs und einer veränderbaren Restliste eines bestimmten Typs.

Umgebungsmodell - Idee

Das Umgebungsmodell besteht aus Umgebungen. Eine Umgebung enthält die jeweils geltenden Variablen und ihre jeweiligen Werte. Eine Umgebung wird immer dann neu erzeugt, wenn neue Werte hinzukommen, die nur für einen bestimmten Bereich gelten sollen (bei Funktionsaufrufen und letrec der Fall). Die Auswertung geschieht dann immer bezüglich der Umgebungen und sie verwendet eben die hier jeweils geltenden Werte der Variablen.

Vorgehensmodell und Prozessmodell

Zu unterscheiden sind Vorgehensmodell und Prozessmodell.

Das Vorgehensmodell ist abstrakt und legt die Reihenfolge der Aktivitäten fest und das, was dabei verwendet wird und welche Rollen beteiligt sind. Das Prozessmodell ist konkreter und bezieht sich auf das jeweilige tatsächliche Projekt. Es nennt auch Personen, Gliederung der Dokumentation und Verantwortlichkeiten.

Prototypen in der Entwicklung von Software

Es gibt verschiedene Arten von Prototypen. Dazu gehören:


  • Evolutionäre Prototypen: Evolution von Ausgangsversion zu nutzbarem System. Zusammen mit Anwender. 
  • Explorative Prototypen (Throw-away): Dienen nur dem Verständnis der Anforderungen. 
  • Experimentelle Prototypen: Für Experimente (an der Uni zB).
  • Horizontaler Prototyp: Nur bestimmte Ebenen des Systems und diese aber vollständig.
  • Vertikaler Prototyp: Bestimmte Teile und diese durch alle Ebenen hindurch.

Alterung von Software

Software kann altern. Dies äußert sich in der Verwendbarkeit.

Softwareunterstützung für Prozess

Es gibt verschiedene Arten von Software, die die Durchführung und Einhaltung eines definierten Entwicklungsprozesses unterstützt. Diese wird auch konkret verwendet und dient zB dem Versionsmanagement und der Kommunikation untereinander.

Java-Wiederholung


  • Eine Java-Klasse hat einen Namen und enthält die passenden Methoden und Attribute.
  • Vererbung bedeutet, dass mindestens 2 Klassen vorhanden sind. Die Oberklasse ist ganz normal. Die Unterklasse erbt durch das Schlüsselwort extends. Erben bedeutet, dass sie alle Attribute und Methoden der Oberklasse bekommt.
  • Eine Schnittstelle ist eine Klasse mit dem Schlüsselwort interface. Sie enthält nur Methodennamen ohne Implementierung. Das Interface muss durch andere Klassen konkretisiert werden. Das geschieht durch das Schlüsselwort implements und die Ausformulierung der Methoden. So kann sichergestellt werden, dass bei Implementierung des Interface alle Methoden vorhanden sind. 
  • Sichtbarkeit bezieht sich auf public und private bei Java-Klassen. Meist sind die Attribute private und die Methoden, die den Zugriff darauf regeln (Getter und Setter) public. 



Das Wasserfallmodell und das iterative Modell als Vorgehensmodelle

Beim Wasserfallmodell unterscheidet man verschiedene Entwicklungsphasen. Diese werden streng eingehalten und jeweils vollständig durchgeführt, bevor die folgende Phase anfängt. Beim iterativen Modell wird das gleiche Schema eingehalten. Der Unterschied ist nur, dass hier immer nur Einzelteile so entwickelt werden - also dass Wasserfallmodell immer wieder für die Einzelstücke durchlaufen wird.

Testfälle vor der Implementierung der Funktionen des Systems

Testfälle werden beim Extreme Programming vor der Implementierung der Funktionen des Systems realisiert. Das hat viele Vorteile.

Pair Programming

Pair Programming bedeutet einfach, dass zwei Leute zusammen programmieren - mit den damit typischerweise verbundenen Vor- und Nachteilen.

Extreme Programming (XP)

Beim Extreme Programming wird Wert auf die Erreichung des Ziels gelegt und nicht auf die Einhaltung von Formalia. Alles soll hochwertig sein und schnell gehen. Teamwork und Kundeneinbindung sind wichtig.

Umgebungsmodell


  • Alles mit define kommt in die globale Umgebung
  • Jeder Aufruf einer Funktion erzeugt eine neue Umgebung; die Werte der Parameter werden hier eingetragen
  • Jedes letrec erzeugt eine neue Umgebung
  • Bei jeder neuen Umgebung wird der Funkionsrumpf dazugeschrieben und anschließend ausgewertet
  • Bei einem Funktionsaufruf wird mit einem geschlängelten Pfeil das Ergebnis angegeben
  • Listen und veränderbare Listen sind Kästen mit cons oder empty. Bei cons werden first und rest eingetragen, wobei rest immer ein Pfeil auf den nächsten Kasten ist.
  • Bei einer Definition durch eine andere Funktion, bei der nur teilweise Parameter angegeben werden und die Angabe der anderen noch offen steht, wird die Funktion ab da definiert, wo es noch keine Eingabe gibt -> zB kommt dann ein lambda-Objekt. Wichtig ist, dass dann die zugeordnete Umgebung eine andere ist.

Der Signaturkonstruktor in Scheme

Der Signaturkonstruktor muss so viele Werte übergeben bekommen, wie Selektoren existieren. Das geht vor allem auch über eine Definition mit einem lambda-Ausdruck und es gilt auch für den gemischten Datentyp (signature - mixed).

Ein Feld mit der Technik der Nachrichtenweitergabe erzeugen

Für ein Feld, das mit der Technik der Nachrichtenweitergabe in Scheme erzeugt wird, müssen die Größe des Feldes und der Inhalt eingegeben werden (der Inhalt ist für jedes Feldelement hier immer der gleiche). Intern wird dann mittels letrec eine Liste erzeugt, die eben entsprechend lang ist und nur aus dem einen Element besteht. Diese Liste kann dann entsprechend verändert werden, wofür man set! benutzt und auch darauf achtet, dass das eingegebene n auch mitverändert wird.

Das Verzeichnis als abstrakter Datentyp

Das Verzeichnis wird implementiert als eine Liste von Paaren. Der Datentyp von Schlüssel und Wert (beim Paar) wird dabei für das Verzeichnis festgelegt. Die beiden Datentypen bestimmen damit sowohl den Typ des Paares als auch den Typ des Verzeichnisses.

Der abstrakte Datentyp

Die Signatur des abstrakten Datentyps enthält alle Funktionen, die dieser zur Verfügung stellt und die entsprechenden Einzelsignaturen. Die allgemeinen Gleichungen sind Beispiele der Anwendung der Funktionen, für die Variablen benutzt werden.

Das Paar als abstrakter Datentyp

Ein Paar sind einfach zwei beliebige Elemente. Man kann dabei aber auch den Typ/die Typen festlegen (pair-of).

Array II

Bei einem Array muss festgelegt werden, was für ein Typ es ist. Dann wird nach der Eingabe einer natürlichen Zahl (natural) ein Wert dieses Typs ausgegeben.

Auswertung in Scheme

Bei der Auswertung von allen Dingen (nach dem Substitutionsmodell) werden die einzelnen Schritte untereinander geschrieben und mit Pfeilen ("=>") verbunden. Die Pfeile stehen der Übersicht halber dabei am besten links und untereinander.

Ein lambda-Ausdruck wird dabei immer durch die zugeordnete Rechenvorschrift ersetzt, wobei dabei dann die konkreten Werte in die Parameter eingesetzt sind.

Huffman-Bäume

Ein Huffman-Baum wird erstellt, indem man die Zeichen entsprechend ihrer Häufigkeit (= Paare von Symbolen und Häufigkeit) aufsteigend in einer Liste sortiert und dann immer die beiden kleinsten von ihnen zusammenfügt und das Konstrukt dann wieder in die Liste zurücklegt. Am Ende bleibt dann nur noch ein Ding. Dieses ist dann der Huffman-Baum.

Er wird beschriftet, indem alle linken Teilbäume eine 0 und alle rechten eine 1 bekommen. Die Codierung erfolgt dann von oben nach unten (= bis das gewünschte Symbol erreicht ist).

In einer Funktion ist zu unterscheiden, ob es sich um ein Blatt handelt oder nicht.

Mengendarstellung in Scheme

Mengen lassen sich als aufsteigend sortierte Listen darstellen. Eine leere Menge ist entsprechend eine leere Liste.

Funktionen lassen sich erstellen, indem man die Folgen entscheidet für die Fälle: Leere Menge(n), erstes Element kleiner als anderes erstes Element (von beiden Seiten) und beide erste Elemente gleich.

Geordneter Binärbaum

Ein geordneter Binärbaum ist entweder eine leere Liste oder ein Knoten, der selbst aus einer Zahl und einem linken und einem rechten Teilbaum besteht. Jeder Teilbaum ist selbst wieder ein geordneter Binärbaum und damit entweder eine leere Liste oder ein Knoten.

Für die Einträge gilt, dass die links vom Knoten alle kleiner sind und rechts davon alle größer ("geordneter" Binärbaum).

Technik der Nachrichtenweitergabe

Bei der Technik der Nachrichtenweitergabe wird durch die Eingabe von irgendwas ein Objekt erzeugt, das Nachrichten in Stringform entgegennimmt und diese mit internen Strings abgleicht und bei Übereinstimmung eine zugeordnete Funktion aufruft.

Strikte und nicht-strikte Auswertung

Es gibt die strikte und die nicht-strikte Auswertung. Bei der strikten Auswertung wird erst ausgerechnet und dann eingesetzt. Bei der nicht-strikten Auswertung werden die Argumente eingesetzt, ohne einen Term vorher ausgerechnet zu haben.

Auswertung

Strukturelle Induktion

De strukturelle Induktion soll die Gültigkeit einer Funktion zeigen, die auf Listen arbeitet. Hierzu wird zunächst gezeigt, dass die Funktion für eine leere Liste gilt. Dann wird die Gültigkeit für eine Liste mit n-1 Elementen vorausgesetzt und damit gezeigt, dass die Funktion auch für alle Listen gilt, die n Elemente besitzen.

Das Zeigen funktioniert ganz normal über das Substitutionsmodell.

Der ADT

Um eine Signatur Sigma für einen abstrakten Datentyp (ADT) zu erstellen, werden die einzelnen Funktionsnamen angegeben und Zahl und Typen der Eingaben und Ausgaben.

Um allgemeine Gleichungen zu erstellen, werden die Funktionen mit Variablen aufgerufen und das Ergebnis als Gleichung hingeschrieben.

Die Signatur soll zeigen, welche Funktionen der ADT bereitstellt. Die allgemeinen Gleichungen zeigen, wie damit umgegangen werden soll.