Modulcode:	infADS2F-01a
Englische Bezeichnung:	Algorithms and Data Structures (2F)
Modulverantwortliche(r):	Prof. Dr. Klaus Jansen
Turnus:	jedes Jahr im SS (SS20 SS21)
Präsenzzeiten:	3V 3Ü
ECTS:	8
Workload:	45 Std. Vorlesung, 45 Std. Präsenzübung, 150 Std. Selbststudium
Dauer:	zwei Semester
Modulkategorien:	2F-BSc (2F-BSc Inf)
Lehrsprache:	Deutsch
Voraussetzungen:	Inf-ProgOO Inf-I1-2FNF Inf-I2-2F

Kurzfassung:

Die Themen dieses Moduls sind grundlegende algorithmische Verfahren zum effizienten Umgang mit (großen) Daten. Dies umfasst die Datenorganisation, -darstellung und -verarbeitung sowie die Analyse der Effizienz dieser Verfahren mit Hilfe mathematischer Methoden.

Lernziele:

• Einfache mathematisches Modellierungen durchführen.
• Grundlegende Beweistechniken anwenden.
• 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 mathematisch beschreiben nachweisen.
• Algorithmische Problemstellungen konstruktiv und effizient lösen.
• Korrektheitsbeweise für Graphalgorithmen führen.
• Algorithmen in Java implementieren.

Lehrinhalte:

• Mengentheoretische Grundlagen (Mengen, Konstruktionen auf Mengen, Potenzmengen und Kardinalitäten, Relationen und Funktionen)
• Folgen und Reihen
• Logische Grundlagen (Sprache und Ausdrucksweise der Mathematik, Aussagenlogik, Prädikatenlogik, induktive Definition)
• Mathematische Beweistechniken (Direkte Beweise, Indirekte Beweise, Beweis durch Widerspruch, Induktionsbeweise, strukturelle Induktion)
• 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, Zusammenhangskomponenten, kürzeste Wege, Minimal spannende Bäume)

Weitere Voraussetzungen:

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

Die für die Veranstaltung wesentlichen mathematischen Grundlagen werden für die Zweifachstudierenden jeweils im Wintersemester in einer Veranstaltung vorgestellt. Die Vorlesung findet jede Woche (insgesamt 7 Mal) statt. Am Ende dieser Veranstaltung wird eine kleiner Test geschrieben. Um die reduzierte Klausur im Sommersemester schreiben zu dürfen, muss dieser Test erfolgreich bestanden werden.

Prüfungsleistung:

1. Während des Semesters wird eine Zwischenklausur stattfinden. Am Ende des Semester wird eine schriftliche Klausur geschrieben.
2. Zum Bestehen der Veranstaltung muss die Endklausur bestanden werden. Die Endnote zum Modul ergibt sich aus der besten Note von
   2.1 30 Prozent Zwischenklausur plus 70 Prozent Endklausur
   2.2 100 Prozent Endklausur

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

Gerhard Berendt. Mathematik für Informatiker. Heidelberg: Spektrum, Akadem. Verlag, 1994

Rudolf Berghammer. Mathematik für Informatiker. Grundlegende Begriffe und Strukturen. 2., erweiterte und aktualisierte Auflage. Wiesbaden: Springer Vieweg, 2017. DOI: 10.1007/978-3-658-16712-7

Manfred Brill. Mathematik für Informatiker. Einführung an praktischen Beispielen aus der Welt der Computer. München: Hanser, 2001

Peter Hartmann. Mathematik für Informatiker. Ein praxisbezogenes Lehrbuch. 6., überarbeitete Auflage. Wiesbaden: Springer Vieweg, 2015. DOI: 10.1007/978-3-658-03416-0

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

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:

Das Modul besteht aus zwei Lehrveranstaltungen in aufeinanderfolgenden Semesters. Die Lehrveranstaltung im Wintersemester bereitet die mathematischen Grundlagen für die Lehrveranstaltung im Sommersemester (Algorithmen und Datenstrukturen) vor.