2006 - Marie-Curie

Marie – Curie – Gymnasium
Städt. Gymnasium Recklinghausen
Abitur 2006
GK Informatik
Vorschlag I
Aufgabe 1)
„Könntest du mir für heute Abend in der Stadt dein Fahrrad leihen?“ fragte Cornelius seine Freundin
Alberta. „Ja natürlich, aber ich komme nur um 10.00 Uhr und um 14.00 Uhr in die Stadt. Wo finde ich
dich dann um dir den Schlüssel zu geben?“ „Ich weiß leider nicht, ob ich dann gerade Zeit habe. Stelle
doch einfach dein Fahrrad um 10.00 Uhr auf den Hof und schließe es ab. Wenn du dann um 14.00
Uhr noch einmal vorbei kommst, kannst du es ja wieder los schließen.“ „ ??, dann wird es sicher bis
zum Abend gestohlen!“ „Sicher nicht, denn ich habe es ja in meiner Mittagszeit mit meinem Schloss
abgeschlossen – so kann nichts passieren und ich kann es am Abend benutzen.“
Dieses ‚Doppelschlossverfahren’ kann genau so gut in der Kryptographie angewandt werden.
a) Eine mögliche, sehr einfache Anwendung des Verfahrens ist eine doppelte
Schlüsselwortaddition zu einem gegebenen Klartext, wobei eine buchstabenweise Addition
über die Alphabetnummer erfolgen kann. Die Gesamtoperation verläuft in o.a. 4 Schritten:
Fahrradbild
Krypto-Verfahren
Beispiel:
Fahrrad
Klartext
Der Waldarbeiter macht eine Pause.
Albertas Schloss
SWort1
Glyzerin
Cornelius’ Schloss
SWort2
Jacke
1. Alberta verschließt das
Fahrrad
2. Cornelius verschließt das
Fahrrad
3. Alberta schließt ihr
Fahrradschloss wieder los
3. Cornelius schließt sein
Fahrradschloss wieder los
und kann fahren
Klartext
+ SWort1 →
1.Geheimtext
1.Geheimtext
+ SWort2 →
2.Geheimtext
2.Geheimtext
– SWort1 →
3.Geheimtext
3.Geheimtext
– SWort2 →
Klartext
DERWALDARBEITERMACHTEINEPAUSE
+GLYZERINGLYZERINGLYZERINGLYZE
=KQQWFDMOYNDIYWAAHOGTJAWSWMTSJ
KQQWFDMOYNDIYWAAHOGTJAWSWMTSJ
+JACKEJACKEJACKEJACKEJACKEJACK
=URTHKNNRJSNJBHFKIRRYTBZDBWUVU
URTHKNNRJSNJBHFKIRRYTBZDBWUVU
-GLYZERINGLYZERINGLYZERINGLYZE
=NFUHFVEDCGOJWPWWBFSYOJQPUKVVP
NFUHFVEDCGOJWPWWBFSYOJQPUKVVP
-JACKEJACKEJACKEJACKEJACKEJACK
=DERWALDARBEITERMACHTEINEPAUSE
Beschreibe den Ablauf einer Simulation dieses Verfahrens unter Angabe der benutzten
Objekte/Variablen und der notwendigen Prozeduren/Funktionen und
implementiere die Delphi-Funktion
function stringaddieren(t1,t2 : string):string;,
die zum String t1 den (auf die richtige Länge gebrachten) String t2 zeichenweise addiert und
als Resultat den Additionsstring ausgibt.
mögliches Formular
b) Beschreibe kurz welche Vor- und Nachteile ein solches Doppelschlossverfahren grundsätzlich
besitzt und welche besondere Eigenschaft die einzelnen Verschlüsselungsverfahren unbedingt
haben müssen.
→
Marie – Curie – Gymnasium
Städt. Gymnasium Recklinghausen
Abitur 2006
GK Informatik
Vorschlag I
Aufgabe 2)
Eine Turingmaschine TM ist ein einfaches Modell eines Computers, das allerdings (theoretisch) alles
berechnen kann, was berechenbar ist. Benannt ist die Turingmaschine nach Alan M. Turing, der sie
1936 erdacht hat.
Eine TM besteht aus einem unendlichen Arbeitsband, das in einzelne Zellen unterteilt ist, die ein
Zeichen enthalten können, einem Schreib- und Lesekopf SLK, der eine Zelle auslesen oder
beschreiben/löschen kann und der sich zur benachbarten Zelle bewegen kann und einem ‚Steuerwerk’,
in dem festgelegt ist, wie die TM auf vorkommende Situationen reagiert. Beim Startzustand s1
befindet sich der SLK auf einer Zelle, eine endliche Anzahl von Zellen ist beschrieben, die restlichen
sind leer (als Zeichen #).
a) Eine spezielle TM ist gegeben durch das Zeichen 1, das gelesen oder geschrieben werden
kann. Das Steuerwerk wird durch die folgenden Regeln bestimmt:
Steht der SLK in s1 auf einer 1, löscht er sie, rückt nach rechts und geht in den Zustand s2
über.
Steht der SLK in s1 auf einer #, bleibt er und geht in den Endzustand s6 über.
Steht der SLK in s2 auf einer 1, rückt er nach rechts und geht in den Zustand s2 über.
Steht der SLK in s2 auf einer #, rückt er nach rechts und geht in den Zustand s3 über.
Steht der SLK in s3 auf einer 1, rückt er nach rechts und geht in den Zustand s3 über.
Steht der SLK in s3 auf einer #, schreibt er eine 1, rückt nach links und geht in den Zustand s4
über.
Steht der SLK in s4 auf einer 1, rückt er nach links und geht in den Zustand s4 über.
Steht der SLK in s4 auf einer #, rückt er nach links und geht in den Zustand s5 über.
Steht der SLK in s5 auf einer 1, rückt er nach links und geht in den Zustand s5 über.
Steht der SLK in s5 auf einer #, schreibt er eine 1, rückt nach rechts und geht in den Zustand s1
über.
1) Beschreibe diese TM als endlichen Automaten und gib seine Funktionen als
Automatentafel oder als gerichteten Graphen an.
2) Starte die TM in der u.a. Startsituation und beschreibe die einzelnen
Abläufe bis zum Eintreten des Endzustands.
#
#
#
#
#
#
#
#
#
#
#
1
1
#
#
#
#
#
#
#
#
#
#
#
b) Gib die Regeln des Steuerwerks einer TM an, die, irgendwo angesetzt auf einer Folge von 1en, links und rechts je eine 1 hinzufügt.
mögliche Startsituation:
#
#
#
#
#
#
#
#
#
1
1
1
1
1
1
1
#
#
#
#
#
#
#
#
#
1
1
1
1
1
1
1
1
1
#
#
#
#
#
#
#
mögliche Endsituation:
#
#
#
#
#
#
#
→