Wettbewerb
"Theoretische Informatik I" - SS 2002
Das 1.000.000ste Computerprogramm
Ergänzungen/FAQ
-
Es ist zweckmäßig, die Möglichkeit von Kommentaren innerhalb
eines Pascal-Programms zu ignorieren. Dann ist eher damit zu rechnen, daß
das 1.000.000ste Programm etwas Sinnvolles tut.
-
Programme sind verschieden, wenn ihre Texte verschieden sind, und sei es
nur wegen eines Leerzeichens.
Thema
Im Abschnitt 2 der Vorlesung haben wir in Satz C ("Die Menge aller Algorithmen
ist abzählbar") eine Funktion definiert, die jedem Text aus X* auf
der Grundlage der Idee der Stellenwertsysteme umkehrbar eindeutig (bijektiv)
eine natürliche Zahl zuordnet. Die Funktion war wie folgt definiert:
Sei nun X={Menge aller 128 Zeichen des ASCII-Codes} und p der ASCII-Code,
also z.B. p(7)=55, p(F)=70, p(;)=59. Zählt man nun alle Texte w aus
X* der Reihe nach, aufsteigend geordnet nach den zugehörigen natürlichen
Zahlen, auf, so kommen unter den Texten auch PASCAL-Programme vor. Das
allererste PASCAL-Programm, das man auf diese Weise erhält, ist z.B.
PROGRAM A;BEGIN END.
Kein Text w mit kleinerer Nummer kann ein syntaktisch korrektes PASCAL-Programm
sein. (Beachte, daß alle Zeichen groß geschrieben sind).
Aufgaben
-
Bestimmen Sie das 1.000.000ste PASCAL-Programm.
-
Welche Funktion berechnet es?
-
Das wievielte Programm ist das folgende Programm:
program p(input,output);
begin writeln('Hello world') end.
-
Bitte begründen Sie, warum die von Ihnen angegebenen Lösungen
korrekt sind.
Abgabetermin
-
30.06.2002 bei einem der Veranstalter
Preise
-
1. Preis: wahlweise 1 Kasten Bier, an dessen Leerung wir uns gerne beteiligen,
oder 5 Punkte Guthaben für die Klausur
-
2. Preis: wahlweise 2 Flasche Sekt oder 3 Punkte Guthaben für die
Klausur
-
3. Preis: wahlweise 1 Flasche Sekt oder 2 Punkte Guthaben für die
Klausur
Bei mehreren gleichwertigen Lösungen entscheidet das Los bzw.werden
die Preise geteilt.
Weitere Informationen
Prof. Dr. Andreas Schwill
Viel Spaß und Erfolg!
|