Universität Bremen  
  Universität Bremen FB3 TZI BISS  
  AG BS > Lehre > SoSe 2002 > Deutsch
English
 

Praktische Informatik 2, SoSe 2002
 

Auf dieser Seite werden während des Semesters weiterführende Informationen sowie die jeweiligen Aufgabenblätter bereitgestellt.

Eine Übersicht über Inhalte, Termine,... der Veranstaltung findet sich in unserer Liste der Lehrveranstaltungen.

Inhalt dieser Seite:

Aufgabenblätter

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

  • Blatt 1 (ps/gzip, 27 kB - pdf, 48 kB): ausgegeben am 8.4.2002.
    Abgabe in den Übungen am 29. April - 2. Mai 2002.
    • Tip: Die Methode checkTerm schreibt Ihr am besten so, daß sie selbst getNextToken() aufruft, das Token in einer Variablen zwischenspeichert und es dann versuchsweise an checkBinterm(...) bzw. checkMinterm(...) übergibt. Für letzteres solltet Ihr eine Version mit Parameter vorsehen, so wie es in der Vorlesung beim Thema Overloading vorgestellt worden ist.
    • Musterlösung: SynCheck.java und dazu das Testprogramm Test.java
  • Blatt 2 (ps/gzip, 26 kB - pdf, 42 kB): ausgegeben am 6.5.2002.
    Abgabe in den Übungen bzw. beim Tutor am 21.-23. Mai 2002.
  • Blatt 3 (ps/gzip, 33 kB - pdf, 55 kB): ausgegeben am 27.5.2002.
    Verlängerung der Abgabe: jetzt für alle Gruppen am
    Donnerstag, den 6. Juni 2002.
    • Korrektur: Anders als es im Blatt 3 steht, ist für die Behandlung von primitiven Java-Typen als Methoden-/Konstruktor-Parameter doch eine Sonderbehandlung notwendig. Der dafür notwendige Java-Schnipsel findet sich hier.
    • Musterlösungen:
  • Blatt 4 (ps/gzip, 56 kB - pdf, 86 kB): ausgegeben am 3.6.2002.
    Abgabe in den Übungen am 17.-20. Juni 2002.
  • Blatt 5 (ps/gzip, 34 kB - pdf, 69 kB): ausgegeben am 10.6.2002.
    Abgabe in den Übungen am 1.-4. Juli 2002.

Zum Nacharbeiten der Übungsblätter für das Fachgespräch sind die Mindmaps zu den Übungsblättern von Michael Skibbe hilfreich (auch als Textversion in PostScript). (Und sie waren seiner Gruppe beim Lösen sicherlich ebenfalls hilfreich.)

Das PI2-Team

Unermüdlich arbeiten für Euch:

Vorlesung

Prof. Dr. Jan Peleska, jp@tzi.de

Übungen

Organisation:
Dr. Jan Bredereke, brederek@tzi.de

Übungsgruppenleiter:

  • Felix Beckwermert, foetus@tzi.de
  • Dr. Jan Bredereke, brederek@tzi.de
  • Stefan Hansen, beeswax@tzi.de
  • Arne Hormann, ah@tzi.de
  • Kolja Köster, warhead@tzi.de
  • Hendrik Mangels, mangels@tzi.de
  • Udo Neitzel, neitzel@tzi.de
  • Bernd Schiffer, bschiff@tzi.de
  • Michael Skibbe, mskibbe@tzi.de
  • Dennis Walter, dw@tzi.de

Newsgruppe zur Veranstaltung

Die Newsgruppe Fb3.lv.pi2 bietet die Möglichkeit, Fragen rund um die Veranstaltung zu stellen und zu beantworten. In erster Linie soll sie zwar als Medium für die Studenten untereinander dienen, aber auch die Tutoren haben Interesse daran geäußert, mitzulesen und im Rahmen ihrer Möglichkeiten mal zu antworten.

Struktur der Veranstaltung

Die Veranstaltung wird dieses Semester in zwei 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 Übungen wird der Stoff aus der Vorlesung noch einmal diskutiert, insbesondere indem auf die Inhalte der begleitenden Übungsblätter eingegangen wird. Weiterhin werden allgemeine Problem und gute Vorgehensweisen bei der Lösung 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.

Prüfungen

Scheinkriterien

In der Vorlesung am 15.4.2002 wurden folgende Scheinkriterien vereinbart:

  • Es gibt n Übungszettel (ca. 14-tägig),
    davon sind mindestens n-1 Zettel abzugeben.
  • 60% der Aufgaben der n Übungszettel müssen erfolgreich gelöst worden sein, um zum Schein-Fachgespräch zugelassen zu werden.
  • Das Fachgespräch findet mit je einer Abgabe-Gruppe statt und dauert ca. 15-20 min.
    • Jeder bekommt eine eigene Note.
    • Es ist (als Einzelprüfung) wiederholbar (ggf. auch für eine bessere Note).

Fachgespräch

Termin: Freitag, 12.7.2002, 9-18 Uhr

Inhalte:

  • Der Stoff der Vorlesung und der Übungen (s.u.)
  • Die Aufgabenblätter (s.o.)

Das Fachgespräch wird gruppenweise mit jeweils einer Aufgabenblatt-Abgabegruppe durchgeführt.

Falls jemand zum Prüfungstermin absolut verhindert ist, kann die gesamte Gruppe nach Absprache mit Jan Bredereke auch am Ersatztermin geprüft werden: Freitag, 30.8.2002, 9-12 Uhr.

Schein mitbringen: Bitte zum Fachgespräch einen ausgefüllten, aber noch nicht unterschriebenen Schein mitbringen. Folgende Informationen sollen eingetragen sein (im Falle von Hauptfach-Informatikern):

  • Name, Vorname
  • Matrikelnummer
  • Titel: "Praktische Informatik 2"
  • Veranstaltungskennziffer: "03-532"
  • Semester: "SS 2002"
  • Wochenstunden: "2+2"
  • Studiengang: "Informatik" (oder ...)
  • Art der Leistung: "Gruppenarbeit + Fachgespräch"
  • Datum hinter "Bremen, den...": "12.7.2002"

Die Listen mit den genauen Terminen am 12.7. wurden in der letzten Vorlesungswoche in den Tutorien herumgegeben. Eventuelle Nachmeldungen jetzt bitte direkt über Jan Bredereke.

Die "Ersatzregelungsliste" liegt ebenfalls im Sekretariat MZH 8190 aus.

Zuordnung von Tutorien zu Prüfern und Räumen am 12.7.2002

Tutor Übungstermin Prüfer Raum
Jan Bredereke Mo 13-15 Jan Bredereke MZH 7260
Kolja Köster Mo 13-15 Dirk Meyer MZH 7210
Udo Neitzel Mo 15-17 Thorsten Scholz MZH 7220
Stefan Hansen Mi 13-15 Stefan Bisanz MZH 7230
Bernd Schiffer Do 8-10 Stefan Bisanz MZH 7230
Arne Hormann Do 8-10 Stefan Bisanz MZH 7230
Felix Beckwermert Mi 15-17 Tillman Vierhuff MZH 7250
Dennis Walter Do 8-10 Jan Peleska MZH 8055
Michael Skibbe Do 10-12 Mike Foedisch MZH 6240
Hendrik Mangels Mo 15-17 (siehe unten) (siehe unten)

Die Tutanden von Hendrik Mangels (Tutorium Mo 15-17 Uhr) werden von allen sieben Prüfern im Wechsel geprüft. Welcher Prüfer für welche Gruppe zuständig ist, ergibt sich aus folgender Tabelle:
Zeit Prüfer Raum
9:15 Jan Bredereke MZH 7260
10:30 Thorsten Scholz MZH 7220
10:50 Stefan Bisanz MZH 7230
13:00 Tillman Vierhuff MZH 7250
13:20 Jan Peleska MZH 8055
14:15 Mike Foedisch MZH 6240
14:35 Jan Bredereke MZH 7260

Ersatztermin Fachgespräch

Termin: Freitag, 30.8.2002, 9-15 Uhr

Die Liste für die Prüfungstermine liegt nicht mehr im Sekretariat aus. Wer sich noch am Ersatztermin prüfen lassen möchte, meldet sich jetzt bitte bei Jan Bredereke (brederek@tzi.de).

Wer die Prüfung vom 12.7. wiederholen möchte (und sei es nur, um seine Note zu verbessern), kann sich am Ersatztermin bei Jan Peleska einzelnd prüfen lassen.

Zuordnung von Terminen zu Prüfern und Räumen am 30.8.2002

Uhrzeit Prüfer Raum
9:00-10:20 Jan Bredereke MZH 7210
10:40-12:00 Stefan Bisanz MZH 7250
13:00-14:40 Jan Peleska MZH 8055

Die Prüfungsinhalte sind die gleichen wie am Haupttermin.

Bitte bringt ebenfalls einen ausgefüllten Schein mit, wie oben beschrieben.

Veranstaltungsinhalte im Detail

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

Zum Nacharbeiten des Vorlesungsstoffs für das Fachgespräch sind die Mindmaps über den gesamten Vorlesungsstoff von Michael Skibbe hilfreich (auch als Textversion in PostScript). Außerdem gibt es von Michael Skibbe einen weiteren Satz von Mindmaps zu den Übungsblättern (ebenfalls auch in PostScript).

Session 0: Syntax, Grammatik und Algorithmen für die Syntaxprüfung

  • Begriffe: Syntax (die möglichen Zeichenfolgen einer gegebenen Sprache) - Semantik (die Bedeutung der Sprachkonstrukte) - Semiotik (die Lehre von den Symbolen und ihrer Bedeutung) - Grammatik (Spezifikation der erlaubten Zeichenfolgen einer Syntax)
  • Alphabet: Menge der als logische Einheit zusammengehörigen Zeichenketten der Sprache. Die Elemente des Alphabets heissen Tokens oder gleichbedeutend Lexeme. Beispiel Java: Die reservierten Worte und Zeichen der Sprache (class, if, else, do, while, ';', '{', '}', ...) sind Lexeme aus dem Java-Alphabet. Zusätzlich können Nutzer noch eigene Tokens einführen (Namen für Klassen, Konstanten, Variablen, Methoden, Literale, ...). Das Java-Alphabet ist daher unbeschränkt.
  • Lexikalische Grammatik: Spezifikation der zum Sprachalphabet gehörigen Tokens.
  • Syntaktische Grammatik: Spezifikation der in der Sprache erlaubten Folgen von Tokens.
  • Scanner: Teil eines Compilers, der für die Erkennung der einzelnen Tokens in der das Programm repräsentierenden Zeichenkette zuständig ist.
  • Syntax Checker: Teil eines Compilers, der für das Prüfen des zu übersetzenden Programms gegen die syntaktische Grammatik zuständig ist.
  • Parser: Kombination des Syntax Checkers mit einer Einheit zum Aufbau des Parse Trees.
  • EBNF (Extended Backus-Naur Form) Notation zur Spezifikation kontext-freier Grammatiken: Jede EBNF-Spezifikation besteht aus
    • Jede EBNF-Spezifikation besteht aus Produktionsregeln der Form <Name der Produktionsregel> ::= ... Spezifikation der Produktionsregel ...
    • Die Namen der Produktionsregeln heissen auch nicht-terminale Symbole.
    • In den rechten Seiten der Produktionsregeln können Tokens (hier dann terminale Symbole genannt) oder Verweise auf andere Produktionsregeln auftreten.
    • In den rechten Seiten der Produktionsregeln werden nicht-terminale oder terminale Symbole, die in der Sprache nacheinander aufzutreten haben, sequenziell aufgeführt. Alternativen zwischen mehreren nicht-terminalen oder terminalen Symbolen werden durch | gekennzeichet. Optionale nicht-terminale oder terminale Symbole werden in [...] eingeschlossen. Beliebig oft (keinmal oder mehrmals) auftretende nicht-terminale oder terminale Symbole werden in {...} eingeschlossen. Die Referenzen auf Produktionsregeln in Form von nicht-terminalen Symbolen dürfen rekursiv verwendet werden. Damit ist die Spezifikation von Sprachen mit unbeschränkt langen Sätzen (also z.B. Computerprogrammen) möglich.

Hintergrundinformationen zu Session 0

  • Das in der Vorlesung am 22.4.2002 durchgesprochene Beispielprogramm zur Syntaxspezifikation mittels EBNF und zur Entwicklung eines Scanners und Syntax Checkers für diese Sprache findet man hier.

Session 1: Merkmale objekt-orientierter Programmiersprachen

Literatur zu Session 1

Balzert: Lehrbuch Grundlagen der Informatik, Abschnitte 2.5, 2.14.
Gosling et al.: The Java Language Specification, Kapitel 8 und 14.

Session 2: Threads

  • Quasi-Parallelität auf 1 CPU
  • zwei Formen von echter Parallelität: enge/lose Kopplung (gemeinsamer Hauptspeicher oder nicht)
  • Thread
  • Klasse Thread in Java
  • Monitor
  • synchronized-Eigenschaft von Methoden
  • atomare Transaktion
  • Producer-Consumer-Muster
  • wait()- und notify()-Methoden bei von der Klasse Thread abgeleiteten Klassen

Hintergrundinformationen zu Session 2

  • AccountAccess.java: Beispiel "Kontenverwaltung"
    Thread-Erzeugung, Monitore und synchronized-Eigenschaft von Methoden, erläutert am Beispiel paralleler konkurrierender Transaktionen auf einem Bankkonto.
  • Prod_con.java: Beispiel "Producer - Consumer"
    wait() und notify()-Methoden - Der Erzeuger produziert Datenpakete, die in einen begrenzten Datenbereich eingetragen werden, solange noch Platz ist. Der Verbraucher entnimmt diesem Bereich die Datenpakete, wenn welche vorhanden sind.

Session 3: Algorithmen und Datenstrukturen

  • Transitionssysteme
    • Definition (s.u.)
    • Markierung/Label
    • Zustand
    • Transition
    • Realisierung in Java
    • abstrakte/konkrete Klassen, Interfaces
  • binäre Bäume
    • siehe auch das Kapitel dazu im Balzert
    • Knoten
    • Wurzelknoten
    • Markierung/Label an Knoten
    • Blatt
    • Suchen, Einfügen, Löschen, sortiertes Ausgeben
    • Darstellung in Java
    • Transformation des Schlüssels in eine Bitfolge für links/rechts-Entscheidungen
    • oder: Schlüssel komplett im Knoten
  • AVL-Bäume
    • Vorteile balancierter Bäume gegenüber normalen binären Bäumen
    • Tiefe, Neigung eines Baumes
    • die Operationen zum Rebalancieren beim Einfügen
  • Hashing/Streuspeicherung
    • Motivation: Wertebereich der Schlüssel viel größer als des Arrays
    • Hashfunktion für Integer
    • Hashfunktion für Strings
    • Hashfunktion ist injektiv: Hinter jedem Array-Eintrag ist eine Liste von "Hash-Buckets" nötig
    • Ziel für die Hashfunktion: Gleichverteilung auf die Array-Indizes
    • Größe des Hash-Arrays: Primzahl

Hintergrundinformationen zu Session 3

  • Definition Transitionssystem:

    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,S0,A,T) mit folgenden Eigenschaften:

    • S ist eine endliche Menge, deren Elemente die Zustände von LTS genannt werden.
    • S0 ist eine Teilmenge von S, deren Elemente die Anfangszustände von LTS genannt werden.
    • A ist eine endliche Menge, genannt das Alphabet von LTS. Die Elemente von A heissen Markierungen oder 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:

    • S0 enthält genau ein Element
    • Wenn (z0,a,z1) eine Transition aus T ist, dann folgt für alle (w0,b,w1) aus T mit w0 = z0 und b = a auch w1 = z1.

    Eine Ausführung (englisch Execution) eines Transitionssystems LTS = (S,S0,A,T) ist eine Folge (z0,a0,z1,a1,z2,a2, ... ), so dass folgende Bedingungen erfüllt sind:

    • z0 ist ein Element von S0
    • Für alle i = 0,1,2,... gilt: (zi,ai,zi+1) ist eine Transition aus T.
  • Binäre Bäume: Das Programm aus der Vorlesung am 17.6.2002:
    BinaryTree.java, BtMain.java
  • Ausführliche Erklärung von binären Bäumen und AVL-Bäumen mit vielen Beispielen und Bildern, verfaßt vom Lehrer Axel Wagner aus Homburg/Saar: http://www.hom.saar.de/~awa/jbaum.htm
  • Das Programm zu Hashing aus der Vorlesung am 1.7.2002 findet man hier.

Session 4: Grafik in Java

Anmerkung: Der Stoff dieser Session ist für das Fachgespräch nicht relevant.

  • AWT vs. Swing
  • Beispiel für eine einfache AWT-GUI: "Lonely PacMan"
  • Ausblick: Java3D

Hintergrundinformationen zu Session 4

Stoff aus den Übungen

  • Packages: Definition und Verwendung
  • Applets
    • Start nicht durch main()
    • Erzeugung/Vernichtung mit init()/destroy()
    • Sichtbarmachung/Unsichtbarmachung mit start()/stop()
  • File-IO
    • Unterschied 8Bit-Bytes vs. Unicode-Buchstaben
    • Ein-/Ausgabe mit Bytes: Input-Streams und Output-Streams
    • Ein-/Ausgabe mit Buchstaben: Reader und Writer
    • File-Streams: FileReader, FileWriter
    • Verkettung von Streams

empfohlene Literatur und Online-Dokumentation

Hintergrundinformationen

  
   
Autor: jp 		 
  AG Betriebssysteme, Verteilte Systeme 
Zuletzt geändert am: 2. November 2022   Impressum