Suchwörter   (werden UND-verknüpft)
Keines der folgenden   keine eigenen Beiträge
Name des Autors 
resp. Themenstellers 

nur dessen Startbeiträge
auch in Antworten dazu
Forum 
 Suchrichtung  Auf  Ab Suchmethode  Sendezeit Empfehlungbeta [?]
       Die Suche erfolgt nach den angegebenen Worten oder Wortteilen.   [Suchtipps]

Link auf dieses Suchergebnis hier

Forum
Thema Eingetragen
Autor

Logik, Mengen & Beweistechnik
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Was ist das für eine Menge?  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-06-29
LernenWollen
 

Hallo!

Betrachtet wird die Menge $\{a_0, \dotsc, a_{n-1}\}$ aus $n$ verschiedenen Zahlen von 0 bis $n-1$ (also eine Permutation), wobei die Position der Elemente rein zufällig ist.

Jetzt ziehe ich die Indikatorvariable
$X_i := 1_{\{a_i ~>~ max(a_{i-1},~a_{i+1})\}}$
heran. Das kennen manche vielleicht unter Dummy-Variable.
$X_i$ ist 1, falls $a_i$ größer als seine beiden nächsten Nachbarn ist, sonst 0.

Soweit gibt es kein Problem.

Jetzt betrachten wir $X_i \cdot X_j := 1_{A\cap B}$
mit
$A = \{a_i > max(a_{i-1},a_{i+1})\}$
und
$B = \{a_j > max(a_{j-1},a_{j+1})\}$,

wobei
$|i-j| \geq 3$.

Mein großes Ziel ist es, an den Erwartungswert von $X_i \cdot X_j$ zu kommen. Aber ich bin etwas verwundert über die Menge $A\cap B$.

Die beiden Elemente liegen also so weit auseinander, dass sich ihre Nachbarn nicht überlappen.
Jedes Mal, wenn ich darüber nachdenke, komme ich in eine Sackgasse, beispielsweise:

Was ist, wenn $A = B$? Dann aber stört mich, dass sich die Mengen irgendwie auch ausschließen. Deswegen kann ich diesen Gedanken nicht weiterdenken.

Was ist das für eine Menge? :)

Danke für eure Antworten!
LernenWollen

Stochastik und Statistik
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Bose-Einstein- und Maxwell-Boltzmann- Zusammenhang  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-06-03
LernenWollen
J

Hallo!

Hier geht es ausschließlich um Besetzungsmodelle, die bei uns durch die Analogie mit der Bosonenverteilung Namen aus der Physik verwenden.

Bei der Maxwell-Boltzmann-Statistik werden $n$ Kugeln auf $N$ Fächer aufgeteilt.
Die Kugeln sind unterscheidbar und es ist Mehrfachbesetzung erlaubt.

Formel:
$P(A^{(m)}_k) = \dbinom{n}{k} \cdot \biggl(\dfrac{1}{N}\biggr)^k \cdot \biggl(1-\dfrac{1}{N}\biggr)^{n-k}$

$A^{(m)}_k$ ist das Ereignis, bei dem das $m.$ Fach genau $k$ Kugeln enthält.

Bei der Bose-Einstein-Statistik werden die Kugeln nicht unterschieden, sonst ist die Ausgangslage gleich.

Formel:
$P(A^{(m)}_k) = \dfrac{\binom{N+n-k-2}{n-k}}{\binom{N+n-1}{n}}$

Der Unterschied ist also die Unterscheidbarkeit der Kugeln.
Wenn man jetzt allerdings beispielsweise 2 Fächer und 3 Kugeln betrachtet und das Ereignis, dass in Fach 1 genau 1 Kugel liegt, fehlt mir der Zusammenhang.

Wähle ich Maxwell-Boltzmann, erhalte ich $\frac{3}{8}$. Hier werden die Kugeln unterschieden.
Mit Bose-Einstein bin ich bei $\frac{1}{4}$.

Der Unterschied ist ein Faktor $\frac{3}{2}$.
Ich hätte nun vermutet, dass die 2 des Nenners eigentlich $2!$ ist (wegen der Reihenfolge, Unterscheidbarkeit) und die 3 des Zählers daher kommt, dass 3 verschiedene unterschiedbare Kugeln vorhanden sind.

Allerdings bestätigt sich diese Vermutung nicht bei anderen Beispielen.

Wie ist daher der Zusammenhang? Wie setzt sich der Faktor zusammen, der die beiden Besetzungsmodelle unterscheidet?

Vielen Dank und liebe Grüße
LernenWollen

Stochastik und Statistik
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Bayessches Verfahren für Maschinelles Lernen  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-05-17
LernenWollen
J

Hallo!

Es geht um ein Problem aus meiner Vorlesung zu maschinellem Lernen.

Einleitend kurz:
Gegeben sind Trainingsdaten aus Paaren $(x, t)$. $x$ sind die Eingaben, $t$ die Zielwerte.
Gesucht sind Parameter $\omega$ einer Funktion $y(x, \omega)$. Ich lasse die Vektorschreibweise mal weg.

Die $t$'s weichen normalerweise etwas von $y(x, \omega)$ ab, so dass man beispielsweise Verfahren wie das der kleinsten Fehlerquadrate nutzen könnte, um das Problem zu lösen.

Zuletzt ging es um Maximum Likelihood unter der Annahme, dass die $t$-Werte normalverteilt um die gesuchte Funktion $y(x, \omega)$ streuen.

Das sieht dann so aus:

$L(\vec{\omega}) = \prod_{i = 1}^n\Biggl(\frac{1}{\sqrt{2\pi \sigma^2}} \cdot e^{\biggl(\dfrac{(t_i - y(x_i, \vec{\omega})^2}{2\sigma^2}\biggr)}\Biggr)$

Da kann dann logarithmiert werden, partiell differenziert, nullgesetzt und so weiter.

Ich glaube, dass ich das bis dahin verstanden habe. Denn in meiner Vorstellung passiert folgendes dabei:

Betrachtet man die Verteilung der Datenpunkte um die Funktion, so erhält man eine Glockenkurve. Ziel ist es, solche Parameter $\omega$ zu finden, bei der die Glockenkurve maximal hoch wird. Stellt man sich das animiert vor, wie die Parameter langsam optimiert werden, so schieben sich die Punkte immer weiter zusammen, die Glocke wird immer schmaler und der Erwartungswert immer wahrscheinlicher.

So ist also mein Verständnis davon.

Nun gab es den Schwenk auf das Bayessche Verfahren.
Es gibt die A-priori-Wahrscheinlichkeit vor dem Lernen,
die A-posterior-Wahrscheinlichkeit nach dem Lernen und
die Formel von Bayes zu bedingten Wahrscheinlichkeiten.

So wie ich es verstanden habe, sorgt das Verfahren dafür, dass sich die Glockenkurve verformt, auch so, dass sie nicht mehr symmetrisch ist.

Allerdings erkenne ich den Grund nicht. Ich habe etwas recherchiert und auch was gefunden, aber wenig verstanden.
Warum wird dieses Verfahren gebraucht und wie ist der Zusammenhang zum Maximum Likelihood?

Vielen Dank! :)

Grüße
LernenWollen


Induktion
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Vollst. Induktion Fibonacci-Folge  
Beitrag No.10 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-05-01
LernenWollen
J

Danke!

Ich sehe grad, dass ich versehentlich von der ursprünglichen Problemstellung abwich. Das war mir gar nicht mehr aufgefallen.

Induktion
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Vollst. Induktion Fibonacci-Folge  
Beitrag No.8 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-04-30
LernenWollen
J

2020-04-27 15:08 - ligning in Beitrag No. 7 schreibt:
Warum? Warum musst du das tun? Du kannst es natürlich machen wie du willst, wenn du unbedingt willst.

Das Müssen ist nicht derart drastisch gemeint, wie es hier überzeichnet wurde. Ich habe im Nebel gestochert, hatte eine einzige Vorstellung.
In dieser Vorstellung, war es der einzige Weg. Ich habe zweimal gesagt, dass ich das nicht weiß und deshalb von jemandem, der es weiß, den Hinweis suche, ob es richtig ist.

Wenn es also nicht richtig ist, dann sag es mir doch einfach. Es ist nicht nötig, mich auf diese Aussagen derart festzunageln, als hätte ich eine wissenschaftliche Arbeit zu verteidigen. Der Ton wurde mir irgendwann zu rau und es ist auch nicht zielführend, wenn man falsche Ideen immer tiefer zu denken versucht. Das hat mir so leider nicht geholfen, sondern die Verwirrung vergrößert.

Deswegen habe ich hier auch nicht weiter gefragt, da ich den Eindruck hatte, es ginge nicht mehr um die Lösung des Problems. Das fand ich schade.

Seither ist es mir gelungen, eine Lösung zu finden.
Da vielleicht andere auch an der Lösung interessiert sind und möglicherweise ganz runterscrollen, kommt hier die
 
LÖSUNG:

Zu zeigen: $a_n \leq \bigl(\frac{1+\sqrt{5}}{2}\bigr)^n$, wobei $a_0 = a_1 = 1, a_{n+2} = a_{n+1} + a_n$.
$a_n$ ist Fibonacci-Folge.

Induktionsanfang:

$a_0 = 1 \leq 1 = \bigl(\frac{1+\sqrt{5}}{2}\bigr)^0$,
$a_1 = 1 \leq 1,5 = \frac{1+2}{2} = \frac{1+\sqrt{4}}{2} \leq \frac{1+\sqrt{5}}{2} = \bigl(\frac{1+\sqrt{5}}{2}\bigr)^1$.


Induktionsvoraussetzung:

$a_n \leq \bigl(\frac{1+\sqrt{5}}{2}\bigr)^n$
und
$a_{n+1} \leq \bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n+1}$
gelten für beliebiges aber festes $n \in \mathbb{N}_0$.


Induktionsschritt:

$a_{n+2} = a_{n+1} + a_n$

$\overset{IV}{\leq} \bigl(\frac{1+\sqrt{5}}{2}\bigr)^n + \bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n+1}$

$= \bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n+2} \cdot \bigl(\frac{2}{1+\sqrt{5}}\bigr)^2 + \bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n+2} \cdot \bigl(\frac{2}{1+\sqrt{5}}\bigr)$

$=\bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n+2} \cdot \biggl(\bigl(\frac{2}{1+\sqrt{5}}\bigr)^2 + \bigl(\frac{2}{1+\sqrt{5}}\bigr)\biggr)$

$\overset{*}{=} \bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n+2} \cdot 1$

$= \bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n+2}$.

$^*~~~ \bigl(\frac{2}{1+\sqrt{5}}\bigr)^2 + \bigl(\frac{2}{1+\sqrt{5}}\bigr)$

$= \frac{4}{6+2\sqrt{5}} + \frac{2}{1+\sqrt{5}}$

$= \frac{4(1+\sqrt{5}) + 2(6+2\sqrt{5})}{(6+2\sqrt{5})(1+\sqrt{5})}$

$=\frac{16 + 8\sqrt{5}}{16 + 8\sqrt{5}}$

$= 1$.

Beweis beendet.


PS:

@ligning: Ich möchte mich bei dir für die Hilfestellungen bedanken, da ich an mehr als einer Stelle dazugelernt habe und das ist letztendlich das Ziel.
Ich hoffe sehr, dass ich künftig wieder von dir lernen kann. Dann hoffe ich auch, dass Ideen Ideen bleiben und keinen übermäßig ernsten Charakter erhalten.

Grüße
LernenWollen

Induktion
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Vollst. Induktion Fibonacci-Folge  
Beitrag No.6 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-04-27
LernenWollen
J

2020-04-27 14:27 - ligning in Beitrag No. 5 schreibt:
Wo kommen die Faktoren a und b her? Die gibt es in der IV nicht.

Ja, ich hatte überlegt, ob ich es noch dazu schreibe, dachte aber dass ich das zum Verständnis nicht bräuchte.

Ich starte meinen IS mit

$\frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^n$.      (1)

Um die IV nutzen zu können, muss ich den Term so umformen (oder eine passende Ungleichung finden), dass

$a \cdot \frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n-1} + b \cdot \frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n-2}$      (2)

mit irgendwelchen $a, b \in \mathbb{R}$ entsteht, die ich nicht kenne.
Erst wenn ich da bin, müsste es einen Schritt geben, bei denen $a, b$ verschwinden und dann kann ich die IV einsetzen und bin am Ziel.
Die Frage ist, wie komme ich von (1) nach (2). Oder muss ich das so gar nicht machen?

Die Werte von $a, b$ sind ja erstmal egal. Ich bin mir noch nicht einmal sicher, ob sie existieren. Immerhin ist ja das Problem, dass ich das Verfahren möglicherweise nicht verstehe.
Aktuell liegt mein Fokus auf dem Weg von (1) nach (2) bzw. falls (2) nicht resultieren wird, der Weg von (1) zu

$\frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n-1} + \frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n-2}$.

Und für mich ist auch nach wie vor ein Rätsel, warum mein ursprünglicher Lösungsversuch

$\frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n+1} = \frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^n \cdot \bigl(\frac{1+\sqrt{5}}{2}\bigr) \overset{IV}{\leq} a_n \cdot \bigl(\frac{1+\sqrt{5}}{2}\bigr)$

falsch ist.

Danke für die Zeit!

Induktion
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Vollst. Induktion Fibonacci-Folge  
Beitrag No.4 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-04-27
LernenWollen
J

2020-04-27 12:57 - ligning in Beitrag No. 3 schreibt:

Du hast nicht geschrieben, was du da machst. Nur dass du es "fortführst", aber mir ist nicht klar, wie.

Ich kann die Fortführung gerne noch einmal in Latex umsetzen, allerdings ist es nur der Beweis, dass $a_n\cdot\frac{1+\sqrt{5}}2 \leq a_{n+1}$ nicht stimmt und hat meiner Meinung nach keinen Mehrwert, da mein Fehler bereits in dem Teil passierte, den ich angab:

$\frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n+1} = \frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^n \cdot \bigl(\frac{1+\sqrt{5}}{2}\bigr) \overset{IV}{\leq} a_n \cdot \bigl(\frac{1+\sqrt{5}}{2}\bigr)$

Ich führte das demnach so fort:
$a_n \cdot \bigl(\frac{1+\sqrt{5}}{2}\bigr) = a_n + \frac{(\sqrt{5}-1)a_n}{2}$.
Damit der Ausdruck nun $\leq a_{n+1}$ wird, müsste nun gelten $\frac{(\sqrt{5}-1)a_n}{2} \leq a_{n-1}$. An dieser Stelle habe ich gemerkt, dass das nicht stimmt. Dass $a_n\cdot\frac{1+\sqrt{5}}2 \leq a_{n+1}$ also unwahr ist. Das bedeutet, dass
$\frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n+1} = \frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^n \cdot \bigl(\frac{1+\sqrt{5}}{2}\bigr) \overset{IV}{\leq} a_n \cdot \bigl(\frac{1+\sqrt{5}}{2}\bigr)$
unwahr ist. Allerdings finde ich nicht, wo ich da den Fehler gemacht habe.
Schließlich komme ich bei jeder Überprüfung zum Schluss, dass ich es richtig gemacht habe. Ich befasse mich seit etwa 5 Stunden damit, ich sehe es einfach nicht.

2020-04-27 12:57 - ligning in Beitrag No. 3 schreibt:
Ja, das ist die IV. Wie du das umsetzen sollst? Probier doch erstmal selbst!

Es ist nicht so, dass ich es nicht probiert hätte, nur mache ich das auf dem Papier, so dass das hier nicht zu sehen ist. :)
Aber ich probiere es mal auch hier in Latex:

Die IV ist nun $\frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n-1} \leq a_{n-1}$ und $\frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n-2} \leq a_{n-2}$.

IS:
$\frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^n = \dotsc$

Jetzt bräuchte ich einen Weg, wie ich zu

$a \cdot \frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n-1} + b \cdot \frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n-2} \overset{IV}{\leq} a_{n-1} + a_{n-2} = a_n$

komme. Allerdings wüsste ich an dieser Stelle auch keinen Weg. Vielleicht bin ich ja auch ganz falsch.

Induktion
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Vollst. Induktion Fibonacci-Folge  
Beitrag No.2 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-04-27
LernenWollen
J

2020-04-27 11:47 - ligning in Beitrag No. 1 schreibt:
richtig, $a_n\cdot\frac{1+\sqrt{5}}2 \leq a_{n+1}$ stimmt nicht, das wird aber auch nicht behauptet.

Das Problem ist nur, dass ich unter Verwendung des Induktionsbeweises dahin komme. Wenn die Vollständige Induktion hier nicht funktioniert, wäre sie ja nicht gültig und dieses Forum würde internationale Berühmtheit erlangen, weil die Gültigkeit der vollständigen Induktion widerlegt würde.
Dass das nicht passiert, ist klar. Die vollständige induktion ist in den Schritten, die ich angewandt habe, immer gleich.
Wenn ich diese Schritte anwende und es kommt was Falsches raus, habe ich einen Schritt falsch angewandt. Aber ich sehe es nicht.

Mir fällt es schwer, einen anderen Weg des Beweises zu gehen, wenn ich nicht weiß, woran es lag. Denn wenn der Fehler nicht korrigiert wird, könnte ich früher oder später meinen Fehler wiederholen.

2020-04-27 11:47 - ligning in Beitrag No. 1 schreibt:
Um die Aussage für $n$ zu beweisen, benutzt du als Induktionsvoraussetzung, dass sie für $n-1$ und für $n-2$ gilt.

Diese Herangehensweise für einen Induktionsbeweis habe ich noch nicht gesehen und weiß leider nicht, was damit gemeint ist.
Zu beweisen ist $\frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^n \leq a_n$.
Ist dann meine IV $\frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n-1} \leq a_{n-1}$ und $\frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n-2} \leq a_{n-2}$? Aber wie soll ich das im IS umsetzen?

Danke für die Antwort!

Induktion
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Vollst. Induktion Fibonacci-Folge  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-04-27
LernenWollen
J

Hallo!

Folgender Beweis:
$\forall n \in \mathbb{N}_0: \frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^n \leq a_n$, wobei $a_n$ die Fibonacci-Folge ist mit $a_0 = a_1 = 1, a_n = a_{n-1} + a_{n-2}$.

Also beweise ich die Fälle n = 0, n = 1, stelle fest, dass das klappt, stelle die Voraussetzung fest und gehe zum Induktionsschritt über.

$\frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^{n+1} = \frac{1}{2}\bigl(\frac{1+\sqrt{5}}{2}\bigr)^n \cdot \bigl(\frac{1+\sqrt{5}}{2}\bigr) \overset{IV}{\leq} a_n \cdot \bigl(\frac{1+\sqrt{5}}{2}\bigr)$.

Die Idee ist nun, dass ich fortführe und mit $ = a_{n+1}$ oder $\leq a_{n+1}$ ende.
Ich hatte auch weitergemacht und kam zu einem Widerspruch, der nicht sein dürfte.
Dann betrachtete ich Folgendes:
Sei $a_n = a_6 = 13$, dann ist $a_7 = 21$.
Also wenn ich bis vorhin richtig lag, müsste auch
$a_n \cdot \bigl(\frac{1+\sqrt{5}}{2}\bigr) = 13\cdot \bigl(\frac{1+\sqrt{5}}{2}\bigr) \leq 21$ sein. Das ist allerdings falsch!
Wo lag also mein Denkfehler. Ich finde ihn einfach nicht.

Vielen Dank!

Erfahrungsaustausch
Universität/Hochschule 
Thema eröffnet von: tillwint
Diskrepanz bei den Unis  
Beitrag No.1 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-02-20
LernenWollen
 

Ich glaube ehrlich nicht daran, dass der Bachelor so vergleichbar ist, wie er angepriesen wird. Dozenten haben totale Freiheiten in ihren jeweiligen Veranstaltungen und so kann ein äquivalentes Modul an der einen Uni leicht sein und an der anderen schwer, weil die verantwortlichen Dozenten einen unterschiedlichen Anspruch haben.

Theoretische Informatik
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Fehler in Pumping-Lemma (regulär)  
Beitrag No.1 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-02-13
LernenWollen
J

Ich muss das mal um einen weiteren Punkt erweitern.

Der Beweis der Nicht-Regularität von $\{a^nb^n~|~n \in \mathbb{N}\}$ wird stets damit geführt, dass $n$ die Pumping-Lemma-Konstante sei.

Das mag sich mir nicht so recht erschließen. Es geht um die Existenz einer Pumping-Lemma-Konstante, ab der die Bedingungen erfüllt sind, falls es sich um eine reguläre Sprache handelt.

Gut, $\{a^nb^n~|~n \in \mathbb{N}\}$ ist wirklich nicht regulär, aber vor einem Beweis "weiß" man das ja (normalerweise) nicht.
Wieso darf ich dann hingehen und sagen, dass das Lemma für $n = p_L$ funktioniert? Woher diese Sicheheit? Es könnte ja auch sein, dass das $n$ zu klein gewählt ist und man deshalb scheitert.

Worauf achtet man, wenn man die Pumping-Lemma-Konstante festlegt?


***Ergänzung***
Wählt man sie so klein wie möglich? Wieso reicht dann nicht $p_L = 1$?
Und wenn man sie so groß wie möglich wählt, wieso dann nicht $p_L = |x|~~~\forall x \in L$?

Theoretische Informatik
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Fehler in Pumping-Lemma (regulär)  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-02-13
LernenWollen
J

Hallo!

Es geht um die Sprache
$L = \{w \in \{a, b, c\}^*: ~~|w|_a + 1 < |w|_b\}$.
Es gibt demnach mindestens zwei $b's$ mehr als $a's$ in $L$.

Für jede reguläre Sprache existiert eine Pumping-Lemma-Konstante $p_L \in \mathbb{N}$, so dass jedes Wort $x \in L$ mit $|x| \ge p_L$ drei Bedingungen erfüllt.

Es steht mir ja frei anzunehmen, dass die Pumping-Lemma-Konstante $p_L = |x|$ ist. Bei einer Zerlegung eines Wortes $x \in L$ zu $x = u.v.w$ ist $w$ somit leer.

Egal welches Wort, $p_L$ ist stets die Länge des Wortes. Demnach müssen die drei Bedingungen

$|v| \ge 1$,
$|u.v| \le p_L$ und
$u.v^i.w \in L ~~~\forall i \in \mathbb{N}_0$

genau für alle Wörter gelten, wenn die Sprache regulär sein soll.
Reicht es dann schon, die Regularität zu widerlegen, indem ich eine einzige Zerlegung finde, die die dritte Bedingung nicht erfüllt?

Beispielsweise der Fall, dass $v$ mehr $a's$ als $b's$ enthält. Damit ist Bedingung drei verletzt.

Da aber $p_L = |x|$ und somit auch $|x| \ge p_L$ , darf es kein Wort geben, das die dritte Bedingung verletzt.

Darf ich so mit der Pumping-Lemma-Konstante $p_L$ umgehen?

Vielen Dank für die Antworten!
LernenWollen

Relationen und Abbildungen
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Supremum und Infimum Verständnis am Beispiel  
Beitrag No.12 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-02-13
LernenWollen
J

Vielen Dank!

Relationen und Abbildungen
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Supremum und Infimum Verständnis am Beispiel  
Beitrag No.10 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-02-13
LernenWollen
J

Dann für $f_3, g_3$.

$f_3(x) = \begin{cases} 0, & \text{falls } x \text{ gerade,}\\ 1, & \text{sonst.}\end{cases}$


$g_3(x) = \begin{cases} 2, & \text{falls } x \text{ gerade,}\\ 0, & \text{sonst.}\end{cases}$


Eigentlich hätte ich zu diesen beiden Funktionen angenommen, die Funktionen $k(x) = 2, b(x) = 0$ bildeten Join und Meet. Für den Meet stimmt das auch, für den Join ist das dann aber die Maximumfunktion.

Betrachte man nun, dass zu jedem $x \in \mathbb{Z}$ mindestens eine von zwei sonst beliebigen Funktionen definiert ist, dann gibt es ja stets ein Minimum und ein Infimum (innerhalb dieses Kontextes). Ist das korrekt?

Vielen Dank!
LernenWollen

Relationen und Abbildungen
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Supremum und Infimum Verständnis am Beispiel  
Beitrag No.8 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-02-13
LernenWollen
J

Für $g_2, f_2$ hatte ich ja angenommen, dass es kein Infimum gibt,also keine Funktion, die für jedes $x \in \mathbb{Z}$ die größte untere Schranke bildet.
Die Minimumfunktion bildet das Infimum.
Bildet die Maximumfunktion dann nicht auch das Supremum?

Relationen und Abbildungen
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Supremum und Infimum Verständnis am Beispiel  
Beitrag No.6 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-02-13
LernenWollen
J

Also ist die Annahme der Nichtexistenz eines Infimums falsch, da die Minimum-Funktion das Infimum bildet?

Relationen und Abbildungen
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Supremum und Infimum Verständnis am Beispiel  
Beitrag No.4 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-02-13
LernenWollen
J

Spricht man von punktweise nicht im Falle von Konvergenz, also im Falle einer Reihe von Funktionen?
Also $\{f_n(x)\}_{n = 1}^\infty$.
Und im Falle einer punktweisen Konvergenz, falls $\{f_n(x)\}_{n = 1}^\infty$ zu irgendeinem $x_0 \in \mathbb{Z}$ konvergiert.
So als punktweises Minimum ist mir die Begrifflichkeit nicht bekannt.

Ist das dann so, dass für alle $x \in \mathbb{Z}$ und unter Annahme, dass alle Funktionen in $F$ eine Reihe bilden, ein konkretes Minimum existiert?
Ich versuche mir das gerade zu veranschaulichen. Eine kurze Recherche hat mir noch nicht geholfen.

Betrifft mein Fehler beim Infimum speziell $f_2$ und $g_2$, also wo ich kein Infimim erkannte, oder auch $f_1$ und $g_1$?

Danke sehr!

LernenWollen

Relationen und Abbildungen
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Supremum und Infimum Verständnis am Beispiel  
Beitrag No.2 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-02-12
LernenWollen
J

Danke für die Antwort!

Natürlich, $F$ ist die betrachtete partielle Ordnung, also ist der Join ein Element von $F$. Das kann dann innerhalb von $\{a, b\}$ liegen, muss es ja nicht.

Trotzdem, wenn ich $f_1, g_1$ mit $f_1(x) = x, g_1(x) = x^2$ betrachte, glaube ich, dass ich immer noch als Join $g$ erhalte.

Die Menge der oberen Schranken von $f_1, g_1$ umfasst alle Abbildungen, die für jedes $x \in \mathbb{Z}$ größer-gleich eben dieser beiden Abbildungen sind.

Und die kleinste ist eben $g_1(x) = x^2$. Jeder höhere Grad ist ohnehin ausgeschlossen, ein kleinerer logischerweise auch. Es muss sich um eine Funktion von Grad 2 handeln, in diesem Fall ist ja
$g_1(x) = 1 \cdot x^2 + 0 \cdot x^1 + 0 \cdot x^0$.
Also komme ich als Ergebnis eben auf $g_1$.

Habe ich es nun? Oder habe ich die falsche Kiste umgeworfen?

Danke sehr!

LernenWollen

Relationen und Abbildungen
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Supremum und Infimum Verständnis am Beispiel  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-02-12
LernenWollen
J

Hallo!

Ich möchte gerne herausfinden, ob mein Verständnis korrekt ist.

Dazu:
Sei $(D, \le)$ eine partielle Ordnung (also reflexiv, transitiv, antisymmetrisch). Sei $X \subseteq D$.

Der Join $j \in D$ (das Supremum) ist die kleinste obere Schranke von $X$, falls $j$ obere Schranke von $X$ und $j \le t$ für alle oberen Schranken $t$ von $X$.
Dann schreibe ich $j = \bigsqcup X$.
Betrachte ich den Join $j'$ von zwei Elementen $a, b \in D$, so schreibe ich $j' = \bigsqcup \{a, b\}$.
Dazu existiert die Infix-Schreibweise $j' = a \sqcup b$.


Zum Meet (Infimum) verkürze ich mal.
Der Meet $m$ ist die größte untere Schranke von $X$, falls $m$ untere Schranke und dazu die größte dieser.
Es existiert auch hier für zwei Elemente $a, b \in D$ die Schreibweise $m' = a \sqcap b$.


Nun sei gegeben eine Menge $F$ aus Abbildungen $f: \mathbb{Z} \to \mathbb{Z}$.
Sei zudem $(F, \le)$ gegeben, wobei für zwei Abbildungen $f, g \in F$ gilt:
$f \le g$,  falls  $f(x)~ \le_{\mathbb{Z}} ~g(x), ~~~~\forall x \in \mathbb{Z}$.
$(F, \le)$ ist damit eine partielle Ordnung.


So, nun, da der Papierkram durch ist, nun der Kern des Beitrags:

Ich möchte den Join und den Meet je zwei Funktionen aus $F$ bestimmen.
Zuerst für $f_1(x) = x$ und $g_1(x) = x^2$.

Nach meinem Empfinden gilt $f_1 \sqcup g_1 = g_1$, da $g_1$ für jedes $x \ in \mathbb{Z}$ größer oder gleich $f_1$ ist.
Ich verstehe das auch so, dass - falls es Meet und Join gibt, das entsprechende Element innerhalb der Menge $\{f_1, g_1\}$ liegt.
Denn ich betrachte ja beide Elemente isoliert. Ist das so richtig gedacht?
Der Meet:
$f_1 \sqcap g_1 = f_1$

Weiteres Beispiel:
$f_2(x) = x$ und $g_2(x) = -2$
$f_2 \sqcup g_2$ existiert nicht, da $f_2$ und $g_2$ mit $\le$ nicht über alle $x \in \mathbb{Z}$ gleich geordnet sind. So ist für $x = -4~$ $g_2$ größer und für $x = 4~$ $f_2$.
$f_2 \sqcap g_2$ existiert demnach auch nicht.

Bin ich mit meinem Verständnis richtig oder ganz falsch?

Vielen Dank und liebe Grüße
LernenWollen

Integration
Universität/Hochschule 
Thema eröffnet von: LernenWollen
Verständnis Fourier-Transformation  
Beitrag No.2 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2020-02-11
LernenWollen
J

Hallo Roland, vielen Dank!

Das hilft schon sehr.

Grüße
LernenWollen
 

Sie haben sehr viele Suchergebnisse
Bitte verfeinern Sie die Suchkriterien

[Die ersten 20 Suchergebnisse wurden ausgegeben]
Link auf dieses Suchergebnis hier
(noch mehr als 20 weitere Suchergebnisse)

-> [Suche im Forum fortsetzen]
 
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]

used time 0.057989