O-Kalkül < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:06 Di 04.01.2005 | | Autor: | Rusty |
Sei g(n) [mm] \in [/mm] O(f1(n) und h(n) [mm] \in [/mm] O(f2(n))
Beweise die Multiplikationsregel g(n) * h(n) [mm] \in [/mm] O(f1*f2)
Ich weis das ist wohl super easy aber ich check das mit dem O-Kalkuel irgendwie nicht(was das ist schon, aber die mathematische Beweisführung nicht). Für ne schnelle Lsg. wäre ich super dankbar.
Hat jemand vielleicht noch nen brauchbaren Buchtipp wo so Sachen wie eben O-Kalkuel, boolsche Algebra etc. auch für nicht Mathematiker brauchbar erklärt ist.
Bin ja eigentlich Biologe - und Programmieren lernen und noch der ganze Mathe sch*** ist echt irgendwie zuviel zur zeit :-(
Noch so ein komischer Beweis:
Auf wie viele verschiedene Arten kann ein 2 * n Brett mit Dominosteinen der Groeße 2*1 überdeckt werden(Beweisen Sie die Behauptung)
Leider auch keine Ahnung. Auch hier wäre ich für ne schnelle Lsg echt dankbar! Geht um meine Klausurzulassung!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo Rusty!
Wir freuen uns hier auch über eine Anrede! 
> Sei g(n) [mm]\in[/mm] O(f1(n) und h(n) [mm]\in[/mm] O(f2(n))
>
> Beweise die Multiplikationsregel g(n) * h(n) [mm]\in[/mm]
> O(f1*f2)
>
> Ich weis das ist wohl super easy aber ich check das mit dem
> O-Kalkuel irgendwie nicht(was das ist schon, aber die
> mathematische Beweisführung nicht). Für ne schnelle Lsg.
> wäre ich super dankbar.
Nach meiner Definition würde ich das so machen:
[mm] g(n)\in O(f_1(n)) \gdw g(n)\le C_1f_1(n)
[/mm]
[mm] h(n)\in O(f_2(n)) \gdw h(n)\le C_2f_2(n)
[/mm]
also [mm] \Rightarrow
[/mm]
[mm] g(n)h(n)\le C_1f_1(n)C_2f_2(n)=C_1C_2f_1(n)f_2(n) \in O(f_1f_2) [/mm] mit [mm] C:=C_1C_2
[/mm]
Ganz sicher bin ich mir nicht, aber ich glaube, viel schwieriger kann's eigentlich nicht sein!
> Hat jemand vielleicht noch nen brauchbaren Buchtipp wo so
> Sachen wie eben O-Kalkuel, boolsche Algebra etc. auch für
> nicht Mathematiker brauchbar erklärt ist.
Eine Buchtipp hätte ich schon, ich weiß aber nicht, ob man das auch als nicht-Mathematiker versteht: Probier's mal mit "Theoretische Informatik" von Alexander Asteroth und Christel Baier (Frau Baier hat letztes Semester unsere Info-Vorlesung gelesen und die war total super!), erschienen bei Pearson Studium. Das Buch ist recht teuer und handelt eben von Theoretischer Informatik, wenn du nur die Mathematik haben möchtest, lohnt es sich wahrscheinlich nicht, es zu kaufen. Aber guck doch mal in der Bibliothek. Außerdem findet man dort in der Regel Bücher wie: Mathematik für nicht-Mathematiker oder Mathematik für Naturwissenschaftler, vielleicht findest du da ja was Brauchbares.
> Bin ja eigentlich Biologe - und Programmieren lernen und
> noch der ganze Mathe sch*** ist echt irgendwie zuviel zur
> zeit :-(
Ja, das verstehe ich! Selbst ich als Informatiker kann immer noch nicht programmieren...
> Noch so ein komischer Beweis:
>
> Auf wie viele verschiedene Arten kann ein 2 * n Brett mit
> Dominosteinen der Groeße 2*1 überdeckt werden(Beweisen Sie
> die Behauptung)
Da würde ich es erstmal für verschiedene n ausprobieren, mit ein bisschen Kombinatorik-Wissen müsste man da was hinbekommen. Aber ich lasse die Frage mal auf halb-beantwortet, vielleicht kann dir da jemand anders mehr helfen!
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:23 Mi 05.01.2005 | | Autor: | Rusty |
Hey Bastiane!
Danke Dir fuer die schnelle Hilfe. Sieht Klasse aus Dein Beweis  !
Ich werde das wohl einfach so übernehmen.
Das mit den Buechern fuer Nicht-Mathematiker habe ich natuerlich schon versucht aber irgendwie war das leider nicht sehr erfolgreich. Denke da muss wohl mal ne "Nachhilfe" her.
Gruss Rusty!
Falls jemandem noch was zum 2. Punkt einfällt schreibt bitte !
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:29 Mi 05.01.2005 | | Autor: | Alef0 |
Hallo Rusty,
Bin mir nicht ganz sicher, ob ich die Fragestellung richtig verstanden habe.
Ich gehe von einem 2D Brett aus mit der horizontalen Länge 2 und der vertikalen Länge n (also ein hohes Brett für die meisten n ;). Desweiteren nehme ich an das die Dominosteine nicht unterschieden werden.
1.
Steine können auf 2 Arten gelegt werden: horizontal und vertikal
2.
Da das Brett vollständig abgedeckt werden soll, dürfen keine zwei Steine vertikal um ein Feld versetzt zueinander gelegt werden.
3.
Die Anzahl der Möglichkeiten wird daher lediglich von den horizontal gelegten Steinen bestimmt.
4. Ist n ungerade muss eine ungerade Anzahl von Steinen horizontal gelegt werden. Analog muss bei n gerade eine gerade Anzahl von Steinen horizontal gelegt werden.
Für n gerade gilt also:
[mm] \summe_{i=0}^{n/2} \vektor{n \\ 2*i}
[/mm]
Für n ungerade gilt:
[mm] \summe_{i=0}^{n/2-.5} \vektor{n \\ 2*i+1}
[/mm]
Das läßt sich auch zu einer Formel zusammenfassen, ich find hier nur leider keine Zeichen zum Abrunden
Ist natürlich kein Beweis, aber ich hoffe, es hilft.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:30 Mi 05.01.2005 | | Autor: | Rusty |
Danke Dir fuer die Mühe Alef0!
Mir raucht gerade sowieso der kopf ab von daher werde ich das wohl auch einfach so übernehmen ( ganzen Tag code getippelt).
Mit dem was ich selber geschaft habe, und eurer Hilfe habe ich dann wohl meine Klausurzulassung geschaft.
Muss die Sache bis spätestens Fr. 9:15 Uhr
abgegeben haben. Vielleicht tut sich ja noch was bzgl. Beweis........
Vorhilfe rockt !!!!!!
|
|
|
|
