Praktische Informatik 1 im Wintersemester 2000/2001

Das PI1-Team

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

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

Übungen - Lektüre:

Programmierpraktikum:

Veranstaltungszeiten

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

        Übungen:		Mo.  8-10 Uhr 
        			Mo. 13-15 Uhr
       				Mi.  8-10 Uhr

        Programmierpraktikum:   Mo.  9-12 Uhr
           			Mo. 15-18 Uhr
       			    	Di. 13-16 Uhr
       			    	Di. 16-19 Uhr
           			Mi.  9-12 Uhr
           			Mi. 13-16 Uhr
           			Mi. 16-19 Uhr
           			Do. 16-19 Uhr
           			Fr.  9-12 Uhr
           			Fr. 13-16 Uhr
           			Fr. 16-19 Uhr

        Freq. Asked Questions   Mi. 10-13 Uhr
	FAQ am Rechner          Fr.  9-12 Uhr

Beginn der Veranstaltungen: 
        Vorlesung:  		Do, 26.10.00
        Übung:			Fr, 27.10.00
        Programmierpraktikum: 	Mo, 30.10.00

Struktur der Veranstaltung

Die Veranstaltung wird in drei Bereiche gegliedert:

Hinweis auf Veranstaltung "Frequently Asked Questions": Vor allem für ausländische Studierende bieten wir die Möglichkeit, Verständnisfragen zu besprechen. Jeden

Mittwoch von 10-13 Uhr im Raum 8140
bietet Hui Shi die Möglichkeit an, in Kleingruppen allgemeine Fragen zu der Praktischen Informatik zu stellen und zu diskutieren. Meldet Euch bitte vorher (kurzfristig) bei ihr an, wenn Ihr einen Teil der Zeit in Anspruch nehmen wollt, z.B. per eMail an shi@informatik.uni-bremen.de.

Zusätzlich bietet Hui Shi ein "freies" Programmierpraktikum an, und zwar jeden

Freitag von 9-12 Uhr im Praktikumsraum P5
Solltet Ihr über Euer Praktikum hinaus noch Fragen haben, die am besten direkt am Rechner zu klären sind, oder solltet Ihr einfach weitere Zeit an den Rechnern benötigen, falls die Zeit in Eurem eigenen Praktikum nicht für die Lösung der Aufgaben ausgereicht hat, so könnt Ihr einfach ohne Anmeldung zu diesem Termin erscheinen.

Literatur

Java, Emacs, LaTeX für Zuhause

Wenn Ihr lieber zuhause arbeiten möchtet, so könnt Ihr das unter allen gängigen Betriebssystemen tun - alle notwendigen Tools dafür stehen kostenfrei im Internet zur Verfügung.

Für Linux (auch auf jeder aktuellen Distribution vertreten):

Für Windows: Für MacOS:

Veranstaltungsinhalte

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 muss nicht notwendig in genau einer Vorlesung abgehandelt werden.

Session 1: Grundlagen aus der technischen Informatik

Vorlesung: Konventionelle Maschinen und Computer im Vergleich - Programm und Prozess: der Begriff des Kontextes - von-Neumann'sche Rechnerorganisation - Rechnerarchitektur - CPU und ihre Grundstruktur (Register und Befehlszähler), Datenbus und Adressbus, Cache, RAM und ROM, Hintergrundspeicher - Bytes, Bits, Maschinenworte - Ein-/Ausgabeeinheit - Arbeitsweise einer CPU - Assembler und Maschinensprache - Speicheradresse versus Speicherinhalt - Die Hierarchie der Programmiersprachen (von "unten nach oben", d.h. von hardwarenah bis anwendungsnah): (1) CPU Mikrocode (2) Maschinencode (3) Assembler (4) Wide-spectrum Languages, 3rd generation (C,C++,Java,Ada,...) (5) Domain-specific Languages (anwendungsspezifische Sprachen) - eine fiktive Assemblersprache und ihre Realisierung im Mikrocode (siehe Lektüre)
Übungen - Lektüre: Wiederholung von Grundbegriffen aus der Logik und Mengenlehre: Hierzu findet man unter Lektüre1 eine Übersicht über die mathematischen Begriffe, mit denen man unbedingt vertraut sein (oder in der Lektürestunde vertraut werden) sollte - - Eine einfache "fiktive" Assemblersprache mit Load/Store/Jump/Integer-Befehlen - Maschinencode - Realisierung der Assemblerbefehle im (fiktiven) Mikrocode einer CPU - Schnittstellen Treiber und Controller: Polling, Interrupts, DMA: Hierzu siehe auch Lektüre2
Programmierpraktikum: Textverarbeitung in LaTeX - Emacs im LaTeX Mode - pdflatex und Acrobat Reader - xdvi - ghostview
Eine Kurzeinführung, die auch Grundlage für das erste Praktikum sein wird, liegt hier zum Download bereit.
Literatur für Vorlesung und Übungen/Lektüre: Oberschelp und G. Vossen: Rechneraufbau und Rechnerstrukturen, Kapitel 8

Session 2: Programmiersprachen und die ersten Schritte in Java

Vorlesung: Semiotik, Syntax, Semantik - maschinell interpretierbare Sprachen - problemorientierte versus maschinenorientierte Programmiersprachen - wide-spectrum languages versus domain-specific languages - Programmiersprachenübersicht - ein Muss für ProgrammiererInnen [:-)]: Hello World-Programm als Java Anwendung - Betriebssysteme und Laufzeitumgebungen - Virtuelle Maschinen - Compiler und Interpreter - Java Byte Code - Die ersten Sprachelemente von Java: Kommentare, Klassen, Objekte, Methoden, die main-Methode, Variablen mit primitiven Typen, Operatoren, Ausdrücke, Anweisungen, Blöcke und Scope, erste Kontrollstrukturen - Arrays als erstes Beispiel für Referenzvariablen - Parameterübergabe bei Methoden - lokale Variablen in Methoden - das Prinzip des Stack - Ein-/Ausgabe: das Konzept von Abstraktion und Verfeinerung - Die Programmierbeispiele der ersten 2 Java-Vorlesungen sind in HelloWorldDoc.java zu finden.
Übungen - Lektüre: Übersicht über die Basiswerkzeuge in einer Programmierumgebung (Shell, Editor, Compiler, Assembler, Linker, Loader, Interpreter, Debugger, Sourcebrowser, HTML-Browser). Vertiefung der Java Spracheinführung. Implementierung kleiner Mengen mit Integer-Variablen und Bit-Operatoren
Programmierpraktikum: Einführung in die grundlegenden Werkzeuge zur Programmentwicklung unter Java: Emacs im Java-Mode, javac, java, appletviewer, Netscape, Debugger, Sourcebrowserfunktion mit Emacs (ctags/etags). Übungsprogramme zum Erlernen der Wertebereiche von primitiven Typen und zum Anwenden der Operatoren.
Literatur für Vorlesung und Übungen/Lektüre: (1) Oberschelp und G. Vossen: Rechneraufbau und Rechnerstrukturen, Kapitel 11.4. (2) The Java Tutorial - A practical guide for programmers: Learning the Java Language, Abschnitt 'Language Basics', http://java.sun.com/docs/books/tutorial/java/nutsandbolts/index.html (3) Wer Details über den Unicode Zeichensatz wissen möchte, findet dies hier: http://www.unicode.org

Session 3: Systematische Java-Spracheinführung

Vorlesung: Vorbemerkung: In der vorigen Session bestand das Lernziel darin, eine intuitive Einführung in die Programmiersprache Java zu geben. In der Session 3 nähern wir uns Java von der wissenschaftlichen Seite: Wie beschreibt man die gültigen, vom Rechner interpretierbaren Sprachkonstrukte auf eindeutige und systematische Weise? Welche grundsätzlichen "Zutaten" gehören zu einer Programmiersprache? Wie kann man die Semantik von Sprachkonstrukten auf eindeutige Weise spezifizieren?
Lexeme und Syntax - lexikalische Grammatik - syntaktische Grammatik - Notation zum Beschreiben von Java-Grammatiken: Java-spezifische Notation, Syntaxdiagramme, EBNF (erweiterte Backus-Naur-Form) - lexikalische Struktur von Java: Unicode, Eingabeelemente, Tokens, Bezeichner, Schlüsselworte, Literale, Separatoren, Operatoren - Einführung in die syntaktische Struktur von Java: Übersetzungseinheit (Compilation Unit), Package Declarations, Import Declarations, Type Declarations, primitive Typen, Variablen, Blöcke und Anweisungen - Ausdrücke und Zuweisungen: die Java/C/C++-Problematik - Anweisungen, insbesondere Kontrollstrukturen: leere Anweisung, Ausdrucksanweisungen, if, switch, while, do, for, break, continue, return, throw-try-catch, Anweisungs-Labels. Zum Package-Konzept siehe die Zusatzinformationen unten. - Das Prinzip der Rekursion
Übungen - Lektüre: Beschreibung der Syntax einfacher fiktiver Sprachen mit der Java Notation für Grammmatiken, mit Syntaxdiagrammen und mit EBNF-Notation - Vertiefung der systematischen Java-Spracheinführung.
Programmierpraktikum: Programmieraufgaben mit primitiven Variablen und Kontrollstrukturen.
Literatur für Vorlesung und Übungen/Lektüre: The Java Language Specification, Chap. 2,3,4(teilweise),7(teilweise),14

Session 4: Algorithmen und Datenstrukturen - Teil 1

Vorlesung: Sortieralgorithmen: Bubble Sort, Merge Sort, Quick Sort - Suchalgorithmen: Binaere Suche auf sortierten Feldern, Hashing (Hierzu werden Listen benötigt, daher wird Hashing nach den Listen und ihren Basisoperationen eingeführt) HINWEIS: Die hier eingeführten Sortier- und Suchalgorithmen kommen mit linearen Datenstrukturen - das sind Arrays und Listen - aus. In der Vorlesung PI2 werden weitere Suchalgorithmen eingeführt, die auf komplexeren Datenstrukturen (Graph-Strukturen, zu denen Bäume und Listen als Spezialfälle gehören) operieren. - Java Klassen zur Realisierung des Kreuzprodukt-Typs - Verzeigerung durch Java-Referenzdatentypen - Listen in Java (ein erstes Programmierbeispiel in Anlehnung an die Einführung in der Vorlesung findet sich unten. Ein komplexeres Paket zur Implementierung von Listen als Abstrakten Datentyp sind in den Aufgaben für das Programmierpraktikum enthalten) - NEBENBEMERKUNG: Referenztypen und Garbage Collection bei Java - rekursive Algorithmen zur Syntaxprüfung -
Übungen - Lektüre: Besprechung von Sortier- und Suchalgorithmen - Abstrakte Datentypen und ihre Interpretation über Mengenkonstruktionen und kanonische Operationen auf Mengen.
Programmierpraktikum: Implementierung von Sortier- und Suchalgorithmen - Implementierung von Listen mit den 'kanonischen Operationen' als Abstrakter Datentyp.
Literatur für Vorlesung und Übungen/Lektüre: Balzert, LE18 (Suchen und Sortieren) und Balzert, LE 17 (Listen). Als weiterführende Lektüre zu und professionelles Arbeiten mit Algorithmen und Datenstrukturen, Sortieren und Suchen, sind sehr zu empfehlen: [1] Aho, Hopcroft, Ullman: Data Structures and Algorithms. Addison-Wesley 1983. [2] Knuth: The Art of Computer Programming Volume 3: Sorting and Searching, 2nd Edition. Addison Wesley 1998. Das ist der Klassiker auf diesem Gebiet, gewisse Professoren gucken immer dort zuerst rein, wenn sie mal einen wirklich guten Algorithmus brauchen und ihn nicht erst selber erfinden möchten - eine Schande, dass diese Buch bei Balzert nicht zitiert wird, oder hab' ich diese Stelle bloß nicht gefunden ? [3] Rosen et al.: Handbook of Discrete and Combinatorial Mathematics. CRC Press 2000. Dies ist ein sehr neues Handbuch, welches eine sehr vollständige Übersicht zu dem breiten Themenspektrum gibt, welches im Titel gekennzeichnet ist. Man findet dort Hinweise auf neuere Ergebnisse; für die man ggf. zum richtigen Verstehen auf dort gegebene Literaturhinweise zurückgreifen muss.

Beispiele und ähnliches

Javadoc

Ein einfaches Beispiel zum Umgang mit javadoc:

Rechnerarithmetik

Beispiel zur Demonstration der Probleme der Ungenauigkeiten der Rechnerarithmetik: Integralberechnung mit Hilfe der Streifenmethode

Packages

Hilfe zum Umgang mit Packages: Postscript-Format   PDF-Format
Als Beispiel für ein Javaprogramm, welches das im Unterverzeichnis 'myfirstpackage' liegende Paket 'myfirstpackage' importiert, kann man sich PackageDemo.java ansehen. Die zum Paket gehörige Klasse ist AuxClass.java.

Listen

Ein erstes Programmbeispiel für die Implementierung von Listen in Java gemäß der Einführung in der Vorlesung und in Anlehnung an Balzert, Abschnitt 3.7.1 findet sich in MyList.java

Listen - Klassisch imperativ

Ein alternatives Vorgehen zur Implementierung von Listen, welches üblicherweise in der imperativen Programmierung Verwendung findet, ist in dem Java-Programm ImpList.java umgesetzt.

Abbildungen in LaTeX

Hilfe zur Einbindung von Abbildungen in LaTeX:
Ein einführender Text und die entsprechenden Quelltexte:

MergeSort

Eine Implementierung von Mergesort in Java:
Quellcode der Klasse dazu:

Hashing

Die Beispielimplementierungen zu Hashing-Verfahren, welche in der Vorlesung 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.

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.

Ab dem dritten Praktikum-Aufgabenblatt sind die Lösungen zu den Aufgaben abzugeben und werden bewertet!

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