Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Algorithmen und Datenstrukturen
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> Algorithmen und Datenstrukturen
 
Autor Nachricht
movdel
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 12.10.2009
Beiträge: 1

BeitragVerfasst am: 12 Okt 2009 - 20:34:55    Titel: Algorithmen und Datenstrukturen

Ich habe jetzt den Kurs "Algorithmen und Datenstrukturen" und wir sollen bis Freitag folgende Aufgaben lösen, aber ich verstehe gar nix. Kann mir jemand helfen? Nur die Lösungen würden mich nicht viel weiter bringen, will und muss es ja auch verstehen. Also ne kleine erläuterung wäre nicht schlecht.



Aufg1:

Sei f ( n ) =O(h( n )), g( n )=O(h( n ))
– Ist f( n )+g( n )=O(h( n ))?
– Ist f( n )·g( n )=O(h( n ))?
Beweisen Sie Ihre Behauptung.




Aufg2:

Peter und Paul streiten sich über die Effizienz eines Algorithmus. Peter sagt, sein O(n·logn)-Algorithmus sei immer schneller als Pauls O(n^2)-Alg. Sie implementieren beide Algorithmen. Zu Peters Enttäuschung finden sie heraus, dass für n<100 der O(n^2)-Algorithums schneller ist und nur wenn n>=100 ist, ist der O(n·logn)-Algorithmus besser.

Erläutern Sie, warum das obige Szenario möglich ist. Numerische Beispiele sind erlaubt.




Aufg3:

Lösen der „Türme von Hanoi“.

Dazu sind Umschichtungen von n Scheiben nötig. Es kann gezeigt werden, dass ein Lösungsansatz T( n ) viele Umschichtungen benötigt, mit

T(1)=1 und
T( n )=2·T(n-1)+1.

Lösen Sie diese Rekursion auf, um eine geschlossene Formel für T( n ) zu erhalten. (Geschlossene Form ist eine Formel der Art T( n ) = term, wobei die Funktion T in term nicht vorkommt.)

Eine Beschreibung der Türme von Hanoi finden Sie auf der folgenden Web-Site. Dort finden Sie auch das Ergebnis der Auflösung der Rekursion. Gefragt ist aber der Weg dorthin...




Aufg4:

Bestimmen Sie für jede Funktion f( n ) und Zeit t in der Tabelle den größten Umfang n eines Problems, das in Zeit t gelöst werden kann. Dabei wird angenommen, dass der Algorithmus zur Lösung des Problems f( n ) Mikrosekunden benötigt. (log n ist Log. zur Basis 2)

1 Sekunde 1 Stunde 1 Monat 1 Jahrhundert
log n ≈ 10 ^300000
√n
n
n log n
n^2
n^3
2^n
n! 12







Danke, movdel
Raziela12
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 05.10.2008
Beiträge: 557

BeitragVerfasst am: 12 Okt 2009 - 22:35:52    Titel:

schön, dass du dir keinen einzigen Gedanken selbst gemacht hast. So wirste hier nicht viel Hilfe bekommen, und bei der Einstellung würd ich das Studium evtl auch nochmal überdenken.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> Algorithmen und Datenstrukturen
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum