Prinzipielle Grenzen der Berechenbarkeit: Unterschied zwischen den Versionen
(→Fleißige Biber) |
|||
| Zeile 8: | Zeile 8: | ||
|} | |} | ||
</div> | </div> | ||
| + | |||
| + | == Gödelisierung == | ||
| + | Mittels der sogenannten Gödelisierung lassen sich beliebige Eingabedaten in natürliche Zahlen umwandeln. Diese wird häufig in der theoretischen Informatik verwendet, da sich Algorithmen dadurch auf Funktionen über den natürlichen Zahlen abbilden lassen. Dafür gibt es verschiedenste Verfahren. Man fasst solch ein Verfahren als Abbildung <math>g</math> von der Menge der Programme <math>M</math> in die Menge der natürlichen Zahlen <math>\mathbb{N}</math> auf: <math>g: M \rightarrow \mathbb{N}</math>. | ||
| + | Die Abbildung muss dabei noch einige Bedingungen erfüllen: | ||
| + | |||
| + | * <math>g</math> muss injektiv sein, d.h. jede natürliche Zahl darf höchstens das Bild von einem Programm sein; aber nicht jede natürliche Zahl muss auch ein Programm sein | ||
| + | * Die Bildmenge muss entscheidbar sein, es muss also einen Algorithmus der Ja ausgibt, wenn die Zahl einem Programm entspricht und Nein, wenn es sich um kein Programm handelt. | ||
| + | * Die Umkehrfunktion <math>g^{-1}</math> muss berechenbar sein, d.h. man muss aus der natürlichen Zahl auch wieder das Programm bekommen können. | ||
| + | |||
| + | |||
{{Aufgabe-Mathe| | {{Aufgabe-Mathe| | ||
Die 26 Buchstaben des Alphabets werden mit den Zahlen 1 bis 26 kodiert. Damit könnte man ein geschriebenes Wort als Zahl schreiben. Dekodiere die Zahl "26235945212097"! | Die 26 Buchstaben des Alphabets werden mit den Zahlen 1 bis 26 kodiert. Damit könnte man ein geschriebenes Wort als Zahl schreiben. Dekodiere die Zahl "26235945212097"! | ||
| Zeile 16: | Zeile 26: | ||
}} | }} | ||
}} | }} | ||
| + | |||
{{Aufgabe-Mathe| | {{Aufgabe-Mathe| | ||
Version vom 17. September 2009, 14:04 Uhr
Ich packe meinen Koffer...
Fülle den Reisekoffer optimal aus und lege nichtbenötigte Gegenstände in die Ablage!
| Koffer | Taschenlampe (15€) |  |
Ameise | Motte | |
| Ablage | Pflaume |  |
Apfel | Kirsche | Banane |
Gödelisierung
Mittels der sogenannten Gödelisierung lassen sich beliebige Eingabedaten in natürliche Zahlen umwandeln. Diese wird häufig in der theoretischen Informatik verwendet, da sich Algorithmen dadurch auf Funktionen über den natürlichen Zahlen abbilden lassen. Dafür gibt es verschiedenste Verfahren. Man fasst solch ein Verfahren als Abbildung 
von der Menge der Programme 
in die Menge der natürlichen Zahlen 
auf: 
.
Die Abbildung muss dabei noch einige Bedingungen erfüllen:
- muss injektiv sein, d.h. jede natürliche Zahl darf höchstens das Bild von einem Programm sein; aber nicht jede natürliche Zahl muss auch ein Programm sein
- Die Bildmenge muss entscheidbar sein, es muss also einen Algorithmus der Ja ausgibt, wenn die Zahl einem Programm entspricht und Nein, wenn es sich um kein Programm handelt.
- Die Umkehrfunktion
muss berechenbar sein, d.h. man muss aus der natürlichen Zahl auch wieder das Programm bekommen können.
Aufgabe
Die 26 Buchstaben des Alphabets werden mit den Zahlen 1 bis 26 kodiert. Damit könnte man ein geschriebenes Wort als Zahl schreiben. Dekodiere die Zahl "26235945212097"! Welche Buchstabenfolge erhält man nach dem Dekodieren?
ZWEIDEUTIG oder was anderes
|
Aufgabe
Nun werden die 26 Buchstaben des Alphabets wie folgt kodiert: Den 26 Buchstaben des Alphabets wird jeweils eine eindeutige Zahl zwischen 1 und 26 zugeordnet. Ein Wort wird nun mit fortlaufenden Primzahlpotenzen kodiert, also wenn a die Zahl 1, b die Zahl 2, c die Zahl 3 zugeordnet wird, dann wird das Wort abbca wie folgt kodiert:
Multipliziert man diese Zahlen miteinander, erhält man die Zahl
hier die Lösung reinschreiben
|
kodiert.
kodiert.
kodiert.
kodiert.
kodiert.
.
Da die Primfaktorzerlegung eindeutig ist, wenn man die Primzahlpotenzen nach der größe der Primzahlen ordnet, kann man aus jeder Zahl das zugehörige Wort erzeugen.
Welche Buchstabenfolge erhält man, wenn man die Zahl *** dekodiert?
Aufgabe
Nun werden die 26 Buchstaben des Alphabets mit den Zahlen 01 bis 26 kodiert. Schreibt man die kodierten Buchstaben hintereinander, so erhält man eine Zahl. Dekodiere die Zahl 26230509060512121519.
ZWEIFELLOS
|
Welches Verfahren eignet sich für eine Gödelisierung? (!Kodierung mit Zahlen 1 bis 26) (Kodierung mit Zahlen 01 bis 26) (Kodierung mit Primzahlpotenzen)(!Keines der Verfahren)
Fleißige Biber
Aufgabe
Die Schüler der Kollegstufe besuchen |
verschiedene Kurse. Jeder Kurs findet einmal pro Woche statt. Belegt ein Schüler zwei Kurse, so dürfen diese nicht gleichzeitig stattfinden. Kann man mit 
verschiedenen Terminen auskommen?
Erstelle hierzu eine Graphen, wobei ein Knoten einem Kurs entspricht. Zwei Knoten werden genau dann miteinander verbunden, wenn ein Schüler die beiden entsprechenden Kurse besucht.
Man kann die Aufgabe als sogenanntes 
