Problem mit einem kompliziertem Ausdruck

volkard

x=7;
solange x<=(7<<3);
x=snoob(x);

zählt die (6 über 3) möglichkeiten auf, 3 bits von 6 zu setzen.

Hallo volkard.

Mir erschließt sich der Sinn der Aufgabe nicht.

Ich habe dem Lehrer jetzt die Aufgabe geschickt mit dem Vermerk, dass ich keine Ahnung habe, was die Funktion konkret macht, ich aber jeden einzelnen Schritt erklären kann.
Jetzt habe ich erfahren, dass dies der "Gosper-Algorithmus" ist.(Was zur Hölle...) Das höre ich gerade zum allerersten mal. Hab danach gegoogelt, und kann zwischen diesem Gospel und dem Listing keinen Zusammenhang erkennen.

Mir erschließt sich der Sinn der Aufgabe nicht.

Soll ich dir mal ein paar Aufgaben zeigen?
zB:

int x = 10, y = 20;
x = x++ + y++;
y = ++y + ++x;

Frage: Welche Werte haben x und y?
Meine Antwort: Ich habe ihm die Ausgabe meines Compilers geschrieben mit dem Anhang, dass dies ein undefiniertes Verhalten erzeugt.
Ergebnis: 0 Punkte, da Post- und Präinkrement immer gleiche Ergebnisse liefern, ist dieses Listing wohldefiniert...
Ich so: wtf..??!!

Wutz

Dein Lehrer hat keine Ahnung.
Da musst du leider mit leben.
Du kannst dich aber gleich daran gewöhnen, dass es im Leben oftmals Leute gibt, die von Dingen reden, von den sie keine Ahnung haben. Das hindert sie aber nicht daran, darüber zu reden, oftmals sogar sehen sie ihre Berufung darin, von Dingen zu reden, von denen sie keine Ahnung haben: Politiker,Manager,Lehrer,...

volkard

wgerhtrj schrieb:

Hallo volkard.

Mir erschließt sich der Sinn der Aufgabe nicht.

Ich habe dem Lehrer jetzt die Aufgabe geschickt mit dem Vermerk, dass ich keine Ahnung habe, was die Funktion konkret macht, ich aber jeden einzelnen Schritt erklären kann.
Jetzt habe ich erfahren, dass dies der "Gosper-Algorithmus" ist.(Was zur Hölle...) Das höre ich gerade zum allerersten mal. Hab danach gegoogelt, und kann zwischen diesem Gospel und dem Listing keinen Zusammenhang erkennen.

Ich meinte, was erwartet er, was Ihr davon lernt? Das ist doch keine lehrreiche Aufgabe, sondern schlichtes "Ich zeige Euch mal, daß ich viel schlauer bin".

wgerhtrj schrieb:

Mir erschließt sich der Sinn der Aufgabe nicht.

Soll ich dir mal ein paar Aufgaben zeigen?
zB:
int x = 10, y = 20;
x = x++ + y++;
y = ++y + ++x;
Frage: Welche Werte haben x und y?

dito.

wgerhtrj schrieb:

Meine Antwort: Ich habe ihm die Ausgabe meines Compilers geschrieben mit dem Anhang, dass dies ein undefiniertes Verhalten erzeugt.
Ergebnis: 0 Punkte, da Post- und Präinkrement immer gleiche Ergebnisse liefern, ist dieses Listing wohldefiniert...
Ich so: wtf..??!!

Leicht bessere Chanchen gehabt, wenn Du ein gut googlebares Wort wir Sequenzpunkte eingebaut hättest. In der Schule kann man gegen sowas noch den Aufstand proben…
Aber im Studium nicht mehr, da hat der Prof einfach Recht. Selbst vor Gericht, was könnte der Richter anderes machen, als den Prof fragen?
Ich bekam mal keine Punkte, weil für mich f(x)=c und f(x)=x Polynome waren, aber er war da ganz anderer Ansicht. wtf..??!!

Am besten, Du übst schonmal. Immer hübsch rausfinden, was er für Sachen falsch macht und die Antwort finden, auf die er am sichersten die volle Punktzahl gibt.

volkard

wgerhtrj schrieb:

Jetzt habe ich erfahren, dass dies der "Gosper-Algorithmus" ist.(Was zur Hölle...) Das höre ich gerade zum allerersten mal. Hab danach gegoogelt, und kann zwischen diesem Gospel und dem Listing keinen Zusammenhang erkennen.

Jo, Gosper's Algorithm ist auch was total anderes. "An Algorithm for finding closed form Hypergeometric Identities."

Für den Gosper's-Hack gibt es anscheinend inzwischen bessere Implementierungen, hier einer, der noch die Ursprüngliche Form nimmt.
http://read.seas.harvard.edu/cs207/2012/?p=64

Weils gerade passt:
http://www.pvv.org/~oma/DeepC_slides_oct2011.pdf

Bashar

volkard schrieb:

Ich bekam mal keine Punkte, weil für mich f(x)=c und f(x)=x Polynome waren, aber er war da ganz anderer Ansicht. wtf..??!!

Vielleicht wollte er darauf hinaus, dass es Polynomfunktionen sind.

volkard

Bashar schrieb:

volkard schrieb:

Ich bekam mal keine Punkte, weil für mich f(x)=c und f(x)=x Polynome waren, aber er war da ganz anderer Ansicht. wtf..??!!

Vielleicht wollte er darauf hinaus, dass es Polynomfunktionen sind.

Ähm, f(x)=5 ist doch auch eine Polynomfunktion, oder?

Das Fach war "Datensicherheit" oder sowas bei einem Lehrbeauftragten. Teil des Spezialisierungsschwerpunkts "Datenschutz". Helau, wer modernistisch tagesaktuellen unausgegorenen Schott belegt, und mehr Semesterwochenstunden abrockt, als sein müssten, verschwendet nicht nur seine Zeit, sondern senkt auch noch seine Note. Ähnliche Dinger gab es in jedem anderen Fach dieses Spezialisierungsschwerpunkts, außer bei "Kryptologie", das hielt eine Mathe-Prof. Da hätte ich beinahe eine 2 gekriegt, aber das war allein meine Schuld.

Es ging darum, uns Idioden-Studenten ein wenig begreiflich zu machen, daß es so manche Sachen gibt, die eher harmlos zu berechnen sind und manche, da steht man davor wie vor einer Wand. Lehrinhalte quasi aus der c't kopiert und wenn's nicht reicht, auch mal die Computerbild.

Sah ungefähr wir folgt aus:
(Hab schonmal angekreuzt, bei 'f' waren wir anderer Meinung.)

Bitte ankreuzen:

Die Funktion f ist...

f(x)    |  konstant | linear | quadratisch | polynomisch | exponentiell 
-----------------------------------------------------------------------
  2^x   |           |        |             |             |     x
-----------------------------------------------------------------------
   5    |     x     |        |             |      f      |
-----------------------------------------------------------------------
  x^2   |           |        |      x      |      x      |
-----------------------------------------------------------------------
   x^3  |           |        |             |      x      |
-----------------------------------------------------------------------
   x    |           |    x   |             |      f      |
-----------------------------------------------------------------------
(2^x)/x |           |        |             |             | x //wer die 1 verdient
-----------------------------------------------------------------------

Bashar

volkard schrieb:

Bashar schrieb:

volkard schrieb:

Ich bekam mal keine Punkte, weil für mich f(x)=c und f(x)=x Polynome waren, aber er war da ganz anderer Ansicht. wtf..??!!

Vielleicht wollte er darauf hinaus, dass es Polynomfunktionen sind.

Ähm, f(x)=5 ist doch auch eine Polynomfunktion, oder?

Ja, aber vielleicht kein Polynom (hängt von der vereinbarten Schreibweise ab).

(Ein Polynom ist durch seine Koeffizienten definiert und eine Funktion durch ihre Wertepaare, was bedeutet, dass zwei verschiedene Polynome als Funktion interpretiert gleich sein können.)

Aber da es bei dir anscheinend um Komplexitätsklassen ging, kann es das eher nicht gewesen sein BTW das ist komisch, weil polynomiale Laufzeit ja lediglich bedeutet, dass die Laufzeit asymptotisch durch ein Polynom beschränkt ist, also ist sogar log, Wurzel, Sinus etc. polynomiell, insbesondere natürlich 5 und x.

volkard

Abgesehen von dem Problemchen damals…

Bashar schrieb:

Ein Polynom ist durch seine Koeffizienten definiert und eine Funktion durch ihre Wertepaare, was bedeutet, dass zwei verschiedene Polynome als Funktion interpretiert gleich sein können.

Leuchtet mir sofort ein. Mir fällt nur gerade kein Fall ein. Bin wohl zu fest damit verhaftet, als Grundmenge die Reellen Zahlen zu nehmen.

Nehmen wir als Definition des Polynoms mal
http://de.wikipedia.org/wiki/Polynom#Definition

Kannste mir auf die Schnelle mal ein Beispiel liefern, damit ich darüber träumen kann? (Bin im Umzug, Fernseher weg, vermutlich endgültig, Mathe-Träumen ist gut, mach ich schon die letzten drei Tage.)

Bashar

Klar: x^2 + x\in\mathbb{F}_2[x] ist (als Funktion auf $\mathbb{F}_2$ ) überall 0.

volkard

Bashar schrieb:

Klar: x^2 + x\in\mathbb{F}_2[x] ist (als Funktion auf $\mathbb{F}_2$ ) überall 0.

lol!
klar.

Wenn schon, denn schon: 5 ist nicht nur konstant und polynomisch, sondern auch linear.

Überhaupt: 5 = 0 * x² + 5 ist auch quadratisch, und in welcher Mathematik bitte ist 2^x / x eine Exponentialfunktion? Lasst euch den Graphen mal plotten und vergleicht.

volkard

seldon schrieb:

Wenn schon, denn schon: 5 ist nicht nur konstant und polynomisch, sondern auch linear.

Uups, übersehen. http://de.wikipedia.org/wiki/Lineare_Funktion

seldon schrieb:

Überhaupt: 5 = 0 * x² + 5 ist auch quadratisch,

Nö, das dann doch nicht.
http://de.wikipedia.org/wiki/Quadratische_Funktion

seldon schrieb:

und in welcher Mathematik bitte ist 2^x / x eine Exponentialfunktion? Lasst euch den Graphen mal plotten und vergleicht.

Haste sie jetzt nur zwischen x=-2 und x=2 plotten lassen?
Also ich würde mal sagen 1.99^x < 2^x/x < 2^x für alle x>=1453, insofern ist sie mir für Komplexitätsüberlegungen exponentiell genug. Ist sie nicht?

Jaaaa...bei der quadratischen Funktion muss ich dir Recht geben. Ich hatte, zugegeben, nicht auf dem Schirm, dass a != 0 gefordert ist.

Bei der Exponentialfunktion sehe ich die Dinge dann aber doch anders. Ob eine Funktion eine Exponentialfunktion ist, hat erstmal wenig mit Komplexitätsklassen zu tun, und 2^x / x verhält sich in vielen Dingen anders als Exponentialfunktionen.

Wenn wir über Komplexitätsklassen reden wollen, sieht die Sache wieder ganz anders aus -- da sprechen wir ja größtenteils über Teilmengen. Eine Funktion, die zeitlich mit Θ(2^x / x) skaliert, ist in EXPTIME, aber das ist mit 5, x, x² und x³ auch der Fall. f(x) in O(1) impliziert f(x) in O(n²), aber f(x) in Θ(2^x/x) impliziert f(x) nicht in Θ(2^x), und beide dieser Dinge implizieren f(x) nicht in Θ(1.99^x). Was ist also unser Kriterium?