Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

Arne

ThI

  • "Arne" is male
  • "Arne" started this thread

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

1

Monday, December 9th 2002, 6:00pm

Theo Inf Übungszettel Nr.8

http://www-thi.informatik.uni-hannover.d…en/uebung08.pdf


erst hatte ich mir bei Aufgabe2 überlegt, dass man das irgendwie mit den Buchstaben zählen machen könnte.. aber Matze meinte heute in der Vorlesung dass das nicht nötig sei sondern man mit dem hin- und hergehen auf dem Wort gehen würde...

jemand ne idee? ?(
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

2

Monday, December 9th 2002, 6:33pm

Quoted

Original von vier
http://www-thi.informatik.uni-hannover.d…en/uebung08.pdf


erst hatte ich mir bei Aufgabe2 überlegt, dass man das irgendwie mit den Buchstaben zählen machen könnte.. aber Matze meinte heute in der Vorlesung dass das nicht nötig sei sondern man mit dem hin- und hergehen auf dem Wort gehen würde...

jemand ne idee? ?(
Man könnte das Wort mehrfach durchlaufen und bei jedem Durchlauf jeweils z. B. das erste a, b und c streichen (bzw. durch eine spezielle Markierung ersetzen). Wenn dann irgendwann nur noch diese Markierungen auf dem Band stehen und während der Durchläufe nichts "Unerwartetes" (z. B. falsche Reihenfolge der Symbole) passiert, wird das Wort akzeptiert.
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message