Algorithmen und Datenstrukturen   

Modulcode:	Inf-ADS
Englische Bezeichnung:	Algorithms and Data Structures
Modulverantwortliche(r):	Prof. Dr. Klaus Jansen
Turnus:	jedes Jahr im SS (SS10, SS11, SS12, SS13, SS14, SS15, SS16, SS17, SS18, SS19, SS20, SS21)
Präsenzzeiten:	4V 2Ü
ECTS:	8
Workload:	60 Std. Vorlesung, 30 Std. Präsenzübung, 150 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	G (BSc Inf.) G (BSc WInf.) G (BSc Inf. (2-Fach)) INF-Math (Inf. als NF) G (BSc Inf. (15)) G (BSc Winf. (15)) 2F-BSc (2F-BSc Inf.) INF-Phy (Inf. als NF)
Lehrsprache:	Deutsch
Voraussetzungen:	Inf-Math-A Inf-ProgOO

Kurzfassung:

Programmierung ist ein - wenn nicht der - zentrale Bestandteil der Informatik. Insofern muss ein an einer "grundlagen- und methodenorientierten Ausbildung" ausgerichteter Informatikstudiengang großen Wert darauf legen, die wichtigen Aspekte der Programmierung zu beleuchten. Einer dieser Aspekte umfasst den effizienten Umgang mit großen Daten. Grundlegende Kenntnisse darüber und in diesem Zusammenhang verwendete Methoden werden im Modul "Algorithmen und Datenstrukturen" vermittelt.

Lernziele:

• Algorithmen nach grundlegenden Prinzipien entwerfen.
• Effiziente Datenstrukturen beim Entwurf von Algorithmen einbinden.
• Effizienz von Algorithmen unter Benutzung spezifischer Techniken einschätzen.
• Komplexität von Algorithmen präzise beschreiben und mathematisch exakt nachweisen.
• Algorithmische Problemstellungen konstruktiv und effizient lösen.
• Korrektheitsbeweise für Graphalgorithmen führen.
• Algorithmen in Java implementieren.

Lehrinhalte:

• Laufzeitanalyse von Algorithmen
• pessimale und amortisierte Laufzeiten
• algorithmische Methoden
  
  • Rekursion
  • dynamische Programmierung
  • Divide and Conquer
  • Backtracking
• Sortieralgorithmen
• Listen, Prioritätsschlangen, Suchbäume, Hashtabellen
• Graphalgorithmen
  
  • Tiefensuche
  • Breitensuche
  • kürzeste Wege
  • Minimal spannende Bäume
  • Travelling Salesman Problem
• Komplexitätstheorie

Weitere Voraussetzungen:

Die in der Beschreibung der Module Inf-Math-A und Inf-ProgOO oder alternativ die in der Beschreibung der Module Inf-I1-2FNF, Inf-I2-2F und Inf-ProgOO aufgeführten Lernziele.

Prüfungsleistung:

1. Die Modulprüfung ist eine schriftliche Klausur.
2. Die Klausurnote ist die Modulnote.

Die Klausurzulassung wird Ihnen nur erteilt, falls Sie uns überzeugt haben, dass Sie die Klausur auch bestehen können. Deshalb knüpfen wir die Zulassung zur Modulprüfung an folgende Bedingungen:

• Sie dürfen in höchstens zwei Aufgabenserien weniger als 40 Prozent der Punkte erreichen, die Sie durch Theorieaufgaben erreichen können.
• Es werden 6 Programmieraufgaben gestellt, von denen Sie mindestens 4 erfolgreich bearbeiten müssen. Für jede der Programmieraufgaben gibt es 3 Punkte und sie gilt als erfolgreich bearbeitet wenn mindestens 2 Punkte erreicht werden. Zusätzlich werden Bonusaufgaben gestellt, für die es jeweils einen Punkt gibt. Wird ein Punkt bei der regulären und ein Punkt bei der Bonusaufgabe erreicht, so gilt die reguläre Aufgabe ebenfalls als erfolgreich bearbeitet.
• Plagiate werden als nicht bearbeitet gewertet. Werden bei den Aufgaben mehrere Lösungen abgegeben, die im wesentlichen gleich sind, so werden diese Abgaben alle als Plagiate behandelt.

Lehr- und Lernmethoden:

Bearbeiten von wöchentlichen Hausaufgaben und deren Präsentation in den Übungen. Ausserdem sollen Präsenzaufgaben in den Übungen gelöst werden.

Verwendbarkeit:

Grundlage für viele Vorlesungen in der Informatik im Bachelor- und Masterstudiengang, insbesondere Lineare Optimierung, Effiziente Algorithmen und Approximative Algorithmen.

Literatur:

N. Blum: Algorithmen und Datenstrukturen: eine anwendungsorientierte Einführung, Oldenbourg, München, 2004, ISBN 3-486-27394-9

T.H. Cormen, C. E. Leiserson, R. L. Rivest, Clifford Stein: Introduction to Algorithms, MIT Press, Boston, 2001, ISBN 978-0-262-03384-8

K. Jansen, M. Margraf: Approximative Algorithmen und Nichtapproximierbarkeit, Walter de Gruyter, 2008, ISBN 978-3110203165

D.E. Knuth: The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed., Addison-Wesley, Boston, 1997, ISBN 978-0-201-89683-1

D.E. Knuth: The Art of Computer Programming. Vol. 3: Sorting and Searching, 2nd ed., Pearson Education, Boston, 1998, ISBN 978-0-201-89685-5

S.O. Krumke, H. Noltemeier: Graphentheoretische Konzepte und Algorithmen, Vieweg + Teubner, Wiesbaden, 2005, ISBN 978-3-8348-0629-1

H. Reß, G.Viebeck: Datenstrukturen und Algorithmen: objektorientiertes Programmieren in C++, Carl Hanser, Leipzig, 2000, ISBN 978-3446213623

R. Sedgewick: Algorithms in Java, Parts 1-4, 3rd ed., Addison Wesley, Boston, 2002, ISBN 978-0201361209

M.A. Weiss: Data Structures and Algorithm Analysis in Java, 2nd ed., Addison-Wesley, Boston, 2007, ISBN: 978-0321370136

K. Mehlhorn, P. Sanders: Algorithms and Data Structures: The Basic Toolbox, Springer, Berlin Heidelberg, 2008, ISBN 978-3-540-77977-3

Verweise:

Kommentar:

Dieses Modul entspricht dem Modul G2.1 der alten BSc-PO.