Praktische Informatik 2 im Sommersemester 2001

Das PI2-Team

Die Veranstaltung Praktische Informatik 2 wird von folgenden Personen durchgeführt:

Vorlesung: Prof. Dr. Jan Peleska, http://www.informatik.uni-bremen.de/~jp, EMail: jp@informatik.uni-bremen.de

Tutorien:

Stefan Bisanz, EMail: alien@informatik.uni-bremen.de
Markus Dahlweid, EMail: dahlweid@informatik.uni-bremen.de
Hans-Jürgen Ficker, EMail: hjficker@informatik.uni-bremen.de
Reiner Leins , EMail: leins@informatik.uni-bremen.de
Christoph Lüth, EMail: cxl@informatik.uni-bremen.de
Oliver Meyer, EMail: emm@informatik.uni-bremen.de
Reinhard Moratz, EMail: moratz@informatik.uni-bremen.de
Jan Peleska, EMail: jp@informatik.uni-bremen.de
Markus Roggenbach, EMail: roba@informatik.uni-bremen.de

FAQ (Frequently Asked Questions)-Veranstaltung: Jan Peleska, EMail: jp@informatik.uni-bremen.de

Veranstaltungszeiten

Vorlesung:              Di. 13-15 Uhr, HS Großer Hörsaal

Übungen:                Mi.  8-10 Uhr, 
                        Mi. 10-12 Uhr,
                        Do.  8-10 Uhr,
                        Fr. 13-15 Uhr

Beginn:                 Vorlesung:  Di, 10.04.00
                        Übung:      Mi, 11.04.00

NEU:                    FAQ (Frequently Asked Questions)-Veranstaltung
                        Mo. 15-17 MZH 7220
                        erste FAQ-Veranstaltung am Montag, 28.05.2001

Struktur der Veranstaltung

Die Veranstaltung wird dieses Semester in drei Bereiche gegliedert:

In der Vorlesung werden die Themenbereiche der Praktischen Informatik im Überblick vorgestellt. Wir versuchen, Fragestellungen und ihre Lösungen zu motivieren, Schwerpunkte zu setzen, Zusammenhänge deutlich zu machen, wichtige Probleme zu verdeutlichen und ganz allgemein den Zuhörern Appetit auf weitere Vertiefung des Lehrstoffs zu machen.
In den Tutorien wird der Stoff aus der Vorlesung noch einmal diskutiert, insbesondere indem auf die Inhalte der begleitenden Übungszettel eingegangen wird. Weiterhin werden allgemeine Problem und gute Vorgehensweisen bei der Lösungen der Übungsaufgaben (auch von Euch) vorgestellt. Natürlich sollte hier auch immer noch genug Zeit bleiben, um auf allgemeine Verständnisfragen aus der Vorlesung einzugehen.
In der FAQ (Frequently Asked Questions)-Veranstaltung können Studierende ihre speziellen Fragen zur Vorlesung, zu den Übungsaufgaben und zum Programmieren mit Java allgemein diskutieren. Hier kann alles besprochen und erläutert werden, was in Vorlesung und Tutorien nach Eurer Meinung nicht ausreichend behandelt wurde. Die Veranstaltung ist nicht für das Plenum gedacht, sondern für einzelne Personen oder Grupen, die ein spezielles Problem eingehender erläutert bekommen möchten.

Es gibt in diesem Semester kein explizites Programmierpraktikum! Ausserhalb der Besprechungen in den Tutorien seid Ihr bei der Lösung der Aufgaben im wesentlichen auf Euch alleine gestellt und auch die zeitliche Einteilung bleibt Euch überlassen (solange Ihr Euch an die Abgabefristen auf den Aufgabezetteln haltet ...).

Literatur

Zum Erlernen der Programmiersprache Java verfahren wir folgendermaßen:
- Die intuitive, motivierende ;-) Einführung in Java erfolgt auf Grundlage des Tutoriums The Java Tutorial - A practical guide for programmers welches im WWW unter http://java.sun.com/docs/books/tutorial zu finden ist.
- Das systematische, wissenschaftlich ausgerichtete Erlernen von Java Syntax und Semantik erfolgt auf Grundlage der "offiziellen" Dokumentation The Java Language Specification von James Gosling, Bill Joy, Guy Steele und Gilad Bracha. Auch dieses Dokument ist im WWW erhältlich: http://java.sun.com/docs/books/jls/index.html
- Einen Überblick über Java Tutorien, Artikel und Bücher findet man auf http://developer.java.sun.com/developer/infodocs/
Für die Themen Programmierprinzipien, Objektorientiertes Programmieren, Algorithmen und Datenstrukturen wird in der praktischen Informatik 1 und 2 folgendes Lehrbuch verwendet: Helmut Balzert: Grundlagen der Informatik. Spektrum Akademischer Verlag 1999.
Unter http://java.sun.com/j2se/1.3/docs/api/index.html befindet sich eine Übersicht über die Java API, die sich gut eignet, um die Parameter und Funktionsweise einzelner Methoden nachzuschlagen.
Die kommentierten Lösungen der im Programmierpraktikum gelösten Aufgaben werden von den Teilnehmern mit LaTeX formatiert. Hierzu gibt es einfach zu handhabende Template-Dateien: pi1-muster.tex und das Hilfsfile defs.tex.
Für die eingehendere Beschäftigung mit diesem System zum anspruchsvollen Setzen von Dokumenten ist als Einstieg Leslie Lamport: Das LaTeX Handbuch. Addison-Wesley 1995 ebenso wie Helmut Kopka: LaTeX Einführung, Band 1. Addison-Wesley 2000 zu empfehlen. Alles, was in bezug auf LaTeX für die Abgabe der Aufgabenblätter notwendig ist, findet man ebenfalls in der online verfügbaren Kurzanleitung zu LaTeX
Fachbegriffe lassen sich häufig sehr gut in der im WWW verfügbaren Encyclopaedia Britannica nachschlagen: http://www.britannica.com
Weitere Lerninhalte, die nicht direkt in der hier genannten Literatur verfügbar sind, werden als Skripte im Laufe des Semesters im WWW veröffentlicht, die Links werden in diesem Abschnitt hier angegeben.

Veranstaltungsinhalte

Die folgende Liste von Lerninhalten wird im Laufe des Semesters entwickelt. Sie dient als Checkliste, mit welchen Themen und Begriffen die Veranstaltungsteilnehmer vertraut werden sollten. Eine "Session" entspricht einer zusammengehörigen Lerneinheit, sie muss nicht notwendigerweise in genau einer Vorlesung abgehandelt werden.

Session 1: Merkmale objekt-orientierter Programmiersprachen

Vorlesung: Objekte: Attribute, Operationen, Methoden, Schnittstellen, Nachrichten, Signatur, Geheimnisprinzip - Klassen: Konstruktoren, Instantiierung, konkrete/abstrakte Klassen - Vererbung: Einfach-/Mehrfachvererbung, Generalisierung, Spezialisierung - Überladen/Überschreiben/Redefinition von Operationenen - Polymorphismus - (spätes) Binden von Operationen an Methoden - Generische (d.h. typunabhängige) Methoden und Klassen, Templates (d.h. Typparametrisierung)

Literatur für Vorlesung und Tutorien: Balzert, Abschnitte 2.5, 2.14

Session 2: Ausprägung objekt-orientierter Programmierkonzepte in Java

Vorlesung: Eine Übersicht der wichtigsten Stichworte und Fakten zum Thema Objekt-orientierter Programmierkonzepte und Java ist hier angegeben. Dazu findet man Beispielquelltexte MyMain.java, MyFiniteStack.java, MyComparable.java, die alle gemeinsam in einem Verzeichnis mit javac *.java zu übersetzen sind.

Literatur für Vorlesung und Tutorien: Balzert, Abschnitte 2.5, 2.10, 2.11, 2.14, 2.16

Session 3: Algorithmen und Datenstrukturen

Vorlesung: Dieser Teil der Vorlesung wird begleitend zu allen anderen Sessions durchgeführt und dient dazu, weitere Datenstrukturen und darauf operierende Algorithmen einzuführen: Stapel (englisch: Stacks) - binäre Bäume, balancierte Bäume, AVL-Bäume - Transitionssysteme (Definition siehe unten)

Literatur für Vorlesung und Tutorien: Balzert, Abschnitte 2.19.6, 3.8

Session 4: Formale Verifikation sequenzieller Programme

Vorlesung: Beweisregeln für sequenzielle Programme: Konsequenzregel - Axiom für die leere Anweisung - Zuweisungsregel - Sequenzregel - if-Regel - while-Regel - Terminierungsbeweis für Schleifen.

Ein Verifikationsbeispiel findet man hier .

Literatur für Vorlesung und Tutorien: Balzert, Abschnitte 3.2.3 - 3.2.7

Beispiele, Zusatzinformationen und ähnliches

Hashing

Die Beispielimplementierungen zu Hashing-Verfahren, welche in der Vorlesung PI-I vorgestellt wurden, finden sich hier: MyHash.java sowie MyHashS.java. Zusätzlich eine Version, welche die einzutragenden Werte aus einem File names raweventsTL.t liest: MyHashFile.java. Eine Beispieldatei hierfür findet sich hier.

Syntax-Prüfung

Als Hilfe für die erste Aufgabenserie für PI-2 gibt es hier nochmal die Folien aus der letzten Vorlesung PI-1 als Postscript: SATZGram.ps, SATZJava.ps und als PDF: SATZGram.pdf, SATZJava.pdf.
Die Methoden auf diesen Folien sind so noch nicht ausführbar, da alle Methoden zum Umgang mit Tokens fehlen (also insbesondere getNextToken), entsprechend sind die Token-Vergleiche in den switch Anweisungen nicht ausführbar, solange keine (z.B. int) Konstanten zur Repräsentation der einzelnen Token festgelegt worden sind. Achtung: Die Darstellung der Grammatik folgt nicht streng den EBNF Regeln, sondern basiert nur auf ihnen. Nichtterminale sind komplett in Grossbuchstaben dargestellt, Terminale (=Token) sind unterstrichen, Regeln werden mit = statt mit ::= definiert. Diese Variante der Darstellung findet man ebenfalls sehr häufig in Büchern über Formale Sprachen oder auch in Syntaxbeschreibungen für Programmiersprachen.

Definition Transitionssystem

Für die Aufgabenserie 4 und als ein Bäume verallgemeinernder Abstrakter Datentyp wurden in der Vorlesung Transitionssysteme eingeführt:

Definition: Ein Transitionssystem (englisch Labelled Transition System) ist ein Quadrupel LTS = (S,S₀,A,T) mit folgenden Eigenschaften:

S ist eine endliche Menge, deren Elemente Zuständen von LTS genannt werden.
S₀ ist eine Teilmenge von S, deren Elemente die Anfangszustände von LTS genannt werden.
A ist eine endliche Menge, genannt das Alphabet von LST. Die Elemente von A heissen Label von LTS.
T ist eine Teilmenge von S × A × S (also eine dreistellige Relation), die Menge der Transitionen von LTS.

Ein Transitionssystem heisst deterministisch, wenn folgende Bedingungen beide erfüllt sind:

S₀ enthält genau ein Element
Wenn (z₀,a,z₁) eine Transition aus T ist, dann folgt für alle (w₀,b,w₁) aus T mit w₀ = z₀ und b = a auch w₁ = z₁.

Eine Ausführung (englisch Execution) eines Transitionssystems LTS = (S,S₀,A,T) ist eine Folge (z₀,a₀,z₁,a₁,z₂,a₂, ... ), so dass folgende Bedingungen erfüllt sind:

z₀ ist ein Element von S₀
Für alle i = 0,1,2,... gilt: (z_i,a_i,z_i+1) ist eine Transition aus T.

Beispiel zur Programmverifikation

Hier findet Ihr noch einmal das Verifikationsbeispiel aus der Vorlesung, diesmal vollständig (totale Korrektheit) und ausführlich dokumentiert (auch als PDF).

Aufgabenblätter

In diesem Abschnitt findet Ihr die Aufgabenblätter und gegebenenfalls Zusatzinformationen für die Lektürestunden zum Herunterladen und ausdrucken.

Die Lösungen zu den Aufgabenblättern müssen mit LaTeX gesetzt werden, dabei sollen die Vorgaben aus pi1-muster.tex und der Hilfsdatei defs.tex verwendet werden.

Die weiteren Aufgabenserien werden im Verlauf des Semesters nach und nach passend zu der Vorlesung hier zu finden sein. Die geplanten Termine für alle Aufgabenblätter könnt Ihr in der hier liegenden Tabelle nachsehen.

Serie X für PI-I: Eine Serie zur freiwilligen Wiederholung / Vertiefung des Stoffs aus dem ersten Semester als Postscript File. Die Aufgaben sind unabhängig voneinander je nach Lust und Bedarf zu lösen. Dabei ist der Programmieraufwand bei Aufgabe 1 sehr gering, bei Aufgabe 2 etwas größer und für die Aufgaben 3 und 4 sollte man schon jeweils mehrere Stunden einplanen.
Serie 1: Postscript oder PDF
Musterlösungen: Aufgabe 1, Aufgabe 2
Gute Lösung der Gruppe Bauerdick/Hois/Wu: Aufgabe 1, Aufgabe 2
Serie 2: Postscript oder PDF
Serie 3: Postscript oder PDF
Musterlösungen: Aufgabe 1, Aufgabe 2
Serie 4: Postscript oder PDF
Passend dazu die Eingabeklasse Input ($Revision 1.3 $).
Serie 5: Postscript oder PDF ACHTUNG: Neuer Abgabetermin: 3. Juli 2001
Das ausführbare Programm dazu: BinSearch.java.

Jan Peleska - TZI - Bremen Institute of Safe Systems BISS / < jp@informatik.uni-bremen.de> / 27 MAY 2001