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
Vorlesung 4 SWS, Übung 4 SWS
10 LP
Learning results & Competences
After completing the first part the students can
- reproduce algorithmic and programming principles, and explain technical terms and basic methods,
- describe known algorithms and new algorithms based on pseudocode and Python code and apply them exemplarily to adequate problem settings,
- implement algorithms in Python and apply selected software engineering tools,
- distinguish between data structures (theoretically and in Python) and apply them in adequate contexts,
- interpret and visualise different types of data,
- analyse algorithms (e.g., compute and classify their running time) and prove their correctness,
- test their code and apply test driven development,
- evaluate code and apply refactoring techniques in order to improve code quality,
- operate a version control system and develop in groups,
- evaluate the quality of a given piece of code and provide reviews for improvement,
- create reproducible environments and build data science workflows, and
- design and develop algorithms based on known methods.
After completing the second part the students can:
- reproduce further algorithms, programming principles, and data structures,
- implement further algorithms in Python and apply selected software engineering tools,
- match algorithms to different algorithmic design paradigms and apply them exemplarily,
- adapt algorithms and data structures and transfer them to new contexts,
- design algorithms according to adequate design paradigms,
- classify and evaluate algorithms according to further analysis techniques, and
- classify algorithmic problems according to basic complexity classes.
Content
This course consists of two parts about algorithm design and programming. It provides an insight into algorithmic and programming tools, combining theoretical and practical methods that build a foundation for further courses in the Master of Articficial Intelligence and Data Science programme.
Winter term:
- Algorithmic foundations and data structures
- Introduction to the Python programming language
- Algorithm analysis (running time analysis, correctness proofs)
- Software engineering methods for code quality (software testing, code review, refactoring)
- Version control systems (e.g., git) and continuous integration
- Classic algorithms (e.g., sorting algorithms, graph algorithms) and data streams
- Selected packages (e.g., numpy, matplotlib, pandas)
- Data science workflows (e.g. snakemake), reproducible environments (e.g. docker)
Summer term:
- Algorithmic design principles (recursion, divide-and-conquer, dynamic programming, greedy algorithms) and their analysis
- Further application of Python programming and software development methods
- Further algorithms (e.g., sorting, search, graph algorithms, pattern matching)
- Further data structures (e.g., search trees, splay trees, B-trees, suffix trees, heaps, hashing)
- Object oriented programming
- Computational complexity (e.g., P vs. NP, NP-completeness)
Teaching
Lecture with (theoretical and practical) exercises
Prerequisites for attending
Formal: Admission to master studies in „Artificial Intelligence and Data Science“.
Contentual: none
Examination
Written examination after both courses about content of lectures and exercises
Prerequisites for receiving credit points
- Regular and active participation in the exercises
- Passing the examination
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
Vorlesung 4 SWS, Übung 4 SWS
10 LP
Learning results & Competences
After completing the first part the students can
- reproduce algorithmic and programming principles, and explain technical terms and basic methods,
- describe known algorithms and new algorithms based on pseudocode and Python code and apply them exemplarily to adequate problem settings,
- implement algorithms in Python and apply selected software engineering tools,
- distinguish between data structures (theoretically and in Python) and apply them in adequate contexts,
- interpret and visualise different types of data,
- analyse algorithms (e.g., compute and classify their running time) and prove their correctness,
- test their code and apply test driven development,
- evaluate code and apply refactoring techniques in order to improve code quality,
- operate a version control system and develop in groups,
- evaluate the quality of a given piece of code and provide reviews for improvement,
- create reproducible environments and build data science workflows, and
- design and develop algorithms based on known methods.
After completing the second part the students can:
- reproduce further algorithms, programming principles, and data structures,
- implement further algorithms in Python and apply selected software engineering tools,
- match algorithms to different algorithmic design paradigms and apply them exemplarily,
- adapt algorithms and data structures and transfer them to new contexts,
- design algorithms according to adequate design paradigms,
- classify and evaluate algorithms according to further analysis techniques, and
- classify algorithmic problems according to basic complexity classes.
Content
This course consists of two parts about algorithm design and programming. It provides an insight into algorithmic and programming tools, combining theoretical and practical methods that build a foundation for further courses in the Master of Articficial Intelligence and Data Science programme.
Winter term:
- Algorithmic foundations and data structures
- Introduction to the Python programming language
- Algorithm analysis (running time analysis, correctness proofs)
- Software engineering methods for code quality (software testing, code review, refactoring)
- Version control systems (e.g., git) and continuous integration
- Classic algorithms (e.g., sorting algorithms, graph algorithms) and data streams
- Selected packages (e.g., numpy, matplotlib, pandas)
- Data science workflows (e.g. snakemake), reproducible environments (e.g. docker)
Summer term:
- Algorithmic design principles (recursion, divide-and-conquer, dynamic programming, greedy algorithms) and their analysis
- Further application of Python programming and software development methods
- Further algorithms (e.g., sorting, search, graph algorithms, pattern matching)
- Further data structures (e.g., search trees, splay trees, B-trees, suffix trees, heaps, hashing)
- Object oriented programming
- Computational complexity (e.g., P vs. NP, NP-completeness)
Teaching
Lecture with (theoretical and practical) exercises
Prerequisites for attending
Formal: Admission to master studies in „Artificial Intelligence and Data Science“.
Contentual: none
Examination
Written examination after both courses about content of lectures and exercises
Prerequisites for receiving credit points
- Regular and active participation in the exercises
- Passing the examination
Vorlesung 2 SWS, Übung 2 SWS
5 LP
Inhalte
Die Veranstaltung ist eine weiterführende Algorithmenvorlesung, die sich mit Randomisierung als Entwurfs- und Analysemethode beschäftigt. Ziel ist es, durch zufällige Entscheidungen effiziente Algorithmen zu erhalten, die deutlich schneller als deterministische Varianten arbeiten und dabei mit möglichst hoher Wahrscheinlichkeit genaue Ergebnisse ausgeben.
• randomisierte Algorithmenmodelle (Las-Vegas- und Monte-Carlo-Algorithmen)
• Laufzeit und Genauigkeitsanalyse
• randomisierte Approximationsalgorithmen (z. B. für SAT- und Graphprobleme)
• Methoden zur Wahrscheinlichkeitsverstärkung
• randomisierte Entwurfsmethoden (z. B. probabilistische Methode, Fingerabdrücke, Hashing)
• Randomisierung in der Datenanalyse
Lernergebnisse/Kompetenzen
Nach erfolgreicher Teilnahme an den Veranstaltungen dieses Moduls können die Studierenden: - Begriffe und grundlegende Methoden der Randomisierung in der Algorithmik beschreiben, - Algorithmen unterschiedlichen Entwurfsparadigmen zuordnen und exemplarisch anwenden, - Eigenschaften wie Laufzeiten und Genauigkeiten randomisierter Algorithmen analysieren und dadurch bewerten und vergleichen und - erste randomisierte Algorithmen nach geeigneten Entwurfsmustern entwickeln.
Literatur
• Juraj Hromkovi¬: Randomisierte Algorithmen: Methoden zum Entwurf von zufallsgesteuerten Systemen für Einsteiger. Teubner-Verlag. Wiesbaden, 2004. 1. Ausgabe
• Michael Mitzenmacher and Eli Upfal: Probability and Computing. Cambridge University Press. Cambridge, 2017. 2nd Edition.
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 Algorithmen und Datenstrukturen, Theoretische Informatik und Mathematik für Informatik 3
Voraussetzungen für die Vergabe von Leistungspunkten
• aktive Teilnahme an den Übungen
• erfolgreiches Bearbeiten der Übungsaufgaben
• abschließende Prüfung (schriftlich oder mündlich)
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.