Schatzsuche mit minimalem Speicherplatz
Wie kann man in einem Falltürenlabyrinth mit sehr viel Rechenzeit, aber enorm wenig Speicherplatz, herausfinden, ob darin ein Schatz versteckt ist? (Satz von Immerman und Szelepcsenyi)
Vorgestellt wird folgende Frage: in einem Irrgarten, den man beliebig oft durchlaufen kann und bei dem jeder Raum mit zwei weiteren Räumen verbunden ist, man aber nach dieser Entscheidung nicht wieder zurückgehen kann (Falltürenlabyrinth), wird nach einem Schatz gesucht. Dabei steht beliebig viel Zeit, aber fast gar kein Speicherplatz zur Verfügung. Insbesondere ist es nicht möglich, eine vollständige Karte vom Labyrinth zu zeichnen. Wie kann man trotzdem herausfinden, ob es tatsächlich einen Schatz im Labyrinth gibt?
Die Frage veranschaulicht den Beweis von Immerman und Szelepcsenyi, der zeigt, dass nichtdeterministische Raumkomplexitätsklassen (NSPACE-Klassen) unter Komplement abgeschlossen sind.
Additional information
| Type | Workshop |
|---|---|
| Language | German |
More sessions
| 10/3/24 |
Programme gleichzeitig im selben Speicher ausführen: was könnte schon schiefgehen? Hier geht's um das wie und anschließend selber mal hands-on damit spielen. Wir schauen uns den Unterbau an, bauen eigene kleine Programme die dann gegenseitig versuchen sich zu überschreiben.
|
| 10/3/24 |
Du wolltest schon immer mal deine eigenen 3D-Modelle entwerfen? Dir war FreeCAD zu kompliziert, als du es das letzte Mal verwendet hast? Hier erhältst du eine kurze Einweisung wie man in FreeCAD modellieren kann.
|
| 10/4/24 |
Mate trinken und erleben mit Meta Mate. Lass uns darüber sprechen, wie wir auf nachhaltige Weise mit Energie versorgen und etwas tun können, das gesund und glücklich macht. Egal, ob Sie Mate zum ersten Mal trinken oder ob Sie es jeden Tag tun, diese Veranstaltung ist offen für alle, die neugierig sind, das ursprüngliche Getränk der commons kennenzulernen.
|
| 10/4/24 |
Hast du dich schon mal gefragt, wie die Glasfaser eigentlich zu dir nach Hause kommt? In diesem Spliceworkshop schauen wir uns den praktischen Teil davon an, also wie man dafür sorgt, dass das Licht von A nach B kommt. Der Workshop ist dabei genau das – ein Workshop. Das heißt jeder kann praktisch ausprobieren einen Splice zu machen, sprich, zwei Glasfaserenden zu verbinden. Wenn die Zeit reicht schauen wir uns auch noch ein paar Messwerkzeuge rund um Glasfasern an.
|
| 10/5/24 |
Für Kinder, Jugendliche und alle anderen, die zu neuen Ufern aufbrechen wollen Programmieren ist für dich bisher (fast) unbekanntes Gewässer? Wir helfen dir bei den ersten Schwimmversuchen! Programmiert werden Microcontroller mit einer graphischen Programmiersprache.
|
| 10/5/24 |
Das Stricken vom ne Mützen* mit der Rundnadel. Eine "Analog Werkstatt" , Craft, Knitting, Hat,Beanie
|
| 10/6/24 |
Wir programmieren ein kleines Spiel mit dem fantasy computer TIC-80.
|
