+ Antworten
Ergebnis 1 bis 20 von 20

Informatik: Kryptisches Mathe

Eine Diskussion über Informatik: Kryptisches Mathe im Forum Hausaufgaben. Teil des Reallife-Bereichs; Hi, es ist mal wieder so weit: Ich komme nicht mehr weiter. Im Anhang eine pdf-Datei, die die Aufgaben für ...

  1. #1
    Feldwebel
    Avatar von XXXNA
    Registriert seit
    08.08.2005
    Alter
    29
    Beiträge
    1.201

    Informatik: Kryptisches Mathe

    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.

    Angehängte Dateien Angehängte Dateien
    ]

  2. #2
    Stabsunteroffizier
    Avatar von DonQuintal
    Registriert seit
    10.09.2004
    Ort
    RheinMain
    Alter
    41
    Beiträge
    975
    Nick
    BetaTester
    Clans
    nie wieder Clan
    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.
    Geändert von DonQuintal (02.05.2009 um 19:09 Uhr)
    "War does not determine who is right - only who is left" -Burtrand Russell

  3. #3
    Stabsunteroffizier
    Avatar von DonQuintal
    Registriert seit
    10.09.2004
    Ort
    RheinMain
    Alter
    41
    Beiträge
    975
    Nick
    BetaTester
    Clans
    nie wieder Clan
    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.
    "War does not determine who is right - only who is left" -Burtrand Russell

  4. #4
    Administrator
    Avatar von stefros
    Registriert seit
    28.07.2001
    Ort
    Hamburg
    Alter
    33
    Beiträge
    62.610
    Name
    Stefan
    Nick
    stefros1983
    Clans
    United-Forum
    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.

  5. #5
    Stabsunteroffizier
    Avatar von DonQuintal
    Registriert seit
    10.09.2004
    Ort
    RheinMain
    Alter
    41
    Beiträge
    975
    Nick
    BetaTester
    Clans
    nie wieder Clan
    Zitat Zitat von stefros Beitrag anzeigen
    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.
    "War does not determine who is right - only who is left" -Burtrand Russell

  6. #6
    Space Cowboy
    Avatar von Macross
    Registriert seit
    10.02.2005
    Ort
    Tokyo, Kasai
    Alter
    33
    Beiträge
    7.340
    Name
    Kurisu
    Nick
    Macross/Paladin
    Clans
    3 2 1 Hasselhoff
    Ist das kompliziert. Ich verstehe nicht 1 einziges Wort. Was genau bezweckt dieses kryptisches Mathe?

  7. #7
    Stabsunteroffizier
    Avatar von DonQuintal
    Registriert seit
    10.09.2004
    Ort
    RheinMain
    Alter
    41
    Beiträge
    975
    Nick
    BetaTester
    Clans
    nie wieder Clan
    Zitat Zitat von Paladinchen Beitrag anzeigen
    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.
    "War does not determine who is right - only who is left" -Burtrand Russell

  8. #8
    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).

    ######

    Zitat Zitat von DonQuintal Beitrag anzeigen
    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.

  9. #9
    Feldwebel
    Avatar von XXXNA
    Registriert seit
    08.08.2005
    Alter
    29
    Beiträge
    1.201
    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)).
    ]

  10. #10
    Stabsunteroffizier
    Avatar von DonQuintal
    Registriert seit
    10.09.2004
    Ort
    RheinMain
    Alter
    41
    Beiträge
    975
    Nick
    BetaTester
    Clans
    nie wieder Clan
    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!
    "War does not determine who is right - only who is left" -Burtrand Russell

  11. #11
    Feldwebel
    Avatar von XXXNA
    Registriert seit
    08.08.2005
    Alter
    29
    Beiträge
    1.201
    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?
    Angehängte Dateien Angehängte Dateien
    ]

  12. #12
    Stabsunteroffizier
    Avatar von DonQuintal
    Registriert seit
    10.09.2004
    Ort
    RheinMain
    Alter
    41
    Beiträge
    975
    Nick
    BetaTester
    Clans
    nie wieder Clan
    Windows sagt: Datei ist ungültig oder beschädigt.
    "War does not determine who is right - only who is left" -Burtrand Russell

  13. #13
    Feldwebel
    Avatar von XXXNA
    Registriert seit
    08.08.2005
    Alter
    29
    Beiträge
    1.201
    Ach zum Teufel. Wieso funktioniert in diesem Forum docx noch immer nicht?
    Angehängte Dateien Angehängte Dateien
    ]

  14. #14
    UF-Spamcrew
    Avatar von Speex
    Registriert seit
    23.06.2008
    Ort
    Augsburg
    Alter
    24
    Beiträge
    43.032
    Name
    Patrick
    Nick
    Speex
    Clans
    UF-Sc
    also ich konnte es downloaden
    "The dark side of the Force is a pathway to many abilities some consider to be unnatural."

  15. #15
    Stabsunteroffizier
    Avatar von DonQuintal
    Registriert seit
    10.09.2004
    Ort
    RheinMain
    Alter
    41
    Beiträge
    975
    Nick
    BetaTester
    Clans
    nie wieder Clan
    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.
    "War does not determine who is right - only who is left" -Burtrand Russell

  16. #16
    Feldwebel
    Avatar von XXXNA
    Registriert seit
    08.08.2005
    Alter
    29
    Beiträge
    1.201
    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!
    ]

  17. #17
    Stabsunteroffizier
    Avatar von DonQuintal
    Registriert seit
    10.09.2004
    Ort
    RheinMain
    Alter
    41
    Beiträge
    975
    Nick
    BetaTester
    Clans
    nie wieder Clan
    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
    "War does not determine who is right - only who is left" -Burtrand Russell

  18. #18
    Gefreiter
    Avatar von AgentLie
    Registriert seit
    29.10.2001
    Ort
    Bad Oeynhausen
    Alter
    31
    Beiträge
    153
    Nick
    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?

  19. #19
    @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.

    Zitat Zitat von AgentLie Beitrag anzeigen
    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.

  20. #20
    Gefreiter
    Avatar von AgentLie
    Registriert seit
    29.10.2001
    Ort
    Bad Oeynhausen
    Alter
    31
    Beiträge
    153
    Nick
    AgentLie
    Zitat Zitat von Osbes Beitrag anzeigen
    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.

+ Antworten

Ähnliche Themen

  1. Mathe 3 Textaufgaben-5€
    Von MamaMiaBiagotti im Forum OFF-Topic
    Antworten: 4
    Letzter Beitrag: 08.07.2004, 18:06
  2. Mathe Hilfe!!!!!!
    Von MeGa im Forum OFF-Topic
    Antworten: 3
    Letzter Beitrag: 17.06.2004, 22:28
  3. muahahahaha physik 1 und mathe war easy
    Von RhiNoTaNk im Forum Kuschelecke
    Antworten: 17
    Letzter Beitrag: 14.11.2003, 00:13
  4. Wenn euch langweilig ist (Mathe Spiel)
    Von TraXX im Forum OFF-Topic
    Antworten: 11
    Letzter Beitrag: 09.07.2003, 02:27
  5. kleines Mathe Spielchen
    Von Mooff im Forum OFF-Topic
    Antworten: 31
    Letzter Beitrag: 24.05.2003, 10:03

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •