Suche Home Einstellungen Anmelden Hilfe  

UNI Didaktik der
Informatik
DdI

Wettbewerb
"Theoretische Informatik I" - SS 2002

Das 1.000.000ste Computerprogramm


Ergänzungen/FAQ

  1. 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.
  2. 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!

     

Benutzer: gast • Besitzer: schwill • Zuletzt geändert am: