Praktische Informatik 1, WiSe 2006/07

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 Sudienbegleitenden Leistungsnachweis (SBLN) der wie folgt ausgefüllt ist Vorlage und zudem Euren Namen und Eure Matrikelnummer enthält.
  • Für die Studiengänge Informatik (Bachelor) oder Digitale Medien (Bachelor) ebenso ein SBLN wie oben mit passend ersetztem Studiengang: Vorlage
  • 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 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 Fachgespräche zur Veranstaltung finden ab dem 12. Februar statt. Die Fachgespräche werden vom jeweiligen Tutor im Beisein des Praktikumsbetreuers durchgeführt, Terminvereinbarungen werden mit dem Tutor direkt getroffen. Alternativ ist es möglich, als Gruppe das Fachgespräch mit Jan Peleska am Montag, dem 12. Februar abzuhalten, hier bitte auch Terminabsprache per mail.
• Die Wiederholungsprüfungen finden am Freitag, dem 30. März statt, bitte auch hier Terminabsprache direkt mit Jan Peleska per mail.

Inhalt dieser Seite

• Termine
• Struktur der Veranstaltung
• Veranstaltungsinhalte
• Übungszettel
• Leistungsnachweise
• Literatur
• Java, Emacs und LaTeX für zu Hause

Termine

Tutorien und Praktika werden in kleinen Übungsgruppen abgehalten. Die Eintragung in die Gruppen findet während der Einführungswoche statt. Bitte sorgt für eine gleichmässige Auslastung der Gruppen. Praktika und Tutorien beginnen ab dem 30.10.2006.

Tutorien/Praktika:
Gruppe 1	Tutorium: Praktikum:	Mo. 15-17 Uhr, MZH 7230 Di. 13 - 16 Uhr, MZH 0210/0220 (P2)	Inessa Seifert
Gruppe 2	Tutorium: Praktikum	Mo. 15-17 Uhr, MZH 7220 Di 13 - 16 Uhr, MZH 0230/0240 (P5)	Achim Mahnke
Gruppe 3	Tutorium: Praktikum: primär für Mathematik/Technomathematik	Mo. 17-19 Uhr, MZH 8090 Di 16 - 19 Uhr, MZH 0210/0220 (P2)	Ulrich Hannemann
Gruppe 4	Tutorium: Praktikum: primär für Digitale Medien	Mo. 17-19 Uhr, MZH 7260 Mi 16 - 19 Uhr, MZH 0210/0220 (P2)	Inessa Seifert
Gruppe 5	Tutorium: Praktikum:	Di. 8-10 Uhr, MZH 7250 Mi 13 - 16 Uhr, MZH 0210/0220 (P2)	Shi Hui
Gruppe 6	Tutorium: Praktikum:	Di. 8-10 Uhr, MZH 7230 Mi 13 - 16 Uhr, MZH 0230/0240 (P5)	Arne Schuldt
Gruppe 7	Tutorium: Praktikum:	Di. 8-10 Uhr, MZH 1380 (kl. Senatssaal) Do 9 - 12 Uhr, MZH 0210/0220 (P2)	Raimar Falke
Gruppe 8	Tutorium: Praktikum: primär für Systems Engineering	Mi. 13-15 Uhr, IW3 0210 Fr 13 - 16 Uhr, MZH 0210/0220 (P2)	Achim Mahnke
Gruppe 9	Tutorium: Praktikum: primär für Mathematik/Technomathematik	Mi. 17-19 Uhr, MZH 7210 Do. 13 - 16 Uhr, MZH 0210/0220 (P2)	Lutz Frommberger
Gruppe 10	Tutorium: Praktikum: primär für Digitale Medien	Mi. 17-19 Uhr, MZH 7220 Do 13 - 16 Uhr, MZH 0230/0240 (P5)	Chen Qizhi
Gruppe 11	Tutorium: Praktikum:: primär für Systems Engineering	Mi 17-19 Uhr, MZH 7230 Fr. 13 - 16 Uhr, MZH 0230/0240 (P5)	Christof Efkemann

Struktur der Veranstaltung

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

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

Veranstaltungsinhalte

Session 1: Grundlagen aus der technischen Informatik

• Begriffe: von-Neumann'sche Rechnerorganisation und 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
• Der Begriff des Algorithmus: terminierender Algorithmus - deterministischer Ablauf eines Algorithmus - determiniertes Ergebnis eines Algorithmus
• 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
• Compiler und Interpreter
• Java Compiler, Java Virtual Machine, Java Laufzeitumgebung

Übungen - Lektüre:

• Wiederholung von Grundbegriffen aus der Logik
• Funktionen und Relationen
• binäre Darstellung positiver ganzer Zahlen
• Beispiele zur Umsetzung einer fiktiven Assemblersprache in Maschinencode
• Beispiele zur Umsetzung von Pseudocode in eine fiktive Assemblersprache

Programmierpraktikum:

• Textverarbeitung in LaTeX
• Emacs im LaTeX Mode
• pdflatex und Acrobat Reader - xdvi - ghostview
• LaTeX-Templates für die Abfassung von Übungsaufgaben

Material zu Session 1:

• Folie zur von Neumannschen Rechnerarchitektur aus der Vorlesung vom 30.10.2006: pdf
• Folie zum Aufbau des Speichers aus der Vorlesung vom 30.10.2006: pdf
• Folie zum Aufbau einer CPU aus der Vorlesung vom 30.10.2006: pdf
• Folie zum I/O aus der Vorlesung vom 30.10.2006: pdf
• Hintergrund: Mikroinstruktionen und Pseudoassembler: pdf
• Hintergrund: Unix- und Latexgrundlagen: pdf

Literatur zu Session 1:

• Oberschelp und G. Vossen: Rechneraufbau und Rechnerstrukturen, Kapitel 8
• Gunter Saake, Kai-Uwe Sattler: Algorithmen und Datenstrukturen, Abschnitt 2.1

Session 2: Erste Schritte in Java

Vorlesung:

• Grundstruktur eines Java-Programms - die main-Methode
• Kommentare
• Deklaration lokaler Variablen: die Basisdatentypen int, long, float, double, boolean,
• Deklaration lokaler Variablen: Arrays von Basisdatentypen, Strings
• Ausdrücke (expressions) und Anweisungen (commands)
• Zuweisungen
• Operatoren auf Basisdatentypen
• Kontrollstrukturen:
  • Sequenzoperator ;
  • Bedingte Verzweigung if-else
  • Verzweigung durch switch
  • Schleifen: while, do-while, for
• Ausgabeanweisung System.out.println()
• Datenabstraktion - Verfeinerung - Abstraktionsfunktion - korrekte Implementierung von n-stelligen Operatoren

Übungen - Lektüre - Praktikum:

• Vertiefung der in der Vorlesung vorgestellten Java-Konstrukte, Beispiele in Java

Programmierpraktikum.

• Einstieg in die Programmierung mit Java: Shell, Editor, Compiler

Material zu Session 2:

• Das Beispielprogramm mit den einfachsten Deklarationen und Anweisungen (Vorlesung vom 13.11.2006): Beispiel1.java
• Die zu Beispiel1 gehörige Dokumentation (mit Doxygen erstellt): Beispiel1-Dokumentation
• Das Doxygen-Konfigurationsfile, welches für Eure Aufgaben in gleicher oder ähnlicher Form verwendet werden kann): Doxyfile
• Das Java-Beispiel (class Set32) für Verfeinerung von Operatoren (Implementierung der Mengenalgebra für Teilmengen von {0,---,31}): Set32.java
  Dieses Programm zeigt auch den Stil der Doxygen-Dokumentation, wie sie für alle zukünftigen Aufgabenblätter erforderlich ist.
  Dabei bitte beachten, dass auch der algorithmische Teil im Code mit Standard-Kommentaren zu versehen ist. Diese erscheinen dann in der Dokumentation an der Stelle, wo sie im Code aufgeführt worden sind. Das Beispiel gibt einen Eindruck, wie der Tiefegrad der Dokumentation in Euren Java-Lösungen aussehen sollte.
  Die mit Doxygen formatierte Dokumentation findet Ihr hier.
  Das zugehörige Konfigurationsfile zur Erstellung der Doxygen-Dokumentation: Doxyfile

Literatur zu Session 2:

• Die unten angegebene Literatur über Java.
• Oberschelp und G. Vossen: Rechneraufbau und Rechnerstrukturen, Kapitel 11.4, bzgl. Linker Loader etc.
• Gunter Saake, Kai-Uwe Sattler: Algorithmen und Datenstrukturen, Abschnitt 3.3 bzgl. imperativen Algorithmen

Session 3: Erste Algorithmen und Datenstrukturen

Vorlesung:

• Rekursive Sortieralgorithmen: Quicksort
• Devide-and-Konquer Algorithmen versus Greedy Algorithmen

Übungen - Lektüre - Praktikum:

• Binäre Suche
• Bubblesort
• Mergesort

Material zu Session 3:

• Das "Quicksort"-Programm aus der Vorlesung vom 04.12.2006 (neu): Qsort.java

Literatur zu Session 3:

• Gunter Saake, Kai-Uwe Sattler: Algorithmen und Datenstrukturen, Kapitel 5
• Die algorithmischen Strategien Devide-and-Konquer und Greedy werden bei Gunter Saake, Kai-Uwe Sattler: Algorithmen und Datenstrukturen, Abschnitte 8.2 und 8.3 diskutiert.

Session 4: Systematische Java-Spracheinführung

Vorlesung:

• Grammatik-Beschreibung mit BNF und EBNF
• Ausdrucksmächtigkeit von BNF im Vergleich zu regulären Sprachen

Übungen - Lektüre - Praktikum:

• Syntaxdiagramme
• Ableitungsbäume

Literatur zu Session 4:

• Die ISO-EBNF-Notation (ISO-normierter Dialekt von der EBNF-Notation, welche wir verwenden): iso-14977.pdf)
• BNF-Grammatik für die Java Syntax: BNF Index of JAVA language grammar - (Am besten bei der Referenz startrule anfangen!)
• Die JAVA Grammatik nach Gosling, Joy und Steele: The Java Language Specification, Third Edition

Session 5: Algorithmen und Datenstrukturen: Listen und Stacks

Vorlesung:

• Listen: mathematische Definition
• Operationen auf Listen: erstellen, einfügen, löschen, traversieren, ...
• Pre- und Postconditions zur Spezifikation von Methoden
• Last-in-first-out (LIFO)- und First-in-first-out (FIFO)-Queues

Übungen - Lektüre - Praktikum:

• Doppelt verkettete Listen
• Stacks auf Basis von Listen

Material zu Session 5:

• Beispiel aus der Vorlesung: Einfach verkettete Liste
• Skript zur Vorlesung vom 23.01.2007: Mathematische Modellierung, operationelle Semantik und Verifikation von Listen in Java

Literatur zu Session 5:

• Gunter Saake, Kai-Uwe Sattler: Algorithmen und Datenstrukturen, Kapitel 13

Session 6: Algorithmen und Datenstrukturen: Hashing

Vorlesung:

• Ziel der Streuspeicherung (=Hashing): schnelles Suchen über Schlüsselwerte möglich machen, wobei der Wertebereich der möglichen Schlüsselwerte sehr groß sein kann

Material zu Session 6:

• Einfaches Beispiel Hashing mit String-Schlüsselnin Java: MyHashS.java

Literatur zu Session 6:

• Gunter Saake, Kai-Uwe Sattler: Algorithmen und Datenstrukturen, Kapitel 15

Übungszettel

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 zu Beginn der Vorlesung abgegeben. Quellcode müsst außerdem per Email an eure Praktikumsleiter schicken.

• Übungsblatt 1, Abgabe am 06.11.2006
• Übungsblatt 2, Abgabe am 13.11.2006
• Übungsblatt 3, Abgabe am 20.11.2006 - Dazu auch der Programmrahmen Bubblesort.java
• Übungsblatt 4, Abgabe am 27.11.2006
• Übungsblatt 5, Abgabe am 04.12.2006 - Dazu auch der Programmrahmen K2-Programmrahmen.java
• Übungsblatt 6, Abgabe am 11.12.2006
• Übungsblatt 7, Abgabe am 18.12.2006
  Der Hinweis zu Aufgabe 1 " Die Tripel werden als Instanzen von Java Klassen mit entsprechenden Attributen und einem Konstruktor gebildet, ..." muss nicht beachtet werden. Als Alternative bietet es sich an (wie in der Vorlesung demonstriert), für jede Komponente des Ergebnistripels einen eigenen 2-dimensionalen Array anzulegen.
• Übungsblatt 8, Abgabe am 08.01.2007
  Wie in der Vorlesung angemerkt, ist die BNF Index of JAVA language grammar nicht vollständig. Für die Aufgabe 2 sollen folgende weitere Produktionen verwendet werden:
  
  • Statement ::= ExpressionStatement;
  • ExpressionStatement ::= Assignment ";" ;
  • Assignment ::= LeftHandSide AssignmentOperator ( numeric_expression | bit_expression);
  • LeftHandSide ::= ( ( "-" | "++" "--" ) identifier ) | ( identifier ( "++" | "--" ) )
  • AssignmentOperator ::= "=" | "*=" | "/=" | "%=" | "+=" | "-=" | "&=" | "< <=" | "> >=" | ">>>=" | "^=" | "|=" |
• Übungsblatt 9, Abgabe am 15.01.2007 - Dazu auch der Programmrahmen AsmInterpreter.java
• Übungsblatt 10, Abgabe am 22.01.2007 - Dazu auch der Programmrahmen MyList-programmrahmen.java
• Übungsblatt 11, Abgabe am 29.01.2007 Abgabe am 05.02.2007
• Die letzte Aufgabenserie: Übungsblatt 12, Abgabe am 05.02.2007

Übungsblatt 11 wird aus der (n-1) - Regelung herausgenommen. Dafür sind nur die n=11 Serien 1 - 10 und 12 relevant. Als Anreiz zur Bearbeitung der Serie 11 werden die erzielten Punkte zusätzlich zu den Punkten aus (n-1) Serien gutgeschrieben.

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 im Beisein des Praktikumsbetreuers durchgeführt. Wiederholungsprüfungen werden bei Jan Peleska abgelegt. Wer im Bachelor-Studiengang ist, muss Diplom/Master durchstreichen und Bachelor drüberschreiben. Es gibt bis jetzt keine gesonderten Scheine.

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 zur Vorlesung

• 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

• Das Buch Guido Krüger: Handbuch der Java-Programmierung ist auch in einer HTML-Ausgabe zum freien Download erhältlich auf http://www.javabuch.de , ebenso wie
• Christian Ullenboom: Java ist auch eine Insel - Programmieren für die Java 2-Plattform in der Version 1.4. Galileo Press GmbH, 2002 und
• Bruce Eckel: Thinking in Java. Prentice Hall PTR, 1998.
• Einen Überblick über Java Tutorien, Artikel und Bücher findet man auf http://developer.java.sun.com/developer/infodocs/

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

• Die Encyclopaedia Britannica ist eines der bekanntesten Lexika: http://www.britannica.com
• Ein Nachschlagewerk in deutscher Sprache mit recht guten Informatik-Erläuterungen ist beispielsweise WIKIPEDIA - Die freie Enzyklopädie http://de.wikipedia.org/wiki

Online-Wörterbuch Deutsch-Englisch

Java, Emacs und LaTeX für zu Hause

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

• Java: http://java.sun.com
• Emacs: http://www.gnu.org/software/emacs/emacs.html
• LaTeX: http://www.dante.de

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

• Java: http://java.sun.com
• Emacs: http://www.gnu.org/software/emacs/windows/ntemacs.html
• LaTeX: http://www.miktex.org/
• Ghostview: http://www.cs.wisc.edu/~ghost/index.html

• Java: http://java.sun.com/docs/books/tutorial/getStarted/cupojava/mac.html
• Emacs: http://members.shaw.ca/akochoi-emacs
• Eine Emacs-Version, die ohne das X11-Paket auskommt (läuft direkt unter OSX[Carbon]): http://www.inf.unibz.it/~franconi/enhanced-carbon-emacs
• LaTeX: http://www.trevorrow.com/oztex/index.html