Programmiertechnik II

Sommersemester 2018

Prof. Dr.Andreas Polze

Ü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://osm.hpi.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
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein; "Introduction to Algorithms"; Third Edition, MIT-Press, 2009, ISBN 978-0-262-53305-8

Hausaufgaben

Mündliche Prüfungen

Die mündlichen Prüfungen finden in den letzten zwei Septemberwochen (17.09.-28.09.2018) im Raum C-1.8 statt.
Eine Terminauswahl ist online mit Ihrem HPI-Benutzerkonto möglich.

Pro Termin werden zwei Personen geprüft. Es steht Ihnen frei zu Beginn der Prüfung einen Fachvortrag (ohne Hilfsmittel) von drei bis fünf Minuten über ein von Ihnen gewähltes Thema aus der Vorlesung zu halten.

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

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
  • Beispiele (tar), Reverse.java

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
  • Beispiele (tar)

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)

Einschub: Codedurchsicht

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

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