Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Suche » Suchergebnis » Hallo Gast [Anmelden|Registrieren]
Zeige Beiträge 1 bis 15 von 57 Treffern Seiten (4): [1] 2 3 nächste » ... letzte »
Autor Beitrag
Thema: Sind die Fragen entscheidbar?
marie m

Antworten: 0
Hits: 3.451
Sind die Fragen entscheidbar? 14.07.2019 10:44 Forum: Theoretische Informatik


Hallo,

ich gucke folgende Aufgabe:

Sind die folgenden Fragen entscheidbar? Geben Sie einen entsprechenden Algorithmus an oder zeigen Sie mit Hilfe des Satzes von Rice, daß das Problem unentscheidbar ist.
(a) Hält ein beliebiger Algorithmus bei jeder Eingabe ungerader Länge?
(b) Hält eine beliebige Turingmaschine auf allen Eingaben kleiner oder gleich 1000 innerhalb der ersten 1000 Schritte?
(c) Gibt ein beliebiger Algorithmus bei geeigneter Eingabe eine Zahl aus, die als String interpretiert ein Palindrom ist?
(d) Liefert ein beliebiger Algorithmus, der für wenigstens eine Eingabe nicht hält, jede natürliche Zahl als Ausgabewert?

Ich habe folgendes gemacht:

(a) Sei [latex]\phi[/latex] die Funktion die von ein Algorithmus berechnet wird.

Da der Algorithmus bei jeder Eingabe ungerader Länge hält haben wir dass die Elemente der Form [latex]2n+1[/latex] im Definitionsbereich der Funktion [latex]\phi[/latex] liegen, das [latex]\phi(2n+1)[/latex] ist also für alle [latex]n\in \mathbb{N}_0[/latex] definiert.

Wir betrachten die daher die Menge [latex]M_1=\{i\in \mathbb{N}_0\mid \text{ Für alle } n\in \mathbb{N}_0 \text{ ist } \phi_i(2n+1) \text{ definiert }\}[/latex].

Seien [latex]i,j\in \mathbb{N}_0[/latex] mit [latex]i\in M_1[/latex] und [latex]\phi_i=\phi_j[/latex]. Wenn [latex]i\in M_1[/latex] dann haben wir dass [latex]\phi_i(2n+1)[/latex] definiert ist.

Da [latex]\phi_i = \phi_j[/latex] folgt es dass [latex]\phi_i (2n+1)= \phi_j (2n+1)[/latex] für alle [latex]n\in \mathbb{N}_0[/latex]. Da [latex]\phi_i(2n+1)[/latex] für alle [latex]n\in \mathbb{N}_0[/latex] definiert ist, folgt es dass [latex]\phi_j(2n+1)[/latex] auch für alle [latex]n\in \mathbb{N}_0[/latex] definiert ist. Davon folgt es dass [latex]j\in M_1[/latex].

Das bedeutet dass [latex]M_1[/latex] Funktionen respektiert.

Nach dem Satz von Rice ist [latex]M_1[/latex] also genau dann entscheidbar, wenn [latex]M_1 = \emptyset[/latex] oder [latex]M_1 = \mathbb{N}_0[/latex] gilt.

Es gibt Indizes [latex]i,j \in \mathbb{N}[/latex] mit [latex]\phi_i(n) = 0[/latex] und [latex]\phi_j(n) = n[/latex] für alle [latex]n \in \mathbb{N}_0[/latex], also gelten [latex]i \in M_1[/latex] (und damit [latex]M_1 \neq \emptyset[/latex]) sowie [latex]j \notin M_1[/latex] (und damit [latex]M_1 \neq \mathbb{N}_0[/latex]). Das heißt, [latex]M_1[/latex] ist nach dem Satz von Rice nicht entscheidbar.


(b) Es ist entscheidbar, ob eine deterministische Turing-Maschine für irgendeine Eingabe kleiner oder gleich [latex]1000[/latex] innerhalb der ersten [latex]1000[/latex] Schritt hält.

Wir führen die Turing-Maschine nacheinander auf allen Wörtern [latex]w \in \Sigma^{\star}[/latex] mit [latex]w \leq 1000[/latex] für höchstens [latex]1000[/latex] Schritte aus.

Wenn wir höchstens [latex]1000[/latex] Schritte simuliert haben, halten wir und geben “ja” aus, ansonsten halten wir, sobald wir die Turing-Maschine auf allen Wörtern [latex]w[/latex] simuliert haben, und geben “nein” aus.

(c) Um den Satz von Rice anzuwenden muss man eine Funktion finden die eine palindrome Ausgabe hat und eine Funktion die keine palindrome Ausgabe hat, um eine nicht-triviale Eigenschaft zu bekommen?


(d) Sei [latex]\phi[/latex] die Funktion die vom Algorithmus berechnet wird. Wir betrachten die Menge [latex]M=\{i\in \mathbb{N}_0 \mid \text{ Für alle } n\in \mathbb{N}_0 \ \text{ ist } \phi_i(n) \ \text{ definiert }\}[/latex], oder nicht?

Seien [latex]i,j \in \mathbb{N}_0[/latex] mit [latex]\phi_i = n[/latex] für eine natürliche Zahl [latex]n\in \mathbb{N}[/latex] und [latex]\phi_j\neq m\in \mathbb{N}[/latex] (da der Algorithmus für wenigstens eine Eingabe nicht hält).

Dann [latex]i \in M[/latex] und [latex]j \notin M[/latex], also [latex]M\neq \emptyset[/latex] und [latex]M\neq \mathbb{N}_0[l/atex], und jetzt kann man den Satz von Rice anwenden.


Ist alles richtig? Könnte ich etwas verbessern?
Thema: Turingmaschine
marie m

Antworten: 0
Hits: 3.184
Turingmaschine 24.07.2017 14:31 Forum: Theoretische Informatik


Hallo,

ich habe folgende Beschreibung einer Turingmaschine gefunden die ein nicht-leeres Wort w aus dem Alphabet { _, x(2), ... , x(m) } spiegelt:
... _ w(1) _ w(2) _ ... -> ... _ w(2)^R _ w(1) _ ...

(s. Anhang)

Diese arbeitet analog zur Kopiermaschine, nur dass sie das Wort spiegelt, und schiebt zum Schluss die gespiegelte Kopie auf das ursprüngliche Wort.


Ich habe die Definition nicht so richtig verstanden.
R ist die große Rechtsmaschine, L ist die große Linksmaschine und V
ist die Verschiebemaschine.
Könnt ihr mir die Definition der TM erklären?


Sind die R, L, V Hilfsturingmaschinen? Sind mit R bzw. L die Recht- bzw. Linksmaschinen gemeint, also diese die einen Schritt nach rechts (links) gehen und anschliessend so lange weiter nach rechts (links) gehen bis sie ein Leerzeichen lesen?
Thema: Representation im Zweierkomplement
marie m

Antworten: 0
Hits: 3.050
Representation im Zweierkomplement 21.12.2016 09:48 Forum: Theoretische Informatik


Hallo,

ich will ein MIMA-Programm schreiben, das den Wert [latex]2^{23}-24[/latex] in Speicherzelle y ablegt.

Ich habe folgendes gemacht:
Es gilt für jedes [latex]n\in \mathbb{N}_0[/latex] dass [latex]2^{n+1}=2\cdot 2^n=2^n+2^n[/latex].
Also haben wir folgendes:
[latex]2^1=2^0+2^0=1+1 \\ 2^2=2^1+2^1=(1+1)+(1+1) \\ 2^3=2^2+2^2=[(1+1)+(1+1)]+[(1+1)+(1+1)] \\ \text{usw}[/latex]

Ausserdem haben wir dass [latex]24=2^3\cdot 3=2^3+2^3+2^3[/latex].

Um den Wert [latex]2^{23}-24[/latex] in der Speicherzelle y abzulegen initialisieren wir den Wert bei y mit 1 und wir wiederholen 23-mal, dass wir den Wert bei y mit sich selbst addieren und das Ergebnis bei y ablegen. Dann berechnen wir das [latex]2^3[/latex] mit der gleichen Methode, dann das Inverse, [latex]-2^3[/latex], und dann addieren wir das Ergebnis 3-mal mit den Wert von y.

Ist die Idee richtig?
Thema: Beweis - Unentscheidbarkeit
marie m

Antworten: 1
Hits: 4.449
Beweis - Unentscheidbarkeit 12.08.2015 09:58 Forum: Theoretische Informatik


Hallo,

weiss jemand in welchen paper von Denef ich den Beweis, dass die existentielle Theorie von einen Polynomring auf eine Sprache unentscheidbar ist, finden kann?
Thema: Element in der Matrix einfügen
marie m

Antworten: 0
Hits: 3.465
Element in der Matrix einfügen 25.10.2014 21:47 Forum: Algorithmen


Hi!

Ich schreibe ein Programm über die Entstehung einer Galaxie "id".
Die neue Galaxie enthält eine leere Liste von Solarsysteme, also in der Liste der Solarsysteme gibt es nur den Listenkopf, und die leere Matrix der Waisen-Planeten (orcl). Die neue Galaxie soll in der Matrix der Galaxien(Gal) eingefügt werden. Die Kompläxitet des Einfügens soll O(1) sein.

code:
1:
2:
3:
4:
struct orcl { 
 int cid; 
 planet_t *or;     //Pointer zu den ersten Knoten der Liste der Waisen-Planeten 
}; 


code:
1:
2:
3:
4:
5:
6:
7:
struct galaxie { 
 int id; 
 solar_t *solars;     //Pointer zu den ersten Element in der Liste der Solarsysteme 
 orcl_t orcl[max];     //Die Matrix der Waisen-Planeten
 solar_t *slistenkopf;      //Pointer zu den Listenknopf der Liste der Solarsysteme
 int index;      //Es zeigt zu der ersten freie Position in der Matrix der Galaxie 
}; 



Ich habe bisher folgendes versucht:

code:
1:
2:
3:
4:
5:
int Entstehung(int id) {
	Gal->solars=Gal->slistenkopf;
	Gal->orcl->cid=int.MaxValue;
	Gal->orcl->or=NULL;	
}


Ist das richtig? Wie kann ich aber die neue Galaxie in der Matrix der Galaxien(Gal) einfügen?
Thema: Anzahl der Activation Records
marie m

Antworten: 1
Hits: 5.076
13.10.2014 11:36 Forum: Berechenbarkeits- und Komplexitätstheorie


Ich habe mir folgendes ueberlegt:
Am anfang gibt es ungefaer high-low Elements.
Dann high-(high-low)/2
Dann high-(high-(high-low)/2)/2
And so weiter...bis (high-low)/2^i=1 also i=log(high-low)

Ist das richtig?
Heisst das i mal deer algorithm us augefuehrt werden muss?

Also ist das die anzahl deer activation records?
Thema: Anzahl der Activation Records
marie m

Antworten: 1
Hits: 5.076
Anzahl der Activation Records 13.10.2014 10:19 Forum: Berechenbarkeits- und Komplexitätstheorie


Hallo!!!

Wie kann ich die Anzahl der activation records einer rekursive Funktion finden?

Zum Beispiel bei diesen folgenden Pseudocode von BinarySearch.


code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
int BinarySearch(int A[1...n], int y, int low, int high) { 
 if (high < low) {
    return -1; //not found 
 }
 mid = low + (high - low) / 2; 
 if (A[mid] > y) {
    return BinarySearch(A, y, low, mid-1); 
 }
 else if (A[mid] < y) {
       return BinarySearch(A, y, mid+1, high); 
 }
 else {
      return mid; //found 
}
} 

Thema: Für welche Sprachen gilt L1* U L2* = (L1 U L2)*
marie m

Antworten: 3
Hits: 5.530
Für welche Sprachen gilt L1* U L2* = (L1 U L2)* 04.09.2014 23:36 Forum: formale Sprachen


Hallo!!!

Für welche Sprachen [latex]L_1[/latex] und [latex] L_2[/latex], die keine Untergruppe voneinander sind, gilt es
[latex]L_1^* \cup L_2^* = \left(L_1 \cup L_2\right)^*[/latex] ?
Thema: Beweis mit Pumping-Lemma
marie m

Antworten: 1
Hits: 4.305
RE: Beweis mit Pumping-Lemma 08.06.2014 02:57 Forum: Theoretische Informatik


Wir nehmen an dass die Sprache [latex]L[/latex] regulär ist.

[latex]p[/latex] ist die Pumping-Länge.

Wir wählen das Wort [latex]x=a^n[/latex], [latex]n[/latex] ist eine Primzahl.

Man kann das [latex]x[/latex] in drei Teilworte zerteilen, [latex]x=uvw[/latex]

[latex]uv^iw \in L, \forall i \geq 0[/latex]

Das heisst dass wenn man [latex]i|uw|[/latex] an der Länge des [latex]x[/latex] dazu addiert, muss es immer noch in [latex]L[/latex] sein.

Also [latex]p+i|uw|[/latex] muss eine Primzahl sein [latex]\forall i \geq 0[/latex].

Für [latex]i=p[/latex] haben wir [latex]p+p|uw|=p(1+|uw|)[/latex]

[latex]p[/latex] ist eine Primzahl [latex]>1[/latex] und [latex]|uw|>1[/latex], also [latex]p(1+|uw|)[/latex] ist keine Primzahl da es ein Produkt von zwei Zahlen, die größer als 1 sind, ist.

Also kann unsere Vermutung nicht stimmen.

Also ist [latex]L[/latex] nicht regulär.
Thema: Master in Informatik
marie m

Antworten: 7
Hits: 9.772
07.06.2014 03:49 Forum: Sonstige Fragen


Ich danke euch für die Informationen!!!

Ich bin noch am Überlegen für welches Aufbaustudium ich mich entscheiden soll. verwirrt
Es gibt drei in Aussicht:
-Informatik:Algorithmik und Systemanalyse
-Angewandte und Numerische Mathematik, Wissenschaftliches Rechnen(Scientific Computing)
-Wirtschaftsmathematik

Welches der drei Richtungen, denkt ihr, hat die besten Berufsaussichten?
Thema: C -Code
marie m

Antworten: 5
Hits: 5.594
RE: C -Code 05.03.2014 03:02 Forum: Theoretische Informatik


Hallo!
In der f2 werden a und b doppelt deklariert und in f3 werden sie gar nicht deklariert.
Vor der main() hast du nur die Funtion f1 deklariert.
Thema: Master in Informatik
marie m

Antworten: 7
Hits: 9.772
04.03.2014 00:45 Forum: Sonstige Fragen


Bei meinen Studiengang konnte man eine Richtung zwischen Informatik, Physik und Wirtschaft aussuchen..Ich hatte ich die Richtung "Mathematische Methoden und Software-Entwicklung" ausgewählt, so habe ich einige Vorlesungen von Informatik gehört.. Was für Kenntisse brauch man um in diesen Bereich ein Aufbaustudium zu machen?

"Algorithmik und Systemanalyse" ist ein Gebiet der Theoretischen Informatik, oder?
Was gibt es für Berufsmöglichkeiten ausser Lehrer?
Thema: Automatenzeichnen, Tricks und Tipps?
marie m

Antworten: 1
Hits: 4.737
RE: Automatenzeichnen, Tricks und Tipps? 03.03.2014 00:00 Forum: Automatentheorie


Hallo!!!

Du musst immer Beispiele von Wörtern machen die die Sprache beschreibt und testen ob diese von den Automaten akzeptiert werden.

Und du musst immer testen ob die Wörter die der Automat akzeptiert in der Sprache sind.
Thema: Master in Informatik
marie m

Antworten: 7
Hits: 9.772
01.03.2014 22:31 Forum: Sonstige Fragen


Ich habe gerade den Studium in Angewandte Mathematik abgeschlossen.
Thema: Master in Informatik
marie m

Antworten: 7
Hits: 9.772
Master in Informatik 01.03.2014 00:01 Forum: Sonstige Fragen


Hallo!

Ich interessiere mich für ein Master in Informatik. Würdet ihr mir den Bereich "Algorithmik und Systemanalyse" empfehlen? Könnt ihr mir einige Informationen über diesen Bereich geben? Was für Berufsaussichten hat man?
Zeige Beiträge 1 bis 15 von 57 Treffern Seiten (4): [1] 2 3 nächste » ... letzte »