Universität Bremen  
  Universität Bremen FB3 TZI BISS  
  AG BS > Lehre > WiSe 2002/03 > Deutsch
English
 

Praktische Informatik 1, WiSe 2002/03

 

Diese Seite gibt weitere Informationen zur Vorlesung. Wir bemühen uns diese Informationen so aktuell wie möglich zu halten.


Anmeldung zum Fachgespäch

Anmeldungen zum Fachgespräch für diejenigen, die zu den ersten Terminen verhindert waren, bitte per e-mail an Ulrich Hannemann: ulrichh@informatik.uni-bremen.de.

Anmeldungen zur Wiederholung des Fachgesprächs bitte direkt an Prof. Dr. Jan Peleska: jp@informatik.uni-bremen.de

Leistungsnachweise

Wer einen Leistungsnachweis erhalten möchte, muß ein vorausgefülltes Formular zum Fachgespräch mitbringen!

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:

  • Hanna Bauerdick
  • Fabian Gutsche
  • Stefan Hansen
  • Sebastian Kropp
  • David Leinhäuser
  • Elmar Loos
  • Hendrik Mangels
  • Elmar Prüsse
  • Torsten Wittig
  • Yi Yang
  • Patrick Zeising
Übungsgruppe Hochschule für Künste Bremen


Veranstaltungszeiten

	Vorlesung:            	Mo. 10 - 12 Uhr, 

  

Raum 0070, Gebäude GW1 HS

Übungen und Programmierpraktikum: Gruppe HfK: Mo. 13 - 15 Uhr, MZH 3150 Gruppe 1: Mo. 15 - 17 Uhr, kl. Senatssaal, MZH 1380 Hui Shi Praktikum: Di. 12 - 15 Uhr, Ebene 0,P1 Gruppe 2: Mo. 15 - 17 Uhr, MZH 7220 Sven Bertel Praktikum: Di. 16 - 19 Uhr, Ebene 0, P1 Gruppe 3: Mo. 17 - 19 Uhr, MZH 6240 Tom Wetjen Praktikum: Mi. 09 - 12 Uhr, Ebene 0, P1 Gruppe 4: Mo. 17 - 19 Uhr, MZH 7220 Sven Bertel Praktikum: Mi. 13 - 16 Uhr, Ebene 0, P1 Gruppe 5: Mo. 17:00 Uhr, MZH 7210 Jan Oliver Wallgruen Praktikum: Mi. 16 - 19 Uhr, Ebene 0, P1 Gruppe 6: Di. 08 - 10 Uhr, kl. Senatssaal, MZH 1380 Thomas Barkowsky Praktikum: Mi. 09 - 12 Uhr, Ebene 0, P2 Gruppe 7: Di. 08 - 10 Uhr, Senatssaal, MZH 1400 Thomas Sindt Praktikum: Do. 13 - 16 Uhr, Ebene 0, P1 Gruppe 8: Di. 08 - 10 Uhr, MZH 7210 Thorsten Scholz Praktikum: Do. 16 - 19 Uhr, Ebene 0, P1 Gruppe 9a: Mi. 13 - 15 Uhr, MZH 5300 Stefan Bisanz Praktikum: Fr. 13 - 16 Uhr, Ebene 0, P1 Gruppe 9b: Mi. 13 - 15 Uhr, NW1 HS2 Ulrich Hannemann Praktikum: Fr. 13 - 16 Uhr, Ebene 0, P5 Gruppe 10: Mi. 15 - 17 Uhr, Senatssaal, MZH 1400 Ulrich Hannemann Praktikum: Fr. 13 - 16 Uhr, Ebene 0, P2 Freq. Asked Questions Mi. 10 - 12 Uhr, Ebene 0, P5 Beginn der Veranstaltungen: Vorlesung: Mo., 21.10.02 Übungen: Mo., 28.10.02 Programmierpraktikum: Di., 22.10.02


Struktur der Veranstaltung

Die Veranstaltung wird 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 Übungen/Lektüre-Stunden wird der vertiefte Stoff in Gruppen eigenständig erarbeitet: Wir sind überzeugt, dass echtes Verständnis nur aus der selbständigen intensiven Beschäftigung mit der Materie entstehen kann. Daher wird im Rahmen der Übungen Fachliteratur erarbeitet und zusammen mit den Tutorinnen und Tutoren besprochen. In diesem Teil werden auch die Lösungsansätze für die Aufgaben besprochen, die von den Teilnehmern im Programmierpraktikum zu lösen sind.

  • Keine Theorie ohne Praxis: Im Programmierpraktikum werden die erarbeiteten Konzepte im Rahmen von Programmieraufgaben umgesetzt.

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
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. Um dabei auch die praktischen Aspekte zu berücksichtigen, findet diese Session im Raum P5, Ebene 0, statt.


Literatur

  • Zum Erlernen der Programmiersprache Java verfahren wir folgendermaßen:

  • Zu den Themen Algorithmen und Datenstrukturen wird im Wesentlichen folgendes Standardwerk verwendet: Aho, Hopcroft, Ullman: Data Structures and Algorithms. In deutscher Sprache ist das Buch Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen empfehlenswert.

  • Einige Grundlagen in Bezug auf Rechnerorganisation, -Architektur und Assembler-/Maschinensprachen werden auf Basis des Buches W. Oberschelp und G. Vossen: Rechneraufbau und Rechnerstrukturen. Oldenburg 1998 eingeführt.

  • 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

  • Eine Einführung in die Grundlagen der Benutzung des UNIX bzw. Linux Betriebssystems findet man in dem SuSE-Linux Handbuch im Kapitel 19. Interessant sind dabei insbesondere die Abschnitte 19.5 bis 19.9.

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


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: 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 ("fetch"-"execute") - Assembler und Maschinensprache - Speicheradresse versus Speicherinhalt, Speicherwort - Darstellung nicht-negativer ganzer Zahlen
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
Übungen - Lektüre: Wiederholung von Grundbegriffen aus der Logik und Mengenlehre - 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. Dazu auch der Lektüretext und die Literaturangabe.
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 ist, 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 - Spezifikationen, Precondition, Postcondition - 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 - Ein erster Sortier-Algorithmus: Quicksort.
Die Programmierbeispiele der ersten 2 Java-Vorlesungen sind in HelloWorldDoc.java zu finden.

Das Beispiel zur Einführung von Methoden ist VorlesungClass.java.

Das Progammskelett für binäre Suche und Quicksort: BinSearch3.java .

Zu den Charakteristika objekt-orientierter Sprachen: Stichworte .

Zur Erläuterung der unterschiedlichen Ansätze von objekt-orientierten und anderen Programmiersprachen gibt es die folgenden drei Beispielprogramme aus der Vorlesung vom 16. Dezember: Modular.java als Beispiel für einen "klassischen" (nicht objekt-orientierten) Ansatz und Oo.java als Beispiel für den objektorientierten Ansatz. Oo2.java illustriert den Zusammenhang zwischen Objekten und Abstrakten Datentypen.

Zu Methodenaufrufen und der Funktion des Laufzeitstacks sind hier einige ergänzende Skizzen.
Übungen - Lektüre: Vertiefung der Java Spracheinführung. - Implementierung kleiner Mengen mit Integer-Variablen und Bit-Operatoren. - Kommentar, Testen und Dokumentation. - ein Bild sagt mehr als viele Worte: Bubblesort .
Programmierpraktikum: Übersicht über die Basiswerkzeuge in einer Programmierumgebung (Shell, Editor, Compiler, Assembler, Linker, Loader, Interpreter, Debugger, Sourcebrowser, HTML-Browser).

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
(4) Das Referenzwerk zur Java Virtual Machine: T. Lindholm, F. Yellin: The Java Virtual Machine Specification, Second Edition, ist auch online verfügbar. (5) Ebenfalls zur JVM: B.Venners: Inside the Java 2 Virtual Machine. Hier stehen ebenfalls einige Kapitel online zur Verfügung.

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, Package-Konzept, Prinzip der Rekursion.
Übungen - Lektüre: Beschreibung der Syntax einfacher fiktiver Sprachen mit der Java Notation für Grammatiken, 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: Vorlesung: Sortieralgorithmen: Bubblesort ,( 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 komplexeres Paket zur Implementierung von Listen als Abstrakten Datentyp: ListHandler.java

Zur den hierbei verwendeten Abstraktionsfunktionen haben wir eine Zusammenfassung mit Anwendung erstellt: Abstraktionen
Ü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: 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 dieses 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.


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. Für die Bewertung der Programmieraufgaben haben wir unsere Grundzüge aufgeschrieben, ebenso wie Hinweise zum Kommentieren und Testen der Programme.
Serie 0 Als Test, ob Ihr LaTeX gut genug beherrscht, solltet Ihr versuchen diesen Beispielübungszettel ( postscript , pdf ) zu erstellen.
28. Oktober: Das erste zu bearbeitende Aufgabenblatt ( postscript , pdf ). Diese erste Serie ist in den Übungsgruppen vom 4. - 11. November abzugeben.
4. November: Das zweite Aufgabenblatt ( postscript , pdf ) enthält die ersten einfachen Programmieraufgaben. Diese Serie ist im Praktikum vom 19. - 22. November abzugeben.
Für die Aufgabenserie 2 soll es hinreichend sein, wenn pro Aufgabe jeweils 3 Sätze Testdaten verwendet werden:

  1. Maximalwertermittlung: 3 verschiedene Felder von Ganzzahlen mit jeweils 10 Einträgen. Schön wäre natürlich, wenn die enthaltenen Zahlen, sowohl negative und positive Zahlen sowie 0 enthalten. Weiterhin wäre ein Test mit einem Feld, welches 10 mal den gleichen Wert enthält, gut.
  2. Reihenentwicklung: 3 verschiedene Belegungen für ε (epsilon)
Die Eingabe der Testdaten erfolgt in dieser Serie hardcodiert, also indem die entsprechenden Quelltextzeilen adäquat ersetzt werden. Für die Testdokumentation soll jeweils die laut Aufgabenstellung geforderte Ausgabe hinreichend sein.
18. November: Das dritte Aufgabenblatt ( postscript , pdf ). Für die erste Aufgabe soll das folgende Programmskelett Sets.java verwendet werden.
2.Dezember: Das vierte Aufgabenblatt ( postscript , pdf ). Für die erste Aufgabe soll das folgende Programmskelett BinSearch3.java aus der Vorlesung verwendet werden. Achtung: Die erste Version enthielt einen Fehler, der mittlerweile korrigiert ist. Nachdem die Methode pushElement bereits in der Vorlesung diskutiert wurde, stellen wir diese auch in BinSearch3.java zur Verfügung. Bei den Methoden binsearch und quicksort sei darauf hingewiesen, daß diese jeweils auf dem gesamten Array operieren sollen, ungeachtet des Wertes von NumElems.

Aufgabe 1 a) soll dabei mit einer Java Methode implementiert werden, die ohne Rekursion zur Lösung kommt (etwa mit einer while-Schleife...).
16.Dezember: Das fünfte Aufgabenblatt ( postscript , pdf ). Für die erste Aufgabe kann entweder die eigene Lösung zu Serie 3, Aufgabe 2 verwendet werden (um eine "remove"-Operation ergänzt), oder die Methoden, die folgender Vorschlag zur Verfügung stellt: BitVector.java .
Ein Hinweis:
In diesem Vorschlag ist MAX_ELEM auf 232 gesetzt. Für die zweite Aufgabe dieser Serie muß dort natürlich 1000 stehen.

Achtung:
Die erste Fassung (Version 1.0) von BitVector.java enthielt einen Fehler, der in Version 1.1 korrigiert worden ist. Wir bedanken uns bei Jörg Meyer für seinen Hinweis.
13. Januar: Das sechste Aufgabenblatt ( postscript , pdf ). Dabei orientiert sich die Aufgabenstellung an dem in der Vorlesung besprochenen Programm zur Verwaltung mittels einfach verketteter Listen: ListHandler.java. Hinweis: Dieses Programm enthielt in der ersten Fassung einen Fehler. Außerdem haben wir die Vor- und Nachbedingungen vervollständigt. (22. Jan. 2002)

Zur ersten Aufgabe hat es einige Nachfragen gegeben, die Aufgabenstellung ist (teilweise) interpretationsfähig. Mit Durchlaufen der Liste (- von rechts nach links, bzw. - von links nach rechts) ist gemeint, daß jeweils auch eine Ausgabe der Listenelemente damit verbunden ist. Der Unterpunkt Ausgabe der Listenelemente entfällt somit, da bereits abgedeckt.

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