21.10., 24.10. Folien 1-52

28.10.: Wdh: Arten von Algorithmen (deterministisch etc).  Freie
Variablen, Gebundene Variablen, Boole'sche Werte, if-then-else, auch
geschachtelt. Danach Folien bis einschl. 62. Ein Beispiel das nicht
auf der Folie war: Anzahl der Moeglichkeiten, ein Rechteck des Formats
h=n, b=2 mit 1*2 Dominos zu pflastern. Antwort: fib(n).

30.10.: Folien bis einschl. 82. Hingewiesen auf
Exmatrikulationsklausel bei wiederholtem Nichtbestehen der
Klausur. Bitte Hinweisblatt von Prof Ohlbach konsultieren oder gleich
gescheit lernen und bestehen.

4.11.: Wdh Abstiegsfunktion, Induktion, siehe auch Kurznotiz auf der
WWW Seite. Folien bis einschl 90.

6.11.: Wdh Folie 89 (Induktionsbeweis). Folien bis einschl.: 100
(Programmierung in OCAML: int, float, Rekursion).

11.11.: Folien bis einschl 110. (Programmierung in OCAML: Rekursion,
Polymorphie, Funktionsparameter, char und string, Lexikographische
Ordnung.).

13.11.: Folien bis einschl 113. OCAML Programmierung der "Tuerme von
Hanoi", siehe die Datei han.ml auf der WWW-Seite.

18.11.: Folien bis einschl 122. Formale Sprachen, Syntax, Semantik,
Pragmatik. BNF Grammatiken an Beispielen, noch keine formale
Definition. 

20.11.: Folien bis einschl 134. Naechstesmal werden Syntaxdiagramme
noch behandelt.

25.11.: Behandlung der Syntaxdiagramme, Anschrieb eines
Herleitungsbaumes fuer let rec fakt = function ... Folien bis
einschliesslich 140.

27.11.: Folien bis einschl 149. Umgebungen, Werte,
Auswertungsfunktion. Strikte Auswertung, verzoegerte Auswertung, lazy
evaluation. Es wurden an der Tafel zahlreiche Beispiele gerechnet.

2.12.: Folien bis einschl 168. Hier eine Ausarbeitung der
"McCarthy-Funktion". Es ist f(x)=if x>100 then x-10 else f(f(x+11)).
Wir sollen zeigen f(x) = if x>100 then x-10 else 91. Wir duerfen
voraussetzen, dass dies fuer alle rekursiven Aufrufe bereits gilt. Wir
machen dann folgende Fallunterscheidung:

Fall 1: x>100. f(x)=x-10 nach Definition von f.
Fall 2: x=100. f(x)=91 nach Definition von f.
Fall 3: 90<=x<100. f(x)=f(f(x+11))=f(x+11-10)=f(x+1) nach Definition von f. 
          Nach Voraussetzung ist aber f(x+1)=91, da ja x+1<=100. 
Fall 4: x<90. f(x)=f(f(x+11))=f(91)=91. 
                             ^---------- dies gilt nach Voraussetzung, da ja
                                         x+11 <= 100.      

Damit folgt nach dem Satz von der partiellen Korrektkeit, dass f(x)=if x>100 then x-10 else 91. 


4.12.: Mehrere Beispiele zur Operationellen Semantik vorgerechnet. Weitere gibt es in den Uebungen. Folien bis 183. 

9.12.: Wdh.: Operationelle Semantik. Typinferenz, Let-Polymorphismus, Ausnahmen. Folien bis 198. Das Beispiel auf Folie 196 wurde nicht gemacht. Denken Sie selbst darueber nach. Eine korrigierte Version der Folien befindet sich im Netz. 

11.12.: Mustervergleich, Verbunde. Folien bis 211. 

16.12.: Varianten, Einfuehrung zu Listen, Folien bis 218.

18.12.: Listen. Folien bis 222. 

23.12.: Weihnachtsvorlesung zum Thema Grafik. Wir haben mit der Grafikbibiothek graphics.cma aus der OCAML Distribution (siehe Doku) experimentiert. Die in der VL geschriebene Datei findet sich auf der Homepage. 

8.1.: Listen, Stapel, Schlangen. Folien bis 227.

13.1.: Reihungen, Binaerbaeume, Darstellung von Termen als Baeume. 
       Folien bis 244. Die Funktion parse wurde noch nicht
       programmiert. Naechstes Mal. 

15.1.: Implementierung der Funktion "parse". Beruecksichtigt
       allerdings weder Punkt-Vor-Strich, noch die Regel, dass Ausdruecke
       gleicher Bindekraft von links zu klammern sind. Eine Implementierung,
       die beides beruecksichtigt, werde ich demnaechst bereitstellen.

       Binaere Suchbaeume. Modularisierung. Folien bis 259. 




20.1.: Folien bis 262. Schnittstellen fuer Stapel und Schlange wurden
in der Vorlesung geschrieben; zwei Implementierungen von Stapeln
wurden geschrieben; einmal als Listen, einmal als Paare (s,l) wobei s
eine Liste ist und l ein Integer, der die Laenge von s
bezeichnet. Dadurch effizientere Implementierung der Funktion length
auf Stapeln. Schliesslich wurde die Breitenordnung fuer Baeume mit
Schlangenimplementiert. Alle Implementierungen befinden sich auf der
WWW-Seite.

22.1.: Datenabstraktion, Separate Kompilierung, Uebungsprojekt, Makefiles, Ausfuehrbare Programme, Binden. Folien bis 282. 

27.1.: VL von M Lange gehalten. Sortieren durch Einfuegen und durch Mischen. Empirischer Effizienzvergleich, O-Notation. 

29.1.: Wdh O-Notation, Repetitive Rekursion

3.2.: Wdh Repetitive Rekursion, Binaerbaeume: Suchen-Einfuegen-Loeschen, Operationelle Semantik von Listen mit Halde (angefangen) 

5.2.: Operationelle Semantik mit Halde, ausgedehnte Beispiele an der Tafel. Partielle Ordnungen, w-CPOs, Stetige Funktionen.

10.2.:

12.2.: