Informatik: Kryptisches Mathe

[XXXNA]

Hi,

es ist mal wieder so weit: Ich komme nicht mehr weiter. Im Anhang eine pdf-Datei, die die Aufgaben für diese Woche zeigt.

Aufgabe 7 und 8 habe ich fertig und auch richtig, da bin ich mir sicher.

Nur die AUfgaben 9 und 10 sind mir ein Rätzel.

10 würde ich mit einigem Aufwand vllt. noch hinkriegen, aber 9, da verstehe ich ja nicht mal die Bedeutung aller Zeichen^^

Wäre vllt. ganz nett, wenn wer die Zeile aus 9a mal auf deutsch übersetzt^^.

Vielen Dank, wenn mir wer helfen kann.

 

[DonQuintal]

Hi,
ist bei mir lange her. Aber als Einstieg hilft es vielleicht:
9a)
Die zweite Aussage ist in der ersten enthalten. Wenn die Aussage für jedes n gilt, dann muss sie auch für ein bestimmtes n0 gelten. Einzig verwirrend ist die Einschränkung, dass die Bedingung: "für jedes n >= n0" hinzugefügt ist. Allein die Einschränkung N verhindert aber, dass man ebenso "A n <= n0" schreiben könnte. Damit würde der Wertebereich beliebig nach Z erweitert werden.
Wenn also n0 die Bedingungen des Wertebereichs erfüllt, dann muss es auch jedes n, dass größer ist.

 

[DonQuintal]

9b)
Was muss passieren, damit der Limes im unentlichen zu 0 wird? Entweder der Zähler wird 0 oder der Nenner unendlich. Beide 0 oder unendlich ist nicht zulässig (Hospital). Ob für beide Funktionen ein Grenzwert existieren muss, kann ich nicht sagen. Vermutlich ja. Allerdings hat die Funktion f(m)=(-1)^m (m El N) keinen Grenzwert, aber für g(n),n->unendl würde der gesamte Ausdruck gegen 0 streben.
Es soll nicht gezeigt werden, dass f(n) ein Teil von g(n) ist. Vielmehr soll f(n) durch die Komplexitätsbeschreibung von g(n) ebenfalls eindeutig beschrieben sein.

 

[stefros]

O(g) := {f | 9 c 2 R+ : 8n 2 N : f(n)  c · g(n) }

Auf Deutsch heisst das:

O von g ist die Menge aller Funktionen f die die Bedingung erfüllen, daß ein c aus R*+ existiert für das gilt, daß für alle n € N gilt, daß f(n) kleiner gleich diesem c mal g(n) ist.

Drunter steht ja fast das Selbe.

Die Definitionen sind allerdings soweit ich das sehe nicht equivalent solange nichts über die Monotonität der beiden Funktionen gesagt ist. Bei der unteren Definition kann ja durchaus ein n1 kleiner als n0 existieren für das f(n) größer als g(n)*c ist. Ausser die Funktionen sind beschränkt? Ist das mit Abbildung nach R*+ impliziert? Dazu müsstest du Osbes fragen. ^^
Sonst würd ich durch Gegenbeweis einfach beweisen dass es nicht so ist.

 

[DonQuintal]

O(g) := {f | 9 c 2 R+ : 8n 2 N : f(n)  c · g(n) }

... Bei der unteren Definition kann ja durchaus ein n1 kleiner als n0 existieren für das f(n) größer als g(n)*c ist....

Hi stefros,

das wird doch durch: "Für jedes n größer/gleich n0" eingeschränkt. Die obere Definition beinhaltet alle n. Die Untere ist bei einem einzigen n0 und allen n größer diesem n0 erfüllt. Man bräuchte also den Wertbereich der oberen Komplexität nur auf alle n>=n0 einschränken. Damit ist wenigstens gezeigt, dass die untere Komplexität in der oberen enthalten ist.

Oder anders:
Die obere Definition beeinhaltet alle n C N. Die untere wählt aus dieser Menge ein festes n0 aus und sagt dann, dass die Beziehung der Definitionen für alle n>= diesem n0 gilt. Die obere Definition lässt sich also durch abschnittsweises Definieren ab einem n0 derart erweitern, dass man die zweite erhält. Für die Gegenrichtung muss man das c hinzuziehen. Zu beachten ist hier, dass es ein festes c ist und was es mit den Funktionen an den Stellen 0, 1 und unendlich macht. Ohne Kenntnis über g(n) und f(n) kann man keine Aussage treffen. Gibt es ein solches c für die obige Definition und sind g(n), f(n) und c bei beiden Definitionen identisch, sind beide Definitionen ohnehin identisch.

 

[Macross]

Ist das kompliziert. Ich verstehe nicht 1 einziges Wort. Was genau bezweckt dieses kryptisches Mathe?

 

[DonQuintal]

Ist das kompliziert. Ich verstehe nicht 1 einziges Wort. Was genau bezweckt dieses kryptisches Mathe?

Manche Probleme lassen sich zu unseren Lebzeiten oder zu "Lebzeiten" eines Computers gar nicht lösen. Er brauch einfach zu lange. Ein beliebtes Beispiel dafür ist "Die Türme von Hanoi". In dem Link gibt es weiter unten einen Punkt "Praktische Unlösbarkeit" und die nebenstehende Tabelle.
Entwirft man ein Computerprogramm oder ein technisches Gerät will man wissen, welche Werte man dem Programm vorgeben darf und wie lange es mit der verwendeten Rechenmethode im Extremfall braucht.

Die Lösung der Probleme erfolgt durch mathematische und logische Funktionen. Mit dieser Schreibweise gibt man an, unter welchen Bedingungen eine solche Funktion gültig ist.

 

[Osbes]

Ich habe mir mal nicht durchgelesen, was meine Vorposter so geschrieben habe, daher ist es ggf. doppelt.

Die sog. O-Funktion ist eine obere Schranke für das Laufzeitverhalten von Algorithmen und kommt ganz gerne in Vorlesungen wie "Komplezität von Algorithmen", "Datenstrukturen und Algorithmen", "Programmieren I usw.", "Programmiersprachen und Übersetzer", ... vor, es ist also sehr wichtig die O-Funktion zu kennen.

Die 1. Aussage ist:

Die Menge O(g) enthält Fnktionen f für die gilt, dass für ein c aus den postiven reellen Zahlen gilt, dass für ALLE n aus den natürlichen Zahlen gilt, dass f(n) kleiner gleich c * g(n) ist.

Die 2. Aussage ist:
Die Menge O(g) enthält Fnktionen f für die gilt, dass für ein c aus den postiven reellen Zahlen gilt, dass ab einem n_o aus den natürlichen Zahlen für ALLE n größer gleich n_0 gilt, dass f(n) kleiner gleich c * g(n) ist.

Diese Aussagen sind gleich, denn bei der 2. Aussage fehlen endlich viele n und da gibt es dann einen maximalen Wert f(n_i), weshalb ich mein c in der 1. Aussage so skalieren kann, dass dort die Funktion auch drin ist.
Das es auch umgekehrt drin ist folgt eigentlich schon aus der Definition.


Probier halt erstmal den Beweis (du musst zeigen, dass die 1. Menge eine Teilmenge der anderen ist und umgekehrt und dass macht man in dem man irgendein f aus der 1. Menge nimmt und zeigt, dass es auch in der 2. ist - und umgekehrt).
Wenn du irgendwann nicht weiterkommst kann ich dir natürlich gerne helfen

######

Ich denke sobald du verstanden hast was die O-Funtion ist kann man sich der Omega-Funktion (die wirkt genau umgekehrt) und der Theta-Funkion (dann gelten beide Aussagen) zuwenden.

Unter dem Begriff Landau-Symbole solltest du einige Beispiele finden, dann kannst du es dir vll besser vorstellen (wobei die Def. natürlich jedes Beispiel beinhaltet).

######

9b)
Was muss passieren, damit der Limes im unentlichen zu 0 wird? Entweder der Zähler wird 0 oder der Nenner unendlich. Beide 0 oder unendlich ist nicht zulässig (Hospital). Ob für beide Funktionen ein Grenzwert existieren muss, kann ich nicht sagen. Vermutlich ja. Allerdings hat die Funktion f(m)=(-1)^m (m El N) keinen Grenzwert, aber für g(n),n->unendl würde der gesamte Ausdruck gegen 0 streben.
Es soll nicht gezeigt werden, dass f(n) ein Teil von g(n) ist. Vielmehr soll f(n) durch die Komplexitätsbeschreibung von g(n) ebenfalls eindeutig beschrieben sein.

Oder anders gesagt:
Wenn f(n) im ab einem n_0 für alle n>=n_0 langsamer wächst als g(n), dann ist es ein Element von O(g).

Das es andersrum nicht geht sieht man übrigens, wenn man sich z.b. zwei konstante Funktionen =!= 0 anschaut.

 

[XXXNA]

Danke für die Antworten, aber verstehen tu ich davon momentan irgendwie nich allzu viel. Besonders der Sinn dieses Zeugs will mir nicht in den Kopf.

Ich habe jetzt Folgendes als Antwort geschrieben zu zu 9 a und b:

9a)

In beiden Fällen existiert ein c € R^+. Es ist also zu untersuchen, ob für O(g(n)) in beiden beschriebenen Fällen in Bezug auf alle „n“ das Gleiche gilt, um die Äquivalenz zu zeigen:

Fall I: n ist € N.
Fall II: Es gibt ein n_0, das den Anfangswert der Komplexität darstellt und € N ist. Alle weiteren n sind größer n_0. Damit gilt auch hier, dass n_0 in die Reihe der n integriert werden kann, so dass n € N.
Somit ist Fall I äquivalent zu Fall II.

b)

Aus lim┬(n→ ∞)⁡〖(f(n))/(g(n))〗 = 0 folgt, dass g(n) schneller gegen ∞ strebt als f(n) oder f(n) schneller gegen 0 als g(n). D.h. g(n) stellt die obere Schranke der Funktion f(n) dar. Somit ist f(n) natürlich € O(g(n)).

 

[DonQuintal]

zu 9a)
Fall I: n ist gemäß Definition immer € N. Das macht die Fallunterscheidung obsolet.
Fall II: Was willst Du mit dem Integral? Male Dir einen Zahlenstrahl auf und trage dort ein paar Werte ein:
von wo bis wo ist die erste/ die zweite Definition gültig?
was ist das n0 und wo kann es liegen?
Was musst Du tun, damit aus der ersten die zweite Definition wird? Schau Dir das auf dem Strahl an.
Mache Dir klar, dass das c zwar frei gewählt werden kann, aber nach der Wahl fest ist. In der Definition steht: "Es gibt (wenigstens) EIN (einziges) c aus dem positiven Bereich der reellen Zahlen."
Suche einen Fall, für den BEIDE Definitionen gültig sind. Was kann man dann ändern, was in der Definition erlaubt ist und beide Fälle nicht mehr gleichzeitig gelten.
gemäß Definition kommt nur der Bereich >0 in betracht. Je nachdem, ob c größer oder kleiner 1 ist (mache Dir das mit einer Wertetabelle deutlich, falls es nicht sofort einleuchtet) kann man den gesamten Werteberich betrachten oder es gibt eine Knickstelle bei 1. Male Dir dann f(n) auf. Das sind nur Punkte und keine durchgezogene Linie! f(n) ist nur bei natürlichen n definiert! g(n) muss darunter verlaufen.

Auf zur Zeichnung!

 

[XXXNA]

So, im Anhang mal unser Endergebnis.

Vllt. bringt das wenigstens ein paar Punkte. Mathematisch beweisen müssen wir Nummer 9 übrigens nicht, nur Nummer 10.
Daher habe ich noch ein wenig Hoffnung, dass es wenigstens etwas gebracht hat, dieses Zeug aufzuschreiben.

Meinungen zu 9 und 10?

 

[DonQuintal]

Windows sagt: Datei ist ungültig oder beschädigt.

 

[XXXNA]

Ach zum Teufel. Wieso funktioniert in diesem Forum docx noch immer nicht?

 

[Speex]

also ich konnte es downloaden

 

[DonQuintal]

Hi,
zum Download: Scheint ein Problem meiner Windows-Installation zu sein. Ich kann auch das Word-Dokument nicht lesen. Habe flink eine Ubuntu-LiveDVD gestartet. Jetzt geht es.

Zum Problem:
Die Erklärungen zu 9) scheinen so ok zu sein. Ich bin kein Mathematiker, sondern Ingenieur. Bei mir muss es funktionieren. Wer ein funktionierendes Gerät abliefert hat recht Die Mathematiker wollen es noch richtig hinschreiben. Dafür braucht es keinen praktischen Nutzen zu haben. Dieses Problem hat aber einen Nutzen.

 

[XXXNA]

Ich als Wirtschaftsinformatiker rege mich ja die ganze Zeit drüber auf, dass wir das alles so theoretisch formal machen.... Bei uns geht´s eben auch drum, DASS es funktioniert und dass es effektiv und effizient ist. Die Informatiker interessiert der theoretische Hintergrund leider etwas mehr^^.


Was hälst du von den Erklärungen zu 10? Wobei du als Ingeneur nicht allzu viel damit zu tun haben wirst, oder?

Danke jedenfalls sehr!

 

[DonQuintal]

Zu 10 kann ich außer Klugsch... nix sagen. Kann ich nicht und sehe im Moment keine Notwendigkeit es mir anzueignen.
Wir mussten im ganzen Studium keinen einzigen mathematischen Beweis machen. Sich den restlichen Mathestoff in den Kopf zu prügeln war hart genug......Aber Spaß hat es gemacht

Wo studierst Du Wirtschaftsinformatik? Ich hatte es mal an der Uni-Siegen angefangen. War mir aber nichts.
€: Habs schon. Wird wohl Münster sein

 

[AgentLie]

Moin! Ich hab jetzt keine Zeit das ordentlich aufzuschreiben, aber ich geb trotzdem mal meinen Senf zu der Aufgabe 9 ab.
9.a) Zu zeigen ist wie bereits gesagt die Gleichheit der Mengen. Insbesondere reicht es die Gleichheit der Bedingungen nachzuprüfen.
Die zweite Bedingung folgt offensichtlich aus der ersten (setze n_0=0). Die erste Bedingung folgt zunächst nur für n>=n_0 aus der zweiten. Da es sich aber um Funktionen von N->R^+ handelt ist die Aussage trivial. Man definiert einfach ein geeignetes c, nämlich folgendermaßen:
f(0) <= c_0g(0), f(1) <= c_1g(1),...,f(n_0-1) <= c_{n_0-1}g(n_0-1) und c = max{c_0,...,c_{n_0-1},c_{Bedingung 2}}. Dieses c hat die gewünschten Eigenschaften.

9.b) lim f(n)/g(n)=0 bedeutet doch: Für alle epsilon>0 existiert ein n_0, so dass für alle n>=n0 f(n)/g(n)<=epsilon <=> f(n)<=epsilon g(n) <=> f(n) Element von =(g(n)).

Edit: Die Schreibweise aus Aufgabe 10 kenne ich leider nicht. Was bedeutet denn das Omega und das Kleinomega?

 

[Osbes]

@Anhang
Also ich habe einen .docx -> .doc Konverter von Windows, jedoch ist die Datei danach immernoch Fehlerhaft.
Am besten ist es, wenn du sie direkt als .doc abspeicherst, da sie dann auch generell von Leute die OpenOffice etc. nutzen gelesen werden kann.


Man sieht bei AgentLie schon sehr genau, wie man es zu Beweisen hat (wobei ich nicht sehe, warum man unbedingt das c aus der Bedingung mit eingliedern will, das ist unnötig, man müsste einfach nur hinschreiben, dass OE c_max echt größer ist als c, da es sonst nicht zu zeigen gibt), mit der Aufgabe solltest du also keine Probleme mehr haben.

Edit: Die Schreibweise aus Aufgabe 10 kenne ich leider nicht. Was bedeutet denn das Omega und das Kleinomega?

Grob und unmathematisch gesagt:
Omega ist f(n) >= c * g(n),
Theta(g) := {f | f € O(g) und f € Omega(g)},
und wo für O noch galt, dass f(n) <= c * g(n) sein müsste, so gilt für o, dass f(n) < c * g(n) sein muss.
Genau so ist es auch für die anderen Symbole.

@Derksowitch
Am besten ist es, wenn du versuchst es einmal selbst zu zeigen und hinterfrage am besten immer deinen Beweis, ob dieser auch wirklich 100% wasserdicht ist.
Beweisführung sollte man schon einmal gelernt haben und dies kann man eigentlich nur lernen in dem man es einmal selbst macht.

Falls du dann soweit bist können wir dir dann aber sicherlich sagen, ob dein Beweis falsch oder richtig ist und falls es nicht ganz richtig ist, woran es liegt.

 

[AgentLie]

Man sieht bei AgentLie schon sehr genau, wie man es zu Beweisen hat (wobei ich nicht sehe, warum man unbedingt das c aus der Bedingung mit eingliedern will, das ist unnötig, man müsste einfach nur hinschreiben, dass OE c_max echt größer ist als c, da es sonst nicht zu zeigen gibt), mit der Aufgabe solltest du also keine Probleme mehr haben.

Na ja, das ist dann ja genau das selbe.