Prüfungsfrage I Fach Informatik Thema "Algorithmen" im Schuljahr 2009/10

Letztmalig dran rumgefummelt: 11.05.10 17:19:36

	Algorithmus - (algorithm) Auch Rechenanweisung. Eine endliche Menge von eindeutig festgelegten Regeln zur Lösung eines Problems durch eine endliche Menge von Einzelschritten. Ein Algorithmus ist demnach eine Beschreibung der Methode, ein Problem oder eine Aufgabe zu lösen. Er besteht aus einer Folge von Einzelschritten, deren richtige Abarbeitung die gegebene Aufgabe erfüllt. Diese Abarbeitung bezeichnet man als einen Prozess. In der Mathematik werden solche Algorithmen als Voraussetzung für die Lösung von berechenbaren, entscheidbaren und aufzählbaren Problemen verwendet. Jedoch ist der Begriff des Algorithmus übertragbar auf sämtliche anderen Bereiche, in denen ebenfalls nach gegebenen Regeln vorgegangen wird. Konstruiert man eine Apparatur, die einen Prozess nach einem Algorithmus durchführen kann, so spricht man von einem Prozessor. Typische Prozessoren sind Automaten, zu denen Computer zu rechnen sind. Computer erhalten ihre Algorithmen in Form von Programmen, die mit Hilfe von Programmiersprachen formuliert worden sind Programme sind also Algorithmen.
	1. Das Thema 2. Die Aufgabe 3. Hilfsmittel 4. Erwartungsbild zum Teil I 5. Zusatzfragen 6. Referenzbild der Zusatzfragen 7. Verweisstruktur
	Informatikprüfung Aufgabe I SJ 2009/10 - Thema Algorithmen - das Logo inhaltlich auf korrektem Stand - evtl. partiell unvollständig ;-) Wissen für Fortgeschrittene der Informatik

1. Das Thema

Algorithmen werden vielfach gleichgesetzt mit technischen oder mathematisch beschreibbaren Abfolgen nach dem Schema: erstens, zweitens drittens ... - dem ist aber nicht so! Algorithmen in Praxi hinterfragen nämlich nach dem Erhalt des Ergebnisses aus Schritt eins dessen Zustand! Und dieser hat das ganz wesentlichen Einfluss auf den weiteren Verlauf.

In neuerer Zeit hat man entdeckt, dass es bei der Gestaltung von Computerprogrammen praktisch nur drei Grundformen von Algorithmen-Mustern gibt, die Reihung (Sequenz), die Auswahl (Selektion) und die Wiederholung (lteration). Das hat zu einer völligen Umstellung der Programmiertechnik (Programmierung, strukturierte) geführt, die erhebliche Verbesserungen hinsichtlich der Übersichtlichkeit, der Änderungsfreundlichkeit und der Benutzerfreundlichkeit bewirkte. Diese Erkenntnisse haben sich bis in die Konstruktion neuer Sprachen ausgewirkt (z. B. bei PASCAL). Besondere Probleme im Zusammenhang von Algorithmen bestehen in ihrer Berechenbarkeit, ihrer Komplexität und ihrer Korrektheit. Wichtige theoretische Vorarbeiten für die Entwicklung von Computern wurden bereits durch die Untersuchungen von Turing u. a. über A. geleistet. Der Name Algorithmus leitet sich von dem Namen des iranischen Mathematikers und Astronomen Mohammed ibn Musa al-Chwarismi ab, der um 820 u. a. Lehrbücher über Algebra schrieb. Diese Bücher wurden im Mittelalter auch ins Lateinische übersetzt und hatten große Verbreitung sowohl im arabischen Kulturkreis als auch in Europa.

2. Die Aufgabe

	Computer sind aus einer Vielzahl von Teilen aufgebaut - wir nennen sie Hardware. Beschreibe die technische Funktion der folgenden PC-Bausteine kurz - der Link auf die angegebene Seite kann dabei nützlich sein:
	Fragekomplex I Teil I Lehrplanbezug Anforderungsniveau Arbeitszeit Das nachfolgend angegebene ARRAY von Integerwerten soll aufsteigend sortiert werden! Beschreiben Sie verbal dazu mindestens 3 unterschiedliche mögliche Verfahren - verwenden Sie die unten angegebene Abbildung Programmieren Sie einen der ausgewählten Algorithmen für mindestens 200 Feldelemente und beschreiben Sie dessen Kernprozedur gegebenes Datenfeld ... verwenden Sie dazu ein Ihnen geeignet erscheinendes Programm Kennen von Grenzen der Berechenbarkeit Beherrschen der Implementierung ausgewählter Algorithmen in einer Programmierumgebung II bis III Vorbereitung maximal 20 Minuten Referieren maximal 10 Minuten
	5 Punkte
	Fragekomplex I Teil II Lehrplanbezug Anforderungsniveau Arbeitszeit Nehmen Sie Stellung zu der Aussage "Ein Algorithmus ist das sinnvolle Durcheinander von Sequenzen, Schleifen und Verzweigungen - weiter nichts. Aber diese können sehr aufwändig sein!“ – machen Sie dies an Ihrem Algorithmus deutlich!" Welche in Ihrem Algorithmus verwendeten Strukturen machen den rechentechnischen Aufwand aus, wenn der Algorithmus eine große Menge von Elementen sortieren muss? Nennen und beschreiben sie "mächtige" Probleme! Kryptologie im gesellschaftlichen Kontext Notwendigkeit und Missbrauch kryptographischer Verfahren II und III Vorbereitung maximal 10 Minuten Referieren maximal 5 Minuten
	3 Punkte

3. Hilfsmittel

	Hier verwendet der Schüler ein vorbereitetes Programm. Dieses muss ihm vertraut sein, da es ansonsten zu lange benötigen würde, sich in eine vorgegebene Datenstruktur einzudenken. Der vorhandene Algorithmus umfasst nachfolgend aufgeführte Problemstellung.
	eigenes Basisprogramm
	Struktogramm-Editoren

4. Erwartungsbild zum Teil I

	Hier nun kommt theoretisch die gesamte Palette der Algorithmen zum Tragen - insgesamt stehen mehr als zehn zur Auswahl, wenngleich sich der Schüler aus seiner Sicht mit hoher Wahrscheinlichkeit auf die bekanntesten beziehen wird. Leider sind dies selten die effizientesten.
	zu Fragekomplex Teil I Teil 1 - Thema Algorithmen Lehrplanbezug Anforderungsniveau Das nachfolgend angegebene ARRAY von Integerwerten soll aufsteigend sortiert werden! Beschreiben Sie verbal dazu mindestens 3 unterschiedliche mögliche Verfahren - verwenden Sie die unten angegebene Abbildung Programmieren Sie einen der ausgewählten Algorithmen für mindestens 200 Feldelemente und beschreiben Sie dessen Kernprozedur Kennen von Grenzen der Berechenbarkeit Beherrschen der Implementierung ausgewählter Algorithmen in einer Programmierumgebung II bis III
	Bubblesort Simplesort Selectionsort Insertionsort Sortieren mit Bubble-Sort Sortieren mit Simple-Sort Sortieren mit Selection-Sort Sortieren mit SInsertion-Sort Das Prinzip basiert darauf, dass systematisch alle Paare benachbarter Elemente miteinander verglichen werden. Ist ein Element größer als sein Nachfolger, so ist gegen das Ordnungsprinzip verstoßen und die beiden Elemente tauschen ihre Plätze. So wandern nach und nach die kleinen Elemente an den Anfang, die größeren hingegen an das Ende des Feldes. Nach hinreichend vielen solcher elementaren Vertauschungen haben schließlich alle Elemente ihren Platz in der richtigen Reihenfolge gefunden. Wir betrachten den ersten Durchlauf: Das nullte Element wird mit allen nachfolgenden Elementen verglichen. Immer dann, wenn sich ein kleineres als das augenblicklich nullte Element findet, tauschen beide Elemente ihren Platz. Nach einer Reihe von möglichen Vertauschungen ist am Ende des ersten Durchlaufs das kleinste Element an Position Null gerückt. Die zweite Runde verfährt nach dem selben Prinzip, kann jedoch das nullte Element außen vor lassen. Jeder nachfolgende Durchgang schiebt auf diese Weise den kleinsten Wert auf das Anfangselement des verbleibenden unsortierten Restfeldes. Nachdem alle Durchläufe stattgefunden haben, ist das Feld schließlich sortiert. Der Algorithmus ist ein naher Verwandter des Simplesort. Während Simplesort jedoch pausenlos das Minimum aktualisiert und somit zeitraubende Vertauschungen vornimmt, ist Selectionsort lediglich darauf bedacht, die Position des Minimums (min) zu bestimmen. Das kleinste Element des Restfeldes wird also zunächst nur ausgewählt (selektiert) und erst ganz am Ende des jeweiligen Durchlaufs an den Anfang des Restfeldes getauscht. Die Anzahl der Vertauschungen wird auf diese Weise reduziert und Selectionsort arbeitet dadurch deutlich effizienter als Simplesort. Insertionsort - ebenfalls ein elementarer Sortieralgorithmus - bedient sich der Methode »Sortieren durch Einfügen«. Der Index i wird beginnend mit 1 so lange erhöht, bis zwei benachbarte Elemente gegen das Ordnungsprinzip verstoßen, d.h. zahl[i]<zahl[i-1]. Dann wird zahl[i] in der Hilfsvariablen help zwischengespeichert. Nun rücken alle links von zahl[i] stehenden Elemente, die größer als help sind, um eine Position nach rechts, bis die richtige Stelle für help gefunden ist. help schließt die entstandene Lücke und es geht mit dem nächsten i weiter.
	Shellsort Quicksort Bucketsort   Sortieren mit Shell-Sort Sortieren mit Quick-Sort Sortieren mit Bucket-Sort   Der Sortieralgorithmus Shellsort (benannt nach D.L. Shell - 1959) basiert auf dem bereits besprochenen Insertionsort. Shellsort kümmert sich jedoch nicht von vornherein um alle Elemente des Feldes sondern setzt ein Raster an, so dass zunächst (z.B.) nur jedes 5. Element einbezogen wird. So werden die Elemente zahl[0,5,10,15,20] mittels Insertionsort vorsortiert. Danach rückt das Raster um eine Position nach rechts (zahl[1,6,11,16,21]), Insertionsort erledigt aufs Neue seine Arbeit, dann wieder eine Position nach rechts usw. Nach 5 derartigen Sortierzyklen ist das gesamte Feld grob vorsortiert. Nun wird der Rasterabstand (z.B.) auf 3 reduziert (zahl[0,3,6,9,12,15,18,21,24]), wodurch sich die Vorsortierung weiter verfeinert. Nach 3 derartigen Zyklen liegt schon ein recht gut sortiertes Feld vor. Da jetzt aber immer noch einige Elemente an der falschen Position stehen, muss das Raster auf jeden Fall im allerletzten Durchlauf den Wert 1 erhalten. Die Rasterabstände können als Integer-Konstanten in einem Array bereitgestellt oder aber auch (in Abhängigkeit von der Feldgröße) dynamisch generiert werden. Nur eine geschickte Festlegung der Rasterabstände garantiert letztendlich auch eine hohe Sortiergeschwindigkeit. Der Grundgedanke besteht zunächst darin, das Gesamtfeld in zwei Teilfelder zu zerlegen. Dies erfolgt durch Festlegen eines Trennelementes, das sich z.B. an der "Nahtstelle" der beiden Teilfelder befindet. Dieses Element wird als sogenanntes Pivot-Element (pivot = Drehpunkt, Drehachse) bezeichnet. Nun werden durch Vergleich mit dem Pivot-Element Vertauschungen derart vorgenommen, dass alle Elemente, die kleiner/gleich pivot sind, im linken Teilfeld und alle Elemente, die größer/gleich pivot sind, im rechten Teilfeld gesammelt werden. Haben auf diese Weise alle Elemente ihre Ordnungsposition in Bezug auf pivot gefunden, so wird das Verfahren im linken Teilfeld durch abermaliges Teilen und Tauschen, dann wiederum im linken Teilfeld durch Teilen und Tauschen u.s.w. fortgesetzt. Wenn es nichts mehr zu teilen gibt, wird der gleiche Algorithmus auf das nächstgrößere rechte Teilfeld angewandt u.s.w. ... In der Literatur findet sich diese Herangehensweise häufig unter der Bezeichnung "devide & conquer" (lat.: dividi et impera) - "Teile und Herrsche!". Gänzlich verschieden zu den bisher besprochenen Sortieralgorithmen arbeitet Bucketsort. Das Grundprinzip besteht darin, dass das Feld (Primärfeld) nicht in sich selbst sortiert sondern zwischenzeitlich auf ein zweites Feld (Sekundärfeld) abgebildet wird. Dabei werden die Elemente während des ersten Felddurchlaufs in Buckets (engl. Eimer, Behälter) einsortiert und anschließend während eines zweiten Durchlaufs wieder in das Ausgangsarray zurückgeschrieben. Bucketsort in seiner einfachsten Form könnte wie folgt aussehen.
	5 Punkte
	zu Fragekomplex Teil I Teil 2 - Thema Algorithmen Lehrplanbezug Anforderungsniveau Nehmen Sie Stellung zu der Aussage "Ein Algorithmus ist das sinnvolle Durcheinander von Sequenzen, Schleifen und Verzweigungen - weiter nichts. Aber diese können sehr aufwändig sein!“ – machen Sie dies an Ihrem Algorithmus deutlich!" Welche in Ihrem Algorithmus verwendeten Strukturen machen den rechentechnischen Aufwand aus, wenn der Algorithmus eine große Menge von Elementen sortieren muss? Beurteilen von Algorithmen bezüglich ihrer Effizienz Komplexität experimentelles Ermitteln und theoretischer Nachweis der Zeitkomplexität Beispiele für Algorithmen mit polynomialem Aufwand II
	Zeitkomplexität, Mächtigkeit, Aufwand alle Sortieralgorithmen nutzen mehr oder weniger tief geschachtelte Schleifen und verzweigen in Abhängigkeit des jeweiligen Ergebnisses oder eine Zwischenergebnisses Aufzeigen der möglichen Programmstrukturen sowie deren Verschachtelung
	Aufwand zur Lösung von Problemen durch Algorithmen auf Computern: Anzahl der Steueroperationen Anzahl von Vergleichsoperationen Anzahl der Tauschoperationen Anzahl von Suchvorgängen Beanspruchung von Hauptspeicher Auslagerung von Daten und Zugriff auf ausgelagerte Daten Mächtigkeit des Problems Aufwand muss messbar gemacht werden - also benötigen wir messbare Kriterien! In der Informatik: Zeit Speicherbedarf Auslagerungsdateien und andere Ressourcen Anzahl von Prozessoren und/oder Computern bei komplexen Problemen Nur Information für die Prüfungskommision - Zeitbestimmende Maße beim Computer sind: die Problemgröße n (die Mächtigkeit des Problems) Arbeit an typischen Operationen A (Additionen, Schleifensteuerungen, Vergleichen, Austauschen, Suchen) Aufwandsbezüge auf die Zeiteinheiten Vergleichen 1 ZE Lesen einer Variablen 1 ZE Speichern einer Variablen 1 ZE Lesen einer k-fach indizierten Variablen (k+1) ZE Addition 5 ZE Multiplikation 10 ZE Zyklussteuerung 5 ZE
	zu Fragekomplex Teil I Teil 3 - Thema Algorithmen Lehrplanbezug Anforderungsniveau Nennen und beschreiben Sie "mächtige" Probleme! Beurteilen von Algorithmen bezüglich ihrer Effizienz Komplexität experimentelles Ermitteln und theoretischer Nachweis der Zeitkomplexität Beispiele für Algorithmen mit polynomialem Aufwand II
	Rundreiseproblem: die kürzeste Trassierung aller Knoten ist gesucht befreundete Zahlen: die Summe der ganzzahligen Teiler (außer der Zahl selbst) zweier beteiligter Zahlen ergibt immer die "Gegenzahl" 220 & 284 Narzißzahlen: die Summer der mit der Stellenanzahl potenzierten Einzelstellen ergibt wieder die Ausgangszahl 153 Rucksackproblem: wie optimiere ich Menge und Wertigkeit einer großen Anzahl von zu transportierenden Gegenständen
	3 Punkte

5. Zusatzfragen

	Hier nun soll ein vollkommen neuer Bereich aufgerollt werden - wir begeben uns in Kryptologie, dem Schreiben im Verborgenen - also etwas zum Hauptthema vollkommen "Artfremden" in Bezug auf das Hauptthema.
	Fragekomplex III  - Thema Sicherheit von Informationen Lehrplanbezug Anforderungsniveau Dechiffrieren sie folgende  nach dem Playfair-Verfahren chiffrierte Nachricht und erklären Sie dazu umfassend das Verfahren, welches Sie auch in das Gesamtsystem kryptographischer Algorithmen einordnen wollen! Das Passwort lautet: KLONDIKE SEHZF MEAXO QHSQA GGWTU NSYSG WLYES AELBL QBOOF AEUQD KGAEK CBSW - (Hinweis: entfernen Sie beim Dechiffrieren die Füllzeichen!) Kryptologie im gesellschaftlichen Kontext Notwendigkeit und Missbrauch kryptographischer Verfahren II 4 Punkte
	Fragekomplex III - Thema Sicherheit von Informationen Lehrplanbezug Anforderungsniveau Ordnen Sie das Verfahren in das Gesamtsystem der Kryptologie ein! Kryptologie im gesellschaftlichen Kontext Notwendigkeit und Missbrauch kryptographischer Verfahren I 1 Punkte
	Fragekomplex III - Modelle der Informatik Lehrplanbezug Anforderungsniveau Rechnen Sie um! 123456D in Hexadezimal! Einblick gewinnen in die Systematik informatischer Modellierung Schrittfolge bei der Modellbildung Nutzen eines Modellierungswerkzeuges II 2 Punkte

6. Referenzbild der Zusatzfragen

	Zumindest für die erste Aufgabe ergeben sich faktisch keine Toleranzen - Interpretationsmöglichkeiten ergeben sich lediglich beim Buchstaben "J" da dieser ebenfalls mit "I" chiffriert worden ist. Ist aber im aktuellen Beispiel unkritisch, da nicht enthalten.
	Grundlage des Verfahrens: Zunächst wird der zu verschlüsselnde Text in Großbuchstaben umgewandelt Umlaute werden aufgelöst, Leerzeichen und Satzzeichen werden weggelassen der Klartext wird in Paaren aufgeschrieben. J wird zu I umgewandelt aufeinander folgende gleiche Buchstaben werden durch "X" oder ein anderes selten in Texten vorkommendes Zeichen ("Q" oder auch "Y") getrennt sollte als letztes ein einzelner Buchstabe stehen wird diesem auch noch ein "X" nachgestellt wir verwenden das Keyword "KLONDIKE" aus einem Schlüsselwort oder -satz wird ein permutiertes Alphabet mit 25 Buchstaben (ohne J) gewonnen. Dieses wird in 5er Reihen aufgeschrieben: Dabei wird das Schlüsselwort zeilenweise in eine 5 × 5 Matrix eingetragen, wobei bereits eingetragene Buchstaben übersprungen werden. Danach werden die zum kompletten Alphabet (ohne j) fehlenden Zeichen in alphabetischer Reihenfolge ergänzt. ich erhalte nachfolgendes Playfair-Quadrat: K L O N D I E A B C F G H M P Q R S T U V W X Y Z es werden immer Paare zu Paaren chiffriert stehen beide Buchstaben in der gleichen Zeile bzw. Spalte, werden jeweils die rechten bzw. unteren Nachbarn genommen stehen die Buchstaben am Rand wird oben bzw. links fortgesetzt (das Quadrat ist also links und rechts sowie oben und unten als verbunden anzunehmen) andernfalls ersetzt man den ersten Buchstaben durch den in der selben Zeile aber in der Spalte des zweiten liegenden der zweite Buchstabe wird durch den in der selben Zeile aber in der Spalte des ersten liegenden Buchstaben ersetzt das Klartextpaar bildet also die gegenüber liegenden Ecken eines Rechtecks, das Geheimtextpaar wird aus den jeweils benachbarten Ecken gebildet.
	Playfair Grundfunktion Kennwort eintragen Playfair-Quadrat generieren Ciphertext einsetzen Ciphertext einsetzen Plaintext von Füllzeichen befreien Leerzeichen einfügen
	RAPP hieß früher stottern, war eine Krankheit und heilbar
	K L O N D I E A B C F G H M P Q R S T U V W X Y Z
	SEHZF MEAXO QHSQA GGWTU NSYSG WLYES AELBL QBOOF AEUQD KGAEK CBSW ->RA HZF MEAXO QHSQA GGWTU NSYSG WLYES AELBL QBOOF AEUQD KGAEK CBSW -> RAPX F MEAXO QHSQA GGWTU NSYSG WLYES AELBL QBOOF AEUQD KGAEK CBSW -> RAPXP H   K L O N D I E A B C F G H M P Q R S T U V W X Y Z     K L O N D I E A B C F G H M P Q R S T U V W X Y Z     K L O N D I E A B C F G H M P Q R S T U V W X Y Z   EAXO QHSQA GGWTU NSYSG WLYES AELBL QBOOF AEUQD KGAEK CBSW -> RAPXP HIE XO QHSQA GGWTU NSYSG WLYES AELBL QBOOF AEUQD KGAEK CBSW -> RAPXP HIESX QHSQA GGWTU NSYSG WLYES AELBL QBOOF AEUQD KGAEK CBSW -> RAPXP HIESX SF   K L O N D I E A B C F G H M P Q R S T U V W X Y Z     K L O N D I E A B C F G H M P Q R S T U V W X Y Z     K L O N D I E A B C F G H M P Q R S T U V W X Y Z   SQA GGWTU NSYSG WLYES AELBL QBOOF AEUQD KGAEK CBSW -> RAPXP HIESX SFRU A GGWTU NSYSG WLYES AELBL QBOOF AEUQD KGAEK CBSW -> RAPXP HIESX SFRUE H GWTU NSYSG WLYES AELBL QBOOF AEUQD KGAEK CBSW -> RAPXP HIESX SFRUE HER   K L O N D I E A B C F G H M P Q R S T U V W X Y Z     K L O N D I E A B C F G H M P Q R S T U V W X Y Z     K L O N D I E A B C F G H M P Q R S T U V W X Y Z   TU NSYSG WLYES AELBL QBOOF AEUQD KGAEK CBSW -> RAPXP HIESX SFRUE HERST NSYSG WLYES AELBL QBOOF AEUQD KGAEK CBSW -> RAPXP HIESX SFRUE HERST OT YSG WLYES AELBL QBOOF AEUQD KGAEK CBSW ->RAPXP HIESX SFRUE HERST OTXT   K L O N D I E A B C F G H M P Q R S T U V W X Y Z     K L O N D I E A B C F G H M P Q R S T U V W X Y Z     K L O N D I E A B C F G H M P Q R S T U V W X Y Z   G WLYES AELBL QBOOF AEUQD KGAEK CBSW -> RAPXP HIESX SFRUE HERST OTXTE R LYES AELBL QBOOF AEUQD KGAEK CBSW -> RAPXP HIESX SFRUE HERST OTXTE RNW ES AELBL QBOOF AEUQD KGAEK CBSW -> RAPXP HIESX SFRUE HERST OTXTE RNWAR   K L O N D I E A B C F G H M P Q R S T U V W X Y Z     K L O N D I E A B C F G H M P Q R S T U V W X Y Z     K L O N D I E A B C F G H M P Q R S T U V W X Y Z   AELBL QBOOF AEUQD KGAEK CBSW -> RAPXP HIESX SFRUE HERST OTXTE RNWAR EI LBL QBOOF AEUQD KGAEK CBSW -> RAPXP HIESX SFRUE HERST OTXTE RNWAR EINE L QBOOF AEUQD KGAEK CBSW -> RAPXP HIESX SFRUE HERST OTXTE RNWAR EINEK R   K L O N D I E A B C F G H M P Q R S T U V W X Y Z     K L O N D I E A B C F G H M P Q R S T U V W X Y Z     K L O N D I E A B C F G H M P Q R S T U V W X Y Z   BOOF AEUQD KGAEK CBSW -> RAPXP HIESX SFRUE HERST OTXTE RNWAR EINEK RAN OF AEUQD KGAEK CBSW -> RAPXP HIESX SFRUE HERST OTXTE RNWAR EINEK RANKH AEUQD KGAEK CBSW -> RAPXP HIESX SFRUE HERST OTXTE RNWAR EINEK RANKH EI   K L O N D I E A B C F G H M P Q R S T U V W X Y Z     K L O N D I E A B C F G H M P Q R S T U V W X Y Z     K L O N D I E A B C F G H M P Q R S T U V W X Y Z   UQD KGAEK CBSW -> RAPXP HIESX SFRUE HERST OTXTE RNWAR EINEK RANKH EITU D KGAEK CBSW -> RAPXP HIESX SFRUE HERST OTXTE RNWAR EINEK RANKH EITUN D GAEK CBSW -> RAPXP HIESX SFRUE HERST OTXTE RNWAR EINEK RANKH EITUN DHE   K L O N D I E A B C F G H M P Q R S T U V W X Y Z     K L O N D I E A B C F G H M P Q R S T U V W X Y Z     K L O N D I E A B C F G H M P Q R S T U V W X Y Z   EK CBSW -> RAPXP HIESX SFRUE HERST OTXTE RNWAR EINEK RANKH EITUN DHEIL CBSW -> RAPXP HIESX SFRUE HERST OTXTE RNWAR EINEK RANKH EITUN DHEIL BA SW -> RAPXP HIESX SFRUE HERST OTXTE RNWAR EINEK RANKH EITUN DHEIL BARX   K L O N D I E A B C F G H M P Q R S T U V W X Y Z     K L O N D I E A B C F G H M P Q R S T U V W X Y Z     K L O N D I E A B C F G H M P Q R S T U V W X Y Z
	RAPXP HIESX SFRUE HERST OTXTE RNWAR EINEK RANKH EITUN DHEIL BARX Füllzeichen entfernen und Leerzeichen einfügen
	RAPP HIESS FRUEHER STOTTERN WAR EINE KRANKHEIT UND HEILBAR
	4 Punkte Zeitkalkulation: ca. 8 Minuten
	Ordnen Sie das Verfahren in das Gesamtsystem der Kryptologie ein!
	Allgemeines Modell der Kryptologie Allgemeines Modell der Kryptologie der PLAYFAIR-Chiffre ist ein symmetrischer polyalphabetischer Substitutionschiffre, wobei auch noch Umordnungen der Zeichen vorgenommen werden. Durch das fehlende Zeichen "J" ist er nicht eindeutig - er muss interpretiert werden!
	1 Punkt Zeitkalkulation: ca. 2 Minuten
	Rechnen Sie um! 123456D in Hexadezimal!
	Grundoperation Ergebnis Rest 123456 : 16 = 7716 also 7716 Rest 0 7716 : 16 = 482,25 also 482 Rest 4 482 : 16 = 30,125 also 30 Rest 2 30 : 16 = 1,875 also 1 Rest E 1 : 16 = 0,0625 also 0 Rest 1 1E240H
	das Verfahren besteht in einer fortlaufenden ganzzahligen Division mit Rest durch 16 bis 0 als Ergebnis steht der entstehende Rest wird hexadezimal notiert und rückwärts eingetragen
	2 Punkte Zeitkalkulation: ca. 5 Minuten

7. Verweisstruktur

	Anders wird in diesem Block lediglich das Ausgangsverfahren für die Chiffrierung gehandhabt - es wird eben Morsecode verwendet, welcher in sich POLYBIUS-Code birgt. Erst wenn diese Codes ausgelesen sind, geht's ans eigentliche Dechiffrieren der Nachricht.
	Algorithmen Algorithmentheorie Probleme & Problemlösungsverfahren Komplexität, Mächtigkeit und Aufwand die Komplexität eines Problems & Komplexitätsklassen Grundalgorithmen Muhammad ibn Musa, Abu Dscha'far al-Kwarizmi NP-vollständige sowie NP-schwere Probleme Worst-Case-Denken
	Kryptologische Verfahren CÄSAR-Chiffrier-, Dechiffrier- und Knackprogramme Playfair-Chiffre Codewandler   Flaggensignale Morse-Code Polybius-Code Chappé-Semaphore

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost am 19. April 2010 um 14.22 Uhr