Binärbäume

Besten Spielzüge erkennen

• Zwei Spieler

• Zugrecht ist abwechselnd

• Alle möglichen Spielzüge müssen beiden Spielern jederzeit bekannt sein

• Nullsummenspiel -> Summe der Gewinne und Verluste auf beiden Seiten gleich

• Keine Zufallszüge -> Würfel

Objekte des Anwendungsbereiches

Beziehungen zwischen den Objekten (Entfernung, Zeit)

Knoten: Städte, Dörfer

Kanten: Autobahnen, Straßen

Kanten haben Gewicht in Abhängigkeit ihrer Eigenschaften

Kanten haben eine Richtung, abhängig ihrer Eigenschaften

• hat eine Menge von Knoten und Kanten

• Knoten sind mit Kanten verbunden

  • Knoten können auch keine Kanten haben, Punkt dann unerreichabar, dennoch ein Graph

• besten Zug bestimmen, indem bei einem 2-Spieler Spiel ein Spielbaum aufgestellt wird

• Nacheinander werden Züge ausgespielt

  • Max Startpieler, Min Gegenspieler

• Max= Maximale Wertung

• Min= minimale Wertung

• Ermittelung durch besten Zug, wer gewinnt oder ob perfektes Spiel (unentschieden)

• Züge, welche für Bestimmung der Endsituaiton unbedeutend sind, werden nicht miterstellt

• möglichst wenige Knoten werden untersucht

• wenn noch wenige Zugmöglichkeiten pro Spielsituation existieren, weil bspw. nur noch wenige Spielsteine auf dem Spielfeld sind, kann die Suchtiefe erhöht werden

Wenn sich die Zahlenwerte an einer Stelle des Suchbaums von Ebene zu Ebene zu stark ändern, kann die Suchtiefe lokal erhöhrt werden

Speichern Spielsituationen und deren Bewertungen, um nicht immer den gesamten Spielbaum durchsuchen zu müssen

• größe eines Spielbaumes in voller Breite und Tiefe

  • Alle Spielsituationen, auch welche nicht möglich sind (z.b. Ende des Spiels)

• Größe eines Spielbaumes mit Abzug der doppelten Spielsituationen, durch Drehungen oder Spiegelungen und auch nicht erreichbaren Situationen, wie das Spielende

• Der Baum wird “Schicht für Schicht” erstellt und jeder Nachfolge eines Blatts wird gespeichert

• Bewertung von voll aufgestellten Spielbaum und deren Ausgangssituation (MinMax-Verfahren)

• Spielbaum wird von links nach rechts aufgestellt

• Bewertung -> es muss nicht der komplette Spielbaum aufgestellt werden

• Bei perfektem Spiel beider Spieler

• Teile des Baumes “gepruned”, welche für endgültige Bewertung keinen Unterschied machen

• Von Profis des jeweiligen Spiels erstellte Bewertung für eine Spielsituation

• Für manche Spiele ist der Spielbaum zu groß (Schach)

• abwägen wie gut eine Spielsituation ist -> Nützlichkeit u. Effektivität eines Spielbaumes

• Spielzuganalyse so gut wie Feldbewertungsfunktion

• Verbesserung des MinMax

Wissenschahft der verborgenen Speicherung oder Übermittlung von Informationen

• Ableitung: Stegano (bedeckt), Graphieren (Schreiben)

• Aus der Zeit seit 450 V. Chr

• Einfach zu knacken

• Nicht erkennbare Einbettung von Nachrichten in digitale inhalte -> Bilder, Audio

• Strategie: LSB (Last Significant Bit) -> Byte wird an letzter Stelle verändert

  • ändert kaum etwas, lässt Text verstecken

    • Finden nur durch genaue Angabe, wo der Text sich befindet

Wissenschaft vom Entwurf, Anwendung und der Analyse von Kryptografischen Verfahren

Verfahren zur Ver- und entschlüsselung von Nachrichten

Analyse der Verfahren in bezug auf Sicherheit

• Vertraulichkeit: Können dritte die Nachricht lesen

• Integrität: wurde die nachricht nach Absenden verändert?

• Authenzität: Identifikation des Absenders

• Verbindlichkeit: Sender darf nicht in der Lage sein, Nachricht abzustreiten

• Selber Schlüssel zum Ver- und entschlüsseln

• Reihenfolge der Zeichen verändert, Zeichen selbst bleiben erhalten

• Skytalle

  • umwickeln eines Papierstreifens um eine Rolle

  • Gleich große Rolle lässt Nachricht entschlüsseln

• Ersetzungsregel pro Zeichen gleich -> Reihenfolge ändert sich

• Zeichen werden durch andere ersetzt (substituiert)

• Häufigkeitsanalyse

• Anzahl der möglichen Schlüssel klein genug, so lässt sich mit ausprobieren der Schlüssel herausfinden (Brute-Force-Angriff)

• monalphabetische Verschlüsselungen unsicher, da Buchstaben nur ersetzt werden aber die gleiche Bedeutung haben

• Cäsar: Verschieben des Alphabets -> Schlüssel=Verschiebung -> 25 Ersetzungsalphabete

  • Systematisches Ausprobieren

• Selber Schlüssel zum Ver- und entschlüsseln

Jeder Buchstabe des KT Alphabets wird mit einem anderen GT Alphabet verschlüsselt

• Buchstaben eines Schlüsselwortes legen Alphabet fest

• Häufigkeitsanalyse unbrauchbar

• Vigenere

Geheimtext Alphabet wird nur aus einem Alphabet zusammengesetzt

BSP: Cäsar mit Schlüsselwort

Zeichen Verändern ihre Bedeutung bzw ersetzt sie durch andere

Zeichen behalten ihre Bedeutung, doch ändern ihre Anordnung

• Schlüssel (Zahl 0 -25) gibt Verschiebung des Ersetzungsalphabet an, Klartext kann verschlüsselt werden

• Empfänger muss denselben Schlüssel haben

Schlüsselwort wird an den Anfang des Ersetzungsalphabet geschrieben, Leerzeichen sowie doppelte Buchstaben werden entfernt

• Nicht einzelne Buchstaben verschlüsselt, sondern ganze Buchstabenblöcke

• siehe Lernzettel

• polyalphabetische Verschlüsselung

• Buchstabe kann mit unterschiedlichen anderen Buchstaben verschlüsselt werden

• beruhgt auf der Cäsar Verschiebung, alle 26 möglichen GT Alphabete verwendent, nach einer Regel abwechselnd

• alle GT Alphabete ergeben (untereinander geschrieben) das Vigenere Quadrat

• Sender und Empfänger einigen sich auf ein SW -> nacheinander unter den KT geschrieben

  • mit hilfe des Vigenere Quadrat den GT-Buchstaben finden

• Polyalphabetisches Verfahren / Substitutionsverfahren

• Schlüssel genau so lang, wie der zu vrerschlüsselnde Text

• Kann mit Vigenere und Additionsverfahren verschlüsselt werden

• GT= KT + S

• KT= GT - S

• S= GT - KT

• 1. Richtig angewendet kann das one time pad nicht geknackt werden

• 2. Ausspähen des Schlüssels

  • Schlüssel nicht ausreichend genug aufbewahrt oder sicher gneug übertragen wird

• 3. Mehrfach Verwendung des selben Schlüssels

  • Bei wissen von beiden GT

• 4. Nicht zufällig genug ausgewählter Schlüssel

• einen öffentlichen und einen privaten Schlüssel

• Asymetrisches Verschlüsselungsverfahren -> nicht der gleiche Schlüssel zum ver- und entschlüsseln

• Entschlüsseln nur mit privatem Schlüssel