Programmiertechnik I

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


Sie finden Aufzeichnungen der Lehrveranstaltung im Tele-Task-System.

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

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 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)