Theoretische Informatik Endklausur

Question	Answer
Was ist eine Berechnung?	Sei SC die Startkonfiguration dann heißt die Sequence unten Berechnung von x auf der Machine M Image: 568dde88-79f8-42d3-be9f-6e345b5bc3ca (image/png)
Definiere Zeitkomplexität	Image: 586ff074-b9d3-469e-91aa-69bddd001b54 (image/png)
Was misst Time(n)?	Time(n) misst die Zeit des Worst-Case bei einer Eingabe der Länge n
Sei C eine gültige Konfiguration, wie ist dann Space(C) definiert? Image: d547b629-9e22-4a4b-b3be-802393455284 (image/png)	Image: fd14dbcd-0a87-4c85-8ae7-96ca4da4c645 (image/png)
Wann und warum statten wir eine Turingmaschine mit einem extra input-Tape aus?	Zur Berechnung des Speicherverbrauches in der Space Funktion, da wir einen Speicherverbrauch der nicht von den Parametern abhängt berechnen wollen
Definiere DTime(t) und DkTime(t)	Image: ba6a7e20-de0d-48d9-addd-8d8f9dfdc36a (image/png)

Resource summary

	Created by Sven Ziegler over 10 years ago