Fachrat Informatik - Forum

Zu 1. und 2.: Auf jeden Fall separates Eingabeband! Sonst wäre es ja sofort linearer Platzbedarf.
1. Generell Algorithmen, deren Eingabe n Objekte enthält und die sich nur eine konstante Anzahl von Positionen darin merken müssen. Da die Positionen z.B. binär codiert werden können (oder allgemeiner: nicht nur unär, sondern auch zu anderen Basen) ergibt sich der logarithmische Platzbedarf. Zum Beispiel: Entscheidungs-Algorithmus für die Sprache {<a,b,c> | a + b = c}, da der aber Inhalt eines der Testate ist kann ich da nicht näher drauf eingehen.
2. Spontan keine sinnvolle Idee. Irgendein Algorithmus, der sich linear viele Positionen merken muss. Die Ideen, die ich dazu bisher habe sind nicht sinnvoll, funktionieren nichtmal so ganz und würden nur verwirren.

zu 3. und 4. hab ich spontan keine Idee auf Turingmaschinen. Als "normale" Algorithmen, also mit wahlfreiem Zugriff auf den Speicher (z.B. durch Verweise in einem Baum) gibts natürlich folgende Standardbeispiele:
3. Suche im ausbalancierten binären Suchbaum
4. Merge-Sort

Hoffe das hilft schon ein bisschen.

Da ich nicht eine Lösung für die Testataufgaben hier reinschreiben will ein anderes (einfacheres) Beispiel für 1:



Ein Entscheidungsalgorithmus für diese Sprache muss Position für Position durch die beiden Wörter gehen und jeweils vergleichen, ob beide Zeichen gleich sind. Dafür genügt es, auf deim Arbeitsband binär hochzuzählen, die wievielte Stelle man gerade vergleichen will UND außerdem, um dann jeweils die richtige Position in bzw. zu erreichen, die aktuelle Position ein zweites mal aufs Arbeitsband zu schreiben und immer wieder 1 zu subtrahieren, bis 0 erreicht wird (in dem Moment wird die richtige Position in bzw. erreicht). Auf diese Weise ist der höchste vorkommende Platzbedarf zweimal der Platzbedarf für die Binärdarstellung der Anzahl von Zeichen von + ein Trennzeichen, also .

Ich bin jetzt nicht auf jedes Detail eingegangen, insbesondere für unterschiedlich lange Wörter braucht man natürlich noch eine Prüfung.

Ein Algorithmus, der tatsächlich benötigt (und nicht mit weniger auskommt) müsste sich entsprechend so etwas wie verschiedene Positionen merken. Dazu habe ich bisher keine gute Idee für ein Beispiel.

Viele Grüße,
Anselm

Quoted from "Anselm"

Zu 1. und 2.: Auf jeden Fall separates Eingabeband! Sonst wäre es ja sofort linearer Platzbedarf.

Also eine Sprache in benötigt kein separates Eingabeband. Ein Beispiel hierfür ist zum Beispiel eine Pfadsuche in einem Graphen. Eine mögliche Lösung wäre die naive Konstruktion des Pfades über Breitensuche, bei der der gesamte Pfad immer im Speicher gehalten (und schrittweise konstruiert) wird. Hierzu müssen wir uns Knotenanzahl (des Pfades) mal Knotennummern merken. Die Knotennummern können wir uns binär speichern, wodurch der logarithmische Faktor zu tragen kommt. Im schlimmsten Fall ist der Pfad so lang wie es Knoten im Graphen gibt. Die Knotenanzahlen sind durch nach oben beschränkt, daher erhält man einen Algorithmus mit Speicherbedarf .

Klarer geworden?

Man kann den Pfad auch hinter die Eingabe schreiben. Klar, damit wird die TM aufwendiger - aber der Platzbedarf bleibt in . Insofern stimmt natürlich, dass nur für 1. ein separates Eingabeband nötig ist.

Wo wir grad dabei sind.... ich habe vergessen, welche Hilfsmittel wir bei der Klausur nutzen dürfen. Skript? Beidseitig beschriebenes DIN-A4-Blatt? Nix?

http://www.thi.uni-hannover.de/166.html

Quoted

Komplexität von Algorithmen, Montag, 02.09.13, 15:00 - 16:15, E-214 (Großer Physiksaal, Hauptgebäude); Erlaubte Hilfsmittel: 1 DinA4 Zettel beliebig beidseitig beschrieben/bedruckt.

Ah, danke!