KvA - Aussagen - Grundlagen der Informatik - Fachrat Informatik

Leela

Mädchen

Posts: 88

Date of registration: Sep 15th 2011

1

Thursday, September 4th 2014, 12:39pm

KvA - Aussagen

Hallo!

Für folgende 3 Aussagen kann ich nicht sagen, ob richtig oder falsch. Könnte mir die vielleicht jemand erklären?

$\bullet \text{ Fuer jede Funktion }f : N \to N \text{ gilt: }f \in O(f).\\ \bullet \text{ Es gilt }LOGSPACE~\neq~P \text{ oder }P~\neq~PSPACE\\ \bullet \text{ Fuer alle Sprachen A, B gilt: } A~{\leq}^{p}_{m}~B~~\Leftrightarrow~~B~{\leq}^{p}_{m}~A$

lg
Doro

Go to the top of the page

nano

Alter Hase

Posts: 146

Date of registration: Oct 11th 2010

Location: Hannover

Occupation: THI

2

Thursday, September 4th 2014, 1:32pm

Hallo Doro,

die erste Aussage ist äquivalent zu: lim(n->inf) f / f ist endlich. Gilt das für alle Funktionen?
die zweite Aussage erhältst du aus dem Platzhierarchiesatz: Wir wissen, dass es Sprachen in PSPACE, aber außerhalb von LOGSPACE gibt. Was würde passieren, wenn die Aussage falsch wäre?
die dritte Aussage behauptet, dass Reduktion symmetrisch ist. Nimm hier mal eine Sprache aus P und eine EXP-vollständige Sprache. Hier kann man beweisen, dass man in eine Richtung auf jeden Fall reduzieren kann, und dass man in die andere Richtung nicht reduzieren kann.

Hilft dir das weiter?

Go to the top of the page

nano

Alter Hase

Posts: 146

Date of registration: Oct 11th 2010

Location: Hannover

Occupation: THI

3

Thursday, September 4th 2014, 1:35pm

Achja, in der Übung hatten wir auch noch die Sprachen "leere Menge" und Σ*. Man kann von diesen Sprachen auf alle anderen reduzieren, man kann aber keine andere Sprache auf die leere Menge oder Σ* reduzieren.

Go to the top of the page

barhoum

Praktikant

Posts: 26

Date of registration: Dec 13th 2010

4

Thursday, September 4th 2014, 4:15pm

Hallo,

hat Jemand eine Lösung zu dieser Aufgabe ?

Go to the top of the page

Leela

Mädchen

Posts: 88

Date of registration: Sep 15th 2011

5

Thursday, September 4th 2014, 4:31pm

Hallo nano,

Quoted from "nano"

die erste Aussage ist äquivalent zu: lim(n->inf) f / f ist endlich. Gilt das für alle Funktionen??

Nein, gilt natürlich nicht.

Quoted from "nano"

die zweite Aussage erhältst du aus dem Platzhierarchiesatz: Wir wissen, dass es Sprachen in PSPACE, aber außerhalb von LOGSPACE gibt. Was würde passieren, wenn die Aussage falsch wäre?

Würde P=NP gelten?

Quoted from "nano"

die dritte Aussage behauptet, dass Reduktion symmetrisch ist. Nimm hier mal eine Sprache aus P und eine EXP-vollständige Sprache. Hier kann man beweisen, dass man in eine Richtung auf jeden Fall reduzieren kann, und dass man in die andere Richtung nicht reduzieren kann.
Hilft dir das weiter?

Ok. Danke

lg Doro

Go to the top of the page

bommy

Praktikant

Posts: 9

Date of registration: Oct 5th 2012

6

Thursday, September 4th 2014, 6:19pm

*hust*

$\lim_{n \to \infty}\frac{f(n)}{f(n)}$

...ist doch ziemlich endlich, denke ich. Lass dich von der Schreibweise nicht verwirren.

Go to the top of the page

Julian

ThI

Posts: 66

Date of registration: Oct 4th 2006

Location: Lehrte

7

Thursday, September 4th 2014, 7:43pm

Mein Kommentar hat sich erledigt. Könnte gelöscht werden.

This post has been edited 2 times, last edit by "Julian" (Sep 4th 2014, 7:45pm)

Go to the top of the page

bommy

Praktikant

Posts: 9

Date of registration: Oct 5th 2012

8

Thursday, September 4th 2014, 7:51pm

Quoted from "Julian"

Wegen Punkt 1.

Ich glaube ihr verwechselt klein o und groß O Notation. Klein o wird über den Limes definiert und groß O über eine Ungleichung.

$f \in O(g) ~\Leftrightarrow~ \exists c,n_0 \in N~ \forall n \ge n_0 ~:~ f(n) \le c \cdot g(n) ~\Leftrightarrow~ \lim_{n \to \infty}\frac{f(n)}{g(n)} \lt \infty$
und
$f \in o(g) ~\Leftrightarrow~ \lim_{n \to \infty}\frac{f(n)}{g(n)} = 0$

Gibt also für beide Varianten eine Limes-Variante.

This post has been edited 1 times, last edit by "bommy" (Sep 4th 2014, 9:16pm)

Go to the top of the page

Julian

ThI

Posts: 66

Date of registration: Oct 4th 2006

Location: Lehrte

9

Thursday, September 4th 2014, 8:34pm

Genau aus dem Grund hab ich den Kommentar weg genommen, weil ich mich verlesen hatte

Das kleiner unendlich übersehen.

Go to the top of the page

SammysHP

Forenwolf

Posts: 712

Date of registration: Oct 11th 2010

Location: Celle

Occupation: Informatiker

10

Thursday, September 4th 2014, 8:41pm

Aber dafür hat die Nachwelt jetzt eine schöne Erklärung.

Go to the top of the page

Leela

Mädchen

Posts: 88

Date of registration: Sep 15th 2011

11

Friday, September 5th 2014, 8:30am

Quoted from "bommy"

*hust*

$\lim_{n \to \infty}\frac{f(n)}{f(n)}$

...ist doch ziemlich endlich, denke ich. Lass dich von der Schreibweise nicht verwirren.

Upsi! Also ist die Aussage korrekt, richtig?

Nun habe ich noch eine Frage zu der Aufgabe die barhoum gestellt hat. Ich verstehe die Zyklusdefinition nicht ganz. Was ist damit genau gemeint? Ist das einfach nur ein Pfad zwischen Knoten oder ein Kreis oder etwas ganz anderes?

Go to the top of the page

SammysHP

Forenwolf

Posts: 712

Date of registration: Oct 11th 2010

Location: Celle

Occupation: Informatiker

12

Friday, September 5th 2014, 9:04am

Ein Pfad über mehrere Knoten, wobei Anfangs und Endknoten gleich sind.

Go to the top of the page

Leela

Mädchen

Posts: 88

Date of registration: Sep 15th 2011

13

Friday, September 5th 2014, 9:25am

Quoted from "SammysHP"

Ein Pfad über mehrere Knoten, wobei Anfangs und Endknoten gleich sind

Ok, quasi ein Hamiltonkreis von s nach t nur innerhalb eines Teilgraphen.

Nun noch eine Frage dazu. Es steht $1~\leq~i~\leq~m$ . Ist also auch ein Kreis der Länge 1 erlaubt?

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

14

Friday, September 5th 2014, 9:34am

Quoted from "Leela"

Quoted from "SammysHP"

Ein Pfad über mehrere Knoten, wobei Anfangs und Endknoten gleich sind

Ok, quasi ein Hamiltonkreis von s nach t nur innerhalb eines Teilgraphen.

Nun noch eine Frage dazu. Es steht $1~\leq~i~\leq~m$ . Ist also auch ein Kreis der Länge 1 erlaubt?

Bei einem Hamilton'schen Kreis wird jeder Knoten im Graphen genau einmal besucht. Davon ist hier nicht die Rede. Ein Zyklus ist einfach ein Pfad von einem Knoten weg und wieder zurück zu ihm (um die Definition in der Aufgabe nochmal natürlich sprachlich zu wiederholen).

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

Go to the top of the page

nano

Alter Hase

Posts: 146

Date of registration: Oct 11th 2010

Location: Hannover

Occupation: THI

15

Friday, September 5th 2014, 10:31am

Quoted from "Leela"

Quoted from "nano"

die zweite Aussage erhältst du aus dem Platzhierarchiesatz: Wir wissen, dass es Sprachen in PSPACE, aber außerhalb von LOGSPACE gibt. Was würde passieren, wenn die Aussage falsch wäre?

Würde P=NP gelten?

Unter anderem. Es wäre LOGSPACE = PSPACE und wegen LOGSPACE $\subseteq$ P $\subseteq$ NP $\subseteq$ PSPACE wäre auch P = NP.
Aber es reicht hier schon zu sagen, dass LOGSPACE = PSPACE durch den Platzhierarchiesatz nicht gelten kann.

Go to the top of the page

barhoum

Praktikant

Posts: 26

Date of registration: Dec 13th 2010

16

Friday, September 5th 2014, 11:43am

das heißt jeder Knoten, der nicht frei steht, ist Teil eines Zyklus ?

This post has been edited 2 times, last edit by "barhoum" (Sep 5th 2014, 12:44pm)

Go to the top of the page

barhoum

Praktikant

Posts: 26

Date of registration: Dec 13th 2010

17

Friday, September 5th 2014, 1:02pm

Beim Übungsblatt 9 Aufgabe 1 warum verbindet man nicht einfach s mit t, in dem Fall wo die Anzahl der Knoten gerade ist.

Go to the top of the page

nano

Alter Hase

Posts: 146

Date of registration: Oct 11th 2010

Location: Hannover

Occupation: THI

18

Friday, September 5th 2014, 1:14pm

Damit würde man teilweise Even-Hamcircs erzeugen, obwohl im Graphen kein Hampath von s nach t war. Versuche da einmal, ein kleines Beispiel zu konstruieren.