Vorlesung: Objektorientierte Programmierung

Veranstaltung: 19523 Proinformatik - Objektorientierte Programmierung

Sommersemester 2011
Veranstalter: Prof. Dr. Marco Block-Berlitz, Michael Kmoch, Benjamin Schönburg, Eduard Wolf, Christoph Krüger, Simon Lang

Termine:
Vorlesung: 8:30-11 Uhr (s.t.) täglich, Hörsaal Takustr. 9
Tutorien: 12-15 und 15-17 Uhr (c.t.) täglich, SR 051, SR 006, K 36, RR Bioinf

Aktuelles

Stand 18.08.2011: Start
Umfrage zur Geschwingigkeit der Vorlesung im Forum gestartet.

Stand 15.08.2011: Start
Heute startet die Vorlesungsreihe.

Inhalt der Veranstaltung

Grundlagen der Berechenbarkeitstheorie [1, 8]:
Berechnungsmodelle (Loop, While, Goto), Universelle Registermaschinen, Syntax und operationelle Semantik imperativer Programmiersprachen
Formale Verfahren zur Spezifikation und Verifikation von imperativen Programmen [2]:
Bedingungen auf dem Zustandsraum (assertions), Hoare-Kalkül, partielle Korrektheit, Termination, Model-Checking
Konzepte imperativer und objektorientierter Programmierung am Beispiel Java [3, 4]:
Primitive und zusammengesetzte Datentypen, Methoden (Prozeduren und Funktionen), Parameterübergabe, Überladung, Module, Klassen, Objekte, Erstellung und Verwendung von Bibliotheken, Klassenkonzept, Vererbung, abstrakte Klassen, Interfaces, UML, AWT, Swing, Applets, Kleine praktische Anwendungen (Bildverarbeitung, KI, OpenGL, GLSL), Spieleprogrammierung, Automatisierte Tests mit JUnit
Programmiermethodik [3, 6]:
Prinzipien der Programmentwicklung, Debuggen und Fehlerbehandlungen, Teile und Herrsche, Backtracking
Analyse von Laufzeit und Speicherbedarf [6, 7, 8]:
Landau-Symbolik, Uniformes versus Bit-Komplexitätsmaß, Umwandlung von Rekursion in Iteration, Analyse von Such- und Sortieralgorithmen

Scheinkriterien

Regelmäßige Teilnahme an den Vorlesungen und Übungen, 60% der möglichen Punkte aller Übungen (bei n-1 Übungszetteln müssen mindestens 20% erreicht sein) berechtigen zur Klausurteilnahme. Bestehen der Klausur am vorletzten Vorlesungstag (08.09.2011, 8:30 Uhr, s.t.). Die Note des Scheins entspricht der Klausurnote.

I Theoretischer Teil

Alle Folien und Skripte der Vorlesung (falls vorhanden) und Verweise zu Literatur und anderen Projekten werden hier bereitgestellt. Trotzdem empfehle ich jedem Teilnehmer der Veranstaltung, alle Notizen eigenständig anzufertigen.

Inhalte und Folien zu den Vorlesungen

1. Tag (15.08.2011) [PDF]:

Motivation und Ziele der Veranstaltung

Einstieg in Java

Primitive Datentypen

Boolesche Algebra

Type casting

2. Tag (16.08.2011) [PDF]:

Programm als Kochrezept, Pseudocode

Methoden der Programmerstellung

if, switch, for, while, do-while, continue, break

Funktionen

3. Tag (17.08.2011) [PDF]:

Externe Programmeingaben

Dateien lesen und schreiben [CODE, CODE]

Daten von der Konsole einlesen

Projekt: Kryptographie [CODE]

Arrays, literale Erzeugung

Performancevergleiche

for-Schleife (vereinfacht)

Projekt: Conway's Game of Life [CODE]

4. Tag (18.08.2011) [PDF]:

Zustandsdiagramme

Enumeratoren

Projekt: JavaGotchi [CODE]

Einstieg in die Objektorientierung

Projekt: Fussballmanager

5. Tag (19.08.2011) [PDF]:

Analysephase der Softwaretechnik

Abstraktion und Geheimhaltungsprinzip

Generalisierung/Spezialisierung

Objekte/Objektreferenzen

Konstruktoren

Einfache Vererbung

Interfaces

Komplexere Textzerlegung

Muster: Model-View-Controller

Projekt: Fussballmanager [CODE]

6. Tag (22.08.2011) [PDF]:

Referenzvariablen

this

Zugriffsmodifikatoren

Eigene Exception-Klasse erstellen

getMessage/printStackTrace

Abstrakte Klassen

Doubleliste

Prinzip des Überladens

Überladen von Konstruktoren

Default-Konstruktor

statische Attribute und Methoden

7. Tag (23.08.2011) [PDF]:

Referenzvariablen

Garbage Collector, Wrapperklassen

String

Projekt: Kryptographie (abstrakte Version)

Standardbibliotheken, Pakete einbinden und verwenden

Klasse Math, Zufallszahlen, Verteilungen

Lineare Algebra - JAMA

Eigene Bibliotheken erstellen

Java AWT und Swing

Fenster erzeugen, positionieren und zentrieren

Textausgaben und Zeichenfunktionen

Klasse Color

Bilder laden und anzeigen, MediaTracker

Fensterereignisse, WindowListener, WindowAdapter

Innere und anonyme Klassen

LayoutManager, Button, Label und TextField

Mausereignisse

Double buffering, Threads, Fullscreen

Projekt: Analoge Uhr [CODE]

Projekt: Eigene bunte Konsole [CODE]

Projekt: Conway's Game of Life [CODE]

Projekt: Bildtransformation in Symbolraum [CODE]

8. Tag (24.08.2011) [PDF]:

WindowListener, MouseListener, MouseMotionListener

KeyListener, ActionListener

HTML

Methoden eines Applets

AppletViewer

Applikation zu Applet

Flackernde Applets vermeiden

Ghosttechnik (Double buffering)

mouseDragged

Live: Applet hacking :)

Obfuscator

9. Tag (25.08.2011) [PDF]:

Reifegrad der Softwaretechnik

Krazy Kindergarten[Link], Artificial Life Projekt MDHchen [Link], Solarsystem [Link]

Phasen der Softwareentwicklung

Analysephase

Anforderungen, Machbarkeit, Dokumentation

UML: Verhaltens- und Strukturdiagramme

Entwurfsmuster OOA:

Liste, Exemplartyp, Baugruppe, Stueckliste,

Koordinator, Rollen, wechselnde Rollen,

Historie, Gruppe, Gruppenhistorie

10. Tag (26.08.2011) [PDF, Tilman Walther]:

Aufbau der Java Platform

Eclipse als Entwicklungsumgebung für Java

Motivation, Projektverwaltung

nuetzliche Funktionen

Live-Coding, Debugging

Projekt: Fussballmanager [CODE]

Projekt: Debugging [CODE]

Fortgeschrittene Eclipsefunktionen

11. Tag (29.08.2011) [PDF]:

Mustererkennung

Einführung in die Vektorenalgebra

Entfernungsmetriken

Klassifikation mit k-nn

Projektstruktur anlegen und planen

Paket linearealgebra

Paket mustererkennung

Projekt: Klassifikator [CODE]

Klassifikation mit k-means

12. Tag (30.08.2011) [Tafel-Mitschrift]:

Einfuehrung in die Algorithmik

Definition und Eigenschaften von Algorithmen

Sieb des Eratosthenes, binaere Suche

Registermaschine, RAM

uniformes Komplexitaetsmaß

Komplexität von Algorithmen

Landau-Symbolik (O, Omega, Theta)

Komplexitätsklassen

Optimalität

13. Tag (31.08.2011) [Tafel-Mitschrift]:

Grenzwertbetrachtung der Landau-Symbolik

Ableitung der Regeln

Landau-Symbolik ("klein" O, "klein" Omega)

Regeln im Umgang mit Schranken

Uniformes versus Bit-Komplexitätsmaß

Berechenbarkeit - Motivation

Symbolik formaler Sprachen

Turing-Maschine (deterministisch, 1-Band)

Konfiguration einer Turingmaschine

14. Tag (01.09.2011) [Tafel]:

Sortieralgorithmen, formale Betrachtung

Laufzeitbetrachtungen: best-, average-, worst-case

BubbleSort (optimiert, nicht-optimiert)

SelectionSort, InsertionSort (optimiert, nicht-optimiert)

Entwurfstechnik: Rekursion

Klassen rekursiver Funktionen

Fakultät, Fibonacci

Ackermannfunktion: primitiv-rekursiv versus Turing-Maschine

Entwurfstechnik: Brute Force

SlowSort

Alternierende Zwei-Spieler-Nullsummenspiele

MinMax-Strategie, Alpha-Beta-Pruning

Komplexitätsbetrachtungen: TicTacToe, Schach, Go

15. Tag (02.09.2011) [Tafel]:

Entwurfstechnik: Greedy

Dynamische Programmierung

Zusammenhang mit adversarialer Suche

Memoisierung

Zusammenhang mit adversarialer Suche

Komplexität von MinMax und Alpha-Beta

Iterative Tiefensuche

Einblick in die Graphentheorie

Adjazenzmatrix, und -liste

Knotenliste

Komplexitätsbetrachtungen: Speicher/Zugriff

Tiefensuche

16. Tag (05.09.2011) [Tafel]:

Einführung in die Programmverifikation

Syntax einer einfachen Programmiersprache

Variablen und Zustände eines Programms

Semantik von Bedingungen

Zustandsänderungen

Semantik der Programmausführung

Zusicherungen

Semantik von Zusicherungen

Substitution

17. Tag (06.09.2011) [Tafel]:

Terminierende und divergierende Programme

Partielle Semantik/Partielle Korrektheit

Totale Semantik/Totale Korrektheit

Hoare-Kalkül-Einführung

Schleifeninvarianten

Erweiterung der Schleifen um Terminierungskriterium

viele Beispiele

18. Tag (07.09.2011) [Tafel]:

Wiederholung der Kernthemen

Wechselseitiges Frage- und Antwortspiel

19.Tag (08.09.2011) [KLAUSUR.PDF]:

KLAUSUR!!! Start 8:30 Uhr (s.t.)

tja -- was haben wir denn alles so gemacht ....

20.Tag (09.09.2011):

Nachbesprechung der Klausur

Vergabe der Noten

Scheinkriterium: Gemeinsames GRILLEN :)

II Praktischer Teil

Bearbeitung der Übungszettel individuell. Jeder Übungszettel wird auf dieser Seite entsprechend zum Download zur Verfügung gestellt. Die Regularien zur Abgabe und zum Vorzeigen der Lösungen werden in den Übungen bekannt gegeben.

Übungsaufgaben

Uebung 1 [PDF]
Uebung 2 [PDF]
Uebung 3 [PDF] (Wochenendzettel)
Uebung 4 [PDF]
Uebung 5 [PDF]
Uebung 6 [PDF] (Wochenendzettel)
Uebung 7 [PDF]
Uebung 8 [PDF]
Uebung 9 [PDF]
Uebung 10 [PDF]
Uebung 11 [PDF] (Wochenendzettel)
Uebung 12 [PDF]
Uebung 13 [Tafelaufgaben vom 06.09.2011]

Musterlösungen zu den Aufgaben

Link zum Forum

Literatur und Links zur Vertiefung

Im Laufe der Vorlesungen werden entsprechende Angaben zu weiterführender Literatur hier eintragen. Das gleiche gilt für wichtige Links. Wir sind für Ergänzungshinweise dankbar.

Linkliste

Java bei Oracle

Editor Notpad++

Entwicklungsumgebung Eclipse

Code-Konventionen

Literaturliste

[1] Hoffmann D.W.: "Theoretische Informatik", Hanser-Verlag 2009
[2] Kleuker S.: "Formale Modelle der Softwareentwicklung - Model-Checking, Verifikation, Analyse und Simulation", Vieweg-Teubner-Verlag 2009
[3] Block M.: "Java Intensivkurs - In 14 Tagen lernen Projekte erfolgreich zu realisieren", 2. Auflage, Springer-Verlag 2009
[4] Gries D., Gries P.: "Multimedia Introduction to Programming Using Java", Springer-Verlag 2005
[5] Weiss M.A.: "Data Structures & Problem Solving Using Java", 3. Auflage, Addison-Wesley-Verlag 2005
[6] Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: "Introduction to Algorithms", 3. Auflage, MIT Press Verlag 2009
[7] Logufatu D.: "Grundlegende Algorithmen mit Java: Vom Algorithmus zum fertigen Programm. Lern- und Arbeitsbuch für Informatiker und Mathematiker", Vieweg-Teubner-Verlag 2008
[8] Hoffmann D.W.: "Theoretische Informatik", Hanser-Verlag 2009