Hasso-Plattner-Institut Potsdam Operating Systems and Middleware Group at HPI University of Potsdam, Germany
Operating Systems and Middleware Group at HPI

Programmiertechnik II

Prof. Dr. Andreas Polze

Sommersemester 2018

Ü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 13:30-15:00, HS1
  • Do 09:15-10:45, HS1

Übungen finden ungefähr 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 http://www.dcl.hpi.uni-potsdam.de/submit/ 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
  • Niklaus 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


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: Freispeicherverwaltung

  • Freispeicherverwaltung
  • Lebensdauer von Objekten
  • Referenzzählung
  • Garbage Collection

Unit 3b: Typen, Module, Klassen, Objekte

  • Abstrakte Datentypen
  • Konstruktion neuer Datentypen
  • Charakteristika von Objekten
  • Polymorphie und Vererbung
  • Objekte in C
  • Mehrfachvererbung, Interfaces, Exceptions

Unit 4: Java

  • 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

  • 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

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

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

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

Unit 11: Logische Programmierung: Prolog

  • Boolesche Logik
  • Closed World Assumption
  • Fakten, Prädikate
  • Regeln
  • Listen
  • Generatoren
  • Cut