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.

Skuld

Erfahrener Schreiberling

  • "Skuld" is male

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:
Übungsblatt 4: (Klausuraufgabe WS 05/06): Beweisen Sie:

Was stimmt denn nun?
Hello, IT, have you tried turning it off and on again?

Wo schlafen Schmetterlinge eigentlich?

Panoramix

Trainee

Posts: 115

Date of registration: Sep 12th 2008

22

Sunday, September 5th 2010, 4:06pm

Bin gerade ein wenig verdutzt.

Übungsblatt 3: (Klausuraufgabe WS 05/06): Beweisen Sie:
Übungsblatt 4: (Klausuraufgabe WS 05/06): Beweisen Sie:

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:

Viele Grüße
Carsten

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


  • "Schokoholic" is male

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:

: Zeige, dass mindestens ein Element von A in B ist.
: 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.

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


Sebastian

Trainee

  • "Sebastian" is male

Posts: 101

Date of registration: Sep 21st 2007

Location: Hannover

24

Sunday, September 5th 2010, 5:18pm

: Zeige, dass mindestens ein Element von A in B ist.
: 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).
: Zeige, dass alle Elemente von A in B sind.
: 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);}

  • "Schokoholic" is male

Posts: 2,518

Date of registration: Oct 4th 2006

Location: Hannover

Occupation: Haarspaltung

25

Sunday, September 5th 2010, 5:23pm

: Zeige, dass alle Elemente von A in B sind.
: 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.

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


cartman

Junior Schreiberling

  • "cartman" is male
  • "cartman" started this thread

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)


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, ?

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

28

Sunday, September 5th 2010, 6:09pm

Wo liegt mein Denkfehler?


Vielleicht, weil als Reduktion

angegeben wird?
Und ich glaube nicht, dass 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)


Arne

ThI

  • "Arne" is male

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

AlexL

Junior Schreiberling

  • "AlexL" is male

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

Skuld

Erfahrener Schreiberling

  • "Skuld" is male

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 :D
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)


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.

Jessie

Unregistered

33

Monday, September 6th 2010, 9:55am

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.

cartman

Junior Schreiberling

  • "cartman" is male
  • "cartman" started this thread

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 ?

SunshineSunny

Sonnenscheinchen auf'm Campus

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.

AlexL

Junior Schreiberling

  • "AlexL" is male

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:
Also das Zertifikat ist immer das, was ein nichtdeterministischer Algorithmus raten würde
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

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.

AlexL

Junior Schreiberling

  • "AlexL" is male

Posts: 222

Date of registration: Feb 10th 2008

Location: Walsrode

Occupation: Master Informatik

38

Monday, September 6th 2010, 12:59pm

Alles klar, vielen Dank für die last Minute Hilfe und viel Glück allen! :-)

Alex

Skuld

Erfahrener Schreiberling

  • "Skuld" is male

Posts: 344

Date of registration: Oct 2nd 2007

Occupation: Student

39

Monday, September 6th 2010, 4:57pm

Na, die Klausur war aber ganz schön hart, aber wenn man gut gelernt hat, eigentlich NP.

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

Wo schlafen Schmetterlinge eigentlich?

Spunkmeyer

Trainee

  • "Spunkmeyer" is male

Posts: 64

Date of registration: Apr 2nd 2008

Location: Wunstorf

Occupation: Programmierer

40

Monday, September 6th 2010, 6:05pm

Gibts eigentlich wie bei Gthi eine Lösung im Stud.IP?
DEADBEEF = 3735928559