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.

Currywurst mit Pommes

Erfahrener Schreiberling

  • "Currywurst mit Pommes" started this thread

Posts: 438

Date of registration: Oct 14th 2002

1

Sunday, September 16th 2007, 4:47pm

KvA Klausur

Hier nun der offizielle Thread :)

Gibt's eigentlich Lösungen für Aufgabe 4 und 5 der Übungen ?

Ach ja, und zu 6) Besucht eine TM nicht n+1 Bandzellen bei n Rechenschritten ? In der Übungslösung war nur von n die Rede.

This post has been edited 1 times, last edit by "Currywurst mit Pommes" (Sep 16th 2007, 5:13pm)

  • Send private message

Currywurst mit Pommes

Erfahrener Schreiberling

  • "Currywurst mit Pommes" started this thread

Posts: 438

Date of registration: Oct 14th 2002

2

Monday, September 17th 2007, 11:51am

In Aufgabe 9 wird gezeigt, dass
A element von TIME(f(n)) <=> (Strich über) A element von TIME(f(n)) ist.

Logisch, denn eine TM kann A in O(f(n)) entscheiden.
D.h. ist ein Wort element von A, so akzeptiert die TM dies in O(f(n)) Zeit.
Ist ein Wort Element von (Strich über) A, also NICHT Element von A, so verwirft die TM dies ebenfalls in O(f(n)).

Ich muss also nur eine TM' entwickeln, die TM simuliert und das Ergebnis "akzeptieren/ablehnen" vertauscht.


Warum aber gilt dies nicht für
A element von NTIME(f(n)) <=> (Strich über) A element von NTIME(f(n)) ?

Mir ist klar, dass es bei nicht-determ. Algorithmen mehrere akzeptierende Zustände, etc. gibt. Aber is das nicht egal ?

Denn auch hier gilt doch: Eine NTM kann A entscheiden in O(f(n))

-> Ist ein Wort element von A, so akzeptiert eine NTM dies in O(f(n))
-> Ist ein Wort element von (Strich über) A, also NICHT in A, so verwirft eine NTM dies in O(f(n)).

Jetzt kann ich doch auch hier wieder einen Schritt anhängen, in dem ich akzeptieren/ablehnen vertausche. Somit bleibt es weiterhin O(f(n)).

Oder liegts an der Mitschrift ? :)

Danke!
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

3

Monday, September 17th 2007, 12:02pm

Quoted

Original von Currywurst mit Pommes
In Aufgabe 9 wird gezeigt, dass
A element von TIME(f(n)) <=> (Strich über) A element von TIME(f(n)) ist.

Logisch, denn eine TM kann A in O(f(n)) entscheiden.
D.h. ist ein Wort element von A, so akzeptiert die TM dies in O(f(n)) Zeit.
Ist ein Wort Element von (Strich über) A, also NICHT Element von A, so verwirft die TM dies ebenfalls in O(f(n)).

Ich muss also nur eine TM' entwickeln, die TM simuliert und das Ergebnis "akzeptieren/ablehnen" vertauscht.


Warum aber gilt dies nicht für
A element von NTIME(f(n)) <=> (Strich über) A element von NTIME(f(n)) ?

Mir ist klar, dass es bei nicht-determ. Algorithmen mehrere akzeptierende Zustände, etc. gibt. Aber is das nicht egal ?

Denn auch hier gilt doch: Eine NTM kann A entscheiden in O(f(n))

-> Ist ein Wort element von A, so akzeptiert eine NTM dies in O(f(n))
-> Ist ein Wort element von (Strich über) A, also NICHT in A, so verwirft eine NTM dies in O(f(n)).

Jetzt kann ich doch auch hier wieder einen Schritt anhängen, in dem ich akzeptieren/ablehnen vertausche. Somit bleibt es weiterhin O(f(n)).

Oder liegts an der Mitschrift ? :)

Danke!


Das Problem ist, dass das Akzeptanzverhalten von NTMs anders ist als du beschreibst. Eine NTM spannt bei einer Rechnung immer einen kompletten Berechnungsbaum auf. Wenn dabei mindestens ein Pfad enthalten ist, der in einen akzeptierenden Zustand führt, so akzeptiert die NTM. Gibt es keinen solchen Pfad, so verwirft sie. D.h. du kannst da nichts an's Ende der Berechnung anhängen, da du immer einen kompletten Berechnungsbaum hast. Dann kann man natürlich auf die Idee kommen akzeptierende und verwerfende Zustände zu tauschen, aber dann fällt man in die folgende Falle:
Sagen wir einfach mal es gäbe 50/50 akzeptierende und verwerfende Zustände bei einer Berechnung; d.h. das Wort ist ja in der Sprache, da es mindestens einen Pfad gibt, der in einem akzeptierenden Zuständ anhält. Wenn du jetzt diese akz. und verw. Zustände tauscht, hast du aber immer noch 50/50 akz. und verw. Zustände, und wärst demnach immer noch in der Sprache, wobei du jedoch keinen Berechnungspfad haben dürftest, der in einem akz. Zustand landet.

Hat das geholfen? ;)
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

4

Monday, September 17th 2007, 12:09pm

RE: KvA Klausur

Quoted

Original von Currywurst mit Pommes
Hier nun der offizielle Thread :)

Gibt's eigentlich Lösungen für Aufgabe 4 und 5 der Übungen ?

Würden vermutlich in deiner Übung besprochen. Wenn Du willst, kannst Du Deine Lösung skizzieren und ich schreib Dir, ob sie korrekt ist.

Quoted

Original von Currywurst mit Pommes
Ach ja, und zu 6) Besucht eine TM nicht n+1 Bandzellen bei n Rechenschritten ? In der Übungslösung war nur von n die Rede.


Kommt darauf an, wie man Rechenschritt definiert. Aber macht das bei Aufgabe 6 jetzt so viel aus? Da geht es doch nur darum zu zeigen, dass wenn man in TIME(f(n)) etwas lösen kann, es auch in SPACE(f(n)) löst, für eine Funktion f:N->N. Da würde die +1 doch in der O-Notation eh als Konstante wegfallen.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

Currywurst mit Pommes

Erfahrener Schreiberling

  • "Currywurst mit Pommes" started this thread

Posts: 438

Date of registration: Oct 14th 2002

5

Monday, September 17th 2007, 3:12pm

Quoted

Original von Arne
Hat das geholfen? ;)


Danke Dir. Ich hab meine zwei Denkfehler jetzt wohl aufgedeckt.

Ich hab mir das nochmal anhand von SAT als NP-Problem klar gemacht:
Hätte ich als eingabe "x1 ^ x2", so würde der nicht-determ. Alg. die Belegung 1 und 1 raten und dann akzeptieren. Alle anderen möglichen Pfade würden zur Ablehung führen.
Würde ich nun (wie von mir erst vorgeschlagen) Akzeptieren/Ablehnen vertauschen, so würde "x1 ^ x2" immer noch akzeptiert werden, weil der nd. Algorithmus dann z.B. 0 0 raten würde, was zwar "falsch" wäre, aber durch das Vertauschen akzeptiert würde.

Quoted


Kommt darauf an, wie man Rechenschritt definiert. Aber macht das bei Aufgabe 6 jetzt so viel aus?


Nein, macht es nicht. Aber ich dachte ich frage nur mal vorsichtshalber. Nicht, dass mal eine Aufgabe dran kommt wo es wichtig sein ... könnte.
  • Send private message

Currywurst mit Pommes

Erfahrener Schreiberling

  • "Currywurst mit Pommes" started this thread

Posts: 438

Date of registration: Oct 14th 2002

6

Monday, September 17th 2007, 6:11pm

Aufgabe 11 d) gibt es leider keine schriftliche Lösung.

f(n) = n^k ist raumkonstuierbar

Meine Idee:

- Fahre zum letzten Symbol rechts (also vor dem ersten Blank)
- Überschreibe Symbol mit X
- Fahre nach ganz rechts auf das erste Blank
- Schreibe k-mal Symbol X
- Fahre nach links bis zum ersten Symbol vor einem X
- Ist dies ein Blank: Fertig, sonst: Fahre fort bei Schritt 2

Gut ? :)
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

7

Monday, September 17th 2007, 6:42pm

Was macht Deine Maschine, wenn k=1 und die Eingabelänge n ist?
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

Currywurst mit Pommes

Erfahrener Schreiberling

  • "Currywurst mit Pommes" started this thread

Posts: 438

Date of registration: Oct 14th 2002

8

Monday, September 17th 2007, 6:57pm

Quoted

Original von Arne
Was macht Deine Maschine, wenn k=1 und die Eingabelänge n ist?


Ja, sehe gerade, ist insgesamt Mist. Werde nochmal 'drüber nachdenken.
  • Send private message

Currywurst mit Pommes

Erfahrener Schreiberling

  • "Currywurst mit Pommes" started this thread

Posts: 438

Date of registration: Oct 14th 2002

9

Monday, September 17th 2007, 7:59pm

Okay. Ich lass es erstmal...

This post has been edited 4 times, last edit by "Currywurst mit Pommes" (Sep 17th 2007, 8:19pm)

  • Send private message

Currywurst mit Pommes

Erfahrener Schreiberling

  • "Currywurst mit Pommes" started this thread

Posts: 438

Date of registration: Oct 14th 2002

10

Tuesday, September 18th 2007, 11:12am

So, nach mehreren Versuchen habe ich verschiedene Algorithmen die zwar lustige Dinge tun, aber kurz vor Schluss merke ich immer, dass er doch nicht ganz das tut was ich will (n*k, oder k*n^n oder so , ...)

Dies wäre wieder ein Fall, wo ich für eine offizielle Lösung dankbar wäre. Hab leider nur welche für a) und b).

This post has been edited 1 times, last edit by "Currywurst mit Pommes" (Sep 18th 2007, 11:14am)

  • Send private message

Jojo

Trainee

  • "Jojo" is male

Posts: 94

Date of registration: Nov 16th 2005

Location: Foreign Recruit :)

Occupation: Programmierer

11

Tuesday, September 18th 2007, 1:16pm

Es ist folgende Aufg gegeben:
Nehmen Sie an, dass Sie drei Turingmaschinen M1, M2 und M3 vorliegen haben, die jeweils
eine Menge L entscheiden. Bei Eingabelänge n arbeite die Maschine M1 in Zeit O(n_hoch_2), die
Maschine M2 in Zeit O(2_hoch_n) und die Maschine M3 in Zeit O(n + 5).
Sei nun x eine Eingabe der Länge 12. Läßt sich mit den obigen Informationen feststellen,
welcher der drei Algorithmen die Zugehörigkeit von x zur Menge L mit der geringsten Anzahl
an Rechenschritten entscheidet? Falls ja: Welcher dieser Algorithmen ist es? Begründen Sie
Ihre Antworten.

wuerde es reichen wenn man O(n+5) waehlt und sagt da 12+5< als die anderen Alternativen od muss man wieder formal irgendwie bescreiben
  • Send private message

Jojo

Trainee

  • "Jojo" is male

Posts: 94

Date of registration: Nov 16th 2005

Location: Foreign Recruit :)

Occupation: Programmierer

12

Tuesday, September 18th 2007, 1:45pm

noch eine Frage:
ueb03 aufg 15
man weiss dass R von Typ 3 ist und nach der Zeit-Platz Einordnung die haben TIME(n) also R ist von TIME(s(n)) => A vereinigt mit R kann nicht groesser sein als SPACE(s(n)) da TIME(s(n)) unter Menge von SPACE(s(n)) ist die Loesung ausreichend ?
  • Send private message

Currywurst mit Pommes

Erfahrener Schreiberling

  • "Currywurst mit Pommes" started this thread

Posts: 438

Date of registration: Oct 14th 2002

13

Tuesday, September 18th 2007, 2:18pm

Quoted

Original von Jojo
Es ist folgende Aufg gegeben:
Nehmen Sie an, dass Sie drei Turingmaschinen M1, M2 und M3 vorliegen haben, die jeweils
eine Menge L entscheiden. Bei Eingabelänge n arbeite die Maschine M1 in Zeit O(n_hoch_2), die
Maschine M2 in Zeit O(2_hoch_n) und die Maschine M3 in Zeit O(n + 5).
Sei nun x eine Eingabe der Länge 12. Läßt sich mit den obigen Informationen feststellen,
welcher der drei Algorithmen die Zugehörigkeit von x zur Menge L mit der geringsten Anzahl
an Rechenschritten entscheidet? Falls ja: Welcher dieser Algorithmen ist es? Begründen Sie
Ihre Antworten.

wuerde es reichen wenn man O(n+5) waehlt und sagt da 12+5< als die anderen Alternativen od muss man wieder formal irgendwie bescreiben


Meiner Meinung nach lässt sich kein Algorithmus wählen, da die O Notation das Wachstum für n -> Unendlich angibt. n ist in diesem Fall aber klein (12). So könnte die M3 Maschine in der Zeit 100000000000 * n + 5 arbeiten und damit in diesem Fall die schlechteste Wahl sein. Siehe Definition von O(...).

This post has been edited 1 times, last edit by "Currywurst mit Pommes" (Sep 18th 2007, 2:18pm)

  • Send private message

Jojo

Trainee

  • "Jojo" is male

Posts: 94

Date of registration: Nov 16th 2005

Location: Foreign Recruit :)

Occupation: Programmierer

14

Tuesday, September 18th 2007, 2:27pm

du hast natuerlich recht habe total vergessen dass man n -> unendlich wachsen laesst.
  • Send private message

aliaatreides

Praktikant

  • "aliaatreides" is female

Posts: 24

Date of registration: May 3rd 2007

Occupation: 4. Semester Informatik

15

Wednesday, September 19th 2007, 8:50pm

Quoted

Original von Currywurst mit Pommes
So, nach mehreren Versuchen habe ich verschiedene Algorithmen die zwar lustige Dinge tun, aber kurz vor Schluss merke ich immer, dass er doch nicht ganz das tut was ich will (n*k, oder k*n^n oder so , ...)

Dies wäre wieder ein Fall, wo ich für eine offizielle Lösung dankbar wäre. Hab leider nur welche für a) und b).


my 2 cents: INDUKTION!
I must not fear. Fear is the mind-killer.
Fear is the little-death that brings total obliteration.
I will face my fear.
I will permit it to pass over me and through me.
  • Send private message

aliaatreides

Praktikant

  • "aliaatreides" is female

Posts: 24

Date of registration: May 3rd 2007

Occupation: 4. Semester Informatik

16

Thursday, September 20th 2007, 10:34pm

Jemanden ne Idee wie soll ich bei Aufgabe 28 einfangen?

Aufgabe 28
Es sei Sigma ein Alphabet. Beweisen Sie die folgende Aussage: Ist P = NP, so sind alle ueber Sigma, die in NP liegen, NP-vollstaendig bis auf 'leere Menge' und Sigma^*.

Danke!
I must not fear. Fear is the mind-killer.
Fear is the little-death that brings total obliteration.
I will face my fear.
I will permit it to pass over me and through me.
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

17

Thursday, September 20th 2007, 10:41pm

Tipp: zeig erstmal, dass alle anderen Sprachen (außer Sigma* und Emptyset) NP-hart sind. Dann überleg, warum das auf die beiden nicht zutrifft.
"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)

18

Friday, September 21st 2007, 11:47am

Quoted

Original von Arne
Tipp: zeig erstmal, dass alle anderen Sprachen (außer Sigma* und Emptyset) NP-hart sind. Dann überleg, warum das auf die beiden nicht zutrifft.
Andersrum ist es vielleicht einfacher: Mache Dir zunächst klar, warum kein NP-vollständiges Problem (also z. B. SAT) auf Sigma^* und \emptyset reduziert werden kann.
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message

Jojo

Trainee

  • "Jojo" is male

Posts: 94

Date of registration: Nov 16th 2005

Location: Foreign Recruit :)

Occupation: Programmierer

19

Friday, September 21st 2007, 11:53am

Nehmen wir zwei Sprachen A, B nicht aus {emptySet, Sigma*} Dann haben wir eine Reduktionsfkt die bei einer Eingabe liefert entweder x und y wobei x aus B und y nicht aus B

f(w) = { x, falls w aus A und y, sonst

Wenn man annimmt dass die Sprachen aus {emptySet, Sigma*} sind, dann kann man keine Reduktionsfkt defienieren dass auf das leere Wort abbildet da diese Menge keine Woerter enthaelt

Ich hoffe es reicht als Loesung ;)

This post has been edited 2 times, last edit by "Jojo" (Sep 21st 2007, 12:30pm)

  • Send private message

Currywurst mit Pommes

Erfahrener Schreiberling

  • "Currywurst mit Pommes" started this thread

Posts: 438

Date of registration: Oct 14th 2002

20

Friday, September 21st 2007, 5:11pm

Meine Idee für die hier angesprochene Aufgabe 28

Es sei Sigma ein Alphabet. Beweisen Sie die folgende Aussage: Ist P = NP, so sind alle Sprachen ueber Sigma, die in NP liegen, NP-vollstaendig bis auf 'leere Menge' und Sigma^*.

ist:

Source code

 
1
2
3
4
5
6
7
8
9
10
11
12

Eine Sprache A ist NP-vollständig wenn
  1) A in NP
  2) A NP-hart ist, also alle Sprachen aus NP auf A polynonminell reduziert werden können

Zu 1) Dies ist als Vorraussetzung durch die Aufgabe gegeben

Zu 2) Es ist zu zeigen, dass jede beliebige Sprache X aus NP auf A reduziert werden kann.
Dazu muss eine Funktion bzw. ein Algorithmus bekannt sein, der Reduktion in poly. Zeit ermöglicht.
Es gilt bei dieser Aufgabe NP = P, also kann X in poly. Zeit entschieden werden. Die Reduktion erfolgt also so:
* Entscheide X
* Wird X akzeptiert/(abgelehnt), so probiere solange alle Wörter aus dem Alphabet der Sprache von A aus, bis A akzeptiert(/ablehnt). Gib dieses Wort aus.
Der Suchvorgang kann in endlicher Zeit geschehen, da die Anzahl der Wörter in A endlich ist. Bei leerer Menge gäbe es kein Wort, das für Akzeptieren ausgegeben werden könnte. Ist A = Sigma*, so wäre kein Wort für Ablehnen zu finden.


Vielleicht kann Arne ja noch etwas dazu sagen.
  • Send private message