Problem mit einem kompliziertem Ausdruck

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?