Praktische Informatik 2, SoSe 2003

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

Inhalt dieser Seite:

• Termine
• Aufgabenblätter
• Das PI2-Team
• Prüfungen
• Struktur der Veranstaltung
• Veranstaltungsinhalte im Detail
• empfohlene Literatur und Online-Dokumentation
• Hintergrundinformationen

Termine

Vorlesung:

Übungen:

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.
Für die Bewertung der Programmieraufgaben haben wir unsere Grundzüge aufgeschrieben, ebenso wie Hinweise zum Kommentieren und Testen der Programme.
Montag, 28. April: Die erste Aufgabenserie ist hier im postscript Format und hier als PDF zu finden. Die PDF-Version deckt sich JETZT mit der Postscript-Variante - die vorherige war unvollständig.
Montag, 12. Mai: Die zweite Aufgabenserie ist hier im postscript Format und hier als PDF zu finden. Für die zweite Aufgabe hier noch einmal der Link zur vollständige Java-Syntaxspezifikation in EBNF-Notation: SCJP-Grammatik.
Montag, 26. Mai: Die dritte Aufgabenserie ist hier im postscript Format und hier als PDF zu finden. Um Eingaben über die Kommandozeile zu verarbeiten, kann die Klasse Input.java benutzt werden. Da wegen Himmelfahrt und Pfingsten diverse Übungstermine ausgefallen sind, wird die Abgabe der Serie 3 auf 16. 06. - 19. 06. verschoben!
Mittwoch, 11.Juni: Wir veröffentlichen schon die vierte Aufgabenserie im postscript Format und als PDF . Bei der Lösung hilft neben der Vorlesung ganz konkret folgender Java-Schnipsel. Hier noch der Link zur Dokumentation von java.lang.reflect . Zum Testen Eures Forschers hat Jan Bredereke zwei marsianische Gäste aus dem vorigen Jahr zur Verfügung gestellt: einen minimalen Marsianer und einen recht komplexen Marsianer , der zudem auch noch von einem Supermarsianer erbt. Die Abgabe der Serie 4 ist bereits vom 23. 06 - 26. 06.!
Montag, 23. Juni: Die fünfte Aufgabenserie ist hier im postscript Format und hier als PDF zu finden. In der ersten Fassung hatten sich leider Fipptehler eingeschlichen, die Klasse Graph soll für den Suchalgorithmus eine Methode public void breitenSuche(IVertex v0, IProperty eigenschaft, IAction aktion) besitzen, d.h. die Parameter müssen den Interfaces entsprechen.

Das PI2-Team

Unermüdlich arbeiten für Euch:

Vorlesung

Prof. Dr. Jan Peleska, jp@informatik.uni-bremen.de

Übungen

Organisation:
Ulrich Hannemann, ulrichh@informatik.uni-bremen.de

Übungsgruppenleiter:

• Stefan Bisanz, alien@tzi.de
• Dr. Jan Bredereke, brederek@tzi.de
• Ulrich Hannemann, ulrichh@tzi.de
• Stefan Hansen, beeswax@tzi.de
• Hendrik Mangels, mangels@tzi.de
• Thorsten Scholz, scholz@tzi.de
• Thomas Vögele, vogele@tzi.de
• Dennis Walter, dw@tzi.de
• Yang Yi, yangyi@tzi.de

Prüfungen

Scheinkriterien

In der Vorlesung am 28.4.2003 wurden folgende Scheinkriterien vereinbart:

• Es gibt n Übungszettel (ca. 14-tägig),
  davon sind n Zettel abzugeben.
• 60% der Aufgaben dieser 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), dann bei Jan Peleska.

Leistungsnachweise

Falls Ihr aus irgendwelchen Grüunden zum vereinbarten Termin verhindert sein solltet, setzt Euch bitte mit dem jeweiligen Mitarbeiter in Verbindung. Meldet Euch für die Einzelnachprüfungstermin bitte direkt bei Jan Peleska, jp@informatik.uni-bremen.de, an!

Fachgespräche

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.

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.

• Session 0: Syntax, Grammatik und Algorithmen für die Syntaxprüfung
• Einschub: Ausnahmebehandlung
• Session 1: Merkmale objekt-orientierter Programmiersprachen
• Session 2: Algorithmen und Datenstrukturen
• Session 4: Formale Verifikation sequenzieller Programme
• Session 4: Grafik in Java

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

• Syntax: Die möglichen Zeichenfolgen einer gegebenen Sprache.
• Semantik: Die Bedeutung der Sprachkonstrukte:
  • Statische Semantik: Die Bedeutung der verwendeten Daten- und Klassentypen sowie die logischen Abhängigkeiten untereinander.
  • Dynamische Semantik (Verhaltenssemantik): Die durch Programmausführung bewirkte Erzeugung/Vernichtung/Änderung von Variablen, Dateien (allgemeiner Objekten), sowie die an den Programmschnittstellen sichtbar werdenden Ein-/Ausgaben.
• Semiotik: Die Lehre von den Symbolen und ihrer Bedeutung.
• Grammatik: Spezifikation der erlaubten Zeichenfolgen einer Syntax.
• Notation zum Beschreiben von Java-Grammatiken siehe [Balzert, pp.91-94]:
  • Java-spezifische Notation: Von Gosling eingeführte Spezialnotation für Java-Syntax, beschrieben in The Java Language Specification, http://java.sun.com/docs/books/jls/index.html, Abschnitten 2.4 und 18.1. Die dort enthaltene vollständige Spezifikation der Java-Syntax ist leider fehlerhaft. Nach unserer Einschätzung hat und wird sich die Java-spezifische Notationstechnik langfristig nicht duchsetzen; wir werden uns in der Vorlesung deshalb nur mit den folgenden 2 Techniken zur Syntaxdefinition befassen. Diese werden heutzutage für beliebige formale Sprachen angewandt.
  • Extended Backus-Naur Form: Eine textuelle Spezifikationsform für Grammatiken. Ist u.a. besonders attraktiv, weil verschiedene Werkzeuge existieren (z.B. yacc und bison), die aus EBNF-Spezifikationen automatisch Syntax Checker (Prüfprogramme für die Korrektheit eines Programmtextes in Bezug auf die Einhaltung der grammatischen Regeln) erzeugen.
  • Syntaxdiagramme: Alternativ zur EBNF-Notation können grammatikalische Regeln durch eine anschauliche Graph-Notation spezifiziert werden.
• 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 Struktur von Java: Unicode, Eingabeelemente, Tokens, Bezeichner, Schlüsselworte, Literale, Separatoren, Operatoren
• Lexikalische Grammatik: Spezifikation der zum Sprachalphabet gehörigen Tokens.
• Syntaktische Grammatik: Spezifikation der in der Sprache erlaubten Folgen von Tokens.
• Einführung in die syntaktische Struktur von Java: Übersetzungseinheit (Compilation Unit), Package Declarations, Import Declarations, Type Declarations. Klassen sind spezielle Typdeklarationen; daher sind Methoden, Variablendeklarationen usw. alle dem Bereich 'Typdeklarationen' zuzuordnen, denn diese müssen immer innerhalb einer Klassendeklaration erfolgen.
• 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, auf dessen Basis dann die Transformation in Objektcode (Java: Bytecode) erfolgen kann.
• 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 ...
  • Eine spezielle Produktionsregel - das Zielsymbol (Goal Symbol) wird markiert, bei der die Syntaxprüfung zu beginnen hat. Beispiel: In der Java-Grammatik heisst das Zielsymbol, mit dem alle Interpretationen beginnen, CompilationUnit.
  • 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

• Programmierbeispiel "einfacher Syntaxchecker" mit endlichen Saetzen und ausschliesslich |-Operatoren in der EBNF: Simplesyncheck.java
• Programmierbeispiel mit Saetzen unbeschraenkter Laenge und allen EBNF-Operatoren: Sc.java
• [Balzert, pp.91-94],
• The Java Language Specification, http://java.sun.com/docs/books/jls/index.html, Abschnitte 2.4 und 18.1.
• Vollständige Java-Syntaxspezifikation in ISO-EBNF-Notation (ISO-normierter Dialekt von der EBNF-Notation, welche wir verwenden: iso-14977.pdf)
  1. http://home.bredband.no/gaulyk/java/grammar/JavaGrammar1.html: Java-Syntaxspezifikation (Parser-optimiert).
  2. http://home.bredband.no/gaulyk/java/grammar/scjp.html: Java-Syntaxspezifikation (alternative Beschreibung - vielleicht etwas leichter lesbar).

Einschub: Ausnahmebehandlung

Session 1: Merkmale objekt-orientierter Programmiersprachen

Hier findet Ihr "Die wichtigsten Stichworte und Fakten zum Thema Objekt-Orientierte Programmiersprachen und OO in Java."

Das Beispiel mit der Datum-Klasse von Stefan Bisanz demonstriert zum einen das Geheimnisprinzip, und außerdem zeigt es, wie man gute Dokumentation mit Javadoc schreiben kann.

Zum Thema Reflektion sind hier einige Ergänzungen zu den Fragmenten aus der Vorlesung vom 16. Juni. Man erfährt zudem noch etwas über Interfaces, Exceptions, Vererbung, Modifier, Overloading und die Implementierung eines endlichen Stacks. Ein Interface: MyComparable.java, eine Klasse, die von Exception erbt: MyFiniteStackException.java, eine Sammlung von endlichen Stacks: MyFiniteStack.java, und schließlich MyMain.java, in welchem die Aufrufe aus dem Reflektionspaket verwendet werden.

Session 3: Algorithmen und Datenstrukturen

Transitionssysteme

• Definition Transitionssystem:

  Als ein allgemeiner 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 die Zustände 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 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:

  • 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.

Breitensuche auf (gerichteten) Graphen

   Für alle  v   aus  V : d[v] = -1  
   u0 = v0 ;
   q = <  u0 > ; 
   d[u0] = 0 ;
   WHILE q != < > DO
                u0 = head(q) ; q = tail(q) ;
                d0 = d[u0] ;
                IF (hasProperty(u0,...) )
                       THEN process(u0,...) ;
                FOR v in adjlist(u0) DO                               
                      IF d[v] < 0 THEN     
                           q = append(q , < v >) ;
                           d[v] = d0 + 1 ;

Binäre Bäume:

Session4 : Formale Verifikation sequentieller Programme

Axiom für die leere Anweisung

{PRE} ; {PRE}

Zuweisungsaxiom

{p[x:=expr]} x = expr; {p}

Konsequenzregel 1

Wenn {p} S {q} und q => r gelten,
dann gilt auch {p} S {r}.

Konsequenzregel 2

Wenn o => p und {p} S {q} gelten,
dann gilt auch {o} S {q}.

Sequenzregel

Wenn {p} S1 {r} und {r} S2 {q} gelten,
dann gilt auch {p} S1; S2 {q}.

Bedingungsregel

Wenn {p AND B} S1 {q} und {p AND NOT B} S2 {q} gelten,
dann gilt auch {p} if (B) S1 else S2 {q}.

Schleifenregel

Wenn {p AND B} S {p} gilt,
dann gilt auch {p} while (B) S {p AND NOT B}

Session 5: Grafik in Java

• Folien zur Vorlesung.
• Quelltext und Applet der vorbereiteten Vorlage von LonelyPacMan.
• Quelltext der in der Vorlesung entwickelten Version von LonelyPacMan.
• Weiterführende Informationen:
  • allgemeines und aktuelles Java-Tutorial, einschliesslich Einführung in "Swing": http://java.sun.com/docs/books/tutorial/index.html
  • altes AWT-Tutorial zum Herunterladen: http://java.sun.com/docs/books/tutorial/download/tut-OLDui.zip
    (daraus waren auch die anfänglichen Beispiele zu grafischen Komponenten)
  • allgemeine Java-API-Doku zu Version 1.4 (inkl. Swing): http://java.sun.com/j2se/1.4/docs/api/index.html
  • allgemeine Java-API-Doku zu Version 1.1: http://java.sun.com/products/jdk/1.1/docs/api/packages.html
  • Java3D:
    • Hauptseite: http://java.sun.com/products/java-media/3D/index.html
    • Dokuseite: http://java.sun.com/products/java-media/3D/collateral/
    • Tutorial: http://java.sun.com/products/java-media/3D/collateral/j3d_tutorial.zip
    • API-Doku zum Herunterladen: http://java.sun.com/products/java-media/3D/download.html

empfohlene Literatur und Online-Dokumentation

• Programmierprinzipien, Objektorientiertes Programmieren, Algorithmen und Datenstrukturen:
  Helmut Balzert: Lehrbuch Grundlagen der Informatik, Spektrum Akademischer Verlag (1999). ISBN 3-8274-0358-8.
• Algorithmen und Datenstrukturen:
  Aho, Hopcroft, Ullman: Data Structures and Algorithms. Addison-Wesley 1983.
• Erlernen der Programmiersprache Java:
  
  • Einführung in Java:
    The Java Tutorial - A practical guide for programmers, http://java.sun.com/docs/books/tutorial
  • Code-Konventionen für Java:
    Die Code-Konventionen finden sich unter http://java.sun.com/docs/codeconv/html/CodeConvTOC.doc.html
    Beim Schreiben von Java-Programmen sollten sie beachtet werden, damit der korrigierende Tutor den Code auch lesen kann.
    Hierzu gibt es eine Folienpräsentation, die in manchen Übungen gezeigt wurde. Sie ist hier in Farbe und in Schwarz-Weiß herunterzuladen.
  • "offizielle" Dokumentation:
    James Gosling, Bill Joy, Guy Steele und Gilad Bracha: The Java Language Specification, http://java.sun.com/docs/books/jls/index.html.
    Diese Dokumentation dient zum systematischen, wissenschaftlich ausgerichteten Erlernen der Java-Syntax und -Semantik.
  • Übersicht über die Java API:
    http://java.sun.com/api/index.html
    Diese Übersicht eignet sich gut, um die Parameter und Funktionsweise einzelner Methoden nachzuschlagen.
  • Überblick über Java Tutorien, Artikel und Bücher:
    http://developer.java.sun.com/developer/infodocs/
• LaTeX:
  • Vorlage für die kommentierten Lösungen der Aufgaben:
    Die Lösungen werden von den Teilnehmern mit LaTeX formatiert. Die herunterladbare Vorlage pi2-muster.tex und die zugehörige Hilfsdatei defs.tex helfen dabei.
  • Kurzanleitung:
    Die hier verfügbare Kurzanleitung zu LaTeX enthält alles, was für die Abgabe der Aufgabenblätter notwendig ist.
  • Eingehendere Einführung in das anspruchsvolle Setzen von Dokumenten mit LaTeX:
    • Leslie Lamport: Das LaTeX Handbuch. Addison-Wesley 1995.
    • Helmut Kopka: LaTeX Einführung, Band 1. Addison-Wesley 2000.
• 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.

Hintergrundinformationen

• Unicode-Zeichensatz:
  http://www.unicode.org/
• Encyclopaedia Britannica:
  http://www.britannica.com
  Hier lassen sich Fachbegriffe häufig gut nachschlagen.