Veranstaltung: 19522 Proinformatik - Funktionale Programmierung

Inhalt der Veranstaltung

Grundlagen der Berechenbarkeit: • Lambda-Kalkül • primitive Rekursion • µ-Rekursion Einführung in die Funktionale Programmierung (Haskell): • Syntax (Backus-Naur-Form) • primitive Datentypen, Listen, Tupel, Zeichenketten • Ausdrücke, Funktionsdefinitionen, Rekursion und Iteration • Funktionen höherer Ordnung, Polymorphie • Typsystem, Typherleitung und –überprüfung • Algebraische und abstrakte Datentypen • Ein- und Ausgabe • Such- und Sortieralgorithmen Beweisen von Programmeigenschaften: • Termersetzung • strukturelle Induktion • Terminierung Implementierung und Programmiertechnik: • Auswertungsstrategien für funktionale Programme • Modularer Programmentwurf

Scheinkriterien

Regelmäßige Teilnahme an den Vorlesungen und Übungen, 60% der möglichen Punkte aller Übungen (bei n-1 Übungszetteln müssen mindestens 20% erreicht sein) berechtigen zur Klausurteilnahme. Bestehen der Klausur am vorletzten Vorlesungstag (13.08.2009, 9 Uhr, c.t.). Die Note des Scheins entspricht der Klausurnote.

Wo finde ich den Vorlesungshörsaal?

Der mit der Nummer "5" markierte rote Punkt zeigt den Eingang zum Hörsaal.



Weitere Hinweise zum erfolgreichen Anreisen befinden sich hier. Damit sollten alle zum ersten Tag pünktlich und am richtigen Ort erscheinen. Wer diesen Einstellungstest nicht besteht, sollte sich überlegen, ob ein Studium das richtige ist (c: ...

I Theoretischer Teil

Inhalte und Folien zu den Vorlesungen

1.Tag (20.07.2009) [PDF]:

• Informatik-Studium an der Freien Universität Berlin
• Ausgewählte Projekte am Fachbereich
• Einführung in die Funktionale Programmierung
• Installation und erste Gehversuche mit Hugs

2.Tag (21.07.2009) [PDF]:

• Ausblick auf tiefergehende Kapitel
• Lokale Definitionen: where, let
• Funktionskompositionen
• Typvariablen
• Eigene Datentypen definieren: Natürliche Zahlen, Listen
• Listen in Haskell, Typklassen

3.Tag (22.07.2009) [PDF]:

• Imperative versus funktionale Programmierung
• Listen, Tupel
• 8-Dame-Problem

4.Tag (23.07.2009) [PDF]:

• Zeichenketten
• Bindungsstärken
• Operatoren zu Funktionen
• Eigene Operatoren definieren
• Funktionen zu Operatoren
• Funktionen höherer Ordnung
• Mapping, Filtern, Faltung, Entfaltung

5.Tag (24.07.2009) [PDF]:

• Zip, Unzip, Funktionskompositionen
• Sortieren: Insertionsort, BubbleSort, QuickSort, MergeSort
• Vergleich des Berechnungsaufwandes von Algorithmen in vereinfachter Form
• Modularisierung und Schnittstellen, Definition, Sichtbarkeit

6.Tag (27.07.2009) [PDF]:

• Vollständige Induktion
• viele Beispiele
• strukturelle Induktion

7.Tag (28.07.2009) [HS]:

• Eigene Datentypen mit type und data
• Rekursive Datentypen, Bäume
• Funktionen auf eigenen Datentypen
• Automatische Auswertung boolescher Ausdrücke [2]

8.Tag (29.07.2009) [Baum.hs, BaumTest2.hs, HuffmanCodeVL.hs]:

• Binäre Suchbäume [1]
• Abstrakte Datentypen: Stack, Queue; pre-, in-, postorder [PDF]
• Suchbaum als ADT [1]
• Huffman-Codierung [1]

9.Tag (30.07.2009) [PDF]:

• Codierungstheorie
• Doppelkodierung, Paritätsbit
• Graycode, Kreuzsicherungscode
• fehlererkennend, fehlerkorrigierend

10.Tag (31.07.2009) [PDF]:

• Lambda-Kalkül
• Natürliche Zahlen
• Addition, Multiplikation
• Nachfolger, Vorgänger, Boolesche Ausdrücke

11.Tag (03.08.2009) [LambdaExpression.hs, LambdaTest.hs]:

• Vertiefung der Konzepte des Lambda-Kalküls
• Fixpunktkombinator, Rekursion
• Parser für Lambda-Kalkül in Haskell

12.Tag (04.08.2009) [siehe Tag davor]:

• Lambda-Ausdrücke in Haskell auswerten
• streambasierte Eingaben

13.Tag (05.08.2009) [streambased.hs, io.hs, GOL.hs]:

• Weiterführung der streambasierten Eingaben
• IO-Konzept in Haskell
• Conway's Game of Life
• Berechenbarkeit: Turingmaschine, Lambda-Kalkül, µ-Rekursion, !! GOL !! (siehe [PDF])
• Halteproblem

14.Tag (06.08.2009) [monaden.pdf]:

• Monaden in Haskell
• do
• Monadengesetze
• IO, Writer

15.Tag (07.08.2009) []:

• Klausurvorbereitung
• Übersicht zu allen bisherigen Themen
• Fragen und Antworten

16.Tag (10.08.2009) [MinMax.pdf]:

• Spielbäume in Haskell
• MinMax, Alpha-Beta

17.Tag (11.08.2009) [PDF (Teil über k-nn)]:

• Mustererkennung, k-nn in Haskell
• µ-Rekursion

18.Tag (12.08.2009) []:

• nur klausurrelevante Dinge....

19.Tag (13.08.2009) [KLAUSUR.PDF]:

• KLAUSUR!!!
• tja, was haben wir alles so gemacht ....

20.Tag (14.08.2009) []:

• Nachbesprechung der Klausur
• Vergabe der Noten
• GRILLEN

II Praktischer Teil

Sammlungen möglicher Klausuraufgaben

Sammlung 1 [PDF]
Sammlung 2 [PDF]

Übungsaufgaben

Uebung 1 [PDF]
Uebung 2 [PDF]
Uebung 3 [PDF]
Uebung 4 [PDF]
Uebung 5 [PDF]
Uebung 6 [PDF]
Uebung 7 [PDF]
Uebung 8 [PDF]
Uebung 9 [PDF, Rauschen.hs]
Uebung 10 [PDF]
Uebung 11 [PDF]
Uebung 12 [PDF]
Uebung 13 [PDF]
Uebung 14 [PDF]
Uebung 15 [PDF]
Uebung 16 [PDF, train.hs, test.hs]

Musterlösungen zu den Aufgaben

Uebung 1, 3, 5 [LHS]
Uebung 2 [HS]
Uebung 4 [HS]
Uebung 4 (ausführlich Aufgabe 2) [PDF, LHS]
Uebung 5 [PDF, LHS]
Uebung 7 [HS]
Uebung 8, Aufgabe 2 [HS]
Uebung 14 [PDF, LHS]

Forum bei Spline

Link zum Forum

Literatur und Links zur Vertiefung

Linkliste

• Haskell Community
• Haskell-Interpreter Hugs
• Editor Notpad++

Literaturliste

• [1] Thompson S.: "Haskell: The Craft of Functional Programming, 2.Auflage, Addison-Wesley Longman, 1999
  
• [2] Hutton G.: "Programming in Haskell", Cambridge University Press 2007
  
• [3] Lippe W.-M.: "Funktionale und Applikative Programmierung", Springer-Verlag 2009