Moin moin!
Es hieß hier in einer AD-Übungsaufgabe:
"Die Laufzeit eines Algorithmus sei
[img]http://mokrates.de/cgi-bin/texstring?f(n)%20%3D%204n%5E2%20-%202n%20%2B%202[/img]. Finden Sie eine Funktion g(n), sodass f(n) = O(g(n)) gilt und beweisen Sie ihre Annahme."

Ich verstehe daraus: finden Sie eine beliebige Funktion g(n), für die die obige Beziehung gilt.
Also hat sich unsere Gruppe daran gemacht, eine solche Funktion zu finden und die Beziehung zu beweisen. Dieser Beweis wurde von unserer Übungsgruppenleiterin als korrekt akzeptiert. Allerdings wurde uns die Hälfte der Punkte dafür abgezogen, dass wir nicht
[img]http://mokrates.de/cgi-bin/texstring?g(n)%20%3D%20n%5E2[/img] gewählt haben. Aus der Aufgabenstellung war dies meiner Meinung nach nicht ersichtlich. Es wurde nach einer nicht näher spezifizierten Funktion gefragt.

Mir geht es hier nicht um die Punkte, sondern ums Prinzip. Ich wäre niemals im Leben darauf gekommen, dass hier als einzig gültige Funktion [img]http://mokrates.de/cgi-bin/texstring?g(n)%20%3D%20n%5E2[/img] erlaubt ist.
Begründet wurde dies folgendermaßen: Es ginge hier schließlich um die O-Notation und man sollte erkennen, dass konstante Faktoren für die Zuordnung zu einer Komplexitätsklasse keine Rolle spielen. Mit anderen Worten: man sollte zeigen, dass man die O-Notation "verstanden" hat.
Ich finde dies ist keine Begründung. Ich kann ja genausogut anführen, dass bewusst eine andere Funktion gewählt wurde (in unserem Falle
[img]http://mokrates.de/cgi-bin/texstring?g(n)%20%3D%20n%5E3%2B2[/img]), um zu zeigen, dass f nicht nur zur Klasse O(n^2), sondern auch O(n^k) für k >= 2 angehört.

Was meint ihr dazu? Die Leute, die es "richtig" gemacht haben: Woher wusstet ihr, dass nur diese eine Funktion erlaubt ist?

Ja, das sehe ich genauso wie Du. Wenn sie unbedingt [img]http://mokrates.de/cgi-bin/texstring?g(n)%3Dn%5E4[/img]
haben wollen, können sie auch schreiben "Eine Funktion g mit [img]http://mokrates.de/cgi-bin/texstring?g%5Cin%20O(f)[/img] und [img]http://mokrates.de/cgi-bin/texstring?f%5Cin%20O(g)[/img]".

hatte mich auch das selbe gefragt, aber da irgendeine Funktion zufinden ja zuleicht wäre war eigentlich klar das n^2 gesucht war

hier ist es wie in den meisten Übungen z.B. RS und FGI - man muss die Aufgabenstellung interpretieren und darf sie nicht wörtlich nehmen :(

Hab Dir, Hackbert, schon in der Übungsgruppe zugestimmt:
Als "Lernmotivation" wurde uns der Punktabzug verkauft :( Daraus gelernt hätten wir aber auch, wenn sie uns die nach ihrer Meinung beste Lösung einfach gesagt hätte… Unterm Strich belibt: Punktabzug trotz korrekter Lösung.

Oh, na da bin ich ja mal gespannt auf morgen, ich hab da erst meine Übung. Wir haben gesagt "Sei g = f" und das dann bewiesen.

Das haben wir auch gemacht, Jan. Das war aber keine sinnvolle Lösung im Sinne der O Notation. Ist zwar eine mathematisch korrekte Lösung, aber in AD anscheinend nicht so gefordert *verwirrt sei*

Ich würde Euch empfehlen, daß Ihr Euch mal an Prof. Andreae (oder wer auch immer AD hält) wendet und ihn um Erklärung für den Punktabzug bittet. So ganz sehe ich das nicht ein, vorallem, wenn die fehlenden Punkte dann am Ende dazu führen, daß jemand den Schein nicht bekommt.

Das mit den Punkten war nicht so dramatisch. Es wurden nur von der Aufgabe die Hälfte abgezogen. Mir geht es hauptsächlich ums Prinzip.

Das haben wir auch gemacht, Jan. Das war aber keine sinnvolle Lösung im Sinne der O Notation. Ist zwar eine mathematisch korrekte Lösung, aber in AD anscheinend nicht so gefordert *verwirrt sei*

Jetzt muss man bei jeder Aufgabe nicht nur die Lösung finden, sondern auch noch einen Blick in die Kristallkugel wagen: Was hat sich der Aufgabensteller gedacht , was neben der korrekten Lösung der Aufgabe noch in seinen Augen sinnvoll ist.

Ich werde das aber dennoch mal bei Herrn Rarey ansprechen. Leider bin ich zur nächsten Vorlesung am Dienstag nicht da. Falls jemand den Prof anspricht, bitte hier mitteilen, nicht das wir ihn doppelt belabern.

Ich werde das aber dennoch mal bei Herrn Rarey ansprechen. Leider bin ich zur nächsten Vorlesung am Dienstag nicht da. Falls jemand den Prof anspricht, bitte hier mitteilen, nicht das wir ihn doppelt belabern.

Wir können uns ja mal zusammentun…

Das mit den Punkten war nicht so dramatisch. Es wurden nur von der Aufgabe die Hälfte abgezogen. Mir geht es hauptsächlich ums Prinzip.

Bei uns wurden 0 Punkte für den Aufgabenteil vergeben. Ich habe dem Übungsgruppenleiter auch gesagt, dass ich es nicht in Ordnung finde, das es für eine korrekte Lösung (sie war ja bewiesen) keine Punkte gibt - seine Antwort war, sie hätten "erwartet, dass die Studenten auch mitdenken können".
Das ist ja so wie: "Nennen Sie eine natürliche Zahl größer als 3." - "10." - "Falsch, 4."

Ich bin auf jeden Fall ziemlich enttäuscht von denen, die dafür verantwortlich sind, da unser Übungsgruppenleiter auch keinerlei Einsicht zeigte. Mir geht es dabei auch nur ums Prinzip und nicht um die Punkte (es sei denn, sie fehlen am Ende).

Wir können uns ja mal zusammentun…

Bin dabei, sprechen wir ihn Dienstag mal darauf an. Nicht, dass uns nochmal irgendwo willkürlich Punkte aberkannt werden.

Wie gesagt, ich bin am Dienstag nicht da. Wenn ihr das ansprecht, setzt meinen Namen mit drunter ;-)

Wir können uns ja mal zusammentun…

Bin dabei, sprechen wir ihn Dienstag mal darauf an. Nicht, dass uns nochmal irgendwo willkürlich Punkte aberkannt werden.
Dann lass' uns das Dienstag mal tun. Vlt bringen wir unsere Übungsblätter mit - das ist sicher hilfreich.

Ihr habt ihn Dienstag nicht drauf angesprochen, weil er nicht da war? Oder?
Dann also morgen?

Ihr habt ihn Dienstag nicht drauf angesprochen, weil er nicht da war? Oder?
Dann also morgen?

Rööchtöög.
D.h. wir haben den Ersatzspieler angesprochen, kurz mit ihm darüber gestritten und uns darauf geeinigt, doch besser Rarey selbst danach zu fragen.

hier ist es wie in den meisten Übungen z.B. RS und FGI - man muss die Aufgabenstellung interpretieren und darf sie nicht wörtlich nehmen :(

Ich hoffe, es ist hier FGI-2 gemeint, bei FGI-1 gab es in den Aufgabenstellungen eigentlich nichts zum freien interpretieren!