Nachstehend finden Sie ergänzende Übungen zur Vorlesung "Grundlagen der Informatik".
-
Codierung, Speicherbedarfe und Zahlensysteme
Übung A-1: BCD-Zahlen
Was versteht man unter einer BCD-Zahl? Wofür steht BCD? Was versteht man unter einer Tetrade und einer Pseudotetrade? (Sehen Sie hierzu bitte bedarfsweise im Skriptum nach.)
Geben Sie exemplarisch bitte an, wie die Dezimalzahlen 17 und 125 als BCD-Zahl abgespeichert werden.Übung A-2: Hexadezimalsystem
Überlegen Sie sich bitte, weshalb das Hexadezimalsystem für Programmierer (in manchen Situationen zumindest) interessant ist. Welchen Vorteil bietet es beispielsweise gegenüber dem Dezimalsystem?
Übung A-3: Bitfolge / Dualsystem
Wofür stehen die nachstehenden Bitfolgen?
0001 1100
01000110 01001000 01000100 01010111
(Hier wird natürlich davon ausgegangen, dass Sie ein digitales Umrechnungswerkzeug für die gro0ßen Zahlen verwenden, auch wenn Sie die Umrechnung grundsätzlich beherrschen sollten.)Übung A-4: Dezimalzahl in Bitfolge umwandeln
Wie kann die Dezimalzahl 117 als Bitfolge dargestellt werden?
Übung A-5: Fehlererkennung
Was versteht man unter einem fehlererkennenden Code? Geben Sie ein konkretes Beispiel.
(Nötigenfalls recherchieren Sie hierzu im Internet!)
Sind Ihnen aus der Praxis Situationen bekannt, in denen auf ähnliche Weise eine automatische Fehlererkennung ermöglicht wird?Übung A-6: Speicherbedarf
Welchen Speicherplatz benötigen Sie zur Abspeicherung eines Pixels (Bildpunktes) bei einer Schwarz-Weiss-Zeichnung? Und bei einer Farbgraphik, bei der 16 verschiedene Farben vorkommen können?
Überlegen Sie sich bitte weiterhin, welchen Speicherplatzbedarf wir in den nachfolgend geschilderten Situationen haben.
- Welche der genannten Informationen passen somit auf eine 1,4-Megabyte-Diskette? (Kennen Sie Disketten überhaupt noch?)
- Welche der hier berechneten Speichermengen passt auf einen USB-Stick, auf dem noch 250 Megabyte Platz frei ist?
- Wie lange würde die Datenübertragung beim letztgenannten Beispiel dauern, wenn wir eine Internet-Anbindung via FTTH / Glasfaser mit 1 Gigabit/s zur Verfügung hätten?
- Eine Graphik der Größe 400 Pixel (Bildpunkte) auf 200 Pixel soll gespeichert werden. Dabei sollen 256 verschiedene Farben möglich sein.
- Dieselbe Graphik soll als Graustufenbild (mit 256 möglichen Abstufungen) gespeichert werden.
- Dieselbe Graphik soll als sogenanntes Strichbild gespeichert werden. (Strichbild bedeutet, dass für jeden Bildpunkt nur die beiden Möglichkeiten "schwarz" oder "weiß" möglich sind.)
- Ein Schwarz-Weiß-Schriftzug soll als Graphik im Format 800 x 600 Pixel abgespeichert werden.
- Von einem Bildschirm mit der Auflösung 1024 x 768 Pixel und einer Farbtiefe von 16 Bit (-wievielen Farben entspricht dies?-) soll ein Abzug gemacht werden.
- Für ein großes Werbebanner im Format 16 x 9 wird eine Graphik mit der Auflösung 16000 x 9000 Pixel und einer Farbtiefe von 16 Millionen Farben benötigt.
-
Algorithmen und Datenstrukturen
Übung B-1: Wahlauszählungsverfahren d'Hondt
Sie kennen das d'Hondt-sche Verfahren (auch Höchstzahlverfahren genannt) zur Auszählung und Bewertung von Wahlergebnissen?
Die nachstehende Tabelle illustriert das Verfahren am konkreten Beispiel. Hier stehen vier Parteien A, B, C und D zur Wahl, die 1000, 700, 400 und 300 Stimmen erhalten haben. Es seien 7 Mandate zu verteilen.
Angenommen, es seien insgesamt 4 Parteien A,B,C,D mit den Stimmergebnissen 1000, 700, 400, 300 gewählt worden. 7 Mandate sind zu vergeben.
Partei: A B C D 1 1000(1) 700(2) 400(4) 300(7) 2 500(3) 350(5) 200 150 3 333,33(6) 233,33 133,33 100 4 250 175 100 75 5 200 140 80 60 Mandate: 3 2 1 1 Die Ergebnisse werden zunächst notiert; anschließend werden alle Ergebnisse halbiert in die nächste Zeile geschrieben. Darunter wiederum werden die Ausgangszahlen durch 3 dividiert notiert. So fährt man fort, solange "es erforderlich ist". (Es liegt an Ihnen, dies konkret auszuformulieren.) Schließlich werden die Zahlen der Größe nach bewertet, d.h. es werden die Mandate der Reihenfolge nach verteilt: das 1.Mandat in unserem Zahlenbeispiel geht an A, denn dort steht in Zeile 1 die 1000, das ist die absolut größte Zahl. Das 2.Mandat geht an B, die höchste (noch nicht verwendete) Bewertungszahl dort ist die 700. Das 3.Mandat geht an die Partei mit der nunmehr höchsten (noch nicht berücksichtigten) Bewertungszahl, das ist erneut die Partei A mit der Zahl 500 in Zeile 2. Das 4.Mandat geht an C mit der Bewertungszahl 400, das 5.Mandat geht wieder an B, das 6.Mandat wieder an A, und erst das 7.Mandat geht an Partei D mit 300 als (noch nicht berücksichtigter) Bewertungszahl. - Alles klar?
Formulieren Sie den Algorithmus von d'Hondt in übersichtlicher Weise allgemein - als Pseudocode oder in einem Struktogramm.
Implementieren Sie anschließend diesen Algorithmus in C (oder C++). (Für die konkrete Implementierung dürfen Sie wiederum von vier Parteien A, B, C, D ausgehen, auch wenn der d'Hondtsche Algorithmus natürlich für beliebig endlich viele Parteien formuliert werden kann.)
Übung B-2: Hare-Niemeyer-Algorithmus
Weil es so schön ist, bleiben wir bei Wahlergebnissen. Neben d'Hondt gibt es ein weiteres bekanntes Auszählungs- und Bewertungsverfahren von Hare-Niemeyer. Hierbei wird das Ergebnis jeder Partei durch die Gesamtstimmenanzahl dividiert und mit der Anzahl der zu vergebenden Mandate multipliziert. Die Zahl vor dem Komma gibt die Anzahl der Grundmandate dieser Partei an. Die eventuell übrigen Mandate gehen der Reihe nach an die Parteien mit den höchsten Nachkommazahlen.
Das ist Ihnen zu theoretisch? - Sehen wir uns das im Beispiel der vorherigen Übung an.
Abgegebene gültige Stimmen: 1000+700+400+300=2400
Partei A: 1000 Stimmen, 1000/2400*7 = 2,92 - das entspricht 2 Grundmandaten.
Partei B: 700 Stimmen, 700/2400*7 = 2,04 - das entspricht ebenfalls 2 Grundmandaten.
Partei C: 400 Stimmen, 400/2400*7 = 1,17 - das entspricht 1 Grundmandat.
Partei D: 300 Stimmen, 300/2400*7 = 0,875 - das entspricht keinem Grundmandat.
Damit gehen fünf der sieben Mandate als Grundmandate an A (2), B (2) und C (1). Zwei weitere Mandate sind zu vergeben.Die höchste Nachkommazahl hat nun mit 0,92 Partei A, A erhält also ein weiteres Mandat. Schließlich geht das siebte Mandat an Partei D, die mit 0,875 die nächstgrößere Nachkommazahl aufweist.
Formulieren Sie den Algorithmus von Hare-Niemeyer ebenfalls allgemein - als Pseudocode oder in einem Struktogramm.
Implementieren Sie anschließend diesen Algorithmus in C oder C++.
Übung B-3: ISBN
Bücher werden mit einer sogenannten ISBN versehen. (ISBN steht für "Internationale Standard-Buchnummer.) Diese Nummer hat (als zehnstellige Nummer, sog. ISBN-10) qualitativ den Aufbau 1-234-56789-0, wobei die Bindestriche in unserem Zusammenhang keine besondere Relevanz besitzen. Die letzte, zehnte Ziffer ist eine Prüfziffer, die aus dem Wertebereich { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, X }stammt; X steht dabei für 10. Alle anderen neun Ziffern sind Werte zwischen 0 und 9 einschließlich.
Die Prüfziffer zur neunstelligen Zahl a1 a2 a3 a4 a5 a6 a7 a8 a9 berechnet sich wie folgt: zunächst wird die Summe 10*a1+9*a2+8*a3+...+3*a8+2*a9 ermittelt. Deren Rest modulo 11 wird von 11 abgezogen, dies ergibt die Prüfziffer.
Beispiele: Zur ISBN 3-540-59101-X wird berechnet: 10*3+9*5+8*4+7*0+6*5+5*9+4*1+3*0+2*1 = 188; 188 modulo 11 = 1; schließlich ist 11-1 = 10, was durch das X dargestellt wird.
Zur ISBN 3-8273-1257-4 wird analog die gewichtete Summe berechnet: 10*3+9*8+...+2*7 = 227; 227 modulo 11 = 7; 11-7 = 4, und das ist wiederum die Prüfziffer.
Formulieren Sie den Algorithmus zur Berechnung der Prüfziffer einer ISBN. Implementieren Sie ihn anschließend in C.
Welche Prüfziffer fehlt bei der ISBN-10 1-234-54321-? ? Ist 3-0815-4711-2 eine gültige ISBN-10?
Anmerkung: Bei der ISBN-13, der 13-stelligen ISBN, handelt es sich um eine EAN, eine Europäische Artikelnummer. Hier wird die Prüfziffer ermittelt, indem die ersten zwölf Stellen abwechselnd mit 1 und mit 3 multipliziert und diese Terme dann aufaddiert werden zur Summe S. Die Prüfziffer ist dann 10 - S mod 10.
Ein Rechenbeispiel hierzu findet sich bei pruefziffernberechnung.de.
Wer mag, kann gerne auch diesen Algorithmus in Form eines kleinen Programms realisieren.Übung B-4: Arrays sortieren
Sie kennen aus der Vorlesung "Programmierung" den Datentyp Array (in C). Deklarieren und definieren Sie ein Array von zehn ganzzahligen Speicherplätzen und initialisieren Sie es mit den Werten 5, 2, 1, 3, 7, 10, 6, 8, 9, 4.
Überlegen Sie sich (mindestens) einen Algorithmus, wie Sie dieses Array absteigend sortieren können. Implementieren Sie ihn bitte in C.
Was müsste an diesem Algorithmus verändert werden, wenn nicht ganze Zahlen sondern Zeichenketten sortiert werden müssten? (Eine entsprechende Implementierung in C wird natürlich nur erwartet, sofern Sie in der Vorlesung "Programmierung" bereits Zeichenketten behandelt haben.)
Übung B-5: Kürzen von Brüchen
Will man Brüche gekürzt darstellen (also 8/3 statt 24/9 usw.), dann benötigt man den größten gemeinsamen Teiler (ggT) von zwei ganzen Zahlen a und b. Dieser kann dadurch berechnet werden, dass von der größeren der zwei (unterschiedlichen) Zahlen die kleinere abgezogen wird. Sind anschließend beide nun vorliegenden Zahlen gleich, dann ist dies der größte gemeinsame Teiler von a und b. Ist dies nicht der Fall, dann wird wiederum von der größeren der beiden Ergebniswerte der kleinere Wert abgezogen. Dies wird fortgesetzt, bis schließlich beide Rechenergebnisse gleich sind; diese Zahl ist der ggT von a und b.
Zahlenbeispiel: Sind a=24 und b=9, so ist a natürlich ungleich b, im ersten Schritt wird die 9 von der 24 abgezogen, die ersten Zwischenergebnisse sind somit 24-9=15 und 9. 15 und 9 sind ungleich, also wird nun 15-9=6 gebildet. Im nächsten Schritt ist 9 die größere Zahl, 9-6=3. 3 und 6 sind ungleich, also wird nun 6-3=3 gebildet. 3 und 3 sind gleich (aha!), also ist 3 der ggT von 24 und 9. (Stimmt tatsächlich.)
Formulieren Sie bitte diesen Algorithmus und implementieren Sie ihn in C.
Übung B-6: Primzahlen
Eine positive, ganze Zahl ist eine Primzahl, wenn Sie größer als 1 ist und sich nur durch sich selbst und durch 1 ohne Rest teilen lässt.
Überlegen Sie sich einen Algorithmus, mit dem Sie eine bestimmte Zahl n daraufhin prüfen können, ob es sich hierbei um eine Primzahl handelt.
Überlegen Sie sich einen zweiten Algorithmus, mit dem Sie zu einer natürlichen (positiven) Zahl n alle Primzahlen von 2 bis n auflisten können.
Implementieren Sie mind. einen der beiden Algorithmen in C.
Übung B-7: Quadratische Gleichung
Sie kennen alle (?) die Formel zur Lösung einer quadratischen Gleichung. Formulieren Sie den entsprechenden Algorithmus, so dass Sie diesen bei Bedarf "sofort" in ein C-Programm umsetzen könnten. Ausgabe soll/en natürlich die Lösung/en der betreffenden quadratischen Gleichung sein.
Übung B-8: Ein Algorithmus
Nachstehend sehen Sie ein Struktogramm. (Original-URL: http://www.thueringen.de/ tkm/ hauptseiten/ grup_medien/ abi98docs/ informgf1.gif).
Was tut der hier beschriebene Algorithmus?
Übung B-9: Arrays und Mengen
Erläutern Sie Gemeinsamkeite und Unterschiede von Arrays (Feldern) und Mengen. (In der Programmiersprache Pascal gibt es beides als vordefinierte Datentypen; in ANSI-C gibt es keinen vordefinierten Datentyp für Mengen.)
Überlegen Sie sich je eine Problemstellung, bei der(en Lösung) Sie den Datentyp Array bzw. Menge einsetzen würden.
Übung B-10: Lineare Liste
In der nachstehenden Skizze ist eine einfache lineare Liste von Kundendatensätzen dargestellt. Implementieren Sie diese Datenstruktur bitte in einem kleinen ANSI-C-Programm kliste.c.
- Definieren Sie den Datentyp KUNDENLISTE; dieser soll eine Lineare Liste von Kundendaten realisieren, wobei die Kundendaten der Einfachheit halber nur aus den Komponenten Nachname, Vorname und Geburtsdatum bestehen sollen.
- Zu Programmstart soll die konkrete Kundenliste selbstverständlich leer sein.
- Das Programm kliste.c soll immer wieder ein Auswahlmenu mit folgenden Elementen
anbieten.
- Ausgeben: Die Lineare Liste aller Kundendaten kann in einfacher Weise auf dem Bildschirm angezeigt werden. Selbstverständlich erscheint bei Ausgabe der leeren Liste ein entsprechender Hinweis.
- Datensatz anhängen: Es kann an die bisherige Liste ein (weiterer) Kundendatensatz angehängt werden.
- Datensatz löschen: Es kann ein Kundendatensatz aus der Liste gelöscht werden. Dabei soll
der Einfachheit halber im Moment nur der Nachname abgefragt werden.
[Im Zweifelsfall werden hiermit eben alle "Meier"s auf einmal aus der Liste entfernt!] - Liste sortieren: Auf Wunsch kann die gesamte Liste auch alphabetisch nach Nachnamen sortiert werden!
Übung B-11: Doppelt verkettete Liste
Unter einer doppelt verketteten Liste (DVL) versteht man eine lineare Liste, bei der neben den Zeigern auf den jeweiligen Nachfolger auch Pointer auf die direkten Vorgänger verwaltet werden. Dies ist insbesondere sinnvoll für alle Problemstellungen, bei denen auch vor einem gefundenen Listenelement etwas geschehen soll - wenn z.B. ein weiteres Element sortiert eingefügt werden soll.
Implementieren Sie ein kleines C-Programm dvliste.c, das wieder auf der zuvor erwähnten Kundendatenstruktur aufsetzt, diesmal aber eine doppelt verkettete Kunden-Liste verwaltet. Dabei soll die Grundfunktionalität dieselbe sein wie zuvor.
Darüber hinaus soll eine Funktion Rückwärts ausgeben bereitgestellt werden, die das tut, was der Name verspricht.
Übung B-12: Implementierung einer Menge
Implementieren Sie in ANSI-C oder in C++ einen Datentyp Menge, der einen "beliebig großen" Teilbereich der natürlichen Zahlen darstellen kann.
Vor dem konkreten Einsatz einer Variablen vom Typ Menge werde der Grundbereich bereits festgelegt. Ein möglicher Grundbereich ist beispielsweise die Menge aller natürlichen x mit
1 <= x <= 100.Zu dem Typ Menge sollen die folgenden Operationen (in C als Funktionen, in C++ als Konstruktoren, Methoden, Operatoren) realisiert werden:
- Eine Menge M soll "sauber" initialisiert werden (als "leere Menge"). Dies soll in C durch eine Funktion init() geschehen, in C++ natürlich durch den Default-Konstruktor.
- Mit aufnehmen() soll ein (weiteres) Element in die Menge aufgenommen werden können.
- Mit streichen() soll ein Element aus der Menge herausgenommen werden können.
- Mit ausgabe() werden die Elemente der Menge auf die Konsole ausgegeben.
- Mit eingabe() soll der Anwender die Möglichkeit erhalten, eine Menge von Tastatur zu befüllen. Hierbei ist selbstverständlich auf den zuvor definierten Grundbereich zu achten!
- Als "optionale" Erweiterungen - je nachdem, wieviel Zeit und Elan Sie noch haben - realisieren Sie bitte die üblichen Mengenoperationen: Schnittmenge (Durchschnitt) sowie Vereinigungsmenge zweier Mengen und die Komplementmenge ("alle Elemente des Grundbereiches, die nicht zu M gehören").
Übung B-13: Arrays und Mengen
Erläutern Sie Gemeinsamkeite und Unterschiede von Arrays (Feldern) und Mengen. (In der Programmiersprache Pascal gibt es beides als vordefinierte Datentypen; in ANSI-C gibt es keinen vordefinierten Datentyp für Mengen.)
Überlegen Sie sich je eine Problemstellung, bei der(en Lösung) Sie den Datentyp Array bzw. Menge einsetzen würden.
Übung B-14: Sortieren von Arrays
In dem Programm intsort.c finden Sie zwei konkrete Sortieralgorithmen umgesetzt.
Arbeiten Sie dieses Programm bitte (noch einmal) durch und erweitern Sie es um den dritten Sortieralgorithmus "Sortieren durch direktes Einfügen". (Vgl. hierzu im Skriptum Abschnitt 4.4.1.)
Was muss an diesem Programm bzw. an der Implementierung der Algorithmen verändert werden, wenn nicht numerische Werte, sondern wenn Zeichenketten sortiert werden müssten?
Übung B-15: Quicksort
Implementieren Sie den Quicksort-Algorithmus, den Sie in Abschnitt 4.4.4 des Informatik-Skriptums dargestellt finden.
(Diese Aufgabe ist unabhängig davon, ob in der Veranstaltung bereits darauf hingewiesen wurde, dass ANSI-C eine Routine qsort() besitzt, die den Quicksort bereits zur Verwendung anbietet. Siehe hierzu auch das Beispielprogramm.)Übung B-16: Rekursion
Machen Sie sich mit dem Prinzip rekursiver Funktionen anhand des folgenden Beispiels vertraut. (Eine Funktion f heißt direkt rekursiv, wenn sie sich selbst aufruft. Eine Funktion f heißt indirekt rekursiv, wenn sie andere Funktionen aufruft, die ihrerseits f - wiederum direkt oder indirekt - aufrufen.)
Die Berechnung der mathematischen Fakultät n! ist ein Paradebeispiel für eine Übungs-Rekursion.
Zu einer positiven natürlichen Zahl n wird n! definiert als das Produkt aller Zahlen von 1 bis n. 3! = 3 * 2 * 1 = 6, 5! = 5 * 4* 3 * 2 *1 = 120.
Rekursiv lässt sich für n > 0 schreiben: (n+1)! = (n+1) * n! . Das heißt: (n+1)! wird mittels n! berechnet!Implementieren Sie bitte eine C-Funktion facult(), die zu einer uebergebenen positiven ganzen Zahl n die Fakultät rekursiv berechnet und zurückliefert.
Übung B-17: Die Türme von Hanoi
Abschließend noch eine Feinschmeckeraufgabe: Die Türme von Hanoi.
Der Turm von Hanoi
Nach einer alten Legende befanden sich vor einem Tempel in Hanoi drei Säulen. Auf der ersten Säule befanden sich einhundert Lochscheiben, deren Durchmesser von unten nach oben abnahm. Es bestand eine Weissagung, dass die Welt untergehen würde, wenn es jemandem gelänge, den Turm unter Beachtung der folgenden Regeln auf eine der
anderen
Säulen umzubauen:
- Man darf jeweils nur eine einzelne Scheibe umlegen.
- Nur die oberste Scheibe einer Säule darf jeweils bewegt werden.
- Keine Lochscheibe mit einem größeren Durchmesser darf auf eine Lochscheibe mit einem kleineren Durchmesser zu liegen kommen.
Aufgabe:
- Entwickeln Sie einen Algorithmus, der das Turm-von-Hanoi-Problem löst, d.h. der einen korrekten Ablauf
beschreibt, in welcher Reihenfolge welche Scheiben wie zu bewegen sind.
Dabei soll natürlich die in der Legende genannte Zahl 100 durch eine beliebige positive natürliche Zahl n ersetzt werden. - Setzen Sie diesen Algorithmus um in ein C-Programm, bei dem mitverfolgt werden kann, von welcher Säule auf welche andere Säule jeweils eine Scheibe gelegt wird. - Hinweis: Es bietet sich eine rekursive Lösung an!
Nachstehend zwei Ablauflistings zu einem solchen Programm.
Zwei Ablauflistings eines Türme-von-Hanoi-Programms
Wie hoch ist der Turm? 2 Groesse: 2, Ausgangsturm 1, Ziel 3, Hilfsturm 2. Groesse: 1, Ausgangsturm 1, Ziel 2, Hilfsturm 3. Groesse: 0, Ausgangsturm 1, Ziel 3, Hilfsturm 2. Bewege oberste Scheibe von 1 nach 2. Groesse: 0, Ausgangsturm 3, Ziel 2, Hilfsturm 1. Bewege oberste Scheibe von 1 nach 3. Groesse: 1, Ausgangsturm 2, Ziel 3, Hilfsturm 1. Groesse: 0, Ausgangsturm 2, Ziel 1, Hilfsturm 3. Bewege oberste Scheibe von 2 nach 3. Groesse: 0, Ausgangsturm 1, Ziel 3, Hilfsturm 2. -- Wie hoch ist der Turm? 4 Groesse: 4, Ausgangsturm 1, Ziel 3, Hilfsturm 2. Groesse: 3, Ausgangsturm 1, Ziel 2, Hilfsturm 3. Groesse: 2, Ausgangsturm 1, Ziel 3, Hilfsturm 2. Groesse: 1, Ausgangsturm 1, Ziel 2, Hilfsturm 3. Groesse: 0, Ausgangsturm 1, Ziel 3, Hilfsturm 2. Bewege oberste Scheibe von 1 nach 2. Groesse: 0, Ausgangsturm 3, Ziel 2, Hilfsturm 1. Bewege oberste Scheibe von 1 nach 3. Groesse: 1, Ausgangsturm 2, Ziel 3, Hilfsturm 1. Groesse: 0, Ausgangsturm 2, Ziel 1, Hilfsturm 3. Bewege oberste Scheibe von 2 nach 3. Groesse: 0, Ausgangsturm 1, Ziel 3, Hilfsturm 2. Bewege oberste Scheibe von 1 nach 2. Groesse: 2, Ausgangsturm 3, Ziel 2, Hilfsturm 1. Groesse: 1, Ausgangsturm 3, Ziel 1, Hilfsturm 2. Groesse: 0, Ausgangsturm 3, Ziel 2, Hilfsturm 1. Bewege oberste Scheibe von 3 nach 1. Groesse: 0, Ausgangsturm 2, Ziel 1, Hilfsturm 3. Bewege oberste Scheibe von 3 nach 2. Groesse: 1, Ausgangsturm 1, Ziel 2, Hilfsturm 3. Groesse: 0, Ausgangsturm 1, Ziel 3, Hilfsturm 2. Bewege oberste Scheibe von 1 nach 2. Groesse: 0, Ausgangsturm 3, Ziel 2, Hilfsturm 1. Bewege oberste Scheibe von 1 nach 3. Groesse: 3, Ausgangsturm 2, Ziel 3, Hilfsturm 1. Groesse: 2, Ausgangsturm 2, Ziel 1, Hilfsturm 3. Groesse: 1, Ausgangsturm 2, Ziel 3, Hilfsturm 1. Groesse: 0, Ausgangsturm 2, Ziel 1, Hilfsturm 3. Bewege oberste Scheibe von 2 nach 3. Groesse: 0, Ausgangsturm 1, Ziel 3, Hilfsturm 2. Bewege oberste Scheibe von 2 nach 1. Groesse: 1, Ausgangsturm 3, Ziel 1, Hilfsturm 2. Groesse: 0, Ausgangsturm 3, Ziel 2, Hilfsturm 1. Bewege oberste Scheibe von 3 nach 1. Groesse: 0, Ausgangsturm 2, Ziel 1, Hilfsturm 3. Bewege oberste Scheibe von 2 nach 3. Groesse: 2, Ausgangsturm 1, Ziel 3, Hilfsturm 2. Groesse: 1, Ausgangsturm 1, Ziel 2, Hilfsturm 3. Groesse: 0, Ausgangsturm 1, Ziel 3, Hilfsturm 2. Bewege oberste Scheibe von 1 nach 2. Groesse: 0, Ausgangsturm 3, Ziel 2, Hilfsturm 1. Bewege oberste Scheibe von 1 nach 3. Groesse: 1, Ausgangsturm 2, Ziel 3, Hilfsturm 1. Groesse: 0, Ausgangsturm 2, Ziel 1, Hilfsturm 3. Bewege oberste Scheibe von 2 nach 3. Groesse: 0, Ausgangsturm 1, Ziel 3, Hilfsturm 2.
Kryptologie
Übung C-1: Einige Begriffe der Kryptologie
Erläutern Sie bitte die nachstehend aufgeführten grundlegenden Begriffe der Kryptologie.
- Plain Text und Cipher Text
- Symmetrisches Kryptosystem
- Transpositionsalgorithmus
- Substitutionsalgorithmus
- ROT13
- monoalphabetisch
Übung C-2: Ein Cipher-Text
Finden Sie bitte (evtl. mit einem kleinen C-Programm) heraus, wie der Cipher-Text "IVRYYRVPUGZNPUGRFVUARANHPUFCNFF" unverschlüsselt heißt.
Übung C-3: Buchstabenhäufigkeit
Schreiben Sie ein C (oder C++) Programm, mit dem Sie die Häufigkeitsverteilung der Buchstaben a bis z (ohne Berücksichtigung von Groß- und Kleinschreibung sowie der Umlaute) aus dem Beispieltext krypto1.txt ermitteln.
Vergleichen Sie Ihr Ergebnis bitte mit der nachstehenden Tabelle, die dem Buch von Beutelspacher (sh. Literaturverzeichnis des Informatik-Skriptums) entnommen wurde.
Buchstabe Häufigkeit % Buchstabe Häufigkeit % a
6,51
n
9,78
b
1,89
o
2,51
c
3,06
p
0,79
d
5,08
q
0,02
e
17,40
r
7,00
f
1,66
s
7,27
g
3,01
t
6,15
h
4,76
u
4,35
i
7,55
v
0,67
j
0,27
w
1,89
k
1,21
x
0,03
l
3,44
y
0,04
m
2,53
z
1,13
Finden Sie über eine Buchstabenverteilungsanalyse heraus, mit welcher Transposition der Text in der Datei cipher.txt codiert wurde. Stellen Sie den Klartext dieser Datei wieder her (mit einem C-Programm).
Übung C-4: Monoalphabetische Chiffrierung
Auch in der Datei cipher2.txt liegt ein verschlüsselter Text vor, der auf einer einfachen monoalphabetischen Chiffrierung beruht. Nutzen Sie wieder die statistische Verteilung der Buchstaben und ein C-Programm, um den Klartext zu ermitteln.
Übung C-5: Das Prinzip von Kerckhoffs
Was versteht man unter dem Prinzip von Kerckhoffs?
Übung C-6: Multiplikative Chiffren
Wir betrachten die folgende Vorschrift der Multiplikation über dem Alphabet { a, b, c, ..., z }. Dabei entspricht a der Zahl 0, b der Zahl 1 usw. bis z = 25, da wir modulo 26 rechnen. Ist n eine natürliche Zahl, so ist das n-fache eines Buchstabens mit dem Wert w gerade nw mod 26. Das 7-fache von c (=2) ist also 14, das 7-fache von z (=25) also 7 x 25 = 175 mod 26 = 19. (Dies könnte auch einfacher gerechnet werden: 25 = -1 mod 26, also ist das 7-fache davon -7 mod 26 = 19.)
Geben Sie bitte an, für welche Werte s (zwischen 1 und 26) das Verschlüsseln eines Zeichens mit dem s-fachen wieder eine Chiffre, eine Codierung ergibt. (Hierfür ist wichtig, dass jeder Buchstabe wieder eindeutig einem Buchstaben zugeordnet wird, so dass die Dechiffrierung ohne Mehrdeutigkeit möglich ist.)
Implementieren Sie anschließend eine solche multiplikative Chiffre in einem kleinen C- oder C++-Programm.
Anmerkung: Als [s,t]-Chiffre wird die Chiffre [sofern es eine ist!] bezeichnet, die einem Klartext-Zeichen c das Ciphertext-Zeichen s*c + t (modulo 26) zuordnet. Die oben erwaehnten Chiffren sind in dieser Notation [s,0]-Chiffren, da keine lineare Verschiebung stattfindet.
Übung C-7: Polyalphabetische Chiffren - Vigenère-Quadrat
- Erläutern Sie das Prinzip des Vigenère-Quadrats.
- Verschlüsseln Sie bitte den Text "einwundervollerwinterstehtbevor" mit dem Schlüsselbegriff
"GUMMERSBACH". (Zur Erinnerung: wir wollten als Klartext der Einfachheit halber nur Kleinbuchstaben
verwenden, daher ist dieser Text ohne Leerzeichen.)
Zur Kontrolle: Sie müssten auf den Cipher Text "KCZIYEVFRXVRFQDAZFUETZZYTFFVNPR" kommen. - Decodieren Sie "XMIJHUIFRAQKRLIZPLNJGYGHWRIIE". Der Schlüsselbegriff lautet hierbei "BERCHTESGADEN".
Übung C-8: Kasiski-Test
Erläutern Sie die Vorgehensweise beim Kasiski-Test.
Welche Schlüssellänge(n) ist/sind bei dem Cipher Text "WVQBIJAUGTKXEVTWMVOWAGIJAPEYVLAPNNJ" wahrscheinlich?
Versuchen Sie mit dieser Vermutung den obigen Text zu decodieren, wenn einer der nachstehenden Begriffe als Schlüssel eingesetzt wurde.JAGUAR ALLIGATOR MERCEDES DINOSAURIERKNOCHEN EICHENLAUB WINTER REGENTONNE UHU ILTIS KAULQUAPPE BIB LUCIFER MITTWOCH DONNERSTAG FREITAG FHDW ALRAUNE
Übung C-9: Eine monoalphabetische Chiffre
Auch in der Datei cipher2.txt liegt ein verschlüsselter Text vor, der auf einer einfachen monoalphabetischen Chiffrierung beruht. Nutzen Sie wieder die statistische Verteilung der Buchstaben und ein C-Programm, um den Klartext zu ermitteln.
Übung C-10: One Time Pad
Was versteht man unter dem One Time Pad?
Was macht dieses Verfahren interessant?
Wofür kann dieses Verfahren eingesetzt werden, wofür ist es eher weniger geeignet?Übung C-11: Lineare Schieberegister
- Jemand behauptet, die Folge 00001000 wäre von einem linearen Schieberegister der Länge 4 erzeugt worden. - Kommentieren Sie diese Behauptung bitte.
- Gibt es ein lineares Schieberegister der Länge 4, das eine Outputfolge der Periode 16 besitzt?
- Betrachten Sie das lineare Schieberegister der Länge 5, bei dem die letzten beiden Zellen additiv modulo 2 auf die erste Zelle rückkoppeln. - Welche Periodenlängen haben die Startfolgen 11011 , 01110 und 10101 ?
Übung C-12: Lineare Schieberegister
Schreiben Sie ein C-Programm, das ein lineares Schieberegister der Länge 8 umsetzt; dabei sollen die letzten beiden Zellen additiv (modulo 2) auf die erste Zelle rückkoppeln.
Testen Sie das Schieberegister und ermitteln Sie die maximal auftretende Periodenlänge.
Wie lautet der Output (über eine Länge von 20 Bits) zur Startbelegung 00100100?