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

Praktische Informatik 2, SoSe 2009
 

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

Aktuelles

  • Die Fachgespräche finden in der Woche vom 13.07.09 statt.
  • Nicht bestandene Fachgespräche werden am 27. oder 28. August nachgeholt.
  • Studenten der Studiengänge Methematik (Dipl.) und Technomathematik (Dipl.) müssen spätestens am 3. Juli eine ausgefüllte Anmeldung zur Fachprüfung bei ihrem Tutor abgegeben haben.
  • Zum Fachgespräch bringen alle Studierenden den für ihren Studiengang vorgesehenen Leistungsnachweis (keinen Teilnahmeschein) mit. Der Schein muss ausgefüllt sein.
  • Auf Stud.IP findet ihr eine Umfrage zur Evaluation der Veranstaltung. Bitte nehmt an dieser Umfrage teil.

Inhalt dieser Seite

Termine

VAK: 03-05-G-700.02
 
Semester: SoSe 2009
 
Vorlesung: Mo., 13 - 15 Uhr, NW1 H1-H0020
ab 6.04.09.  

Die Tutorien werden in kleinen Übungsgruppen abgehalten und beginnen in der Woche vom 6.04.09.
Die Anmeldung für diese kann über Stud.IP vorgenommen werden.
Tutorien:
Tutorium 1 Mo. 17 - 19 Uhr, MZH 7220
(am 6.4.09 im MZH 1400) 		Daniel Möhlmann
Tutorium 2 Mo. 17 - 19 Uhr, MZH 1380 Denise Peters
Tutorium 3 Mo. 17 - 19 Uhr, MZH 4194 Karsten Hölscher
Tutorium 4 Di. 8 - 10 Uhr, GW1 B2130 Florian Lapschies
Tutorium 5 Di. 10 - 12 Uhr, MZH 7250 Stefan Haase
Tutorium 6 Di. 15 - 17 Uhr, MZH 4194 Denise Peters
Tutorium 7 Di. 15 - 17 Uhr, MZH 7220 Serge Fopoussi
Tutorium 8 Di. 17 - 19 Uhr, MZH 1380 Elena Vorobev
Tutorium 9 Mi. 10 - 12 Uhr, MZH 7260
(fällt am 13.05.09 aus.) 		Martin Stommel
Tutorium 10 Mi. 10 - 12 Uhr, MZH 7250 Karsten Hölscher
Tutorium 11 Mi. 10 - 12 Uhr, MZH 7220 Elena Vorobev

Struktur der Veranstaltung

Die Veranstaltung ist in zwei Bereiche gegliedert:
  • In der Vorlesung werden die Themenbereiche der Praktischen Informatik 2 im Detail präsentiert. Die Themenschwerpunkte sind
    • Objekt-orientierte Programmierung in Java
    • Algorithmen auf Bäumen und (allgemeiner) Graphen, sowie ausgesuchte Algorithmen aus den Bereichen Pattern Matching und weiteren Gebieten.
    Die detaillierten Vorlesungsinhalte findet man unten auf dieser Seite.

  • In den Tutorien werden Fragen zur Vorlesung erörtert und die Übungsaufgaben besprochen.

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: 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, diese wird durch einen oder mehrere Parameter n definiert, welche die Größe der Eingabedatenstruktur bzw. des algorithmisch zu untersuchenden Raums charakterisieren. 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 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]

Rechenregeln für Aufwandsfunktionen und zugehörige Ordnung:

  • Ist der Aufwand konstant, a(n) = c, so ist die Ordnung O(1)
  • Ist der Aufwand a(n) = b(n) + c, so ist die Ordnung O(b(n))
  • Ist der Aufwand a(n) = c*b(n), so ist die Ordnung O(b(n))
  • Ist der Aufwand polinomiell, a(n) = p_k*n**k + p_(k-1)*n**(k-1) + ... + p_1*n + p_0, so ist die Ordnung O(n**k)
  • Ist der Aufwand logarithmisch zur Basis k, a(n) = log_k (n), so ist die Ordnung O(log_m(n)) zu jeder beliebigen Basis m, man schreibt daher einfach O(log n).

Material zu Session 2:

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

Session 2: Exceptions in Java - Java-Bibliotheken

Vorlesung:

  • Motivation: Verwendung von Exceptions statt Nutzung von Fehlercodes in Rückgabewerten der Methoden: Wenn der Rückgabewert im Normalfall Nutzdaten an den Aufrufer zurück gibt, lässt sich der Fehlerwert ggf. nicht leicht von den Nutzdaten unterscheiden. (Beispiel: Ariane 5 Unglück)
  • Exceptions zur Prüfung von Preconditions
  • Ableitungen der Klasse Throwable - ausgelöste Exceptions als Instanzen von Exception oder einer anderen Ableitung von Throwable
  • Wichtige vordefinierte Ableitungen von Exception: RuntimeException, NullPointerException, IllegalArgumentException ...
  • Die Anweisungen try, catch und finally
  • Assertions im Programmcode: die assert-Anweisung zur Prüfung von Konsistenzbedingungen im Programmablauf.
    • Assertions werden angewendet, um die Korrektheit der internen Berechnungen - und nicht etwa die Korrektheit der Eingaben ! - zu prüfen. Sie werden typischerweise so eingesetzt, dass es sinnvoll ist, die Programmausführung abzubrechen, sobald eine Assertion fehlgeschlagen ist.
    • Assertions zur Prüfung von Klassen-Invarianten und von Postconditions
    • Syntax 'assert' Boolean-Expression [':' Hinweis-String]';'
    • Aktivierung der Ausnahmebehandlung mittels Schalter -ea ("Enable assertion"):
      'java -ea'[':'ClassName] ('-ea:'ClassName)* ClassName Args
  • Die Java-Klassenbibliothek
Material zu Session 2: Schiedermeier: Programmieren mit Java, Pearson Studium (2005): Kapitel 9
Programmbeispiel Exceptions und Assertions.

Session 3: Reflection

Vorlesung:

  • Attribut class und (äquivalent) Methode getClass() sind auf allen Objekten verfügbar und geben die Referenz auf ein ``Auskunftsobjekt'' vom Typ Class an.
  • Statische Methoden auf Class:
    • Class.forName(String) gibt ein Class-Objekt für die Klasse oder das Interface, die als String-Parameter an die Methode übergeben wurde, zurück.
  • Methoden auf Class-Instanzen c:
    • c.getName() gibt den Klassennamen der in der c beschriebenen Klasse zurück.
    • getMethods() gibt einen Methoden-Array zurück
    • newInstance() erzeugt eine neue Instanz der in c spezifizierten Klasse
  • Methoden auf Method:
    • getName()
    • getParameterTypes()
    • invoke()
  • Analoge Verfahren zum Analysieren von Attributen
  • Analoge Verfahren zum Analysieren und Verwenden von Konstruktoren
  • Package java.lang.reflect
  • Beispielprogramm Java und Reflection.
Literatur zu Session 3: Link zur Dokumentation von java.lang.reflect

Session 4: Bäume und Graphen

Vorlesung:

  • Definition ungerichteter Graph
  • 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 - siehe Beispielprogramm unten (bintree0.tgz)
  • 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) - generischer Algorithmus
  • Anwendung DFS auf die Kantenklassifikation (Backward Edges, Forward Edges, Cross Edges) und Test auf Zyklenfreiheit
  • Algorithmus von Tarjan (ebenfalls eine DFS-Anwendung) zur Bestimmung starker Zusammenhangskomponenten in gerichteten Graphen (siehe auch Algorithmus von Tarjan aus Wikipedia
    • Definition starke Zusammenhangskomponente (Strongly Connected Component (SCC): Maximaler Teilgraph eines gerichteten Graphen, so dass je zwei Knoten des Teilgraphs durch einen ganz im Teilgraph enthaltenen Graphen verbunden sind.
    • Sonderfall triviale SCC: Teilgraph, der aus einem einzigen Endknoten des Ausgangsgraphen besteht, der keine ausgehenden Kanten besitzt.
  • Definition von Bäumen
  • 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.
    Achtung: In der Vorlesung wurde bereits darauf hingewiesen, dass ein Absatz dieses Textes irreführende Schreibfehler enthält: Im letzten Absatz auf Seite 1 (vor Lemma 1) muss es heissen:

    "The reasoning above leads to the following method: Start with an automaton A without unreachable states. If A has undistinguishable states p; q, combine them into one state. (For instance, remove q and reroute all transitions into q to go into p instead.) Repeat this process until no more undistinguishable states can be found. At this point we will not be able to reduce A further. But does it necessarily mean that A is minimum? Conceivably, there could be a completely different automaton B, with a completely different topology but with fewer states, that accepts the same language as A. Quite remarkably, it turns out that this is impossible, namely, any automaton whose all states are pairwise distinguishable must be minimum."

    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:

    Hinweis: In dieser Beispielimplementierung werden die unterscheidbaren Zustände in der symmetrischen Matrix dis[p][q] mit true markiert. Zu gegebenem Repräsentantenzustand p ist die Äquivalenzklasse von p NICHT unterscheidbarer Zustände damit durch [p] = { q | dis[p][q] == false } gegeben.
Literatur zu Session 4: Gunter Saake, Kai-Uwe Sattler: Algorithmen und Datenstrukturen. dpunkt 2004, Kapitel 14 und 16

Beispielprogramm zu binären Bämen: bintree0.tgz Dazu 2 graphViz(dot)-Bilder welche einen Binärbaum vor dem Löschen und nach dem Löschen des Elementes shvckyhj8ssdkshv zeigen.

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: Multi-Threading und Synchronisation

Vorlesung:

  • Prozesse mit separatem Adressraum versus Threads im gemeinsamen Adressraum
  • Nebenläufigkeit, Quasiparallelität und echte Parallelität im Multicore-/Multi CPU System
  • Probleme, die durch Nebenläufigkeit entstehen können: Racing Conditions
  • Die Thread Klasse
    • Zu überschreibende Methode run()
    • Methode start()
    • Methode yield()
    • Methode sleep()
    • Methode join()
  • Atomare Operationen auf Maschinenworten
  • Synchronisierte Methoden (Schlüsselwort synchronized): Durchführung erfolgt in Gegenwart einer Objektsperre. Für andere Threads heisst das, dass alle synchronized Methoden eines Objektes für sie gesperrt sind, wenn der Thread t1 eine synchronized Methode ausführt.
  • Die wait, notify, notifyAll Methoden. Hierzu ein Beispiel: MyThread.java - 2 Threads greifen auf einen Stack mit beschränkter Kapazität zu und wecken sich gegenseitig mittels Notification.
Literatur zu Session 6: Gosling, Java Language Specification, Chapters 14, 17; Java Bibliothek, Klasse Thread

Übungszettel

In diesem Abschnitt findet Ihr die Aufgabenblätter und gegebenenfalls Zusatzinformationen zum Herunterladen und Ausdrucken. Die Lösungen sollen mit LaTeX unter Verwendung der Dokumentenklasse pi2.cls erstellt werden und jeweils Montags vor der Vorlesung abgegeben werden. Zusätzlich erfolgt die Quellcodeabgabe im Repository im jeweiligen Unterverzeichnis tutoriumXX/gruppeYY/uebungZZ.

Kriterien für den Erwerb eines Leistungsnachweises

Die Kriterien sind dieselben wie bei PI1 im WS 2008/2009: Es werden wöchentlich Übungszettel ausgegeben, die jeweils in Gruppen zu dritt bearbeitet werden. Die Vornote ergibt sich aus der Prozentzahl der erfolgreichen Bearbeitung, gemittelt über alle Übungsblätter:

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

Jede Gruppe muss mindestens einmal im Semester eine Aufgabe im Tutorium vorführen.

Aus den Übungszetteln ergibt sich die Vornote für das Fachgespräch am Ende des Semesters, falls die erreichte Note mindestens 4,0 ist. Hier wird die Einzelleistung der Gruppenmitglieder überprüft und bewertet.

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