Beweis von Teilmengenbeziehung < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Beweisen Sie die Aussagen:
a) f [mm] \in [/mm] O(g) [mm] \gdw [/mm] g [mm] \in \Omega [/mm] (f)
b) O(f) [mm] \subseteq [/mm] O(g) [mm] \gdw \Omega [/mm] (g) [mm] \subseteq \Omega [/mm] (f) |
Hallo,
ich habe diese Frage in keinem anderen Forum gestellt,
ich weiß nur, dass es um Teilmengenbeziehungen geht, ich habe leider keinen Plan, welche Bedeutung das O bzw. [mm] \Omega [/mm] in dieser Aufgabe haben, dadurch ist mir auch die Zuordnung in ein entsprechendes Forum unklar.
Danke an alle Teilnehmer im Matheraum
Steffi
|
|
| |
|
> ich weiß nur, dass es um Teilmengenbeziehungen geht, ich
> habe leider keinen Plan, welche Bedeutung das O bzw. [mm]\Omega[/mm]
> in dieser Aufgabe haben, dadurch ist mir auch die Zuordnung
> in ein entsprechendes Forum unklar.
Hallo,
vielleicht erinnerst Du Dich ja noch an das Fach und daran, worum es sich im Moment dreht.
Falls das nicht der Fall ist, ist es ja völlig sinnlos, wenn Du Dich mit der Aufgabe beschäftigst.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:04 Mo 23.10.2006 | | Autor: | Steffi21 |
es handelt sich um eine Aufgabe aus einer Übungsserie Informatik, es hat aber meiner Ansicht nach nicht direkt mit Informatik zu tun, die anderen Übungsaufgaben dieser Serie habe ich mit vollständiger Induktion gelöst
Steffi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:20 Mo 23.10.2006 | | Autor: | noresund |
Das hat sehrwohl was mit Informatik zu tun, nämlich mit der Laufzeit.
Die Laufzeit gibt an, wieviele Schritte ein Algorithmus bei einer Eingabelänge n benötigt.
Die Funktion T(n) beschreibt diese Anzahl genau.
Dann gibt es noch Komplexitätsklassen, mit denen man T(n) abschätzen kann, die sogenante 0-Notation, bzw Omega-Notation.
Grob gesagt:
Eine Funktion f(n) ist Element von O(g(n)), wenn f(n) [mm] \le [/mm] c*g(n). c [mm] \in \IR [/mm]
g(n) beschreibt eine asymptotische obere Schranke.
Omega-Notation
T [mm] \in [/mm] Omega(g): T(n) wird durch g(n) nach unten beschränkt, wenn gilt:
Es ex. ein [mm] n_{0} \in \IN [/mm] >1, c [mm] \in \IR>0: [/mm] für alle n [mm] \ge n_{0}: [/mm] c*g(n) [mm] \le [/mm] T(n)
Aber falls du das noch alles gar nicht hattest, hast du jetzt einen kleinen Überblick.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:20 Mi 25.10.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
