Universität Bremen  
  Universität Bremen FB3 TZI BISS  
  AG BS > Lehre > WiSe 2008/09 > Deutsch
English
 

Praktische Informatik 1, WiSe 2008/09
 

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

Aktuelles

  • Diejenigen Studierende, die ihr Fachgespräch nicht bestanden haben oder nicht zum Fachgespräch erschienen sind, haben noch die Möglichkeit einen Schein zu erwerben durch ein Fachgespräch bei Jan Peleska. Diese Nachprüfungen finden am 30. und 31. März statt.

    Diejenigen, die ihr erstes Fachgespräch nicht bestanden haben, sollten mittlerweile eine mail mit einem festgesetzten Termin erhalten haben.

    Diejenigen, die zum Fachgespräch zugelassen, aber nicht erschienen sind, sollten ebenfalls eine mail erhalten haben. Falls Ihr die Möglichkeit der Nachprüfung wahrnehmen wollt, müsst Ihr auf diese Mail antworten, damit ein Termin festlegt werden kann.

    Sollte jemand der Ansicht sein, einer der beiden obigen Gruppen anzugehören, aber keine mail bekommen haben: Schickt bitte schnell eine mail an Ulrich Hannemann (ulrichh) , damit wir das klären können.

  • Da die Veranstaltung für Studierende mehrere Studiengänge angeboten wird, hier einige Hinweise zu den Anmeldeformalitäten (nach bestem Wissen):
    • Studierende der Studiengänge Informatik und Digitale Medien der Universität Bremen haben sich hoffentlich bereits bis zum 30.11. 2008 beim Prüfungsamt angemeldet - ansonsten darf kein Fachgespräch stattfinden. Zum Fachgespräch muss ein vorbereiteter SBLN mitgebracht werden:
    • Studierende im Studiengang Systems Engineering haben sich ebenfalls bei ihrem Prüfungsamt angemeldet - die Formulare gehen uns automatisch zu.
    • Studierende im Studiengang Mathematik/Technomathematik Bachelor melden sich im Prüfungsamt MZH 7. Ebene rechtzeitig (2 Wochen +??? vor dem Fachgespräch) an und bringen einen vorbereiteten SBLN mit: Auch wenn die Veranstaltung "Praktische Informatik 1" hier anscheinend dem Bereich "General Studies" zugeordnet wird , kann die Veranstaltung nur angerechnet werden, wenn ein Leistungsnachweis vorliegen, also ein Fachgespräch bestanden wird.
    • Studierende im Studiengang Mathematik/Technomathematik Diplom müssen das graue/orange Anmeldeformular zur Vordiplomsprüfung (Fachprüfung) ausfüllen, von Jan Peleska (Prüfer) und dem jeweiligen Tutor (Beisitzer) unterschreiben lassen und im Prüfungsamt abgeben - rechtzeitig(2 Wochen +??? vor dem Fachgespräch) - die landen dann bis zum Fachgespräch wieder bei uns, zusätzlich bitte auch hier einen vorbereiteten SBLN mitbringen:
    • Die Studierenden, die nicht in diese Kategorien fallen, klären bitte die Prüfungsanmeldungsmodalitäten mit ihrem zuständigen Prüfungsamt.

      Für alle nicht abgedeckten Fälle ein Blanko SBLN

  • Zur Begleitung der Veranstaltung wurde unter STUD.IP das zugehörige Forum freigeschaltet, Fragen und Hinweise zur Vorlesung können auch dort geklärt werden.

Inhalt dieser Seite

Termine
VAK: 03-05-G-700.01/03-05-G-700.04
 
Semester: WiSe 08/09
 
Vorlesung: Mo. 13-15 Uhr, NW1 H1 (H0020)
Mi. 15-17 Uhr, NW1 H1 (H0020)
regulär ab 27.10.2008 (inkl. Tutoriumsbetrieb)
 

Die Tutorien 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. Die Tutorien beginnen ab dem 28.10.2008.
Tutorien:
Tutorium 1: Di. 10 - 12 Uhr, MZH 7230 Jan Frederik Sima
Tutorium 2 (primär für Digitale Medien): Di. 10 -12 Uhr, MZH 2492 Martin Stommel (bislang:Burcu Cinaz)
Tutorium 3:
Di 13 - 15 Uhr, MZH 7230 Kai Florian Richter
Tutorium 12 : Di. 13 - 15 Uhr,MZH 2492 Serge Fopoussi
Tutorium 4 (primär für Digitale Medien): Mi. 10 - 12 Uhr, MZH 7230 Jan Frederik Sima
Tutorium 13 : Mi. 10 - 12 Uhr,MZH 2492 Christian Genz
Tutorium 5 : Mi. 13 - 15 Uhr, MZH 7230 Stefan Haase
Tutorium 6 (primär für Mathematik/Technomathematik): Mi. 13 - 15 Uhr, MZH 2492 Elena Vorobev
Tutorium 7 (primär für Mathematik/Technomathematik): Do. 10 - 12 Uhr, MZH 7230 Daniel Möhlmann
Tutorium 8: Do. 10 - 12 Uhr, MZH 2492 Ulrich Hannemann
Tutorium 9 : Do. 13 - 15 Uhr, MZH 7230 Florian Lapschies
Tutorium 10 (primär für Systems Engineering) Do. 15 -17 Uhr, MZH 7230 Elena Vorobev
Tutorium 11 (primär für Systems Engineering): Do. 15 - 17 Uhr, MZH 2492 Oliver Birbach

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. Ferner werden auch die Lösungsansätze für die Aufgaben besprochen, die von den Teilnehmern im Tutorium zu lösen sind.

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

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 0 - Begrüßungsvorlesung: Praktische Informatik und ihre Anwendungen

In dieser Vorlesung wird ein Überblick über den Inhalt von PI1 (und ebenso ein bisschen von PI2) gegeben. Ziel dieses Überblicks ist es, zu illustrieren, dass dieser Lernstoff die Grundlage für nahezu alle aktuellen Entwicklungen in Forschung, Technik und Gesellschaft bildet. Die Vorlesung ist eher motivierender Natur; es werden dabei allerdings folgende Begriffe eingeführt, die zum "echten Stoff" von PI1 gehören:
  • Betriebssystem versus Laufzeitumgebung
  • Interpretierte versus kompilierte Programmiersprachen
  • Programmiercode auf verschiedenen Abstraktionsebenen bei kompilierten Programmiersprachen:
    • Quellcode in "Höherer" Programmiersprache, z.B. C, C++: Wird durch den Compiler übersetzt in
    • Assembler: Wird durch den Assembler übersetzt in
    • Maschinencode: wird durch den Linker übersetzt in
    • Ausführbares Programm: wird durch das Betriebssystem transformiert in einen laufenden
    • Prozess: Wird auf der CPU interpretiert durch den
    • Microcode
  • Beispiele für kompilierte Programmiersprachen:
    • C
    • C++
    • Algol
    • Pascal
    • Fortran
    • Modula 2
    • Ada
  • Programmiercode auf verschiedenen Abstraktionsebenen bei Java
    • Java Quellcode: Wird durch den Compiler javac übersetzt in
    • Java Byte-Code: wird durch die Java Laufzeitumgebung (JRE) interpretiert
    • Die Java Laufzeitumgebung muss für jede Rechnerplattform (CPU, Betriebssysrem) neu durch einen konventionellen Compiler, Assembler und Linker in ein ausführbares Programm übersetzt werden.
  • Beispiele fü interpretierte Programmiersprachen (auch Skriptsprachen genannt):
    • Lisp
    • Smalltalk
    • Basic
    • Unix Shells, z.B. bash
    • Python
    • JavaScript
    • Java
  • Die Sonderstellung von Java unter den interpretierten Programmiersprachen: die Java Laufzeitumgebung (die Java Virtual Machine) interpretiert den Byte-Code, in welchen das Java Programm vorübersetzt wurde.
  • C# und Microsoft Intermediate Language (MSIL) unter .NET (Common Language Runtime und Framework Class Library) als konkurrierende Alternatve zu Java, Byte-Code und JRE, Java API
  • Just in Time (JIT) Kompilation: Byte-Code oder MSIL Code wird erst dann in Maschinencode übersetzt, wenn er tatsächlich zur Ausführung kommt.
  • Alphabet: Der Zeichenvorrat einer Sprache (in unserem Zusammenhang immer: Programmiersprache)
  • Syntax: Die formalen Beziehungen zwischen Zeichen einer Sprache, d.h.: Die Konstruktionsvorschrift zur Erzeugung wohlgeformter ("erlaubter") Ausdrücke einer Sprache
  • Grammatik: Formale Erfassung aller Syntaxregeln
  • Semantik: Die Lehre von der Bedeutung von (sprachlichen) Zeichen
  • Semiotik: Die Lehre von den Zeichen
  • Algorithmus: Endliche Anweisung zur Lösung eines Problems in endlicher Zeit, unter Verwendung von elementaren auf dem Computer ausfürbaren Schritten
  • Security: Schutz vor (böswilliger oder versehentlicher) menschlich verursachten Störungen des intendierten Verhaltens von Computersystemen

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
  • eine fiktive Assemblersprache und ihre Realisierung im Mikrocode
Schemata und Begriffe .

Session 2: Erste Schritte in Java

  • Programmierparadigmen: Imperativ (Pascal, C), objekt-orientiert (Java, C++, C#, Smalltalk), funktional (Lisp, Haskell), logisch (Prolog)
  • Imperative Programmiersprachen arbeiten mit Variablen, auf denen Anweisungen operieren.
  • Deklarationen und Deklarative Programmiersprachen
  • Klassendeklaration in Java - die main()-Methode
  • Lokale Variablendeklarationen in Java: Basistypen und Referenztypen
  • Anweisungen: Zuweisungen, Kontrollstrukturen, Variablendefinitionen, Ein-/Ausgabeanweisungen
  • Ausdrücke und Operatoren
  • Erläuterungen zu den oben genannten Begriffen findet man in den Kommentaren im folgenden Java Beispielprogramm . Hinweis: Die Kommentare sind im Doxygen-Stil geschrieben - mit diesem Doxyfile wird Dokumentation generiert.

Session 3: Erste Algorithmen und Datenstrukturen: Suchen und Sortieren

  • Definition des Begriffs Algorithmus
  • Eingenschaften von Algorithmen:
    • Korrektheit
    • Terminierung
    • Laufzeitbedarf
    • Speicherbedarf
  • Der Bubble-Sort Algorithmus
  • Berechnung des Laufzeitbedarfs für den Bubble-Sort Algorithmus
  • Der Algorithmus Binäre Suche auf sortierten Arrays
  • Berechnung des Laufzeitbedarfs im schlimmsten Fall ( Worst Case Execution Time WCET) für die Binäre Suche
  • Programmbeispiel Binäre Suche mit Anwendung eines Back-to-Back Testverfahrens und Hinweisen zur Berechnung des Laufzeitbedarfs
  • Der Quick Sort Algorithmus.
    • Fehlerhafter Algorithmus, wie in der Vorlesung 2008-11-19 diskutiert.
    • Korrigierter Algorithmus, aus der Vorlesung 2008-11-19.
    • Korrekter Algorithmus - eine elgantere Alternative nach Aho, Hopcroft, Ullman: Data Structures and Algorithms, Addison Wesley 1983.
      Neu 2008-11-25: Der Quellcode ist im Doxygen-Stil dokumentiert. Im Verzeichnis q/ befindet sich die Quelldatei zusammen mit der Doxygen Konfigurationsdatei Doxyfile. Im Unterverzeichnis q/doc/html findet man die von Doxygen erzeugte HTML-Dokumentation.
    • Link für den Download von Doxygen
    • Link für den Download von GraphViz - dieses Werkzeug wird benötigt, um Aufrufgraphen, Klassenhierarchien etc. zu visualisieren.
  • Rekursive Methodenaufrufe und die dabei erfolgende Nutzung des Stacks

Session 4: Systematische Java-Spracheinführung

  • Begriffe: Syntax, Alphabet, Token (= Lexem oder Terminales Symbol), Kontext-freie Grammatik, Produktionsregel, nicht-terminales Symbol, terminales Symbol, Zielsymbol
  • Lexikalische Grammatik: Spezifiziert das von der syntaktischen Grammatik verwendete Alphabet
  • Syntaktische Grammatik: Spezifiziert die Menge der erlaubten Forlgen terminaler Symbole
  • Java Syntax: siehe Gosling, The Java Language Specification, Third Edition
  • Syntaktische Metasprachen: Sprachen zur Spezifikation der Syntax anderer Sprachen. Beispiele für syntaktische Metasprachen sind
    • Extended Backus-Naur Form EBNF
    • Syntaxgraphen
    • Reguläre Ausdrücke
    • Die von Gosling eingeführte Syntaxnotation in The Java Language Specification, Third Edition
  • Die ISO-EBNF-Notation: ISO-normierter Dialekt von der EBNF-Notation, welche wir verwenden): iso-14977.pdf
  • Entwicklung von Algorithmen für die Syntaxprüfung
  • Syntaxdiagramme als Alternative zur EBNF-Notation
  • Operationelle Semantik von while-Sprachen und ihre Anwendung auf einfache Java-Algorithmen.

Session 5: Algorithmen und Datenstrukturen: Listen und Stacks

  • Java Klassen können Kreuzprodukt-Datentypen definieren: class T { t1 x1; t2 x2; ... tn xn; } repräsentiert die Menge T = t1 x t2 x ... x tn. Die Komponenten x1, x2, ..., xn heissen Attribute oder auch Feldelemente der Klasse.
  • Rekursive Datentypen sind in Java durch Klassen T definiert, die Attribute besitzen, welche wieder per Referenz auf T verweisen. class T { t1 x1; ... tn xn; T y; } (Im allgemeinen Fall rekursiver Datentypen hat man eine zyklische Verweiskette T1 -> T2 -> T3 -> ... -> T1).
  • Doppelt verkettete Ringlisten - im Detail erläutert am Beispiel MyList.java
  • Operationelle Semantik und Verifikation von Listen in Java:
    • Ausführliche Beschreibung hier: listen.pdf (letzter Update: 2009-01-19, 20:00)

Session 6: Algorithmen und Datenstrukturen: Hashing

  • Zielsetzung des Hashings: Bilde grossen Schlüsselbereich moeglichst gleichverteilt auf kleinen Indexbereich ab.
  • Hashfunktion für Integer
  • Hashfunktion für Strings
  • Beispielprogramm MyHashS.java: Streuspeicherung mit einem Array, dessen Elemente null sind, oder den Kopf einer einfach verketteten Liste bilden.
  • Streuspeicherung auf Basis eines Arrays allein, dessen Elemente direkt auf Nutzdaten referenzieren. Suchverfahren bei Kollisonen: nächster freier Index, bei Bedarf weitere Indices im logarithmisch mit der Anzahl der Fehlschläge zunehmenden Abstand suchen.

Session 7: Grundlagen der objekt-orientierten Programmierung mit Java

  • Java und Objektorientierung
  • Beispiel: MyListOO.java: Objekt-orientierte Version des Beispiels der Ring-verketteten Listen. Letzte Aktualisierung: 2009-01-28, 13:30
  • Statische Attribute und Objektattribute, Vererbung, überschriebene Methoden und Polymorphismus, illustriert am Beispiel: World of Dogs
  • Sortenreine abstrakte Datentypen mit Laufzeitüberprüfung der Typen und Generics mit Typprüfung zur Übersetzungszeit, illustriert am Beispiel: MyGenerics.java
  • Nutzung von normalen und generischen Interfaces, Klassen, sowie Packages und Import-Anweisungen: Beispiel: Verzeichnisbaum generics.tgz. Beim Ausprobieren ist hier der Pfad bis generics/ in den CLASSPATH aufzunehmen.

Ü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 pi1.cls erstellt werden und jeweils Montags vor der Vorlesung abgegeben werden. Als Hilfe zur lesbaren Erklärung von Java Programmen, hier eine .tex Datei, die auch Code präsentiert. Für die Serien 3 und 4 soll der Java Quellcode per e-mail an den jeweiligen Tutor geschickt werden. Ab Serie 5 erfolgt die Quellcodeabgabe im Repository der jeweiligen Gruppe tXXgYY in einem Unterverzeichnis uebungZZ, mit ZZ = 05, 06, ...

Kriterien für den Erwerb eines Leistungsnachweises

Es werden wöchentlich Übungszettel ausgegeben, die jeweils in Gruppen zu dritt bearbeitet werden. 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%: nicht bestanden

Jede Gruppe muss mindestens einmal 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 zur Vorlesung

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
  • Die Java-Klassenbibliothek zum Nachschlagen
  • Ein empfehlenswertes Lehrbuch zur Einführung in Java ist Reinhard Schiedermeier: Programmieren in Java. Pearson 2005.

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