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

Berechenbarkeitstheorie
Universität/Hochschule 
Thema eröffnet von: katenum
Entscheidbarkeit durch Reduktion/Satz von Rice  
Beitrag No.2 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2018-08-06
katenum
J

Okay da habe ich wohl nicht richtig nachgedacht ^^
Die Sprache \(\bar{L}\) ist ja einfach \(\{\langle M \rangle|\text{M hält in den ersten 100 Schritten}\}\) und somit natürlich entscheidbar weil man die ersten 100 Schritte simulieren kann.

Vielen Dank für die Hilfe!

MfG katenum

Berechenbarkeitstheorie
Universität/Hochschule 
Thema eröffnet von: katenum
Entscheidbarkeit durch Reduktion/Satz von Rice  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2018-08-04
katenum
J

Hallo,

es ist die Frage, ob die folgende Sprache entscheidbar ist:
\(L = L_1 \cup L_2\) mit
\(L_1 = \{\langle M \rangle|\text{M hält nicht auf der leeren Eingabe}\}\)
\(L_2 = \{\langle M \rangle|\text{M hält auf der leeren Eingabe, aber frühestens nach 100 Schritten}\}\)

Bei \(L_1\) kann man ja den Satz von Rice anwenden, da die Sprache nur von der Funktion abhängt und diese nicht trivial ist. Also sollte diese Sprache nicht entscheidbar sein oder?

Bei \(L_2\) habe ich versucht folgende Reduktion von \(H\) also dem Halteproblem auf \(L_2\) zu machen:

1. Prüfe, ob Eingabe von der Form \(\langle M\rangle w\), sonst verwerfe.
2. Konstruiere \(\langle M_w\rangle\) wie folgt:
   a) Führe 100 Schritte aus
   b) Lösche Eingabe von Band
   c) Simuliere M auf w
3. Übernehme das Akzeptanzverhalten

Dann gilt:
\[
\begin{align*}
\langle M\rangle w \in H &\Rightarrow \text{M hält auf w}\\
&\Rightarrow L_2 \text{ hält auf } \langle M_w\rangle \text{ nach frühestens 100 Schritten}
\end{align*}
\]
\[
\begin{align*}
\langle M\rangle w \not\in H &\Rightarrow \text{M hält nicht auf w}\\
&\Rightarrow L_2 \text{ hält nicht auf } \langle M_w\rangle \text{ nach frühestens 100 Schritten}
\end{align*}
\]
Also ist L zwar rekursiv aufzählbar wegen H aber nicht entscheidbar, richtig?

MfG
katenum

Berechenbarkeitstheorie
Universität/Hochschule 
Thema eröffnet von: katenum
Halteproblem auf anderes Problem reduzieren  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2018-05-28
katenum
 

Hallo,

Die folgende Sprache ist gegeben:

\(L_3 = \left \{ \left \langle M \right \rangle |\text{DTM M akzeptiert genau 3 Eingaben} \right \}\)

Es ist zu zeigen, dass die DTM nicht entscheidbar ist. Mir ist klar, dass die Sprache nicht entscheidbar sein kann, da es ja ähnlich wie beim Halteproblem nicht festgestellt werden kann, ob die Maschine nach 3 akzeptierten Eingaben (falls es diese gibt) alle weiteren verwirft oder gar nicht hält.

Wie kann ich diese Anschauung in eine sinnvolle Reduktion (\(H \leq L_3\)) mit einer berechenbaren Funktion übertragen?

MfG katenum

Theoretische Informatik
Universität/Hochschule 
Thema eröffnet von: katenum
Rekursive/rekursiv aufzählbare Sprachen  
Beitrag No.4 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2018-05-15
katenum
J

Hatte einen Denkfehler.
Bei \(\{\left \langle M \right \rangle x | ...\}\) ist \(\left \langle M \right \rangle\) die Gödelnummer einer Maschine M und x das Wort, welches auf dem Band liegt.
So sollte es aber gehen:
Halteproblem \(H = \{\left \langle M \right \rangle x| \text{ M hält bei Eingabe x}\}\). Das kann aufgeteilt werden in \(H_i = \{\left \langle M \right \rangle x| \text{ M hält bei Eingabe x nach i Schritten}\}\). Die Sprachen sind entscheidbar, da die universelle Maschine beim Simulieren von M die Anzahl der Schritte zählen kann.
Also gilt \(H = \bigcup_{i \in \mathbb{N}}H_i\)
Mit \(\overline{H}\) nicht rekursiv aufzählbar folgt \(\exists i \in \mathbb{N}: \overline{H_i}\) nicht rekursiv.

Theoretische Informatik
Universität/Hochschule 
Thema eröffnet von: katenum
Rekursive/rekursiv aufzählbare Sprachen  
Beitrag No.2 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2018-05-15
katenum
J

Ah okay. Könnte man bei (a) sagen, dass \(L_i = \{\left \langle M \right \rangle x| \) M hält nicht bei Eingabe x der Länge i\(\}\)? Was ja entscheidbar sein sollte und nach Vereinigung \(\overline{H}\) ist (\(H\) ist Halteproblem), also nicht rekursiv aufzählbar.

Kann man bei der (b) \(H\) und \(\overline{H}\) vereinigen, sodass die Eingabe von x egal ist?

Theoretische Informatik
Universität/Hochschule 
Thema eröffnet von: katenum
Rekursive/rekursiv aufzählbare Sprachen  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2018-05-15
katenum
J

Hallo,

Folgende Aufgabe ist gegeben:

Wir betrachten Sprachen \(L_1, L_2, ...\) und \(L = \bigcup_{i \in \mathbb{N}}L_i\). Finden Sie Gegenbeispiele für die folgenden beiden Aussagen:

(a) Wenn \(L_1, L_2, ...\) rekursiv sind, dann ist \(L\) rekursiv aufzählbar.

(b) Wenn \(L\) rekursiv ist, so sind alle Sprachen \(L_1, L_2, ...\) rekursiv aufzählbar.

Die (a) verstehe ich nicht, da ja für zwei rekursive Sprachen gilt, dass ihre Vereinigung wieder rekursiv ist (über eine DTM, die \(L_1 \) und \(L_2\) simuliert). Wenn man jetzt die gegebenen \(L_1, L_2, ...\) je paarweise vereint und das rekursiv wiederholt, dann hat man am Ende eine Sprache übrig, die wieder rekursiv ist. Was ist daran falsch?

Zur (b) finde ich keinen Ansatz.

MfG

katenum

Eigenwerte
Universität/Hochschule 
Thema eröffnet von: katenum
Spektralsatz, Eigenwertzerlegung  
Beitrag No.4 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2017-12-18
katenum
J

Okay also
\[|T^* \cdot T| =
|\begin{pmatrix}
a_{1,1} & 0  & 0\\
* & * & 0\\
* & * &  *\\
\end{pmatrix}
\begin{pmatrix}
a_{1,1} & *  & *\\
0 & * & *\\
0 & 0 &  *\\
\end{pmatrix}|
=|a_{1,1}|^2
\] und
\[
|T \cdot T^*| =
|
\begin{pmatrix}
a_{1,1} & *  & *\\
0 & * & *\\
0 & 0 &  *\\
\end{pmatrix}
\begin{pmatrix}
a_{1,1} & 0  & 0\\
* & * & 0\\
* & * &  *\\
\end{pmatrix}
|
=|a_{1,1}|^2 + \sum^{m}_{j = 2}|a_{1,j}|^2

\]
mit \(T \cdot T^* = T^* \cdot T\) gilt dann \(\forall j \in \{2,...,m\}: T_{1,j} = 0\)

Vielen Dank!

Eigenwerte
Universität/Hochschule 
Thema eröffnet von: katenum
Spektralsatz, Eigenwertzerlegung  
Beitrag No.2 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2017-12-18
katenum
J

Zunächst soll ich ja nur zeigen, dass in der ersten Zeile \(T_{1,j} = 0\) für alle \(j \in \{2,...,m\}\) gilt und das dann mit vollst. Induktion fortsetzen. Wie kann ich das beim T sehen?

Eigenwerte
Universität/Hochschule 
Thema eröffnet von: katenum
Spektralsatz, Eigenwertzerlegung  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2017-12-17
katenum
J

Hallo,

Gegeben ist eine normale Matrix A.
Für diese existiert eine Schur-Faktorisierung \(A = Q \cdot T \cdot Q^*\), wobei \(Q \in \mathbb{C}^{m \times m}\) unitär ist und \(T \in \mathbb{C}^{m \times m}\) eine obere Dreiecksmatrix ist.

Zu zeigen ist, dass in der ersten Zeile von T nur auf der Diagonalen ein Eintrag ungleich 0 sein kann und danach, dass T sogar eine Diagonalmatrix ist.

Ich habe schon gezeigt, dass T eine normale Matrix ist, also \(T \cdot T^* = T^* \cdot T\). Wie mache ich weiter?

MfG
katenum

Algorithmen / Datenstrukturen
Universität/Hochschule 
Thema eröffnet von: katenum
Union-Find Beweis zur Laufzeit  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2017-12-16
katenum
 

Hallo,

folgende Aufgabe ist gegeben:

Wir betrachten die Union-Find-Datenstruktur, d. h. ein n-elementiges Feld A, in dem für jedes Element \(i \in \{1,...,n\}\) gespeichert ist, zu welcher Menge es gehört. Zusätzlich ist für jede Menge ihre Größe und eine Liste der Elemente der Menge gegeben.

In der Vorlesung wurde gezeigt, dass die Laufzeit für jede Folge von Union-Operationen auf n Elementen höchstens \(O(n \cdot log n)\) ist. Wie sieht eine Folge solcher Union-Operationen auf n Elementen aus, deren Laufzeit wirklich \(\Theta(n \cdot log n)\) beträgt? Beweisen Sie Ihre Aussage. Beschränken Sie sich dabei auf den Fall, dass n eine Zweierpotenz ist.

Das die Laufzeit für wiederholtes Aufrufen der Union Operation in \(\Theta(log n)\) liegen kann verstehe ich noch, da ich die Teilmengen ja z.B. so vereinen kann: Ein x gehört erst zu einer Menge mit nur einem Element, dann mit 2 Elementen, 4, 8, .. bis \(2^i=n\) Elementen, was \(log n\) Umhängeoperationen entspricht. Dann habe ich aber nurnoch eine Menge und für die anderen \(n-1\) Elemente ist das nicht mehr anwendbar. Wie komme ich auf \(c \cdot n \cdot log n\) Operationen?
Die Find(x) Operation liegt ja in \(O(n)\), fällt also raus.

Eigenwerte
Universität/Hochschule 
Thema eröffnet von: katenum
Beweis: Eigenwert, charakteristisches Polynom  
Beitrag No.2 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2017-12-11
katenum
J

Okay, danke!

Eigenwerte
Universität/Hochschule 
Thema eröffnet von: katenum
Beweis: Eigenwert, charakteristisches Polynom  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2017-12-11
katenum
J

Hallo,

zu zeigen ist, dass \(\lambda\) ein EW von A genau dann ist, wenn es eine Nullstelle des charakteristischen Polynoms ist, also \(det(I \cdot \lambda - A) = 0\)

Für die EW gilt ja für \(x \neq 0\) das ein \(\lambda\) existiert mit:
\[
\begin{align*}
    && Ax &= \lambda x \\
    &\Leftrightarrow& Ax - \lambda x &= 0 \\
    &\Leftrightarrow& (A - I \cdot \lambda)x &= 0 \\
    &\Leftrightarrow& Kern(A - I \cdot \lambda) &\, \text{nicht leer} \\
    &\Leftrightarrow& \text{A nicht invertierbar} \\
    &\Leftrightarrow& det(A - I \cdot \lambda) &= 0
\end{align*}
\]
Ist das korrekt und ausreichend als Beweis?

Analysis
Universität/Hochschule 
Thema eröffnet von: katenum
O-Notation/Landau Symbole - Beweis zu Polynomen  
Beitrag No.2 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2017-10-13
katenum
 

Ja genau die meine ich.

Analysis
Universität/Hochschule 
Thema eröffnet von: katenum
O-Notation/Landau Symbole - Beweis zu Polynomen  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2017-10-13
katenum
 

Hallo,

Folgende Aufgabe ist gegeben:

Seien <math>p_1(n) = a_1 \cdot n^{d_1}, p_2(n) = a_2 \cdot n^{d_2}</math> Polynome wobei <math>a_1, a_2</math> positiv.

Zeigen Sie, dass dann gilt:

<math>p_1 = \Theta(p_2) \Leftrightarrow d_1 = d_2</math>

Ich weiß schon dass <math>g \in \Theta(f) :\Leftrightarrow g\in O(f)
\wedge g \in \Omega(f)</math>, dass also f eine untere und obere Schranke für g bildet.
Wie beweise ich das korrekt?

MfG
katenum

Programmieren
Universität/Hochschule 
Thema eröffnet von: katenum
Java: Subklassen Compilier-/Laufzeitfehler  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2017-08-10
katenum
 

Gegeben sind eine Klasse A und ihre Subklasse B.
Java
class A {}
class B extends A {}

Geben Sie für folgende Zuweisungen an, ob diese zu einem Kompilierfehler, Laufzeitfehler (in Form einer Exception) oder zu keinem Fehler führen.
Java
A test1 = (B)new A();
A test2 = (A)new B();
B test3 = (A)new B();
B test4 = (B)new A();
A test5 = (B)new B();
B test6 = (A)new A();

Ich verstehe noch nicht ganz, wann es zu Kompilierfehlern und wann zu Laufzeitfehlern kommt.
Ich denke, dass es bei 3 und 6 zu Kompilierfehlern kommt, weil A nicht zu B konvertiert werden kann.

Bei 2 sollte es zu keinem Fehler kommen, weil B ja Subtyp von A ist, aber wie sieht es bei 5 aus? (ist 5 das gleiche weil im Endeffekt doch zu A gecastet wird?)

Bei 1 und 4 bin ich aufgeschmissen..

MfG

Folgen und Reihen
Universität/Hochschule 
Thema eröffnet von: katenum
Reihe Konvergenz bzw. Divergenz zeigen  
Beitrag No.6 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2017-07-23
katenum
J

Zur Vollständigkeit noch mein Ergebnis:

<math>\frac{2n}{3n^2+1} \geq \frac{2n}{3n^2+n^2} = \frac{1}{2} \cdot \frac{1}{n}</math>

<math>\sum^{\infty}_{n=1}\frac{1}{2} \cdot \frac{1}{n} = \frac{1}{2}
\sum^{\infty}_{n=1}\frac{1}{n}</math>

Da die harmonische Reihe divergiert, divergiert auch die Reihe <math>\sum^{\infty}_{n=1}\frac{2n}{3n^2+1} \geq \frac{1}{2}
\sum^{\infty}_{n=1}\frac{1}{n}</math>

Hoffe das stimmt so.

Danke euch!

Folgen und Reihen
Universität/Hochschule 
Thema eröffnet von: katenum
Reihe Konvergenz bzw. Divergenz zeigen  
Beitrag No.4 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2017-07-22
katenum
J

Hm okay das Integralkriterium kannte ich noch garnicht ^^
Komisch, dass zur Klausurvorbereitung eine Reihe gewählt wird, die mit den in der Vorlesung gelernten Methoden anscheinend nicht untersucht werden kann oder gibt es noch eine andere Möglichkeit?

Edit:
Okay dann probiere ich es nochmal mit abschätzen



[Die Antwort wurde nach Beitrag No.2 begonnen.]

Folgen und Reihen
Universität/Hochschule 
Thema eröffnet von: katenum
Reihe Konvergenz bzw. Divergenz zeigen  
Themenstart
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2017-07-22
katenum
J

Hallo,
Es soll geprüft werden ob die folgende Reihe konvergiert oder divergiert. <math>\sum^{\infty}_{n = 1} \frac{2n}{3n^2+1}</math>
Mit dem Quotientenkriterium komme ich für <math>n \rightarrow \infty</math> auf 1 was nicht weiterhilft.
Nach oben oder unten abschätzen hilft mir auch nicht weiter weil die Reihe zwischen der harmonischen Reihe (divergent) und <math>\sum^{\infty}_{n = 1} \frac{1}{n^2}</math> (konvergent) liegt.

Wie muss ich also weitermachen?

MfG

Konvergenz
Universität/Hochschule 
Thema eröffnet von: katenum
Funktionenfolge punktweise/gleichmäßig konvergent  
Beitrag No.4 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2017-07-17
katenum
 

2017-07-17 17:09 - Dragon11 in Beitrag No. 3 schreibt:
Egal welche Zahl du wählst der Limes ist immer 0.

Okay aber wie kann ich das praktisch zeigen? Im Prinzip fallen ja die beiden ersten Teildefinitionen weg weil <math>\frac{2}{n} = 0</math> für <math>n \rightarrow \infty</math>.

Konvergenz
Universität/Hochschule 
Thema eröffnet von: katenum
Funktionenfolge punktweise/gleichmäßig konvergent  
Beitrag No.2 im Thread
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag2017-07-17
katenum
 

2017-07-17 16:45 - Dragon11 in Beitrag No. 1 schreibt:
Kannst du beim letzten das x immer so wählen, dass nicht 0 rauskommt, egal wie groß das n wird? Falls ja ist die Folge nicht gleichmäßig konvergent.

Wenn ich <math>x = \frac{1}{n}</math> wähle, dann ist ja <math>f_n(x)
= 1</math> für jedes n also ist die Folge nicht gleichmäßig konvergent oder?

Könntest du an einem Beispiel zeigen wie ich das bei der punktweisen Konvergenz mache? Ich verstehe noch nicht was das Festhalten von x dabei bedeutet.

MfG
 

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-2021 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.695858