Thema: Sind die Fragen entscheidbar? |
|
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 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 im Definitionsbereich der Funktion liegen, das ist also für alle definiert.
Wir betrachten die daher die Menge .
Seien mit und . Wenn dann haben wir dass definiert ist.
Da folgt es dass für alle . Da für alle definiert ist, folgt es dass auch für alle definiert ist. Davon folgt es dass .
Das bedeutet dass Funktionen respektiert.
Nach dem Satz von Rice ist also genau dann entscheidbar, wenn oder gilt.
Es gibt Indizes mit und für alle , also gelten (und damit ) sowie (und damit ). Das heißt, ist nach dem Satz von Rice nicht entscheidbar.
(b) Es ist entscheidbar, ob eine deterministische Turing-Maschine für irgendeine Eingabe kleiner oder gleich innerhalb der ersten Schritt hält.
Wir führen die Turing-Maschine nacheinander auf allen Wörtern mit für höchstens Schritte aus.
Wenn wir höchstens Schritte simuliert haben, halten wir und geben “ja” aus, ansonsten halten wir, sobald wir die Turing-Maschine auf allen Wörtern 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 die Funktion die vom Algorithmus berechnet wird. Wir betrachten die Menge , oder nicht?
Seien mit für eine natürliche Zahl und (da der Algorithmus für wenigstens eine Eingabe nicht hält).
Dann und , also 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 |
|
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 |
|
Hallo,
ich will ein MIMA-Programm schreiben, das den Wert in Speicherzelle y ablegt.
Ich habe folgendes gemacht:
Es gilt für jedes dass .
Also haben wir folgendes:
Ausserdem haben wir dass .
Um den Wert 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 mit der gleichen Methode, dann das Inverse, , und dann addieren wir das Ergebnis 3-mal mit den Wert von y.
Ist die Idee richtig?
|
|
Thema: Beweis - Unentscheidbarkeit |
|
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 |
|
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 |
|
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 |
|
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: Beweis mit Pumping-Lemma |
|
Wir nehmen an dass die Sprache regulär ist.
ist die Pumping-Länge.
Wir wählen das Wort , ist eine Primzahl.
Man kann das in drei Teilworte zerteilen,
![[latex]uv^iw \in L, \forall i \geq 0[/latex]](http://www.matheboard.de/latex2png/latex2png.php?uv^iw \in L, \forall i \geq 0)
Das heisst dass wenn man an der Länge des dazu addiert, muss es immer noch in sein.
Also muss eine Primzahl sein .
Für haben wir ![[latex]p+p|uw|=p(1+|uw|)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?p+p|uw|=p(1+|uw|))
ist eine Primzahl und , also 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 nicht regulär.
|
|
Thema: Master in Informatik |
|
Ich danke euch für die Informationen!!!
Ich bin noch am Überlegen für welches Aufbaustudium ich mich entscheiden soll.
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 |
|
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 |
|
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? |
|
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 |
|
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?
|
|
|
|
|