Praktische Informatik 3 (WS2001/2002)
Willkommen auf der Heimatseite der Lehrveranstaltung "Praktische
Informatik " im Wintersemester 2001/2002.
Hier findet ihr Inhaltliches, Organisatorisches, Details zu Scheinen und
Fachgesprächen, Kopien der Vorlesungsfolien und Aufgabenzettel, ein Literaturverzeichnis, etwas über Haskell-Software, Links über
Haskell, und Haskell in Space.
Inhaltliches
Das Thema dieser Veranstaltung ist die funktionale
Programmierung.
Funktionale Sprachen erlauben eine wesentlich abstraktere
Programmierung als ihre imperativen Gegenstücke. Das Programm
spezifiziert eher, was zu tun ist, nicht wie (mit
welcher Reihenfolge von Zustandsveränderungen (also Zuweisungen)) es
zu tun ist. Dieser Abstraktionsgewinn erlaubt es, in Konzepten und
Algorithmen zu denken, nicht in Klassenstrukturen und geschweiften
Klammern.
Aus diesem Grunde sollte jeder Informatiker zumindest eine funktionale
Sprache einmal kennengelernt haben - wie zum Beispiel die in dieser
Veranstaltung verwendete Sprache Haskell.
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.
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, sonder auch eminent nützlich sind, werden wir
nach Weihnachten diese Konzepte dann anwenden, und zwar im Bereich der
Animation und Grafik --- die sogenannte funktionale reaktive
Programmierung.
Organisatorisches
Die VAK der Veranstaltung ist 03-533.
Termine
Die Vorlesung ist Montags 10-12 im kleinen Hörsaal
("Keksdose").
Neben der Vorlesung werden vier Tutorien angeboten:
Di | 08-10 |
MZH 6240 |
Christoph Grimmer (crimson) |
Do | 13-15 |
MZH 7210 |
Peter König (pkoenig) |
Do | 13-15 |
MZH 7200 |
Rafael Trautmann (pirate) |
Do | 13-15 |
Sportturm C5130 |
Thomas Meyer (mclee) |
Entgegen den Angaben im Vorlesungsverzeichnis wurden die zwei Tutorium am
Dienstag morgen zusammengelegt, und wegen des großen Andrangs ein
Zusatztutorium am Donnerstag nachmittag eingerichtet.
Übungsbetrieb
Es werden wöchentlich (ab Weihnachten zweiwöchentlich)
Vorlesungsblätter ausgegeben - sie sind Montags ab 16:00 auf
dieser Webseite verfügbar.
Die Übungsblätter werden in den Tutorien besprochen. Ab dieser
Besprechung ist eine Woche (ab Weihnachten zwei Wochen) Zeit zur
Bearbeitung der Übungsblätter; danach werden die Übungsblätter in den
Tutorien beim Tutor abgegeben.
Scheinkriterien
In der ersten Vorlesung wurden folgende Scheinkriterien ausgehandelt
und mit 146:0:1 Stimmen angenommen:
- Von den n ausgegebenen Übungsblättern müssen n-1
bestanden werden, wobei ein Übungsblatt als bestanden gilt, wenn
mindestens 40% der Punkte erreicht werden.
- Insgesamt müssen bei den n-1 besten Übungsblättern im
Schnitt 60% der Gesamtpunktzahl erreicht werden. (Der Schnitt bezieht
sich auf n-1 Blätter, nicht auf alle.)
- Gegebenfalls findet in folgende Fällen am Ende des Semesters ein
Prüfungsgespräch statt:
- Auf Wunsch des Studenten, oder
- nach Maßgabe des Tutors (dieser stellt die Individualität der
Leistung fest).
Scheinrelevanz
Der in der DPO'93 aufgeführte prüfungsrelevante PI3-Schein kann (in
diesem Semester) nicht nur (wie bisher) über das SWP sondern
alternativ auch über PI3 abgedeckt werden. Die in der DPO zusätzlich
aufgeführte Forderung der erfolgreichen Teilnahme am SWP bleibt davon
unberührt.
Kurz gesagt kann also gewählt werden zwischen
- entweder prüfungsrelevante Studienleistung in PI3 sowie
erfolgreiche Teilnahme an SWP
- oder prüfungsrelevante Studienleistung in SWP.
Mehr dazu hier.
Man beachte ferner, dass die Veranstaltung PI3 in ihrer jetzigen Form
den Inhalt abdeckt, der früher in PI1 gelehrt wurde. Daher können
Studenten, die schon in PI1 funktionale Programmierung (entweder in
Haskell oder in Scheme) gemacht haben, den PI3-Schein nicht in das
Vordiplom einbringen.
Studienbegleitende Leistungsnachwiese
Wer einen studienbegleitenden Leistungsnachweis (vulgo: der Schein) in das
Vordiplom einbringen möchte, der besorge sich bitte einen
Scheinvordruck (vor der Fachbereichsverwaltung, MZH 7. Ebene), und
fülle diese wie folgt aus:
- Im oberen Teil:
- oben links: Fachbereich 3
- Euren Name, Matrikelnummer
- Titel der Lehrveranstaltung: Praktische Informatik 3
- Veranstaltungskennziffer: 03-533
- WS 01/02
- Wochenstunden:2+2
- Die folgenden sind in dem unteren Teil ("nicht vom Studenten
auszufüllen"):
- Gruppenleistung ankreuzen
- Inhalt und Form der Leistung:
Erfolgreiche Bearbeitung von Übungsblättern
- Prüfungsgebiet: Praktische Informatik
Danach gebt den Schein bitte entweder beim Veranstalter (MZH 8110) oder Sylvie
Rauer (MZH 8190) ab, oder bringt ihn zum Fachgespräch mit.
Fachgespräche
Ob ihr für ein Fachgespräch vorgesehen seit, erfahrt ihr von eurem
freundlichen Tutor. Eine Liste mit Terminen für Fachgespräche findet
ihr an der Tür des Veranstaltungsbüros (MZH 8110).
Ansonsten gilt für Fachgespräche:
- Es soll der Überprüfung der Individualität der Leistung dienen und
keine mündliche Prüfung sein.
- Der Zeitraum ist ca. fünf bis zehn Minuten pro Teilnehmer.
- Der Inhalt ist der Inhalt der Übungsblätter, und dazu relevanter
Übungsstoff.
- Die erste Frage ist immer: "Was ist ein funktionales Programm"?
Vorlesungsfolien und Übungsblätter
Hier finden sich die Vorlesungsfolien und Übungsblätter, sowie der
Haskell-Quellcode aus den Vorlesungen.
Vorlesungsfolien:
Es gibt entweder alle Folien im
Überblick (im PDF-Format zum bequemen Betrachten), oder Handouts
pro Vorlesung (in schwarz-weiß-grauem Postscript zum besseren
Drucken):
- [1] vom 22.10.01.
- [2] vom 29.10.01.
Dazu die Quellen:
Factorials.hs,
Nim.hs,
Palindrome.hs.
- [3] vom 05.11.01.
Dazu die Quellen:
Library.hs,
Queens.hs,
Sorting.hs.
- [4] vom 12.11.01.
Dazu die Quellen:
Sorting.hs.
(Achtung, die ursprüngliche Version von qsortBy hatte einen
Fehler. Dieses ist die korrigierte Version.)
- [5] vom 19.11.01.
Dazu die Quellen: Primes.hs,
Index.hs.
- [6] vom 26.11.01.
Dazu die Quellen: Trees.hs
(binäre, geordnete, ausgeglichene Bäume),
Lecture6.hs
(sonstiges).
- [7] vom 03.12.01.
Dazu die Quellen:
Store1.hs,
Store2.hs,
Queue.hs,
Set.hs,
RelGrph.hs.
- [8] vom 10.12.01.
Dazu die Quellen:
Slides8.hs,
Parsing.hs,
ExprParse.hs.
- [9] vom 17.12.01.
Dazu die Quellen:
Nim.hs,
Slides9.hs (wc,
Kontrollstrukturen, IO im Eigenbau).
- [10] vom 07.01.02.
Dazu die Quellen:
HelloWorld.hs,
Balls.hs,
Geometry.hs,
GeoEx.hs.
Ferner die Quellen und das
Handbuch für die
Hugs Graphics Library.
Diese Version von HGL benötigt Hugs vom Dezember 2001
(lokale Kopie hier).
- [11] vom 14.01.02.
Dazu die Quellen:
Geometry.hs (neue Version),
SimpleAnim.hs,
Space.hs.
- [12] vom 21.01.02.
Dazu die Quellen:
Animation.hs.
- [13] vom 28.01.02.
Dazu die Quellen:
Slides13.hs
(die verschiedenen Farben, der schwingende Ball und der springende Ball),
Pong.hs.
Beide benötigen
Geometry.hs (siehe oben) und
Fal.hs, die
Implementation der reaktiven funktionalen Animation, welche wiederum
Memo.hs benötigt.
- [14] vom 04.02.02.
Kleiner Tip: mit gunzip -c lecture-X.ps.gz | psnup -r -2 |
lp
(oder sogar -4
) lassen sich die
Druckversionen papiersparend ausdrucken.
Übungsblätter
- [0], ausgegeben am 22.10.01.
- [1], ausgegeben am 29.10.01.
- [2], ausgegeben am 05.11.01.
- [3], ausgegeben am 12.11.01.
Alternative Version mit besserer Definition: [3a], ausgegeben am 16.11.01.
- [4], ausgegeben am 19.11.01.
- [5], ausgegeben am 26.11.01.
- [6], ausgegeben am 03.12.01.
- [7], ausgegeben am 17.12.01.
- [8], ausgegeben am 14.01.02.
Einige Lösungen für das letzte Übungsblatt finden sich auf dieser
Webseite: Haskell in Space.
Bücher und weiterführende Literatur
Die Veranstaltung basiert auf folgendem Buch:
Simon Thompson:
Haskell: The Craft of Functional Programming
Zweite Auflage
Addison-Wesley Publishing Company, 1999
ISBN 0-201-34275-9
Wer's gern bunt und multimedial mag, dem sei folgendes Buch ans Herz
gelegt:
Paul Hudak:
The Haskell School of Expression
Cambridge University Press, 2000
ISBN 0-521-64408-9
Dieses Buch ist etwas formaler als die beiden 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
Software: Haskell in Aktion
Der Übungsbetrieb basiert auf dem Haskell-Interpreter Hugs. Hugs ist lokal im
FB3-Netz installiert, und wird mit
/usr/local/lang/hugs
aufgerufen. Auf der Hugs
Homepage gibt es Implementationen für viele verschiedene
Betriebssysteme (Unix/Linux, Windows, Mac &c). Hier
ist eine lokale Kopie der
Unix-Version.
Es gibt auch mehrere Haskell-Compiler, der Glasgow Haskell Compiler hat sogar eine Hugs vergleichbare, interaktive Kommandozeilenschnittstelle. Für den anfänglichen Übungsbetrieb sind diese zwar etwas zu schwergewichtig, aber später werden wir sie vielleicht benutzen.
Links zu Haskell und Hugs
Christoph Lüth
Last modified: Fri Apr 5 18:17:55 CEST 2002