Manchmal hat ein Algorithmus eine große Eingabe, aber nur wenig frei beschreibbaren Arbeitsspeicher. Zum Beispiel könnte die Eingabe im Internet für Anfragen zur Verfügung stehen, aber in ihrer Gesamtheit so riesig sein, dass es unmöglich oder unpraktisch ist, sie auf den lokalen Rechner herunterzuladen.
Die Vorlesung beschäftigt sich aus theoretischer Sicht mit Algorithmen, die mit weniger Arbeitsspeicher als klassische Algorithmen für dieselben Probleme auskommen. Der Fokus liegt auf Graphenprobleme wie die Durchführung einer Tiefensuche oder die Berechnung starker Zusammenhangskomponenten, aber auch Sortieren und platzeffiziente Datenstrukturen kommen zur Sprache. Ein Großteil der in der Vorlesung vorgestellten Ergebnisse wurde seit 2014 am Lehrstuhl für Theoretische Informatik erzielt. Die Vorlesung behandelt somit ein sehr aktives und aktuelles Forschungsgebiet.
Anmelderegeln
Diese Veranstaltung gehört zum Anmeldeset "Anmeldung gesperrt (global)".
