Praktische Informatik 3
Willkommen auf der Heimatseite der Lehrveranstaltung „Praktische Informatik 3“ im Wintersemester 2006/2007.
Inhaltliches
Das Thema dieser Veranstaltung ist die funktionale Programmierung.
Bei der funktionalen Programmierung werden Programme als Funktionen modelliert, die eine Eingabe auf eine Ausgabe abbilden. Dieser unschuldige Satz hat weitreichende Konsequenzen. Zum ersten bedeutet es nämlich, daß unsere Programme zustands- und variablenfrei sind; eine Funktion f muß nämlich für eine Eingabe a immer dasselbe Ergebnis liefern, und kann nicht in Abhängigkeit von einem globalen oder internen Zustand ein anderes Ergebnis zurückgeben.
Diese Eigenschaft (auch referentielle Transparenz genannt), zusammen mit den anderen Eigenschaften funktionaler Programmiersprachen, wie (strenge) Typisierung, Funktionen höherer Ordnung und algebraischen Datentypen, machen funktionale Programme elegant, kurz, mathematischen Betrachtungen (Korrektheitsbeweisen) zugänglich und vor allem ganz anders als imperative oder objektorientierte Programme, wie wir sie in PI1/PI2 kennengelernt haben. Dieser Abstraktionsgewinn erlaubt es, in Konzepten und Algorithmen zu denken, nicht in Klassenstrukturen und geschweiften Klammern.
Aus diesem Grunde sollte jeder Informatiker eine funktionale Sprache einmal kennengelernt haben — wie zum Beispiel die in dieser Veranstaltung verwendete Sprache Haskell.
Gliederung
Bis Weihnachten werden wir uns mit den Grundkonzepte der funktionalen Programmierung beschäftigen, wie Funktionsdefinition, Typisierung, Basisdatentypen, Funktionen höherer Ordnung, Polymorphie, algebraischen Datentypen und abstrakten Datentypen (ADTs).
Um zu demonstrieren, dass funktionale Programmiersprachen nicht nur elegant und abstrakt, sondern auch eminent nützlich sind, werden wir nach Weihnachten diese Konzepte dann anwenden.
Organisatorisches
Die VAK der Veranstaltung ist 03-05-G-700.03.
Termine
Die Vorlesung ist Dienstags 8-10 im Hörsaal NW1 H2 (W0020).
Wegen der Erstsemesterorientierung findet die erste Vorlesung am Dienstag, den 31.10. und ab diesem Termin dann auch die Tutorien statt.
Neben der Vorlesung werden sechs Tutorien angeboten:
Di  | 17-19 | MZH 1380 | Diedrich Wolter (<dwolter>) |
Mi | 8-10 | MZH 7250 | Friederike Jolk (<rikej>) |
MZH 7260 | Cui Jian (<ken>) | ||
Mi | 13-15 | MZH 7210 | Klaus Hartke (<hartke>) |
MZH 8090 | Christian Maeder (<maeder>) | ||
Mi | 17-19 | MZH 4194 | Matthias Berger (<tokio>) |
Außerdem gibt es neben den Tutorien noch eine „FAQ“ (Fragestunde), die sich insbesondere an Studenten wendet, die sprachliche Probleme haben. Hier könnt ihr alles fragen, was im Tutorium oder der Vorlesung zu kurz kam.
Die Fragestunde wird Di von 10-12 und nach Vereinbarung (Email) von Berthold Hoffmann (<hof>) in seinem Büro (Cartesium 2.048) abgehalten.
Scheinkriterien
In der ersten Vorlesung wurden folgende Scheinkriterien ausgehandelt und einstimming angenommen:- Von den ausgegebenen Übungsblättern müssen alle bearbeitet werden. Ein Übungsblatt gilt als bearbeitet, wenn insgesamt 40% der Gesamtpunktzahl erreicht werden.
- Insgesamt müssen mindestens 50% der Punkte erreicht werden (siehe Notenspiegel unten).
- Es gibt ein Bonusübungsblatt, um Ausfälle zu kompensieren
- Die Individualität der Leistung wird in der Regel sichergestellt durch ein Fachgespräch am Ende des Semesters.
- Kann der Tutor die individuelle Leistung feststellen, z.B. durch regelmäßige mündliche Beteiligung oder Vorstellung der Lösung zu einer Aufgabe im Tutorium, kann das Fachgespräch entfallen.
Fachgespräche
Die Fachgespräche finden am 20.02 und 21.02. in der Zeit von 9:00 bis 17:00 statt. Eine Anmeldung ist jetzt nicht mehr möglich.
Notenspiegel
Die Note für den PI3-Schein ergibt sich aus den in den Übungen erzielten Punkten nach folgendem Schlüssel:
Prozente | Note | Prozente | Note | Prozente | Note | Prozente | Note |
---|---|---|---|---|---|---|---|
85-89.5 | 1.7 | 70-74.5 | 2.7 | 55-59.5 | 3.7 | ||
95-100 | 1.0 | 80-84.5 | 2.0 | 65-69.5 | 3.0 | 50-54.5 | 4.0 |
90-94.5 | 1.3 | 75-79.5 | 2.3 | 60-64.5 | 3.3 | 0-49.5 | n/b |
Spielregeln
Gruppenübergreifende Zusammenarbeit und Recherche in Internet und der wissenschaftlichen Literatur zur Lösung der Aufgaben ist zulässig (und erwünscht), aber es die Angabe der Quellen ist zwingend erforderlich und gute wissenschaftliche Praxis.
Eine Übernahme der Lösung von einer anderen Gruppe oder aus einer anderen Quelle ohne Quellenangabe gilt als Täuschungsversuch.Beim ersten Täuschungsversuch gibt es null Punkte für den gesamten Übungszettel, und ein Fachgespräch; spätestens beim zweiten Täuschungsversuch gibt es keinen Schein mehr.
Wer seinen Übungszettel ohne vorherige Entschuldigung nach der Abgabefrist einreicht, erhält null Punkte. Also bei Verspätungen im eigenen Interesse möglichst frühzeitig den Tutor (z.B. per Mail) benachrichtigen.
Feedback
Eure Meinung ist gefragt! Um diese Veranstaltung ständig weiter zu verbessern, führen wir eine Evalutation auf freiwilliger Basis durch. Bitte füllt den Fragebogen aus, und lasst ihn uns durch den Tutor, im Postfach, persönlich oder per mail zukommen. Danke!
Vorlesungsfolien
Die Vorlesungsfolien sind jeweils verfügbar als ganzseitiges, buntes PDF zum Betrachten, und 8:1 schwarz-weißes PostScript zum Drucken:
- Vorlesung vom 31.10.06: [PDF] [PS]
- Vorlesung vom 07.11.06: [PDF] [PS]
- Vorlesung vom 14.11.06: [PDF] [PS]
- Vorlesung vom 21.11.06: [PDF] [PS]
- Vorlesung vom 28.11.06: [PDF] [PS]
- Vorlesung vom 05.12.06: [PDF] [PS]
- Vorlesung vom 12.12.06:
[PDF]
[PS]
Quellcode dazu: Set.hs - Vorlesung vom 19.12.06:
[PDF]
[PS]
Quellcode dazu: Parser (Parser.hs), Parsierung von Ausdrücken (Expr1.hs), und die Korrektur (Expr2.hs). - Vorlesung vom 09.01.07:
[PDF]
[PS]
- Vorlesung vom 16.01.07:
[PDF]
[PS]
Quellcode dazu: die einfachen Beispiele (Hello.hs und Ball.hs), der springende Ball (Simpleanim.hs), und der Raumschiffsimulator (Space.hs mit der dazu benötigen Bücherei Geometry.hs); für alle ein Makefile. - Vorlesung vom 23.01.07:
[PDF]
[PS]
Korrektheitsbeweis von mergesort [PDF] [PS]. - Vorlesung vom 30.01.07: [PDF] [PS]
- Vorlesung vom 06.02.07: [PDF] [PS]
Video-Aufzeichnungen der Vorlesung sind als mobile lecture im Rahmen des Projektes m-lecture verfügbar (Direktlink).
Übungsblätter
- 1. Übungsblatt (Ver 1.0), ausgegeben am 31.10.06, abzugeben am 14.11.06: [PDF] [PS]
- 2. Übungsblatt (Ver 1.1, ChangeLog), ausgegeben am 14.11.06, abzugeben am 28.11.06: [PDF] [PS]
- 3. Übungsblatt (Ver 1.0), ausgegeben am 28.11.06, abzugeben am 12.12.06: [PDF] [PS]
- 4. Übungsblatt (Ver 1.1, ChangeLog), ausgegeben am 12.12.06, abzugeben am 09.01.07: [PDF] [PS]
- 5. Übungsblatt (Ver 1.0), ausgegeben am 09.01.07, abzugeben am 23.01.07: [PDF] [PS]
- 6. Übungsblatt (Ver 1.0), ausgegeben am 23.01.07, abzugeben am 06.02.07: [PDF] [PS]
- Bonusübungsblatt (Ver 1.0), ausgegeben am 16.01.07, abzugeben am 06.02.07:
[PDF]
[PS]
Dazu die Quellen: [TGZ] [ZIP]
Die Abgabe sollte mit LaTeX gesetzt werden. Dazu benutzt bitte die Klasse pi3.cls; hier sind Beispiele dazu.
Bücher und weiterführende Literatur
Die Veranstaltung basiert lose auf folgendem Buch:
Simon Thompson:
Haskell: The Craft of Functional Programming
Zweite Auflage
Addison-Wesley Publishing Company, 1999
ISBN 0-201-34275-8
Dieses Buch wendet sich eher Programmieranfänger, und bietet neben Haskell auch eine Einführung in Unix-artige Betriebssysteme:
Manuel Chakravarty und Gabriele Keller:
Einführung in die Programmierung mit Haskell.
Pearson Studium, 2004.
ISBN 3-8273-7137-6
Einen bunteren und zugleich abstrakteren Einstieg in Haskell bietet folgendes Buch:
Paul Hudak:
The Haskell School of Expression
Cambridge University Press, 2000
ISBN 0-521-64408-9
Das folgende Buch ist formaler als die vorherigen, und betont eher den Aspekt der formalen, korrekten Programmentwicklung:
Richard Bird:
Introduction to Functional Programming using Haskell.
Prentice Hall Series in International Computer Science.
Prentice Hall, 1998.
ISBN 0-13-484346-0
Dieses Buch bietet einen etwas langsameren Einstieg in das Thema, und behandelt neben der Sprache Haskell auch die Sprachen ML und Opal:
Peter
Pepper:
Funktionale
Programmierung in OPAL, ML, HASKELL und GOFER
Springer
Verlag
Zweite Auflage, 2003.
ISBN 3-540-43621-9
Software: Haskell in Aktion
Der Übungsbetrieb basiert auf dem Haskell-Interpreter Hugs oder dem Glasgow Haskell Compiler ghc.
Hugs ist lokal im FB3-Netz als /usr/local/bin/hugs
installiert. Auf der Hugs
Homepage gibt es Implementationen für viele verschiedene
Betriebssysteme (Unix/Linux, Windows, Mac &c).
Der Glasgow Haskell Compiler hat eine Hugs vergleichbare, interaktive Kommandozeilenschnittstelle, kann aber auch separat ausführbare Programme erzeugen. Der GHC übersetzt langsamer als Hugs und ist für den anfänglichen Übungsbetrieb vielleicht etwas zu schwergewichtig, hat aber wesentlich bessere Fehlermeldungen.
Links zu Haskell und Hugs
- Die Haskell Homepage. Anlaufpunkt für alle Haskell-Resourcen weltweit.
- Die Homepage der Haskell Graphics Library.
- Ein Index der vordefinierten Funktionen (aus dem Anhang der Sprachdefinition).
- Lokale Kopie von Miloslav Nic's Haskell Reference (hier das Original).
- Die Sprachdefinition: Haskell98 Report (lokale Kopie) (vielleicht etwas schwerverdaulich; auch als PS oder PDF).