Profil Effizienz und Korrektheit von Algorithmen
Algorithmen sind ein zentrales Thema der Informatik, weil sie dafür sorgen, dass sowohl grundlegende als auch hochspezialisierte Aufgaben automatisiert erledigt werden — z.B. für unsere nächste Websuche, Navigationsanfrage oder auch nur dafür, dass wir unsere Musikliste sortiert angezeigt bekommen können. Essentiell für Algorithmen sind dabei deren Effizienz und Korrektheit, denn Anfragen müssen häufig innerhalb kürzester Zeit beantwortet werden und eine unbeschränkte Anzahl von Fehlern ist meist nicht tolerierbar.
Zur Effizienz von Algorithmen
- zeigen wir, wie man diese überhaupt misst,
- entdecken wir Algorithmen, die auch für große Eingaben effizient sind,
- lernen Entwurfsparadigmen kennen, die auch bei unbekannten Problemen helfen,
- schlagen eine Brücke zur Praxis durch Implementieren theoretischer Ergebnisse,
- studieren konkrete Beispiele für leistungsfähige Lösungen herausfordernder Probleme
Zur Korrektheit von Algorithmen
- zeigen wir, wie wir diese beweisen oder algorithmisch verifizieren können,
- entdecken, wo die Grenzen für die von Algorithmen lösbaren Probleme liegen,
- lernen zertifizierende Algorithmen kennen, die die Ausgabe jeder Eingabe verifizieren.
Verantwortlich: Prof. Schmidt (jens.schmidtuni-rostockde), Prof. Wolf (karsten.wolfuni-rostockde)
Effizienz und Korrektheit von Algorithmen im Bachelor
- Einführung in Graphenalgorithmen
- Algorithm Engineering
- Parallele Algorithmen
- Automatisches Zeichnen von Graphen, WS
- Computational Geometry, WS
- Projekt „Kompetitive effiziente Programmierung“, „Weiterentwicklung von Modelchecking Tools“ oder „ACM-Challenge“, WS oder SS
Module aus der Mathematik, insbesondere aus den Gebieten diskrete Mathematik, Kombinatorik, Graphentheorie und Optimierung
Teilnahme an Veranstaltungen zu kompetitiver effizienter Programmierung inklusive regelmäßiger Fahrt zum NWERC (Northwestern Europe Regional Contest)
Auslandsaufenthalt
z.B. Yokohama National University, Japan / Ghent University, Belgium / KU Leuven, Belgium / La Trobe University, Melbourne, Australia / IIT Tirupati, India
Effizienz und Korrektheit von Algorithmen im Master
Veranstaltungen aus dem Wahlpflichtbereich “Komplexe Systeme”, z.B.
- Effiziente kombinatorische Optimierung, WS
- Computergestützte Verifikation, WS
- Verteilte Algorithmen, WS
- Algorithmische Graphentheorie, SS
- "Neueste Entwicklungen in der Informatik", etwa zu einem Thema wie „Algorithm Engineering“ oder „Algorithmischer Graphentheorie", WS oder SS