[Parametrisierte Algorithmen] H16 + H17

Vorlesungen, Seminare und Praktika aus dem Bereich Theoretische Informatik (Abkürzungen)
Lectures, seminars and labs from the area Theoretical Foundations (Abbreviations)

[Parametrisierte Algorithmen] H16 + H17

Beitragvon ibogi » 18.01.08 00:27

Hallo,

ich habe den Blick auf Hausaufgaben geworfen, und frage ich mich: was ist der Unterschid zwischen dem Fall wenn es kein beschränktes Alphabet gibt und dem Fall wenn es gibt? Was ist der Unterschied zwischen non multi-tape und multi-tape turing machine? Ich habe keine Idee wie anzufangen.
ibogi
 
Beiträge: 54
Registriert: 29.12.07 00:53

Beitragvon Tommytb » 18.01.08 01:08

Eine Multitape TM hat mehrere Schreib-/Leseköpfe, welche alle unabhängig voneinander bewegt werdne können. Eine Einband-TM hat nur einen kopf der bewegt werden kann. Und was für Auswirkungen die Beschränkung des Alphabets hat... tjoa, das überleg ich mir grade auch... vorschläge sind immer willkommen ;-)
Benutzeravatar
Tommytb
 
Beiträge: 427
Registriert: 27.05.06 16:56
Wohnort: Aachen
Studiengang: Informatik (Dipl.)
Anwendungsfach: E-Technik

Beitragvon ibogi » 21.01.08 00:03

Das erste Problem liegt in FPT, es ein sehr einfacher Algorithmus dafur lasst sich entwerfen. Fur zweites, ich vermute das es ist W[2] hart (versuche ich mit einer Reduktion von Dominating Set auf Short Turing Multi-Tape Machine Acceptance)
ibogi
 
Beiträge: 54
Registriert: 29.12.07 00:53

Beitragvon Tommytb » 21.01.08 14:44

genau so gehts ;-)
Benutzeravatar
Tommytb
 
Beiträge: 427
Registriert: 27.05.06 16:56
Wohnort: Aachen
Studiengang: Informatik (Dipl.)
Anwendungsfach: E-Technik


Zurück zu Theoretische Informatik / Theoretical Foundations