Programmiertechnik II

Sommersemester 2013

Prof. Dr. Andreas Polze

Tutoren: Sven Köhler, Sven Knebel

Überblick

Die Lehrveranstaltung vermittelt Theorie und Praxis der Programmierung von Software am Beispiel der Sprachen Java und Prolog.

Diskutiert werden Algorithmen und Datenstrukturen zum Sortieren und Suchen, Graphenalgorithmen, Algorithmen und Datenstrukturen zur Implementierung objekt-orientierter Sprachen sowie die deklarative Programmierung. Diese Inhalte werden in den allgemeineren Kontext der Softwareproduktion eingebettet.

Termine:

Vorlesung:

Di 11:00-12:30, HS1
Do 11:00-12:30, HS1

Übungen finden alle 2 Wochen zum Vorlesungstermin am Donnerstag statt. Zu den Übungen werden Übungsaufgaben ausgegeben (insgesamt 6 Serien). Diese sollen in Zweier-Gruppen bearbeitet und den Tutoren präsentiert werden. Für eine Zulassung zur Klausur ist der Erwerb von mindestens 50% aller Punkte der jeweiligen Übungsaufgaben erforderlich.

Lösungen zu den Übungsaufgaben müssen über das Abgabesystem unter /pt2prak/ eingereicht werden. Sie können sich dort unter Auswahl der HPI-OpenID-Providers mit Ihrem HPI-Benutzerkonto anmelden.

Literatur

Heinz Peter Gumm, Manfred Sommer; "Einführung in die Informatik"; 9. Auflage, Oldenburg Verlag, 2011
N.Wirth: "Algorithmen und Datenstrukturen"; Stuttgart: Teubner (1979); ASIN: B003E6764A
Robert Sedgewick; "Algorithmen in Java"; 3. Auflage, Pearson, 2003, ISBN: 978-3-8273-7072-3
Donald E. Knuth; "The Art of Computer Programming, Vol.. III: Sorting and Searching"; 2nd Edition, Reading, Massachusetts: Addison-Wesley, 1998, ISBN 0-201-89685-0
William F.Clocksin, Christopher S. Mellish; "Programmieren in Prolog"; Springer-Verlag, 1981, ISBN 0387110461

Hausaufgaben

Serie 1; Abgabe bis zum 2.5.2013
tar-Archiv mit Skelett der Lösung
Serie 2; Abgabe bis zum 23.5.2013
In.java zum Einlesen ganzer Zahlen
Serie 3; Abgabe bis zum 6.6.2013
Matrixmultiplikation - die zu analysierenden Programme.
Serie 4; Abgabe bis zum 20.6.2013
Serie 5; Abgabe bis zum 4.7.2013
Serie 6; freiwillig - Diskussion in der mündlichen Prüfung

Sie finden Aufzeichnungen der Lehrveranstaltung im tele-task-System unter http://tele-task.de/archive/series/overview/945/.

Ablauf

Unit 1: Übersicht

Konzepte OOP
Implementierung OOP
Programmiersprache Java
Algorithmische Komplexität
Sortieren
Suchen
Graphen
Deklarative Programmierung

Unit 2: Objektorientierte Programmierung

Programmieren im Großen
Von Modulen zu Objekten
OO Konzepte im Überblick
Regeln für objektorientierten Entwurf
Liskov Substitution Principle (LSP)
Vererbung
Polymorphie

Unit 3: Typen, Module, Klassen und Objekte

Abstrakte Datentypen
Konstruktion neuer Datentypen
Charakteristika von Objekten
Freispeicherverwaltung
Polymorphie und Vererbung
Objekte in C
Lebensdauer von Objekten
Garbage Collection
Mehrfachvererbung, Interfaces, Exceptions

Java Geschichte
Lexik, Datentypen, Variablendeklarationen
Methoden und Klassen
Zugriffssteuerung
Konstruktoren und Überladung
Programme, Pakete, Java-Werkzeugkette
Ausdrücke, Blöcke, Sichtbarkeit
Anweisungen
OO: Klassen, Vererbung, späte Bindung
Abstrakte Klassen und Schnittstellen
Ausnahmebehandlung, weitere Konzepte
Beispiele (tar)

Unit 5: Analyse von Algorithmen

Vernetzungsprobleme - ein Beispiel
Quickfind, Quickunion
Laufzeitbetrachtung
Empirische Analyse
Mathematische Analyse
Komplexitätsklassen
O() Notation
Lineare und binäre Suche

Unit 6: Modultest mit JUnit

Test-Driven Development (TDD)
Testen mit JUnit 4
Einschub: Annotationen in Java
Bestimmung des Testergebnisses
Exceptions testen
Fixtures: definierten Ausgangszustand herstellen
Integration von Testfällen
Parametrisierung von Tests

Unit 7: Datentypen in Java

Primitive Datentypen
Strings
Objekttypen
Arrays
Mengen: Collection, Set
Implementierungsstrategien: verkettete Listen
Listenoperationen
Maps: HashMap, TreeMap
Collections im Überblick
Generische Typen
Beispiele (tar)

Unit 8: Elementare Sortieralgorithmen

Sortieren
Elementdarstellung, Primitive Operationen
Internes vs. Externes Sortieren
Bewertung
Zahl Vergleiche, Austauschoperationen, Speicherplatzbedarf
InsertionSort, SelectionSort, BubbleSort
Komplexität der einfachen Algorithmen
ShellSort
Sortieren von Listen
Beispiele (tar)

Unit 9: Optimierte Sortieralgorithmen

Quicksort
Grundidee, Partitionierung, Rekursion
Analyse von Quicksort
Optimierung für kleine Mengen
Mergesort
Mischen von Stapeln
Mischen im selben Speicher
Top-Down-Mergesort, Bottom-Up-Mergesort
Heapsort
Priority Queues
Heap-Eigenschaft
Radixsort
Sortieren anhand spezieller Eigenschaften der Schlüssel
Timsort
Beispiele (tar)

Unit 10: Suchen

Symboltabellen und binäre Suchbäume
Symboltabellen
Binäre Suchbäume
Balanzierte Bäume
2-3-4-Bäume
Rot-Schwarz-Bäume
AVL-Bäume
Skiplisten
Datenstrukturen - Hash-Tabellen
Hashfunktionen
String-Hashing
Offene Adressierung
Hash-Tabellen und Binäre Suchbäume
Beispiele (tar)

Unit 11: Logische Programmierung: Prolog (swi-prolog)

Boolesche Logik
Closed World Assumption
Fakten, Prädikate
Regeln
Listen
Generatoren
Cut
Beispiele (tar)