Wiederkehrende Lehrveranstaltungen
In der Regel im Sommersemester
Vorlesung 2 SWS, Übung 2 SWS
5 LP
Inhalte
Dieses Modul vermittelt grundlegende Kenntnisse aus folgenden Bereichen.
• Suchmethoden auf Graphen
• Topologische Anordnungen
• Zusammenhangsprobleme
• Kürzeste Wege
• Minimale Spannbäume
• Netzwerkfluss-Probleme
• Matching-Probleme
Lernergebnisse/Kompetenzen
Nach erfolgreicher Teilnahme an den Veranstaltungen dieses Moduls können die Studierenden:
• die besprochenen Graphalgorithmen wiedergeben und erklären,
• die besprochenen Graphalgorithmen unterschiedlichen Problemstellungen zuordnen und geeignet anwenden,
• die besprochenen Graphalgorithmen auf ihre Laufzeit und Korrektheit hin analysieren und
• neue einfache Graphalgorithmen entwickeln und analysieren.
Literatur
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung. De Gruyter Oldenbourg. 2017. 4. Auflage.
• Ravindra Ahuja, Thomas Magnanti, James B. Orlin: Network Flows: Theory, Algorithms and Applications. Prentice Hall. Englewood Cliffs, 1993. 1. Ausgabe
Verwendbarkeit des Moduls
• Wahlbereich Bachelor-Studiengang PO 2021
• Wahlpflicht- und Schwerpunktbereich Bachelor-Studiengang PO 2013 und PO 2016
• Anwendungsfach im Bachelor-Studiengang Mathematik und Anwendungsgebiete
• Nebenfach im Bachelor-Studiengang Physik
• Nebenfach im Bachelor-Studiengang Medizinische Physik
Teilnahmevoraussetzungen
• Inhaltlich: Inhalte der Module Programmierung, Algorithmen und Datenstrukturen und Mathematik für Informatik 1
Voraussetzungen für die Vergabe von Leistungspunkten
• aktive Mitarbeit in den Übungen
• Abgabe der Hausaufgaben
• schriftliche Klausur
Vorlesung 2 SWS, Übung 2 SWS
5 LP
Inhalte
Diese Vorlesung ist eine weiterführende Algorithmenvorlesung, die die grundlegenden Konzepte aus dem Bereich der Approximationsalgorithmen einführt. Approximationsalgorithmen sind polynomiell zeitbeschränkte Algorithmen für schwere Optimierungsprobleme, für die eine beweisbare Gütegarantie für die Lösungen gilt. Besprochen werden Techniken für den Entwurf und die Analyse von Approximationsalgorithmen, insbesondere:
• gierige Algorithmen
• Approximationsalgorithmen für Graphprobleme
• Probleme mit euklidischen vs metrischen vs nicht-metrischen Eingaben
• (I)LP-basierte Algorithmen
• polynomielle Approximationsschemata
Lernergebnisse/Kompetenzen
Nach erfolgreicher Teilnahme an den Veranstaltungen dieses Moduls können die Studierenden:
• das Konzept „Approximationsgüte” erklären und Ergebnisse aus diesem Bereich einordnen,
• die besprochenen Optimierungsprobleme formal definieren,
• komplexe Beweise geeignet zusammenfassen und erklären,
• einfache Techniken für die Analyse von Approximationsgüten anwenden, und
• einfache Entwurfstechniken für Approximationsalgorithmen anwenden.
Literatur
• Vijay Vazirani: Approximation Algorithms. Springer-Verlag, Berlin, 2003. 1. Ausgabe
• David P. Williamson and David B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press, Cambridge, 2011, 1. Ausgabe.
Verwendbarkeit des Moduls
• Wahlpflichtbereich Theoretische Informatik
• Schwerpunktbereich
• Individuelle Ergänzung
• Anwendungsfach für den Ergänzungsbereich im Master-Studiengang Mathematik
Teilnahmevoraussetzungen
• Bachelor-Studierende müssen die Voraussetzungen für den Vorgriff auf Mastermodule erfüllen.
Voraussetzungen für die Vergabe von Leistungspunkten
• Aktive Mitarbeit in den Übungen
• Abgabe der Übungsaufgaben
• Bestehen der Klausur zum Ende des Semesters
Inhalte
In diesem Modul sollen Studierende das selbständige wissenschaftliche Arbeiten erwerben und sich auf die Master-Arbeit vorbereiten. Die Inhalte hängen deshalb sehr stark vom jeweiligen Fachgebiet und den Interessensgebieten der Person ab.
Lernergebnisse/Kompetenzen
Nach erfolgreicher Teilnahme an den Veranstaltungen dieses Moduls können die Studierenden:
• die wichtigen Konzepte des Fachgebiets der Projekt- bzw. zukünftigen Master-Arbeit zusammenfassen und veranschaulichen können
• wichtige Artikel und Bücher für spezifische Problemstellungen des Fachgebiets ermitteln können
• Konzepte des Fachgebiets hinterfragen können und entscheiden können welche für seine zukünftige Master-Arbeit in Betracht kommen
• die wissenschaftlichen Methoden des Fachbereichs beschreiben und anwenden können
Literatur
• In Absprache mit den Betreuungspersonen.
Verwendbarkeit des Moduls
• Projektarbeit
Voraussetzungen für die Vergabe von Leistungspunkten
• Die konkreten Anforderungen hängen von der zu bearbeitenden Aufgabenstellung ab. Daher sind die Kriterien zum Erwerb der Leistungspunkte zu Beginn der Projektarbeit individuell festzulegen.
3 LP
*: Während der Masterarbeit nehmen Studierende nach Absprache am Abschlusseminar für Bachelorstudierende oder am Oberseminar teil.
Inhalte
Im Rahmen des benoteten Abschlussseminars werden Thema und Ergebnisse der Abschlussarbeit der entsprechenden Arbeitsgruppe (oder einem Zusammenschluss solcher) mit anschließender wissenschaftlicher Diskussion präsentiert.
Lernergebnisse/Kompetenzen
Nach der Teilnahme am Abschlussseminar sind die Studierenden in der Lage
• ein selbstständig erarbeitetes Thema in einem Vortrag zu präsentieren
• wissenschaftlichen Vorträgen anderer Absolvent*innen zu folgen
• sich in die Diskussion zu wissenschaftlichen Vorträgen anderer Absolvent*innen einzubringen
Verwendbarkeit des Moduls
• Bachelorarbeit
Teilnahmevoraussetzungen
Die Abschlussarbeit muss angemeldet sein.
Voraussetzungen für die Vergabe von Leistungspunkten
Aktive Teilnahme am Abschlussseminar und Präsentation des eigenen Themas in einem mündlichen Vortrag mit Diskussion.
Im Oberseminar "Algorithmen und Datenstrukturen" werden Vorträge zu aktuellen Themen der Algorithmik von Mitarbeiter:innen des Lehrstuhls sowie von Gästen gehalten und aktuelle Forschungsthemen diskutiert.
Während der Masterarbeit nehmen Studierende nach Absprache am Abschlusseminar für Bachelorstudierende oder am Oberseminar teil.
In der Regel im Wintersemester
Vorlesung 4 SWS, Übung 2 SWS, Projektseminar 6 SWS
10 LP
Inhalte
Das Modul befasst sich mit einer Auswahl von grundlegenden Algorithmen und Datenstrukturen aus Theorie und Praxis. Anhand der vorgestellten Algorithmen und Datenstrukturen wird erläutert, wie der Ressourcenverbrauch (Rechenzeit- und Speicherplatzbedarf) theoretisch analysiert und vorhergesagt werden kann.
• Algorithmen und ihre formalen Grundlagen
• Rechenmodelle, Effizienzmaße
• Suchstrategien (Binärsuche)
• Sortierverfahren (Quicksort, Heapsort, Mergesort, …)
• Grundlegende Datenstrukturen (Arraylisten, verkettete Listen, Stacks und Queues)
• Suchbäume (Binärbäume, Balancierte Suchbäume)
• Dictionaries (offene Hashverfahren, dynamische Hashverfahren)
• Prioritätswarteschlangen (Binäre Heaps)
• Verwaltung von Mengensystemen (Union Find)
• Amortisierte Laufzeitanalyse
• Graphenalgorithmen (Tiefensuche, Breitensuche, Spannbäume, Kürzeste Wege)
• Entwurfsmuster (Greedyalgorithmen, Divide-and-Conquer, Dynamische Programmierung)
• Grenzen effizienter Algorithmen (Ausblick)
Lernergebnisse/Kompetenzen
Nach erfolgreicher Teilnahme an den Veranstaltungen dieses Moduls können die Studierenden:
• die vorgestellten Algorithmen/Datenstrukturen anwenden, analysieren und ihre Funktionsweise erklären,
• einen geeigneten Algorithmus/eine geeignete Datenstruktur für eine Problemstellung erkennen und aus einem Repertoire auswählen,
• aus einer natürlichsprachlichen Beschreibung eine Spezifikation eines Algorithmus oder einer Datenstruktur entwickeln und bestehende Spezifikationen erklären und Fragen dazu beantworten
• den Resourcenbedarf von Algorithmen und Datenstrukturen mit den fundamentalen Techniken der Vorlesung analysieren, vorhersagen und vergleichen,
• nachweisen, dass ein Algorithmus/eine Datenstruktur korrekt arbeitet und andere davon überzeugen und
• die vorgestellten Algorithmen und Datenstrukturen anpassen und kombinieren.
Literatur
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung. De Gruyter Oldenbourg. 2017. 4. Auflage.
• Robert Sedgewick, Kevin Wayne: Algorithmen. Pearson Studium. 2014. 4. Auflage.
• Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen. Spektrum. 2012. 5. Auflage.
• Jon Kleinberg, Eva Tardos: Algorithm Design. Addison Wesley. 2006.
Verwendbarkeit des Moduls
• Pflichtbereich Bachelor-Studiengang PO 2021
• Pflichtbereich Bachelor-Studiengang PO 2016, 2013
• Anwendungsfach im Bachelor-Studiengang Mathematik und Anwendungsgebiete
• Nebenfach im Bachelor-Studiengang Physik
• Nebenfach im Bachelor-Studiengang Medizinische Physik
• Modul CL6 im Bachelor-Studiengang Computerlinguistik
Teilnahmevoraussetzungen
• Inhalte des Moduls Mathematik für Informatik 1
Voraussetzungen für die Vergabe von Leistungspunkten
• aktive Mitarbeit in den Übungen
• Abgabe der Hausaufgaben
• schriftliche Klausur
Vorlesung 2 SWS, Übung 2 SWS
5 LP
Inhalte
Die Vorlesung ist eine weiterführende Algorithmenvorlesung, die sich mit Clusteringalgorithmen beschäftigt.
Wir besprechen in dieser Vorlesung vorwiegend kombinatorische Modellierungen von Clusteringproblemen
und zugehörige Algorithmen. Insbesondere geht es um folgende Themen:
• Hierarchisches Clustering
• Algorithmen für das k-center Problem
• Algorithmen für das k-supplier Problem
• ähnlichkeitsbasierte Clusteringverfahren.
Lernergebnisse/Kompetenzen
Nach erfolgreicher Teilnahme an den Veranstaltungen dieses Moduls können die Studierenden:
• kombinatorische Argumente wiedergeben und entwickeln,
• die besprochenen Clusteringalgorithmen anwenden,
• hierarchische Clusteringmethoden diskutieren und bewerten, und
• Clusteringverfahren analysieren.
Literatur
• Ausgewählte Veröffentlichungen zum Thema der Lehrveranstaltung.
• Eigenes Skript
Verwendbarkeit des Moduls
• Wahlbereich Bachelor-Studiengang PO 2021
• Wahlpflicht- und Schwerpunktbereich Bachelor-Studiengang PO 2013 und PO 2016
• Anwendungsfach im Bachelor-Studiengang Mathematik und Anwendungsgebiete
• Nebenfach im Bachelor-Studiengang Physik
• Nebenfach im Bachelor-Studiengang Medizinische Physik
Teilnahmevoraussetzungen
• Inhaltlich: Inhalte des Moduls Mathematik für Informatik 1
Voraussetzungen für die Vergabe von Leistungspunkten
• aktive Teilnahme an den Übungen
• erfolgreiches Bearbeiten der Übungsaufgaben
• abschließende Prüfung
Inhalte
In diesem Modul sollen Studierende das selbständige wissenschaftliche Arbeiten erwerben und sich auf die Master-Arbeit vorbereiten. Die Inhalte hängen deshalb sehr stark vom jeweiligen Fachgebiet und den Interessensgebieten der Person ab.
Lernergebnisse/Kompetenzen
Nach erfolgreicher Teilnahme an den Veranstaltungen dieses Moduls können die Studierenden:
• die wichtigen Konzepte des Fachgebiets der Projekt- bzw. zukünftigen Master-Arbeit zusammenfassen und veranschaulichen können
• wichtige Artikel und Bücher für spezifische Problemstellungen des Fachgebiets ermitteln können
• Konzepte des Fachgebiets hinterfragen können und entscheiden können welche für seine zukünftige Master-Arbeit in Betracht kommen
• die wissenschaftlichen Methoden des Fachbereichs beschreiben und anwenden können
Literatur
• In Absprache mit den Betreuungspersonen.
Verwendbarkeit des Moduls
• Projektarbeit
Voraussetzungen für die Vergabe von Leistungspunkten
• Die konkreten Anforderungen hängen von der zu bearbeitenden Aufgabenstellung ab. Daher sind die Kriterien zum Erwerb der Leistungspunkte zu Beginn der Projektarbeit individuell festzulegen.
3 LP
*: Während der Masterarbeit nehmen Studierende nach Absprache am Abschlusseminar für Bachelorstudierende oder am Oberseminar teil.
Inhalte
Im Rahmen des benoteten Abschlussseminars werden Thema und Ergebnisse der Abschlussarbeit der entsprechenden Arbeitsgruppe (oder einem Zusammenschluss solcher) mit anschließender wissenschaftlicher Diskussion präsentiert.
Lernergebnisse/Kompetenzen
Nach der Teilnahme am Abschlussseminar sind die Studierenden in der Lage
• ein selbstständig erarbeitetes Thema in einem Vortrag zu präsentieren
• wissenschaftlichen Vorträgen anderer Absolvent*innen zu folgen
• sich in die Diskussion zu wissenschaftlichen Vorträgen anderer Absolvent*innen einzubringen
Verwendbarkeit des Moduls
• Bachelorarbeit
Teilnahmevoraussetzungen
Die Abschlussarbeit muss angemeldet sein.
Voraussetzungen für die Vergabe von Leistungspunkten
Aktive Teilnahme am Abschlussseminar und Präsentation des eigenen Themas in einem mündlichen Vortrag mit Diskussion.
Im Oberseminar "Algorithmen und Datenstrukturen" werden Vorträge zu aktuellen Themen der Algorithmik von Mitarbeiter:innen des Lehrstuhls sowie von Gästen gehalten und aktuelle Forschungsthemen diskutiert.