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

Praktische Informatik 2, SoSe 2005
 

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

Aktuelles

  • Zettel 7 wurde samt Hintergrundmaterial modifiziert, da es bei der Aufgabenstellung zu Missverständnissen kam.
  • Die Musterlösung von Blatt 4 wurde korrigiert.
  • Die Musterlösung von Blatt 1 wurde auf Anregung hin nochmal modifieziert.
  • Das Tutorium von Tom Wetjen findet ab sofort im Raum MZH 7210 statt.
  • Das neue Tutorium wird von Dienstag auf Mittwoch verschoben. Gleiche Zeit, anderer Ort ( SpT C4180)!
  • Aufgrund der überfüllten Tutorien, gibt es nun ein Tutorium 9, immer dienstags von 8-10 im Raum MZH 5210. Wir weisen schon mal darauf hin, dass die Tutoriengröße auf maximal 9-10 Gruppen festgelegt ist und ihr notfalls auch zwangsweise umgesiedelt werden. Aufgrund von Korrekturen und Fachgesprächen ist das notwendig, damit einzelne Tutoren nicht überlastet werden!
  • Achtung: Raumänderung! Tutorium 3 findet jetzt immer im GW1-HS 1010 statt!
  • Die Eintragung in die Tutorien findet am Montag, 11.4.2005 von 9-12 Uhr vor dem Hörsaal NW1 HS1 statt.

Inhalt dieser Seite

MZH HS Termine

VAK: 03-700.02
 
Semester: SoSe 2005
 
Vorlesung: Mo, 10:00 - 12:00, NW1 H1 (H0020), ab 11.4.2005 (inkl. Tutoriumsbetrieb)
 

Tutorien:
Gruppe 1 Mo. 13-15 Uhr, MZH 7220
Gruppe 2 Mo. 13-15 Uhr, MZH 7210
Gruppe 3 Mo. 13-15 Uhr, GW1-HS 1010
Gruppe 4 Di. 8-10 Uhr, MZH 6240
Gruppe 5 Mi. 10-12 Uhr, MZH 7220
Gruppe 6 Do. 10-12 Uhr, MZH 7220
Gruppe 7 Do. 10-12 Uhr, MZH 7250
Gruppe 8 Do. 10-12 Uhr, MZH 7260
Gruppe 9 Mi. 8-10 Uhr, SpT C4180

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 (= Ü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.

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

Vorlesung:

  • Grundbegriff der Asymptotischen Komplexität - O-Notation
  • Bestimmung der Komplexität von eigenen Programmen
  • Komplexitätsklassen
  • Beweis: konstante Faktoren sind unerheblich
  • Beweis: der größte Summand dominiert
  • mittlere Komlexität basierend auf Gleichverteilung, Wahrscheinlichkeitsanalyse

Übungen - Lektüre:

  • Bestimmung der Komplexität bei
    • einfachen Anweisungen
    • Sequenzen
    • Schleifen
    • Verzweigungen

Material zu Session 1:

Literatur zu Session 1:

  • Saake, Sattler: Kap. 7.3.2-7.3.4
  • Aho, Hopcroft, Ullman: Kap. 1.5
  • Schöning: Kap. 1.7

Session 2: Hashtables

Vorlesung:

  • Schlüssel, Hashfunktion, Hashwert
  • Auswahl einer guten Hashfunktion, z.B. für Zeichenketten
  • Kollisionen
  • Kollisionsbehandlung: Sondieren und Verkettung

Übungen - Lektüre:

  • Offenes Hashing mit Sondierfunktionen
  • Hashing in Java

Material zu Session 2:

  • Beispiel Hashing mit Verkettung aus der Vorlesung vom 18.4.2005: MyHashS.java

Literatur zu Session 2:

  • Saake, Sattler: Kap. 15
  • Aho, Hopcroft, Ullman: Kap. 4.7 und 4.8
  • Schöning: Kap. 3

Session 3: Bäume

Vorlesung:

  • Gerichteter Graph: Kanten, Knoten, Pfad
  • Baum als Sonderfall eines Graphen:
    • Wurzel
    • Blatt
    • innerer Knoten
    • Höhe eines Baums
    • Niveau eines Knotens im Baum
  • n-äre Bäume, Sonderfall binärer Baum
  • Suchbäume (geordneter Baum)
  • Durchlaufen von Bäumen: Inorder, Preorder, Postorder, Levelorder
  • Einfügen und Löschen in Bäumen
  • Balancierte Bäume: AVL-Bäume

Übungen - Lektüre:

  • Huffman-Kodierung auf Basis binärer Bäume
  • Einlesen von Dateien mit Java
  • Erstes Beispiel von Exceptions: IOException
  • Java-Klasse Vector, Verwendung von Vector als List in Collections (Sortieren)
  • Java-Interface Compareable mit Methode compareTo()
  • Heapsort
  • Binäre Bäume zur Darstellung von Termen in Polnischer Notation
  • Einfügen und Löschen in AVL-Bämen
  • Tries als Beispiel von Digitalen Bämen

Material zu Session 3:

Literatur zu Session 3:

  • Saake, Sattler: Kap. 14
  • Aho, Hopcroft, Ullman: 3
  • Schöning: Kap. 8.1

Session 4: Graphen

Vorlesung:

  • Kanten und Knoten
  • Graph mit:
    • gerichteten/ungerichteten Kanten
    • gewichteten/ungewichteten Kanten
  • Adjazenz
  • Sonderfall: Labelled Transition System
  • Graphrepräsentation als:
    • Kantenliste
    • Knotenliste
    • Adjazenzmatrix
    • Adjazenzliste
  • Breitensuche
  • Tiefensuche
  • Minimierung und Äquivalenz von endlichen, deterministischen Automaten

Übungen - Lektüre:

  • Implementierung von Transitionssystemen als Graph
  • Dijstra's Algorithmus zur Bestimmung der kürzesten Wege

Material zu Session 4:

Literatur zu Session 4:

  • Saake, Sattler: Kap. 16
  • Aho, Hopcroft, Ullman: 6,7
  • Schöning: Kap. 6

Session 5: Java: Exceptions und Reflection

Vorlesung:

  • Excpetions in Java:
    • throw
    • throwstry-catch
  • Das reflect--Paket:
    • Class
    • Field
    • Method
    • Constructor
    • Modifier

Übungen - Lektüre:

  • Erforschung des Marsianers

Material zu Session 5:

Literatur zu Session 5:

  • Saake, Sattler: Kap. 12.5

Session 6: Textsuche

Vorlesung:

  • Brute-Force Ansatz
  • Algorithmus von Knuth/Morris/Pratt

Übungen - Lektüre:

  • Algorithmus von Boyer/Moore

Material zu Session 6:

Literatur zu Session 6:

  • Saake, Sattler: Kap. 17
  • Schöning: Kap. 12

Session 7: Graphik

Vorlesung:

  • Nicht für das Fachgespräch relevant!

Material zu Session 7:

Literatur zu Session 7:

Ü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 Übungszettel werden ausgedruckt und montags nach der Vorlesung abgegeben. Quellcode müsst ausserdem per Email an eure Praktikumsleiter schicken.

Kriterien für den Erwerb eines Leistungsnachweises

Die Kriterien für den Erwerb eines Leistungsnachweises werden in der ersten Vorlesung verhandelt. Der Vorschlag der Lehrveranstalter sieht folgendermaßen aus:

Ein Übungszettel gilt als erfolgreich bearbeitet, wenn er zu mindestens 40% gelöst wurde. Es darf nur maximal ein Übungzettel nicht bestanden werden. Bei der Benotung wird der Übungszettel mit der schlechtesten Bewertung nicht berücksichtigt, wobei dies auch ein nicht bestandener Zettel sein kann. Die Note ergibt sich aus der Durchschnittsprozentzahl der erfolgreichen Bearbeitung der restlichen Ü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% oder bei mehr als einem nicht bestandenen Übungszettel: nicht bestanden

Aus den Übungszetteln ergibt sich die Vornote für das Fachgespräch am Ende des Semesters. Hier wird die Einzelleistung der Gruppenmitglieder überprüft und bewertet.

Alle Fachgespräche werden vom jeweiligen Tutor durchgeführt. Wiederholungsprüfungen werden bei Jan Peleska abgelegt.

Zur Prüfung muss der ausgefüllte Schein (gibt's in der 7. Ebene oder hier als Vordruck zum Ausdrucken) mitgebracht werden:

  • Informatik Diplom: Vordruck
  • Informatik Bachelor: Vordruck
  • Digitale Medien: Vordruck
  • Technomathematik: Vordruck
  • Systems Engineering: Scheine liegen bereits vor, nichts mehr mitbringen
  • Andere: eigene Scheine mitbringen oder Informatik-Scheine benutzen (Vordruck) und im eigenen Prüfungsamt anerkennen lassen
Wer im Bachelor-Studiengang ist, muss Diplom einfach durchstreichen. Es gibt bis jetzt keine gesonderten Scheine.

Die Prüfungen finden in der ersten Woche nach Vorlesungsende (11.-15.7.2005) statt. Die Termine für die einzelnen Gruppen werden direkt mit dem Tutor abgesprochen.

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

Zum Erlernen der Programmiersprache Java verfahren wir folgendermaßen:
  • 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. In den Tutorien werden in der ersten Woche Sammelbestellungen aufgenommen.
  • 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
  • Auch sehr gut:
    Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: Data Structures and Algorithms. Addison-Wesley 1987
  • Etwas tiefergehend:
    Uwe Schöning: Algorithmik. Spektrum 2001

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