You are not logged in.

nethwa

Praktikant

  • "nethwa" is male
  • "nethwa" started this thread

Posts: 10

Date of registration: Apr 16th 2012

1

Monday, April 16th 2012, 3:50pm

KvA Übung - Aussagen beweisen

Hallo alle zusammen,

Ich bin Juniorstudent und habe unter Anderem die Vorlesung Komplexität von Algorithmen gewählt - leider konnte ich (aus terminlichen Gründen)
nicht an der Vorlesung teilnehmen und sitze nun an dem Übungszettel und habe nur eine grobe Ahnung, wie man die gegebenen Aussagen
formal falsifizieren oder verifizieren soll.

Als Beispiel:
Teilaufgabe a) von Aufgabe 1:
2n ∈ O(n)

Ich meine, dass die Aussage falsch ist, da 2n außerhalb von O(n) liegt (da n die obere Schranke ist).
Doch nun weiß ich nicht, wie ich das formal begründen soll, sodass die Lösung auch gewertet wird.
Als Ansatz hätte ich:

2n [nicht element von] O(n)
O(n) = {0,... ,n}

Ist das so richtig oder mache ich es ganz falsch?

Gruß,
Nelo

Ps:
Als Juniorstudent fehlen mir natürlich auch idealerweise sämtliche Grundlage zu KvA aus GTI, also seid gnädig mit mir :D

Sebastian

Trainee

  • "Sebastian" is male

Posts: 101

Date of registration: Sep 21st 2007

Location: Hannover

2

Monday, April 16th 2012, 4:01pm

Schwierig dir zu helfen ohne gleich die Lösung zu offenbaren.

Hallo alle zusammen,
2n [nicht element von] O(n)
O(n) = {0,... ,n}

Das kannst du so auf keinen Fall machen. 2n ist in dem Beispiel eine Funktion und O(n) ist eine Laufzeitklasse.
In der Vorlesung/Übung müsste es Rechenregeln zum Umgang mit Laufzeitklassen gegeben haben, wenn ich mich recht erinnere ist die einfache Anwendung einer davon auch schon der Beweis für wahr/falsch.
try {MessageBox.Show(message);} catch(Exception e) {MessageBox.Show(e.Message);}

This post has been edited 2 times, last edit by "Sebastian" (Apr 16th 2012, 5:06pm)


Anselm

borlark

Posts: 164

Date of registration: Oct 13th 2010

Occupation: WiMi ThI

3

Monday, April 16th 2012, 4:09pm

Wie Sebastian schreibt: Das was du da schreibst, stimmt so nicht und der Beweis leitet sich sehr direkt aus der Definition bzw. den einfachen Rechenregeln für Laufzeitklassen ab
(deren Richtigkeit zumindest vom Verständnis auch gut nachvollziehbar ist).

Die Definition für O(n) ist wie folgt:


c ist dabei ein beliebiger konstanter Faktor.

Umgangssprachlich bedeutet "ist Element von O(g(n))" also "wächst höchstens so stark, wie g(n) - abgesehen von einem konstanten Faktor"

(Hinweise zur Notation: "genau dann, wenn" wird oft mit "gdw." abgekürzt oder auch als Äquivalenz geschrieben, also <=>.
Das umgedrehte E bedeutet "es existiert" und das umgedrehte A bedeutet "für alle")

Hoffe, dass das schon ein bisschen geholfen hat.

Mit freundlichen Grüßen,
Anselm
"Once you figure out what a joke everything is, being the comedian's the only thing makes sense."
~The Comedian

This post has been edited 6 times, last edit by "Anselm" (Apr 16th 2012, 4:15pm)


nethwa

Praktikant

  • "nethwa" is male
  • "nethwa" started this thread

Posts: 10

Date of registration: Apr 16th 2012

4

Monday, April 16th 2012, 5:01pm

Okay erstmal danke für die Antworten, dass hat mir schon weitergeholfen.

Die Rechenregeln habe ich auch schon gefunden, allerdings behandeln diese nur Gleichungen wie zB c*O(f) = O(f) (um mal das einfachste Beispiel zu nehmen).
Wenn ich das auf diese Aufgabe anwenden will kommt bei mir das hier raus:



Bin damit auf dem richtigen Weg oder laufe ich gerade ganz in die falsche Richtung?

Gruß,
Nelo

Ps:
Hier habe ich im "Infostudium Wiki" die Rechenregeln gefunden - sind das die Korrekten?
http://wiki.infostudium.de/wiki/Landau_Notation

This post has been edited 1 times, last edit by "nethwa" (Apr 16th 2012, 5:02pm)


Sebastian

Trainee

  • "Sebastian" is male

Posts: 101

Date of registration: Sep 21st 2007

Location: Hannover

5

Monday, April 16th 2012, 5:10pm

Das ist zwar ein wenig durcheinander/unkorrekt aufgeschrieben, aber du bist definitiv auf dem richtigen Weg!
Schau dir noch mal genau die 2 ersten Regeln (sehen richtig aus) von deinem Link genau an und dann führ jeden Schritt einzeln aus.
try {MessageBox.Show(message);} catch(Exception e) {MessageBox.Show(e.Message);}

Anselm

borlark

Posts: 164

Date of registration: Oct 13th 2010

Occupation: WiMi ThI

6

Monday, April 16th 2012, 5:16pm

Denke schon, dass das die richtigen sind ;) Und letztlich lässt sich der Beweis für deine Beispielaufgabe ja auch schon direkt aus der Definition ableiten.
Eine weitere recht grundlegende Rechenregel ist übrigens O(f(n)+g(n)) = O(max{f(n), g(n)})
Sollte klar sein: Wenn das Maximum über die stärke des Wachstums definiert ist lässt sich die schwächer wachsende natürlich durch die stärker wachsende ausdrücken,
somit "reicht" die stärker wachsende in der O-Notation aus.
Also ich würde hier den Beweis wohl einfach so führen, dass ich meine Beispielfunktion 2n und die Funktion n, zu deren Laufzeitklasse sie gehören soll, in der Schreibweise der Definition schreibe,
um so zu zeigen, dass 2n Element von O(n) gemäß Definition.

Im übrigen ist n hier KEINE funktion, sondern die Variable, von der die Funktionen abhängen können (üblicherweise in den Anwendungsfällen dann die größe des Arguments, also z.B. Anzahl der Elemente einer Liste oder derartiges).
Du schreibst entsprechend nicht n(x), sondern wenn dann f(n) und g(n) und setzt da entsprechend deine Funktionen ein.

Mit freundlichen Grüßen,
Anselm

PS: Hoffe ich nehme nicht schon zuviel vorweg, aber irgendwie muss ein Grundverständnis ja aufgebaut werden ^^
"Once you figure out what a joke everything is, being the comedian's the only thing makes sense."
~The Comedian

newgame

Trainee

Posts: 45

Date of registration: Sep 30th 2009

7

Monday, April 16th 2012, 5:18pm

Die Definition von lautet . Natürlichsprachlich kann man vielleicht sagen, das ab einem festen multipliziert mit einer Konstanten eine obere Schranke für ist.

Um zu beweisen ob gilt oder nicht, musst du entweder die entsprechenden Konstanten finden, sodass die obige Definition erfüllt wird, oder aber zeigen, dass es keine gibt, die obige Definition erfüllen.

Dazu kannst du dir erstmal hinschreiben ggf. umformen und überlegen, was hier zutrifft.

nethwa

Praktikant

  • "nethwa" is male
  • "nethwa" started this thread

Posts: 10

Date of registration: Apr 16th 2012

8

Monday, April 16th 2012, 5:33pm

Okay, ich hab mal versucht, das soweit zu verstehen, dass ist dabei rausgekommen:



@Anselm:
Aber die Rechenregel muss ich doch nicht anwenden, oder?
Schließlich liegen eine Konstante und eine Variable vor und die Konstante kann vernachlässigt werden, da sie nur
bei niedrigen Laufzeiten Auswirkungen hat (oder verwechsel ich hier gerade [wieder] was?).

@newgame:
D.h. ich müsste nur beweisen, dass ist, um das zu falsifizieren?

Sebastian

Trainee

  • "Sebastian" is male

Posts: 101

Date of registration: Sep 21st 2007

Location: Hannover

9

Monday, April 16th 2012, 5:52pm

Gleich die erste Umformung solltest du anders angehen.
Wenn du die Regel

auf

anwenden willst, dann steht das f(n) für 2n (mit 2!). Und vergiss nicht das O mit aufzuschreiben.
try {MessageBox.Show(message);} catch(Exception e) {MessageBox.Show(e.Message);}

nethwa

Praktikant

  • "nethwa" is male
  • "nethwa" started this thread

Posts: 10

Date of registration: Apr 16th 2012

10

Monday, April 16th 2012, 6:00pm

Also etwas in der Richtung?


Das Zweite könnte man so auflösen:

This post has been edited 1 times, last edit by "nethwa" (Apr 16th 2012, 6:00pm)


Anselm

borlark

Posts: 164

Date of registration: Oct 13th 2010

Occupation: WiMi ThI

11

Monday, April 16th 2012, 7:02pm

Noch ein bisschen anders ;)
Du hast ja schon eine Vorgabe, zu welcher Laufzeitklasse deine Funktion gehören soll, also wirst du in etwa so rangehen:




Zudem wirst du nie links eine Laufzeitklasse stehen haben: Eine Laufzeitklasse kann nicht Element einer anderen Laufzeitklasse sein, wenn überhaupt nur Teilmenge (da beide Mengen von Funktionen sind, nicht einzelne Funktionen). Dann ist entsprechend nur zu zeigen, dass gilt:

Ist jetzt irgendwie schon sehr viel geholfen, aber ist eben eine sehr grundlegende Aufgabe. Ich denke es macht wenig Sinn bei etwas, was fast nur die Schreibweise betrifft zu hoffen, dass du selber drauf kommst ;) Muss man denke ich eher einfach mal gesehen haben.
"Once you figure out what a joke everything is, being the comedian's the only thing makes sense."
~The Comedian

This post has been edited 2 times, last edit by "Anselm" (Apr 16th 2012, 7:02pm)


nethwa

Praktikant

  • "nethwa" is male
  • "nethwa" started this thread

Posts: 10

Date of registration: Apr 16th 2012

12

Monday, April 16th 2012, 8:04pm

Okay, ich glaube mir fehlt da ein großer Teil Aussagenlogik, damit ich die Aufgaben überhaupt bewältigen kann.
Gibt es eine Seite oder ein Buch, wo auch Beispiele erklärt vorgerechnet werden (oder auch Lehr-Videos oder
Skripte/Folien von bestimmten Vorlesungen, in der KvA-Vorlesung konnte ich weder im Skript noch in den Folien
dazu fündig werden)?

Die einzige Idee von mir, wie ich beweisen könnte, dass gilt, wäre mit einem Limes.

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

13

Monday, April 16th 2012, 9:16pm

Also mit Aussagenlogik hat das eigentlich nichts zu tun. Warte einfach die Übung ab, dort wird alles weiter erläutert. Außerdem werden aller Voraussicht nach nicht alle Aufgaben gelöst, sodass Du die Möglichkeit bekommst anschließend noch solche Aufgaben selber zu lösen.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

pythong

Trainee

  • "pythong" is male

Posts: 112

Date of registration: Oct 23rd 2005

Location: Ehemals Preußisches Gebiet

Occupation: Ehemals Studentenquäler. I'm finally done with school!

14

Monday, April 16th 2012, 9:31pm

du machst es dir viel schwerer als es ist.

Der Post von Anselm (19:02) sagt bereits alles, was du beweisen sollst.






Also nochmal auf deutsch: 'es gibt ein n0 in den ganzen Zahlen und ein c in den reellen Zahlen, sodass für alle n größer/gleich als n0 gilt, dass c*2*n kleiner oder gleich n ist'

Jetzt fängst du an zu testen: (später siehst du's sofort bzw. wenn du in der Schule dauernd Ungleichungen rechnen musstest, auch). Such dir ein c aus den reellen Zahlen aus. Nehmen wir zB. c = dreißig Millionen, passt es schon mal nicht, egal welches n0 ich nehme. Geht das überhaupt? Kriegst du schon raus

Übrigens: GTI und Aussagenlogik brauchst du in KvA nicht wirklich, aber es hilft ein bißchen (vllt zu 5%). Was du tun musst, ist das Skript verstehen (VERSTEHEN, nicht nur lesen) und sonst den Kopf anstrengen. Und die Übungen helfen vor allem auch
don't ask me, google it

This post has been edited 1 times, last edit by "pythong" (Apr 16th 2012, 9:31pm)


Anselm

borlark

Posts: 164

Date of registration: Oct 13th 2010

Occupation: WiMi ThI

15

Monday, April 16th 2012, 9:38pm

Naja, gerade bei so einfachen Sachen ist es teilweise schwer zu sehen, was man dann denn überhaupt noch hinschreiben soll, aber auch insgesamt ist es gewöhnungssache, einen Anfang zu finden. Aber mit der Zeit hat man das dann raus. In der Schule hatte ich wenig bis gar nichts in Richtung Beweise, aber in eigentlich allen theoretischen Vorlesungen (sei es nun Mathe oder GTI) bekommt man das Vorgehen recht schnell mit und bekommt dann ein Gefühl dafür. Mach dir also keine Sorgen, falls du noch Probleme hast.
Und wie pythong schreibt: Es fehlt bei dem, was ich geschrieben habe, nurnoch etwa eine Zeile. Und nicht zu kompliziert denken :)
"Once you figure out what a joke everything is, being the comedian's the only thing makes sense."
~The Comedian

nethwa

Praktikant

  • "nethwa" is male
  • "nethwa" started this thread

Posts: 10

Date of registration: Apr 16th 2012

16

Monday, April 16th 2012, 9:45pm

Okay danke für die ganze Hilfe.
Ich denke wenn ich mich jetzt noch etwas dran setze und das alles in Ruhe durchgehe, werde
ich das schon verstehen - notfalls bleibt immernoch die Übungsgruppe :D