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 SS22)
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 (15)) 2F-BSc (2F-BSc Inf) G (BSc WInf (15)) G (BSc Inf) G (BSc Inf (2-Fach)) G (BSc WInf) INF-Math (Inf. als NF) 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 einschätzen.
• Korrektheit von Algorithmen beweisen.
• Algorithmische Problemstellungen effizient lösen.
• Algorithmen in Java implementieren.

Lehrinhalte:

• Laufzeitanalyse von Algorithmen
• Pessimale und durchschnittliche Laufzeiten
• Algorithmische Methoden
• Grundlegende Datenstrukturen
• Sortieralgorithmen, Suchverfahren, Graphalgorithmen
• Ausblick: approximative Algorithmen

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. Am Ende des Semester wird eine schriftliche Klausur geschrieben.
2. Zum Bestehen der Veranstaltung muss die Klausur bestanden werden. Die Endnote des Moduls ist die Klausurnote.

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 drei Aufgabenserien weniger als 40 Prozent der Punkte erreichen, die Sie durch Theorieaufgaben erreichen können.
• Es werden 4 Programmieraufgaben gestellt, von denen Sie mindestens 3 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 wird eine fünfte Bonus-Programmieraufgabe gestellt. Wenn diese erfolgreich bearbeitet wird, kann mit ihr eine nicht erfolgreich bearbeitete Programmieraufgabe ausgeglichen werden.
• 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 sowie das Lösen von Programmieraufgaben. Ausserdem werden Übungsaufgaben in den Übungen besprochen.

Verwendbarkeit:

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

Literatur:

Hinweis: Die Online-Versionen sind nur aus dem Uninetz (zB. per VPN) heraus verfügbar.

• Klaus Jansen, und Marian Margraf: Approximative Algorithmen und Nichtapproximierbarkeit, Walter de Gruyter, 2008. Online-Version
• Norbert Blum: Algorithmen und Datenstrukturen: eine anwendungsorientierte Einführung, Oldenbourg 2004.
• Thomas H. Cormen, Charles E. Leiserson, und Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, Boston: MIT Press Vol 3, 2009. Online-Version
• Martin Dietzfelbinger, Kurt Mehlhorn, Peter Sanders: Algorithmen und Datenstrukturen - Die Grundwerkzeuge, Springer Vieweg 2014. Online-Version
• Donald E. Knuth: The Art of Computer Programming. Vol. 1: Fundamental Algorithms, 3rd ed., Addison-Wesley 1997. Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley 1998.
• Sven Oliver Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen, Teubner 2005.
• Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen, Springer Vieweg 2017. Online-Version
• Harald Reß und Günter Viebeck: Datenstrukturen und Algorithmen: objektorientiertes Programmieren in C++, Hanser 2000.
• Robert Sedgewick: Algorithms in Java, Parts 1-4, 3rd ed., Addison-Wesley, 2002.
• Mark Allen Weiss: Data Structures and Algorithm Analysis in Java, 2nd ed., Addison-Wesley, 2007.

Verweise:

Kommentar:

Im SS 22 findet keine Vorlesung statt. Die Videos aus dem Vorjahr werden zur Verfügung gestellt und es finden Übungen und Klausurvorbereitung statt.