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

Praktische Informatik 2, SoSe 2007
 

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

Aktuelles

  • Bringt bitte zu den Fachgesprächen die dazu nötigen Formulare mit:
    • Im Studiengang Informatik (Diplom) einen Studienbegleitenden Leistungsnachweis (SBLN) der wie folgt ausgefüllt ist und zudem Euren Namen und Eure Matrikelnummer enthält: Vorlage I.
    • Für Studierende aller anderen Studiengänge ebenso ein SBLN wie oben mit passend ersetztem Studiengang: Vorlage II
    • Studierende im Studiengang Systems Engineering brauchen nichts mitzubringen, die entsprechenden SBLNe erhalten die Veranstalter vom zuständigen Prüfungsamt.
    • Studierende in den Studiengängen Mathematik(Diplom) oder Technomathematik(Diplom) geben bitte bis spätestens zum Fachgespräch ihr Anmeldeformular zur Fachprüfung im Nebenfach Informatik beim jeweiligen Tutor ab. Zum Fachgespräch selbst ist der ausgefüllte SLBN Vorlage II mitzubringen.
    • Studierende anderer Studiengänge klären bitte mit ihrem Prüfungsamt, welche Formulare nötig sind. Im Zweifelsfall ist auch in diesem Fall ein SBLN des FB3 mitzubringen Vorlage.
    Die Prüfungsordnung bestimmt im Übrigen, das die Kandidaten sich ggf. durch Vorlage eines Identitätsnachweis mit Lichtbild ausweisen müssen.
  • Die Fachgespäche werden in der Woche 23. - 27. Juli stattfinden. Terminvereinbarungen werden i.A. mit den Tutoren getroffen.
  • Fachgespräche bei Jan Peleska finden am 23. Juli statt, dazu bitte Anmeldung per e-mail.
  • Die Wiederholungsprüfungen finden am Montag, dem 24. September statt, bitte auch hier Terminabsprache direkt mit Jan Peleska per mail.

Inhalt dieser Seite

Termine
VAK: 03-05-G-700.02
 
Semester: SoSe 2007
 
Vorlesung: Mo., 13 - 15 Uhr, NW1 H2 (W0020), ab 16.4.2007
 

Die Tutorien werden in kleinen Übungsgruppen abgehalten. Die Eintragung in die Gruppen findet am 16.04. statt. Bitte sorgt für eine gleichmässige Auslastung der Gruppen.
Tutorien:
Gruppe 1 Mo. 17 - 19 Uhr, MZH 7220 Ulrich Hannemann
Gruppe 2 Mo. 17 - 19 Uhr, MZH 7230 Jasper van de Ven
Gruppe 3 Mo. 17 - 19 Uhr, MZH 1380 (kl. Senatssaal) Philipp Steiner
Gruppe 4 Di. 8 - 10 Uhr, MZH 4194 Arne Schuldt
Gruppe 5 Di. 8 - 10 Uhr, MZH 7210 Sven Werner
Gruppe 6 Di. 13 - 15 Uhr, MZH 7220 Chen Qizhi
Gruppe 7 Mi. 10 - 12 Uhr, MZH 7220 Nikola Kalchev
Gruppe 8 Do. 8 - 10 Uhr, MZH 7260 Raimar Falke
Gruppe 9 Do. 10 - 12 Uhr, MZH 1380 (kl. Senatssaal) Achim Mahnke

Struktur der Veranstaltung

Die Veranstaltung ist 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 Tutorien 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 zu lösen sind.

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: Objektorientierung und Java

Vorlesung: Die wichtigsten Stichworte und Fakten zum Thema Objekt-orientierte Programmiersprachen und Objektorientierung in Java.

Material zu Session 1: Beispiel 1 zum o.g. Text: Vererbung mit Redefinition. Beispiel 2: Erzwingung von Sortenreinheit (a) ohne Generics (class MyNotSoGenericStack), (b) mit Generics (class MyReallyGenericStack), (c) mit generischem Stack, der auf unbeschränkter generische Liste aufsetzt (class MyReallyGenericUnboudedStack).

Literatur zu Session 1: Schiedermeier: Programmieren mit Java, Pearson Studium (2005): Abschnitt 4.7, Kapitel 8, Kapitel 12

Session 2: Komplexität von Algorithmen

Vorlesung: Komplexität von Algorithmen: Benötigter Aufwand in Bezug auf (a) Speicherplatz und (b) Laufzeit. Der Aufwand hängt von der sog. Problemgröße ab, dies sind ein oder mehrere Parameter n, welche die Größe der Eingabedaten bzw. des algorithmisch zu untersuchenden Raums charaktersieren. Weiterhin hängt der Aufwand häufig von der Beschaffentheit der Daten (z.B. statistische Verteilung der Eingabewerte) ab. Interessant ist dabei der n-abhängige Aufwand (a) für den besten Fall - d.h. optimale Werteverteilung -, (b) den schlechtesten Fall (besonders häufig interessiert die Worst Case Execution Time (WCET)), und (c) im statistischen Mittel der Eingabewerteverteilung.

Für die zeitliche Aufwandsbestimmung wird die Anzahl der der in Abhängigkeit von der Problemgröße auszuführenden Anweisungen zugrunde gelegt.

O-Notation für den asymptotischen Aufwand eines Algorithmus: Der vom Algorithmus benötigte Aufwand a(n) ist von der Ordnung O(g(n)), wenn eine Konstante c existiert, so dass ab einem gewissen n0 für alle größeren n immer a(n) <= c*g(n) gilt.

Komplexitätsklassen O(1) [konstant], O(log n) [logarithmisch], O(n) [linear], O(n*log n), O(n**k) [ploynomial], O(2**n) [exponentiell]

Material zu Session 2:

Literatur zu Session 2: Gunter Saake, Kai-Uwe Sattler: Algorithmen und Datenstrukturen. dpunkt 2004, Abschnitt 7.3

Session 3: Algorithmen für die Syntaxprüfung

Vorlesung: Einfache deterministische EBNF-Grammatiken mit Hilfe (in der Regel wechselseitig rekursiver) Java-Methoden prüfen. Die Operatoren der EBNF-Syntax geben Hinweise darauf, wie der Syntaxchecker zu strukturieren ist:

  • Neues nicht-terminales Symbol T : (ggf rekursiver) Aufruf einer Methode checkT(), welche die mit T verbundenen Syntaxregeln prueft.
  • |-Operator: Switch-Statement über die Anfangssymbole einer jeden |-Alternative.
  • Sequenz über terminale Symbole t1,t2,t3,...: Konjunktion
    getNextToken() == t1 &&
    getNextToken() == t2 &&
    ...
  • Optionales terminales Symbol [t]:
    tok = getNextToken();
    if ( tok == t )
    tok = getNextToken();
    // ... jetzt weiter mit check von tok
  • Wiederholung {t}:
    while ( (tok = getNextToken()) == t );
    // ... jetzt weiter mit check von tok
Für dieses besonders einfache Verfahren müssen nicht-deterministische Grammatiken zuerst in deterministische Form gebracht werden.

Material zu Session 3: Java Syntaxchecker für eine einfache Grammatik Simplesyncheck.java

Session 4: Bäume und Graphen

Vorlesung:

  • Definition ungerichteter Graph
  • Definition gerichteter Graph
  • Graphrepräsentation mit Adjazenzliste
  • Graphrepräsentation mit Adjazenzmatrix
  • Gerichtete, markierte Graphen als Transitionssysteme (Definition siehe unten) - Interpretation von Transitionssystemen
  • Breitensuche in Graphen (Breadth-First Search BFS)
  • Tiefensuche in Graphen (Depth-First Search DFS) und Test auf Zyklenfreiheit
  • Topologisches Sortieren: Definition Halbordnung - Bestimmung der Sortierreihenfolge mit Hilfe von DFS
  • Definition von Bäumen
  • Binäre Bäume: Elternknoten, Kindknoten, Blätter - Höhe - Kanonische Datenstrukturen in Java - Einfügen, Suchen, Löschen auf binären Bäumen - Inorder/Preorder/Postorder/Levelorder-Traversierung von binären Bäumen - entartete binäre Bäume; die Notwendigkeit zur Balancierung
  • Eine kurze Zusammenfassung zu den AVL - Bäumen
  • Minimierung endlicher deterministischer Automaten (DFA): Siehe Erläuterungen dazu im Manuskript von Marek Chrobak: Minimization of Finite Automata. Eine einfache Java-Implementierung findet man unter Dfa.java. Der dabei behandelte Ursprungsautomat und der aus dem Minimierungsalgorithmus resultierende Automat sind hier als dot-Bilder dargestellt:
Literatur zu Session 4: Gunter Saake, Kai-Uwe Sattler: Algorithmen und Datenstrukturen. dpunkt 2004, Kapitel 14 und 16

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

  • S ist eine endliche Menge, deren Elemente Zuständen von LTS genannt werden.
  • s0 ist eine Element von S, der der Anfangszustand von LTS genannt wird.
  • A ist eine endliche Menge, genannt das Alphabet von LTS. 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:
  • 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 = s0
  • Für alle i = 0,1,2,... gilt: (zi,ai,zi+1) ist eine Transition aus T.

Session 5: Suchen in Texten

Vorlesung:

  • Problemstellung: Suche des Musters (Pattern) pat[0..m] im Text text[0..n]. Laufzeitkomplexität des naiven Suchalgorithmus ist O(n*m)
  • Der Boyer-Moore Algorithmus mit günstigster Laufzeitkomplexität O(n/m)
Literatur zu Session 5: Gunter Saake, Kai-Uwe Sattler: Algorithmen und Datenstrukturen. dpunkt 2004, Kapitel 17, insbesondere Abschnitt 17.3

Session 6: Refelection

Vorlesung:

  • Attribut class und (äquivalent) Methode getClass() sind auf allen Objekten verfügbar und geben die Referenz auf ein ``Auskunftsobjekt'' vom Typ Class an.
  • Methoden auf Class bzw. Class-Instanzen:
    • getName()
    • getMethods()
  • Methoden auf Method:
    • getName()
    • getParameterTypes()
    • invoke()
  • Beispielprogramm Java und Reflection.
Literatur zu Session 6: Link zur Dokumentation von java.lang.reflect

Übungszettel

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. Dazu gibt es die Dokumentenklasse und ein Beispiel für die Erstellung der Lösungsvorschläge mit LaTeX/pdfLaTeX. Für manche Installationen (z.B. MikTeX) werden auch noch fancyhdr.sty und moreverb.sty benötigt. Diese kann man aber auch über das Setup-Programm nachinstallieren (empfohlen)

Für die Bewertung der Programmieraufgaben haben wir unsere Grundzüge aufgeschrieben, ebenso wie Hinweise zum Kommentieren und Testen der Programme.

Die mit Latex gesetzten Übunszettel werden ausgedruckt und montags nach der Vorlesung abgegeben. Quellcode müsst außerdem per Email an eure Praktikumsleiter schicken.

Übungszettel Zusatzmaterial Ausgabe Abgabe
Übungsblatt 1a 16. 04.2007 Abgabe am 30.04.2007
Übungsblatt 1b 23. 04.2007 Abgabe am 30.04.2007
Übungsblatt 2 30. 04.2007 Abgabe am 7.05.2007
Übungsblatt 3 7. 05.2007 Abgabe am 14.05.2007
Übungsblatt 4 14. 05.2007 Abgabe am 21.05.2007
Übungsblatt 5 21. 05.2007 Abgabe am 4.06.2007
Übungsblatt 6 4. 06.2007 Abgabe am 11.06.2007
Übungsblatt 7 11.06.2007 Abgabe am 18.06.2007
Übungsblatt 8 18.06.2007 Abgabe am 25.06.2007
Übungsblatt 9 (regulär) 25.06.2007 Abgabe am 2.07.2007
Übungsblatt 9 (Extrablatt, optional) 25.06.2007 Abgabe am 09.07.2007
Übungsblatt 10 2.07.2007 Abgabe am 09.07.2007

  • Zur Serie 5 eine Hilfe: Das Einlesen von Daten aus einem File kann in wenigen Zeilen wie im folgenden Beispiel Einlesen.java erfolgen.

    Syntaxchecker für die polnische Notation der Serie 3 PNSyntaxCheck.java

  • Auch zur Serie 6 eine Ergänzung: Mit den Codefragmenten aus Input.java können ausgewählte Konsoleneingaben verarbeitet werden und so das Verhalten im Transitionssystem der Aufgabenstellung beeinflussen. Die Datei Input.java ist alleine nicht funktionsfähig.
  • Eine Lösung für die abstrakte Modellierung von Transitionssystemen aus Serie 6: Zustand.java, Transition.java, Markierung.java und TransitionsSystem.java.
  • Eine bewertete Adjazenzmatrix als Datenbasis für die reguläre Serie 9: Verbindungsgraph.java

Kriterien für den Erwerb eines Leistungsnachweises

Die Kriterien für den Erwerb eines Leistungsnachweises wurden in der ersten Vorlesung verhandelt.

Aus den 10 Übungszetteln ergibt sich die Vornote für das Fachgespräch am Ende des Semesters.

Ab 95%: 1,0
Ab 90%: 1,3
Ab 85%: 1,7
Ab 80%: 2,0
Ab 75%: 2,3
Ab 70%: 2,7
Ab 65%: 3,0
Ab 60%: 3,3
Ab 55%: 3,7
Ab 50%: 4,0
Unter 50%: nicht bestanden

Ein Übungsblatt kann durch den Zusatzzettel (Serie 9 optional) ersetzt werden.

Literatur

An dieser Stelle findet sich eine kleine Auswahl an Literatur zur Vorlesung. 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 angegeben.

Literatur zu Java

  • 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 guten Einstieg bietet das Handbuch Java 2 , Grundlagen und Einführung geeignet, welches beim Zentrum für Netze erhältlich ist.
  • Die Java-Klassenbibliothek zum Nachschlagen
  • Java-Buch das auch 1.5 behandelt: Programmieren mit Java von Reinhard Schiedermeier, Pearson Studium

Online-Literatur zur Java

Algorithmen und Datenstrukturen

  • Zu den Themen Algorithmen und Datenstrukturen wird im Wesentlichen folgendes Buch verwendet:
    Gunter Saake, Kai-Uwe Sattler: Algorithmen und Datenstrukturen. dpunkt 2004

Rechnerorganisation und -architektur

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

Latex

  • 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

Linux und Unix

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

Nachschlagewerke

Allgemeine Fachbegriffe und auch spezielle Begriffe der Informatik werden häufig sehr gut in den im WWW verfügbaren Nachschlagewerken erklärt.

Online-Wörterbuch Deutsch-Englisch

Ein sehr gutes Wörterbuch für Übersetzungen Deutsch-Englisch wird von der TU-Chemnitz zur Verfügung gestellt: http://dict.tu-chemnitz.de

Java, Emacs und LaTeX für zu Hause

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:

Eine Einführung in die Installation von Latex unter Windows findet ihr hier (Miktex-Webseite) und hier (bebildertes pdf-Dokument).

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