Belegaufgaben

Sören Balko, Ilona Blümel, Dr. Martina Engelke, Markus Feldbach, Niels Grabe, Dr. Reinhard Köppe, Uwe Scholz, Nadine Schulz, Dr. Fritz Zbrog

BELEGAUFGABEN

Ausgabe: 04.05.01

Bearbeitung: in Gruppen von zwei Studierenden (können aus verschiedenen Studienrichtungen sein)

Abnahme des lauffähigen JAVA-Programms im SUN-Pool in 03-304b: ab 18. Juni 2001

Konsultationsmöglichkeiten: beim Tutor

Die Lösung ist als JAVA-Applet oder Applikation abzuliefern und im SUN-Pool verfügbar zu machen.

Als Dokumentation ist bis zum 18.06.01 in gedruckter Form beim Übungsleiter abzugeben:

• kurze Beschreibung der Lösungsidee
• Beschreibung der verwendeten Datenstrukturen und Algorithmen
• Testdaten
• kein!! Quelltext

Achten Sie darauf, dass die Oberfläche in einer separaten Klasse formuliert wird.

Bei der Belegabnahme wird geprüft, inwieweit das vorgeführte Programm läuft und verstanden ist (Programm muss gut erklärt und leichte Modifikationen müssen vorgenommen werden können).

Von den folgenden Aufgaben ist eine zur Bearbeitung auszuwählen!

1. Auswertung von arithmetischen Ausdrücken mit Hilfe eines Baumes

Schreiben Sie ein JAVA-Programm, das den Syntaxbaum eines arithmetischen Ausdrucks anschaulich darstellt.

Beispiel: ((x * y) + 6) / (4 - z) ergibt folgenden Syntaxbaum:

Die Auswertung erfolgt wie folgt rekursiv:

Falls der Inhalt des Knotens k '+',  '-',  '*'  oder '/' ist, so

• berechne den Wert des linken Teilbaumes,
• berechne den Wert des rechten Teilbaumes und
• verknüpfe beide Werte mit dem Operationszeichen k.

Die Berechnung der Wurzel liefert dann den gesuchten Wert des Ausdrucks.

2. Hash-Verfahren

Es ist ein JAVA-Programm zu schreiben, das die Speicherung von Daten mit Hash-Verfahren demonstriert. Bei Kollisionen sollen die Daten mit gleichen Hash-Funktionswerten

• in einer linearen Liste verkettet werden.
• Alternativ dazu soll demonstriert werden, wie Kollisionen unter Benutzung des vorgegebenen Adressraumes durch lineare und durch quadratische Verschiebung platziert werden.

Das Einfügen von Daten und das Suchen von Daten sollte anschaulich auf dem Bildschirm dargestellt werden. Der die jeweilige Aktion auslösende Quelltext-Teil ist auf dem Bildschirm anzuzeigen.

3. Variation des Abzählreims

In diesem Spiel sitzt eine Gruppe von Kindern im Kreis. Die Kinder reichen hinter sich in Uhrzeigerrichtung ein Taschentuch herum bis der Spielleiter eine Glocke läutet. Das Kind, hinter dem zu diesem Zeitpunkt das Taschentuch liegt, muss den Spielkreis verlassen. Der Prozess wird solange wiederholt bis nur noch ein Kind überbleibt, das ist dann der Gewinner.

• Beschreiben Sie eine effiziente Methode, um das Spiel zu implementieren. Diskutieren Sie dabei als zu Grunde liegende Datenstrukturen ein einfaches Array und die doppelt verkettete Liste.
• Wie hoch ist die Laufzeit-Komplexität in O-Notation in Abhängigkeit von n (Anzahl der teilnehmenden Kinder) für beide Datenstrukturen?
• Implementieren Sie das Spiel unter Benutzung der von Ihnen favorisierten Datenstruktur.
• Schreiben Sie als Testrahmen eine geeignete visuelle Darstellung des Spieles.

4. Schiffe versenken

Visualisieren Sie folgendes Spiel:

• Dieses Spiel wird normalerweise von zwei Personen mit Papier und Bleistift gespielt. Hier ist jedoch der Computer einer der beiden Spieler. Er hält auch den Spielstand fest und zeigt ihn an. Wenn der Computer an der Reihe ist, spielt er immer absolut zufällig. Das Spiel ist also sehr vereinfacht.
• Zwei Gitter 10x10 werden am Bildschirm angezeigt. Das Heimatgitter stellt einen Ozean dar und zeigt die Position Ihre Schlachtschiffe an. Das Feindgitter zeigt, wohin Sie einen Schuss abgefeuert haben, aber Sie können den Feind nicht sehen. Sie wissen nicht, wohin der Computer die Schiffe platziert hat. und der Computer weiß nicht, wo sich Ihre Schiffe befinden.
• Zu Beginn platzieren Sie irgendwo in Ihrem Gitter ein Fünfer-, ein Vierer-, zwei Dreier- und ein Zweier-Schlachtschiff. Das geschieht durch das Anklicken der Quadrate mit der Maus. Der Computer platziert seine zehn Schiffe ebenfalls irgendwo im Zielgitter. Er platziert seine Schiffe zufällig, aber Sie können selbstverständlich strategisch vorgehen.
• Der Computer bestimmt zufällig, wer anfängt. Sie und der Computer spielen dann abwechselnd.
• Sie feuern einen Schuss auf den Feind (den Computer) ab, indem Sie das entsprechende Quadrat des Zielgitters anklicken. der Computer zeigt die Position auf dem Gitter an, so dass Sie sehen können, wohin Sie Ihre Schüsse abgegeben haben. der Computer zeigt an, ob ein Schiff versenkt wurde oder nicht.
• Danach ist der Computer dran. Obwohl er die Positionsdaten Ihrer Schiffe enthält, benutzt er die Daten nicht und entscheidet sich zufällig, wohin er auf Ihrem Gitter feuert. Aber der Computer erinnert sich daran, wohin er bereits gefeuert hat.
• Das Spiel wird solange fortgesetzt, bis ein Spieler alle feindlichen Schiffe versenkt hat.

unsere Lösung (Daniel Hakenjos und Sebastian Nusser)

5. RSA-Chiffre

Das Generieren eines Schlüsselpaares erfolgt in diesen Schritten:
1. Wähle zwei Primzahlen p und q (im Beispiel p=47, q=59)
2. Berechne n = p*q (n = 2773)
3. Berechne f = (p-1)*(q-1) (f = 2668)
4. Wähle ein e, das teilerfremd zu n und f ist: (e = 17)
5. Berechne das modulare Inverse d so, dass die Beziehung (e*d)%f = 1 gilt. (d  = 157).
Die Primzahlen p und q sind zu vergessen, als öffentlicher Schlüssel wird (e,n) verwendet, als geheimer Schlüssel (d,n).

Das Chiffrieren eines Klartextblockes m (einer Zahl m <n) erfolgt mit einer modularen Potenzierung: c = m^e mod n.
Das Ergebnis ist der Geheimtextblock c, ebenfalls eine Zahl.  (Beispiel: für m = 920  ist c = 948)
Das Dechiffrieren erfolgt ebenso durch die Berechnung der modularen Potenz mit dem geheimen Schlüssel: m = c^d mod n.

Für kleine n ist das RSA-Verfahren unsicher, da aus n die beiden Primzahlen ermittelt werden können und damit aus der Kenntnis des öffentlichen Schlüssels der geheime berechnet werden kann. Das RSA-Verfahren ist sicher, wenn das n genügend groß ist. Aus diesem Grund sollten die gewählten Primzahlen mindestens 512 Bit lang sein.

Schreiben Sie eine Klasse MyRSA für die Generierung der Schlüssel, die Chiffrierung und die Dechiffrierung. Für die Demo-Beispiele sollen Zahlen aus dem Bereich Integer gewählt werden können, für den sicheren Einsatz auch große Zahlen (nutzen Sie die in Java vorhandene Klasse BigInteger).
In einer Applikation sollen Schlüsselgenerierungen möglich sein, das Chiffrieren und Dechiffrieren. Die Zahlen können als Hexadezimalzahlen dargestellt werden. Die Schlüssel sollten in einer Datei gespeichert werden.

6. Knack den Code

Das Knacken eines Geheimtext gehört seit jeher zu den reizvollsten Aufgaben. Das einfache Durchprobieren aller Möglichkeiten, der Brute-Force Angriff kommt bei den meisten Chiffrierverfahren nicht in Frage, da er zu lange dauert. Kennt man das Chiffrierverfahren, gelingt die Kryptanalyse der klassischen Verfahren fast online.

Die folgenden Geheimtexte wurden mit einem monoalphabetischen Verfahren chiffriert. Dazu wird eine Tabelle benötigt, die jedem Klartextbuchstaben genau einen Geheimtextbuchstaben zuordnet. Einzige Randbedingung ist, dass nicht zwei verschiedene Zeichen durch ein gleiches ersetzt werden dürfen. Die Tabelle, bzw. deren Generierungsvorschrift muss dem Empfänger der Nachricht bekannt sein, damit er danach dechiffrieren kann. Der Kryptanalytiker versucht, diese Tabelle zu konstruieren.

Das systematische Durchprobieren erfordert, alle Permutationen des Alphabets, also alle verschiedenen Anordnungen zu durchsuchen. Das sind mit 26! » 4*10²⁶ Möglichkeiten zu viel, deshalb setzt man statistische Methoden ein. Die charakteristische Häufigkeitsverteilung der Buchstaben ist sprachabhängig und bleibt im Geheimtext erhalten, so kann man vermuten, dass der häufigste Buchstabe (in der deutschen Sprache mit 17%) das 'e' sein wird. Mit der Kenntnis der Häufigkeiten der Buchstaben und der Buchstabenpaare sowie der erhaltenen Textmuster versucht man intuitiv, alle weiteren Buchstaben der Tabelle zu erraten. Irrtümer sind möglich und können wieder korrigiert werden.

In der Belegaufgabe soll eine Java-Applikation geschrieben werden, die ein Knacken des monoalphabetisch chiffrierten Geheimtextes unterstützt.

Auf dem Bildschirm soll angezeigt werden:

• ein Textfeld zum Anzeigen des Geheimtextes,
• ein Textfeld zum Anzeigen des Klartextes, das anfangs leer ist,
• die Häufigkeiten der einzelnen Buchstaben des Geheimtextes,
• die Ersetzungstabelle, bei der anfangs nur die Buchstaben des Geheimtextes eingetragen sind.

Wenn die Ersetzungstabelle vollständig gefüllt ist, sollte ein verständlicher Klartext angezeigt werden.

Die Geheimtexte sind in Dateien gespeichert, die Eingabe soll über den Dateinamen erfolgen.

Erleichternd für das Knacken des Geheimtextes ist, wenn die einzelnen Wortlängen erkennbar sind. Aus diesem Grund wird der Geheimtexten in Großbuchstaben umgewandelt und alle Zeichen entfernt, die keine Buchstaben sind. Zur besseren Lesbarkeit werden die Buchstaben in Gruppen angeordnet.

Beispiel: Der Klartext:

"Die klassische Aufgabe der Kryptographie ist es, eine Nachricht oder Aufzeichnung für den Unbefugten unverständlich zu machen."

wird mit dieser Tabelle:
 

in den folgenden Geheimtext chiffriert:

KJPQU OHHJH GYPOF ZWOLP KPCQC MRIEW CORYJ PJHIP HPJTP TOGYC JGYIE KPCAF ZVPJG YTFTW ZCKPT FTLPZ FWIPT FTSPC HITKU JGYVF NOGYP T

7. Visualisierung der Funktionalitäten des ADT "Stack"

Im Rahmen dieser Aufgabe sind die in der Vorlesung eingeführten Funktionen eines Stacks mit Hilfe eines Java-Applets zu implementieren und für einen Benutzer graphisch zu visualisieren. Ein Benutzer soll dabei die Möglichkeiten besitzen Elemente in Form eines Zeichens (zum Beispiel a, b, c, ...) und die auszuführende Operation in Form einer Auswahlbox (zum Beispiel Listbox oder Checkbox) einzugeben. Entsprechend dieser Informationen sind die jeweiligen Operationen auszuführen und schrittweise dem Benutzer zu verdeutlichen.

8. Visualisierung von Petrinetzen

---

9.  Das Spiel "Pasch"

Schreiben Sie ein Applet, daß eine Registermaschine bezüglich des Inhaltes der Register, der Befehlsnummer und des im Fokus stehenden Befehls animiert.
Der Befehlsvorrat sei load, cload,store, cstore, add, mult, div, goto  und  halt . Die Befehlseingabe soll per vorzubereitendem File erfolgen.  Das Applet ist mit Hilfe der Buttons Neu, Step und Exit zu steuern.

Schreiben Sie ein Applet, das auf seinen Darstellungsflächen jeweils die ADT-Spezifikation eines finiten Stacks und im anderen Teil die Java-Implementation (Sourcecode) darstellt.
Wird eine Zeile der Spezifikation angeklickt, färbt sie sich und im zweiten Teil der Darstellungsfläche wird der zugehöhrige Java-Text entsprechend eingefärbt.

Es ist ein in einem zweckmäßigen Format gegebenen Bild durch die Anwendung einer Filtertechnik zu verbessern. Das Bild kann auch eingescannt werden.
Als Filter kann z.B. ein Medianfilter (siehe unter Bildverarbeitungsvorlesung) eingesetzt werden. Das Ausgangs- und das Resultatsbild sind anzuzeigen.

Visualisieren Sie in einem Applet die zwei-dimensionale Simulation der mechanischen Abläufe beim Billard-Spiel. Dazu gehören der initiale Impuls des Queues auf die erste Kugel, die Kollision von Kugeln untereinander, sowie die Kollision von Kugeln und Bande. Löcher, Spielregeln usw. brauchen nicht berücksichtigt zu werden. Es sollen mindestens zwei Kugeln dargestellt werden.

Die Kugeln sind durch ihre Mittelpunkte (x,y) in einem Rechteck gegeben. Der initiale Bewegungsvektor (dx,dy) ist (0,0), d.h. die Kugeln ruhen. Durch den Queue wird einer Kugel ein Impuls gegeben. In jedem Animations-Schritt wird jede Kugel um ihren Bewegungsvektor versetzt. Falls dabei eine Kollision mit einer anderen Kugel auftritt bzw. die Bande getroffen wird, wird der Bewegungsvektor der betroffenen Kugeln neu berechnet. Außerdem ist die Reibung zu berücksichtigen, die den Bewegungsvektor in jedem Schritt verkleinert.

Stellen Sie den Verlauf einer mathematischen Funktion mittels eines Java-Applets dar. Der Parameterbereich soll veränderbar sein sowie zusammen mit dem automatisch bestimmten Wertebereich an den Achsen angetragen werden. Wählen Sie eine der folgenden Varianten:

Variante 2D: Die darzustellende Funktion f(x) wird als String eingegeben und mittels Stacks berechnet. Die Darstellung erfolgt zwei-dimensional (analog zu diesen Beispielen, wobei die Darstellung mehrerer Kurven in einem Diagramm nicht verlangt ist). Als Operatoren sind mindestens die Grundrechenarten +, -, * und / vorzusehen.

Variante 3D: Es soll eine zwei-dimensionale Funktion f(x,y) dargestellt werden. Die Auswertung des Ausdrucks ist nicht verlangt, es reicht aus, aus einer Reihe vordefinierter Funktionen auswählen zu können. Dafür sollen in der Darstellung die verdeckten Linien entfernt werden (siehe diese Beispiele).

Startseite