Aussagen richtig oder falsch? < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Sind die folgenden Aussagen jeweils korrekt oder falsch?
1) Es ist [mm]\mathcal{O}(4n+17n*log(n)) \subseteq \mathcal{O}(n*log(n))[/mm]
2) Es ist [mm]\Theta(17n^3+4n^2) = \Theta(n^4)[/mm]
3) Seien X, X' Probleme mit [mm]X \leq_{p} X'[/mm], dann gilt [mm](X')^C \leq_{p} X^C[/mm]
4) Es ist DTIME([mm]\mathcal{O}(n^3)[/mm]) [mm] \subseteq[/mm] DSPACE([mm]\mathcal{O}(n^3)[/mm])
5) Es ist DSPACE([mm]\mathcal{O}(n^2)[/mm]) [mm] \subseteq[/mm] DTIME([mm]\mathcal{O}(n^3)[/mm])
[mm]\leq_{p}[/mm] bezeichnet die Polynomialzeitreduktion. |
Hallo zusammen,
ich muss zu den gegebenenen Aussagen sagen, ob sie jeweils wahr oder falsch sind und für mein Verständnis bin ich auch an einer informellen Begründung (d. h. kein Beweis im mathematischsen Sinne) interessiert.
Meine Lösungsansätze:
1) Die Aussage ist falsch! Grund: [mm]4n+17n*log(n)[/mm] wächst deutlich schneller als [mm]n*log(n)[/mm], demnach kann die obere Schranke ("Groß-Oh") des ersten Ausdrucks keine Teilmenge der oberen Schranke des zweiten Ausdrucks sein.
2) Die Aussage ist falsch! Grund: Im linken Ausdruck ist die höchste vorkommende Potenz [mm]n^3[/mm], im rechten Ausdruck ist die höchste vorkommende Potenz [mm]n^4[/mm]. Es handelt sich also um zwei verschiedene Komplexitätsklassen.
3) Ich meine, die Aussage ist falsch! Grund ist ein Satz aus dem Skript, welchem die entsprechende Vorlesung zu Grunde liegt: "Sei [mm]A \leq_{p} B[/mm], dann ist auch [mm]A^C \leq_{p} B^C[/mm]." Allerdings kann man wohl auch beide Aussagen treffen – dann sind die Probleme A und B gleich schwer.
4) Die Aussage ist wahr! (Trivial)
5) Hier habe ich leider keine Idee.
Ich würde mich freuen, wenn Ihr meine Antworten korrigiert bzw. kommentiert.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:29 Mi 22.01.2014 | | Autor: | DieAcht |
Hallo,
> Sind die folgenden Aussagen jeweils korrekt oder falsch?
>
> 1) Es ist [mm]\mathcal{O}(4n+17n*log(n)) \subseteq \mathcal{O}(n*log(n))[/mm]
>
> 2) Es ist [mm]\Theta(17n^3+4n^2) = \Theta(n^4)[/mm]
> 3) Seien X, X'
> Probleme mit [mm]X \leq_{p} X'[/mm], dann gilt [mm](X')^C \leq_{p} X^C[/mm]
> 4) Es ist DTIME([mm]\mathcal{O}(n^3)[/mm]) [mm] \subseteq[/mm] DSPACE([mm]\mathcal{O}(n^3)[/mm])
>
> 5) Es ist DSPACE([mm]\mathcal{O}(n^2)[/mm])
> [mm]\subseteq[/mm] DTIME([mm]\mathcal{O}(n^3)[/mm])
>
> [mm]\leq_{p}[/mm] bezeichnet die Polynomialzeitreduktion.
>
>
> Hallo zusammen,
>
> ich muss zu den gegebenenen Aussagen sagen, ob sie jeweils
> wahr oder falsch sind und für mein Verständnis bin ich
> auch an einer informellen Begründung (d. h. kein Beweis im
> mathematischsen Sinne) interessiert.
>
> Meine Lösungsansätze:
>
> 1) Die Aussage ist falsch! Grund: [mm]4n+17n*log(n)[/mm] wächst
> deutlich schneller als [mm]n*log(n)[/mm], demnach kann die obere
> Schranke ("Groß-Oh") des ersten Ausdrucks keine Teilmenge
> der oberen Schranke des zweiten Ausdrucks sein.
Wieso wächst [mm] 4n+17n*\log(n) [/mm] deutlich schneller als [mm] n*\log(n) [/mm] ?
Setze [mm] T(n):=4n+17n*\log(n), [/mm] dann gilt:
Es existiert ein [mm] C\in\IR [/mm] und ein [mm] N\in\IN, [/mm] sodass für alle [mm] $n\ge [/mm] N$ gilt:
[mm] T(n)=n(4+17(\log(n)))\le C*n*\log(n)
[/mm]
[mm] \Rightarrow T(n)\in\mathcal O(n*\log(n)).
[/mm]
> 2) Die Aussage ist falsch! Grund: Im linken Ausdruck ist
> die höchste vorkommende Potenz [mm]n^3[/mm], im rechten Ausdruck
> ist die höchste vorkommende Potenz [mm]n^4[/mm]. Es handelt sich
> also um zwei verschiedene Komplexitätsklassen.
Die Argumentation reicht nicht aus.
[mm] n
Setze $T(n):=10n+123$, dann gilt:
[mm] T(n)\in\mathcal O(n)\in\mathcal O(n^2)\in\mathcal O(n^3)\in\mathcal O(n^4)\in\ldots
[/mm]
Ich glaube, dass die Informatiker folgende Schreibweise benutzen:
[mm] T(n)=\mathcal O(n)=\mathcal O(n^2)=\mathcal O(n^3)=\mathcal O(n^4)=\ldots
[/mm]
Hier siehst du, dass solche Argumentationen alleine nicht ausreichen.
Es geht hier aber um die genaue Komplexität [mm] \Theta, [/mm] sodass es Sinn macht.
Das musst du aber in deine Argumentation einfließen lassen.
> 3) Ich meine, die Aussage ist falsch! Grund ist ein Satz
> aus dem Skript, welchem die entsprechende Vorlesung zu
> Grunde liegt: "Sei [mm]A \leq_{p} B[/mm], dann ist auch [mm]A^C \leq_{p} B^C[/mm]."
Dann bist du hier fertig.
> Allerdings kann man wohl auch beide Aussagen treffen –
> dann sind die Probleme A und B gleich schwer.
Das verstehe ich nicht.
> 4) Die Aussage ist wahr! (Trivial)
Ja, denn es gilt für [mm] $t(n)\ge [/mm] n+2$ folgendes:
[mm] $DTIME(t)\subseteq NTIME(t)\subseteq [/mm] DSPACE(t)$
> 5) Hier habe ich leider keine Idee.
Siehe 4)
> Ich würde mich freuen, wenn Ihr meine Antworten korrigiert
> bzw. kommentiert.
Gruß
DieAcht
|
|
|
|
