irgendein Algorithmus beweisen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 16:33 So 11.01.2009 | | Autor: | start |
| Aufgabe | a) Zeigen Sie formal, dass [mm] 1024*n^{2}+5*n+7*n*log(n)\in teta?(n^{2}) [/mm] gilt.
b) FÜr welche narbeitet einAlgorithmus mit Zeitbedarf [mm] 256*n^{2} [/mm] auf der gleichen Maschine schneller als ein Algorithmus mit Zeitbedarf [mm] 2^{n}, [/mm] für welche n arbeitet er langsamer. Begründen sie Ihre Antwort. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo vorhilfe.de
wir haben diese Woche die obige Aufgabe als einen Teil unserer wöchentlichen Aufgaben. Leider muss ich gestehen das ich bzw wir völlig planlos vor der Aufgabe stehen und nicht wirklich wissen wie man Formal so etwas begründet / beweist.
Gibt es hier vllt jemanden der uns bei dieser Aufgabe auf irgendeine Art helfen kann :( sind wirklich für jede Hilfe Dankbar!
mfg
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:57 So 11.01.2009 | | Autor: | bazzzty |
> a) Zeigen Sie formal, dass [mm]1024*n^{2}+5*n+7*n*log(n)\in teta?(n^{2})[/mm]
> gilt.
Vielleicht schaust Du Dir mal die Definition von [mm] \Theta(f) [/mm] an -- Du brauchst ein $c$ und ein [mm] $n_0$. [/mm] Im Zweifel einfach beides ziemlich groß wählen und nur noch nachrechnen. Wenn Du nicht weiterkommst, schreib hin, wo Du hängst.
> b) FÜr welche narbeitet einAlgorithmus mit Zeitbedarf
> [mm]256*n^{2}[/mm] auf der gleichen Maschine schneller als ein
> Algorithmus mit Zeitbedarf [mm]2^{n},[/mm] für welche n arbeitet er
> langsamer. Begründen sie Ihre Antwort.
Wo hängst Du? Die Frage heißt: Für welches $n$ ist [mm] $256*n^2<2^n$.
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:13 So 11.01.2009 | | Autor: | start |
also b hatten wir so oder so raus... zwar 16 ^^ war net zu schwer... hatte ich nur vergessen zu erwähnen
allerdings die erste aufgabe! die Definition sagt mir absolut mal garnix und hatten wir auch nicht in den vorlesungen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:32 Mo 12.01.2009 | | Autor: | bazzzty |
> also b hatten wir so oder so raus... zwar 16 ^^ war net zu
> schwer... hatte ich nur vergessen zu erwähnen
>
> allerdings die erste aufgabe! die Definition sagt mir
> absolut mal garnix und hatten wir auch nicht in den
> vorlesungen
Ich helfe ja gerne dabei, die Aufgabe zu verstehen, aber dafür wäre es hilfreich, zu wissen, wo ihr steht. Wenn Du Deinen Hintergrund ins Profil einträgst, wüßte ich z.B. in welchem Semester Du bist. Es ist auch einfacher, wenn ihr etwas konkreter sagt, wo ihr hängt. Wenn ihr eine Definition nicht versteht, schreibt sie wenigstens hin. Sonst redet man aneinander vorbei.
So kann ich nur ganz allgemein mal nachhaken:
Ist euch klar, wann für zwei Funktionen [mm] $f,g:\IN\to\IN$ [/mm] gilt, dass [mm] $f\in [/mm] O(g)$, d.h. kennt ihr die Definition und habt sie verstanden?
[mm] $f\in O(g):\Leftrightarrow \textrm{es gibt ein\ }c>0\textrm{\ und ein\ }n_0\in \IN\textrm{, so dass\ }f(n)\leq cg(n)\textrm{\ für alle\ } n\geq n_0$
[/mm]
Wenn das klar ist: Könnt ihr zeigen, dass [mm] $n^2+n\in O(n^2)$, $3n^2+17\in O(n^3)$ [/mm] und [mm] $2^n\not\in O(n^3)$?
[/mm]
Wenn ihr soweit seid, dann sollte es nicht so schwer sein, die Aufgabe zu lösen. Etwas einfacher ist es, wenn man verstanden hat, daß
[mm] $f\in \Theta(g):\Leftrightarrow f\in O(g)\textrm{\ und\ }g\in [/mm] O(f)$
Sagt einfach mal, an welcher Stelle ihr aussteigt. Wenn ihr selbst noch irgendwo nachlesen wollt: $O$ und [mm] $\Theta$ [/mm] gehören zu den sogenannten "Landau-Symbolen". Die Wiki-Seite ist weniger hilfreich, aber es gibt viele andere Quellen, auch im Internet.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 Di 13.01.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
