KVA Fragen und Antworten - Page 2 - Grundlagen der Informatik - Fachrat Informatik

Skuld

Erfahrener Schreiberling

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

21

Sunday, September 5th 2010, 3:26pm

Bin gerade ein wenig verdutzt.

Übungsblatt 3: (Klausuraufgabe WS 05/06): Beweisen Sie: $NTIME(n) \subseteq PSPACE$
Übungsblatt 4: (Klausuraufgabe WS 05/06): Beweisen Sie: $NTIME(n) \not \subseteq PSPACE$

Was stimmt denn nun?

Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

Go to the top of the page

Panoramix

Trainee

Posts: 115

Date of registration: Sep 12th 2008

22

Sunday, September 5th 2010, 4:06pm

Quoted from "Skuld"

Bin gerade ein wenig verdutzt.

Übungsblatt 3: (Klausuraufgabe WS 05/06): Beweisen Sie: $NTIME(n) \subseteq PSPACE$
Übungsblatt 4: (Klausuraufgabe WS 05/06): Beweisen Sie: $NTIME(n) \not \subseteq PSPACE$

Was stimmt denn nun?

Bei 4 steht im Original nicht "ist nicht Untermenge von", sondern "ist ECHTE Untermenge von". Das ist ein riesengroßer Unterschied ...

(es ist nicht das ganze Symbol durchgestrichen, sondern nur der Querbalken, der für eine eventuelle Gleichheit steht.)

Nachtrag: dieses Symbol für die echte Untermenge ist evtl. bekannter: $\subset$

Viele Grüße
Carsten

This post has been edited 3 times, last edit by "Panoramix" (Sep 5th 2010, 4:13pm)

Go to the top of the page

Schokoholic

Fritz

Posts: 2,518

Date of registration: Oct 4th 2006

Location: Hannover

Occupation: Haarspaltung

23

Sunday, September 5th 2010, 5:07pm

Falls es so ist, wie Panoramix meint, dann müsste man folgendes zeigen:

$A \subseteq B$ : Zeige, dass mindestens ein Element von A in B ist.
$A \subset B$ : Zeige, dass mindestens ein, aber nicht alle Elemente von A in B sind, also dass A und B nicht gleich sind.

PS: das richtige LaTeX-Symbol ist eigentlich \subsetneq, aber das kann mimetex (was wir hier benutzen) wohl nicht. So sollte es aussehen.

Hier gibt es nützliche Links zum Studium

This post has been edited 4 times, last edit by "Schokoholic" (Sep 5th 2010, 5:25pm) with the following reason: I stand corrected.

Go to the top of the page

Sebastian

Trainee

Posts: 101

Date of registration: Sep 21st 2007

Location: Hannover

24

Sunday, September 5th 2010, 5:18pm

Quoted from "Schokoholic"

$A \subseteq B$ : Zeige, dass mindestens ein Element von A in B ist.
$A \subset B$ : Zeige, dass mindestens ein, aber nicht alle Elemente von A in B sind, also dass A und B nicht gleich sind.[/url].

Da würde ich spontan überlegt widersprechen (aus Mengenlehre-Sicht).
$A \subseteq B$ : Zeige, dass alle Elemente von A in B sind.
$A \subset B$ : Zeige, dass alle Elemente von A in B sind und finde ein Element in B, das nicht in A ist.

try {MessageBox.Show(message);} catch(Exception e) {MessageBox.Show(e.Message);}

Go to the top of the page

Schokoholic

Fritz

Posts: 2,518

Date of registration: Oct 4th 2006

Location: Hannover

Occupation: Haarspaltung

25

Sunday, September 5th 2010, 5:23pm

Quoted from "Sebastian"

$A \subseteq B$ : Zeige, dass alle Elemente von A in B sind.
$A \subset B$ : Zeige, dass alle Elemente von A in B sind und finde ein Element in B, das nicht in A ist.

Hm, du hast natürlich Recht. Tut mir Leid.

Ergänzend sollte man sagen, dass man in KVA mit den Problemklassen nicht unbedingt so vorgeht sondern besondere Eigenschaften der Problemklassen und der zugrundeliegenden O-Notationen verwendet (vgl. Musterlösungen). Aber zu verstehen, welches Prinzip aus der Mengenlehre dahinter steckt ist sicher nicht verkehrt.

Hier gibt es nützliche Links zum Studium

Go to the top of the page

Georg

Praktikant

Posts: 8

Date of registration: Oct 3rd 2008

26

Sunday, September 5th 2010, 5:35pm

Reduktion von PART auf BIN-PACKING

- Gelöscht: Fehlüberlegung aus Lesefehler -

This post has been edited 4 times, last edit by "Georg" (Sep 5th 2010, 6:10pm) with the following reason: Alle Überlegungen aus Lesefehler, nicht weiter beachtenswert

Go to the top of the page

cartman

Junior Schreiberling

Posts: 154

Date of registration: Mar 10th 2009

Location: Laatzen

27

Sunday, September 5th 2010, 5:35pm

dann zu einer Aufgabe aus der letzten Klausur dazu, zu zeigen ist (das in der Vorlesung verwendete Zeichen für die echte Teilmenge kann man hier ja nicht darstellen, aber nach der Erklärung oben sollte klar sein, was gemeint ist)
$NL \subset TIME(2^n)$

ich bin da immer noch am rumkrebsen, wie man da ungefähr vorgeht,

nach den Sätzen gilt NL=NSPACE(log n)

kann ich so weitermachen, dass ich dann zeige, $NSPACE(log n) \subseteq TIME(2^n)$ ?

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

28

Sunday, September 5th 2010, 6:09pm

Quoted from "Georg"

Wo liegt mein Denkfehler?

Vielleicht, weil als Reduktion
$\langle a_1, \dots, a_n\rangle \in \text{PART} \Leftrightarrow \left\langle \frac{2a_1}{\sum_{i=1}^na_i},\dots,\frac{2a_n}{\sum_{i=1}^na_i},2\right\rangle\in\text{Bin-Packing}$
angegeben wird?
Und ich glaube nicht, dass $\langle \frac{4}{9},\frac{6}{9},\frac{8}{9},2\rangle\in\text{Bin-Packing}$ gilt...

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

This post has been edited 1 times, last edit by "Arne" (Sep 5th 2010, 6:10pm)

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

29

Sunday, September 5th 2010, 6:12pm

@cartman: du solltest echte Teilmenge zeigen. Hier solltest Du irgendwie mit einem der Hierarchiesätze argumentieren, sodass links NL und rechts Time(2^n) steht...

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page

AlexL

Junior Schreiberling

Posts: 222

Date of registration: Feb 10th 2008

Location: Walsrode

Occupation: Master Informatik

30

Monday, September 6th 2010, 3:03am

Hallo zusammen, hab da 2 Fragen.
Also zum einen, sind die Antworten auf die kurzfragen der letzten Klausur: falsch, richtig, falsch, rest richtig?
Und zum anderen verstehe ich beim Überprüfungsalgorithmus nicht so ganz was "vorrausgesetzt" und was zu prüfen ist. Bsp Übung 11, aufgabe 1b: Der LPATH Überprüfungsalgorithmus bekommt G, u, v, k und einen Pfad zB als Kantenliste ?! Oder "einen einfachen Pfad der von u nach v führt"?
Also was wäre dann zu prüfen? Obs ein Pfad ist, ob er einfach ist, ob er von start zu ziel führt? ob er in G liegt? oder einfach nur wie lang er ist? Also kann ich ja alles machen aber will da nicht ne Stunde dran setzen wenns nicht sein muss ;-)

Danke schonma, Alex

Go to the top of the page

Skuld

Erfahrener Schreiberling

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

31

Monday, September 6th 2010, 8:19am

Also ich würde sagen, du musst zwei Dinge überprüfen:
1. Dass überhaupt ein Pfad von u nach v existiert
2. Dass er eine Länge >= k hat.

Generell soll doch im Algorithmus überprüft werden, ob deine Eingabe für das Problem gültig ist, hier also wie gesagt, dass ein Pfad von u nach v von mind. Länge k existiert.

Hoffe das stimmt so

Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

This post has been edited 1 times, last edit by "Skuld" (Sep 6th 2010, 8:54am)

Go to the top of the page

Peter

Praktikant

Posts: 31

Date of registration: Feb 1st 2008

32

Monday, September 6th 2010, 8:59am

Also das Zertifikat ist immer das, was ein nichtdeterministischer Algorithmus raten würde. Dass Zertifikat zu überprüfen besteht dann streng genommen daraus, dass man ein Wort prüft, ob es ein gültiges Zertifikat ist.
In deinem Beispiel muss man also prüfen, ob die Eingabe die Kodierung eines Pfades in dem Graphen ist und ob dieser Pfad einfach ist, von u nach v führt und mind. Länge k hat.

Go to the top of the page

Jessie

Unregistered

33

Monday, September 6th 2010, 9:55am

Quoted from "AlexL"

sind die Antworten auf die kurzfragen der letzten Klausur: falsch, richtig, falsch, rest richtig?

"Rest richtig" stimmt nicht ganz, schau Dir nochmal die vorletzte Frage an: "Alle NP-harten Probleme können nichtdeterministisch in polynomieller Zeit entschieden werden." Das hieße ja, dass ALLE Probleme entscheidbar wären, auch die allerschwierigsten.
Erinner Dich am besten mal an die Skizze von der Fragestunde mit den Überschneidungen von P,NP und NP-harten Problemen --> Nicht alle Probleme, die NP-hart sind, liegen in NP (das hat mich auch lange verwirrt).
Beispiel "Halteproblem", das ist NP-hart, aber liegt nicht in NP, weil es überhaupt nicht entscheidbar ist.

Go to the top of the page

cartman

Junior Schreiberling

Posts: 154

Date of registration: Mar 10th 2009

Location: Laatzen

34

Monday, September 6th 2010, 11:18am

ist Behauptung 3 deshalb falsch, weil da s'=O(s) und nicht s'=o(S) steht ?

Go to the top of the page

SunshineSunny

Sonnenscheinchen auf'm Campus

Posts: 1,071

35

Monday, September 6th 2010, 11:21am

jop genau...

Manche Männer bemühen sich lebenslang, das Wesen einer Frau zu verstehen.
Andere befassen sich mit weniger schwierigen Dingen z.B. der Relativitätstheorie.

Go to the top of the page

AlexL

Junior Schreiberling

Posts: 222

Date of registration: Feb 10th 2008

Location: Walsrode

Occupation: Master Informatik

36

Monday, September 6th 2010, 11:25am

oh ja natürlich, danke Jessie.

So und das andere... die beiden Antworten sind recht ähnlich, daher Zitiere ich mal von Peter:

Quoted from "Peter"

Also das Zertifikat ist immer das, was ein nichtdeterministischer Algorithmus raten würde

Quoted from "Peter"

In deinem Beispiel muss man also prüfen, ob die Eingabe die Kodierung eines Pfades in dem Graphen ist [...], von u nach [...] führt

Ich hatte nun erst gedacht ich sage

Quoted

Eingabe: <<G,u,v,k>, E> wobei G,u,v,k wie in Aufgabe definiert und E ist die Kantenliste eines Pfades in G der bei u startet

also dass der Pfad in G ist und in u startet wäre von einem nichtdeterministischen algorithmus ja auch nicht rein zufällig so, sondern das wäre fest ?!
Oder kriege ich eine Kantenliste (oder sonstige kodierung eines Pfades), muss feststellen dass es ein Pfad ist und dann alles andere?

@cartman: jupp

Go to the top of the page

Peter

Praktikant

Posts: 31

Date of registration: Feb 1st 2008

37

Monday, September 6th 2010, 12:09pm

Letzteres ist richtig. Du kriegst die Kantenliste und musst dann alles überprüfen. Das ist natürlich meist nicht schwierig... aber manchmal halt doch.
Bei der Antwort von Skuld ist folgender Haken: Er schreibt, dass überprüft werden muss, ob ein Pfad mit den gewünschten Eigenschaften existiert. Aber das ist nicht das, was ein Verifizierungsalgorithmus hier machen muss, denn der kriegt den Pfad schon vorgegeben und muss nur seine Korrektheit überprüfen.