Zusammenfassung des Grundkurs Informatik Schuljahr 2011/12 ... · Klassische Kryptographie Caesar Vigenere One-Time-Pad DirkBongartz Zusammenfassung GKInformatik2011–2013. Public-Key-Kryptographie

Zusammenfassung des Grundkurs InformatikSchuljahr 2011/12 – Schuljahr 2012/13

Dirk Bongartz

GK Q2/13 Informatik,St. Wolfhelm Gymnasium Schwalmtal

Marz 2013

1 Objektorientierte Programmierung (allgemein)

2 Datenstrukturen und Algorithmen (Q1/12.1)

3 Automaten und formale Sprachen (Q1/12.2)

4 Kryptographie (Q1/12.2)

5 Datenbanken (Q2/13.1)

6 Netzwerkprogrammierung (Q2/13.1)

7 Turingmaschinen und Berechenbarkeit (Q2/13.2)

Dirk Bongartz Zusammenfassung GK Informatik 2011–2013

1 Objektorientierte Programmierung (allgemein)

2 Datenstrukturen und Algorithmen (Q1/12.1)

3 Automaten und formale Sprachen (Q1/12.2)

4 Kryptographie (Q1/12.2)

5 Datenbanken (Q2/13.1)

6 Netzwerkprogrammierung (Q2/13.1)

7 Turingmaschinen und Berechenbarkeit (Q2/13.2)

8 Mundliches Abitur


GrundlagenSoftware-Lebenszyklus — nicht explizit

Vorgaben

Klasse, Objekt

Attribut, Konstruktor, Methode (Anfrage/Auftrag)

Geheimnisprinzip

UML-Klassendiagramme (Entwurfs- undImplementierungsdiagramme

(gerichtete) Assoziation mit MultiplizitatVererbung

Vererbungskonzept

Abstrakte KlassenPolymorphie


GrundlagenSoftware-Lebenszyklus — nicht explizit

Phasenmodell

Problem . . . Problemanalyse

→ Andorderungsdefinition . . . Entwurf

→ Spezifikation . . . Implementierung

→ dokumentiertes Programm . . . Funktionsuberprufung

→ modifiziertes Programm . . . Installation/Abnahme

→ anforderungsgerechtes Produkt Wartung

→ Verschrottung


DatenstrukturenAlgorithmen

Vorgaben

Lineare Strukturen

Schlange und Stapel(Anwendung und Implementierung der Standardoperationen)Lineare Liste(Anwendung der Standardoperationen)Such- und Sortieralgorithmen fur Felder und Listen

SuchenSortieren durch direktes Einfugen (Insertionsort)

Baumstrukturen

Binarbaum (Anwendung der Standardoperationen,Traversierungsalgorithmen)Binarer Suchbaum (Anwendung der Standardoperationen)



Arrays und Listen

Arrays: statische Große, direkter Zugriff

Einfach verkettete Liste

Implementierung: Element, Liste, (Object)Implementierung: Suchen, Anhangen, Loschen, ...

Erweiterung: Doppelt verkettete Liste



Abstrakte Datentypen — ADT

Stapel (Stack)

LIFO-SpeicherOperationen: push, pop, top, isEmptyImplementierung(Anwendung: Klausurenstapel)→ 1. Klausur GK Q1/12 Informatik

Schlange (Queue)

FIFO-SpeicherOperationen: dequeue, enqueue, first, isEmptyImplementierung (direkt und als Unterklasse von List)Anwendung: Patientenwarteschlange



Graphen — nicht explizit

Definition aus Knoten und Kanten, G = (V,E)

Beispiele:

Konigsberger Bruckenproblem (Eulerkreis-Problem)Haus vom Nikolaus

Reprasentationsformen: Adjazenzmatrix, Adjazenzliste



Baume, Binarbaume und Suchbaume

Baum: zusammenhangender, kreisfreier, ungerichteter Graph

Binarbaum: Jeder Knoten hat maximal 2 Sohne.

Verfahren zum Durchlauf von Binarbaumen (Traversierung)Rekursiv: Inorder, Preorder, PostorderTermbaume: Beziehung zu Infix-, Postfix-, PrefixnotationDatenkompression: Huffman-Kodierung

Binare Suchbaume: Suchbaumeigenschaft

Operationen: Einfugen, Loschen, Suchenrekursive Implementierung mit abstrakten Klassen



Effizienzmessung/Laufzeitmessung

Bestimmung der (ungefahren) Anzahl der elementaren Operationendes Programms abhangig von der Große der Eingabe.

nur Großenordnung interessant → keine Konstanten,Koeffizienten, etc.

Landau-Symbole (Oh-Notation) f : N → R+

O(g(n)) := f(n) | es gibt ein c ≥ 0 und ein n0 ∈ N,so dass fur alle n ≥ n0 gilt: f(n) ≤ c · g(n)

Ω(g(n)) := f(n) | es gibt ein c > 0 und ein n0 ∈ N,so dass fur alle n ≥ n0 gilt: f(n) ≥ c · g(n)

Θ(g(n)) := O(g(n)) ∩ Ω(g(n)).

Messung der Laufzeit bei Listen-Operationen,Stack-Operationen, Baumdurchlaufen, Sortieralgorithmen, etc.



Konzept: Rekursion

binare Suche

Fakultat, Fibonacci-Folge

Euklidischer Algorithmus zur Berechnung des ggT

Pythagoras-Baum

Rekursiver Aufbau von Baumen (vgl. 2. Klausur GK Q2/12)

Turme von Hanoi



Konzept: Teile und Herrsche

1 Aufteilen eines Problems in Teilprobleme

2 Losen der Teilprobleme (rekursiv)

3 Zusammenfugung der Losungen der Teilproblem zur Losungdes Gesamtproblems

Beispiele:

Binare Suche — Herrsche Schritt entfallt

Quicksort

Mergesort



Konzept: Dynamische Programmierung

Bottom-Up-Berechnung der Fibonacci-Zahlen

CYK-Algorithmus

Alignment zweier Strings



Sortieralgorithmen

Selectionsort

Bubblesort

Insertionsort

Quicksort

Mergesort


Endliche AutomatenGrammatiken

Vorgaben

Modellieren kontextbezogener Problemstellungen alsdeterministische endliche Automaten

Darstellung von deterministischen endlichen Automaten alsGraph und als Tabelle

Formale Sprachen: Regulare Sprachen und ihre Grammatiken



Deterministische endliche Automaten (DEA)

Definition M = (Q,Σ, δ, q0, F ), Sprache des Automaten

formale und graphische Darstellung

Pattern-Matching-Automat

Konstruktion von Automaten fur verschiedene Sprachen

L = anbn | n ∈ N ist nicht durch einen DEA erkennbar(indirekter Beweis)

Abschluss unter Schnitt, Vereinigung, Differenz(Produktautomat)



Nicht-deterministische endliche Automaten (NEA)

Definition: wie DEA – allerdings Ubergangsrelation

statt linearer Berechnung (DEA), Berechnungsbaum

Umwandlung in DEA durch Potenzmengenkonstruktion



Grammatiken

Definition G = (N,T, P, S), Nichtterminalalphabet,Terminalalphabet, Produktionsregeln, Startsymbol

Einschrankungen zu den Produktionsregeln →Chomsky-Hierarchie

Typ-0-Grammatiken: keine Einschrankungen (entsprechen TM)Typ-1-Grammatiken: rechte Regelseite ist nicht kurzer als linke(kontextsensitive Sprachen, entsprechen linear beschrankten,nichtdeterm. TM)Typ-2-Grammatiken: linke Regelseite nur Nichtterminal(kontextfreie Sprachen, entsprechen Kellerautomaten)Typ-3-Grammatiken: rechte Regelseite enthalt maximal einNichtterminal (regulare Sprachen, entsprechen endlichenAutomaten)rechtsregular A → bC und D → e

linksregular A → Bc und D → e



Grammatiken und endliche Automaten

DEA → Typ-3-Grammatik

Typ-3-Grammatik → NEA



Erganzungen

Kellerautomaten

Wortproblem fur kontextfreie Sprachen und CYK-Algorithmus


Modellierung

Vorgaben

Modellieren kontextbezogener Problemstellungen alsDatenbanken mit dem Entity-Relationship-Modell

Normalisierung: Uberfuhrung einer Datenbank in die 1. bis 3.Normalform

Relationenalgebra (Selektion, Projektion, Vereinigung,Differenz, kartesisches Produkt, Umbenennung, Join)

SQL-Abfragen uber eine und mehrere verknupfte Tabellen

Datenschutzaspekte


Modellierung

Entity-Relationship-Diagramme

Entities: Objekte der Datenbank

Relationships: Beziehungen zwischen Entities

Kardinalitat: 1:1, 1:n, n:m

Attribute: Naherer Beschreibung von Entities undRelationships

zusammengesetzte Attribute: z.B. PLZ und Ort als Adressemehrwertige Attribute: z.B. mehrere Buchautoren

IS-A-Beziehung: Spezialisierung/Generalisierung im Sinneeiner Vererbung


Modellierung

Relationale Datenbanken

Grundlegendes Element: Relationen/Tabellen

Ubersetzung von ER-Diagrammen in Relationen


Modellierung

Normalisierung

Update-Anomalien

Einfuge-AnomalieLosch-AnomalieAnderungs-Anomalie

Definition: Funktionale Abhangigkeit

Normalformen1 1. Normalform: alle Attribute sind atomar (nicht

zusammengesetzt, nicht mehrdeutig)2 2. Normalform: 1. NF und jedes Nichtschlusselattribut ist nur

von der gesamten Schlusselmenge aber nicht von einem Teilfunktional abhangig.

3 3. Normalform: 2. NF und keine transitive Abhangigkeit einesNichtschlusselattributs vom Schlussel.

Erzeugung von Normalformen → Dekomposition in mehrereTabellen


Modellierung

Relationale Algebra

Selektion: S[B]R = r | r ∈ R ∧B(r)

Projektion: P [L]R = r(L) | r(L) ∈ R

Equi Join:R1[AΘB]R2 = r1⊕r2 | r1 ∈ R1∧r2 ∈ R2∧A(r1) = B(r2)


Modellierung

SQL — Anfragesprache

SELECT AttributlisteFROM RelationenWHERE Bedingungen


Vorgaben

Modellieren und implementieren kontextbezogenerProblemstellungen als Netzwerkanwendungen

NetzwerkprotokolleClient-AnwendungenClient-Server-Anwendungen

Kryptografie

Symmetrische Verschlusselungsverfahren (Caesar, Vigenere)Asymmetrische Verschlusselungsverfahren (RSA)Schlusselaustausch (Diffie-Hellmann)


Klassische Kryptographie

Caesar

Vigenere

One-Time-Pad


Public-Key-Kryptographie

Allgemeines Prinzip: Public-Key, Private-Key,Einwegfunktionen

RSA-Verfahren

SchlusselgenerierungVerschlusselungEndschlusselung


RSA-Implementierung

Modulare Binare Exponentiation

Erweiterter Euklidischer Algorithmus

Primzahltest


Netzwerkprogrammierung

Grundlagen: Aufbau von Netzwerken

Schichtenmodelle (ISO/OSI, TCP/IP)

Time-Client

Nebenlaufige Prozesse/Threads

POP3-Protokoll

Chat-Client/Chat-Server


TuringmaschinenBerechenbarkeit

Grundlagen Turingmaschinen

Definition

Vergleich zu endlichen Automaten

Graphische Darstellung

Turingmaschinen zur Berechnung von Funktionen



Abzahlbar und Uberabzahlbar

Definition

Eine Menge A heißt abzahlbar, wenn sie entweder endlich ist oderdurch eine Bijektion auf die naturlichen Zahlen abgebildet werdenkann, d.h. jedem Element in A kann genau eine naturliche Zahlzugeordnet werden und umgekehrt.Die Elemente der Menge A konnen durchnumeriert werden.Eine unendliche abzahlbare Menge besitzt die gleiche Machtigkeitwie die Menge der naturlichen Zahlen.

Die Menge aller geraden Zahlen ist abzahlbar.

Die Menge der ganzen Zahlen ist abzahlbar.

Die Menge der rationalen Zahlen ist abzahlbar.

Die Menge der reellen Zahlen ist (schon im Intervall [0..1]uberabzahlbar.



Kodierung von Turingmaschinen

Turingmaschinen konnen durch eine Folge von 0 und 1 kodiertwerden.

Man kann feststellen, ob eine 01-Folge die Kodierung einerTM darstellt.

Man kann die i-te Kodierung einer TM generieren.



Berechenbar?

entscheidbar / rekursiv

semi-entscheidbar / rekursiv aufzahlbar



Diagonalisierung und Diagonalsprache

Definition

Diagonalsprache:

Ldiag = w ∈ 0, 1∗ | w = wi und Mi akzeptiert wi nicht.

Theorem

Die Diagonalsprache Ldiag ist nicht rekursiv aufzahlbar.(Diagonalisierungsverfahren)



Methode der Reduktion

Anwendung:

L∁diag ist nicht entscheidbar, Ldiag ≤R L∁

diag

LU ist nicht entscheidbar, L∁diag ≤R LU

LH ist nicht entscheidbar, LU ≤ LH .


Mundliches Abitur

Organisatorisches

Kommission: Vorsitzender, Schriftfuhrer, Prufer

30 min Vorbereitungszeit

etwa 20 min Prufungszeit (10 + 10 min)

mindestens 2 Themenblocke aus unterschiedlichen Halbjahren

zunachst der vorbereitete Prufungsteil, anschließend weitereFragen

zwischenzeitliche, abkurzende Unterbrechungen


Mundliches Abitur

Mogliche mundliche Prufung — I

Da immer mehr Geschafte auf elektronischer Basis getatigt werden,wird der Ruf nach einer verlasslichen elektronischen Signatur lauter.Diese soll dazu dienen, eine elektronische Nachricht eindeutigeinem Verfasser zuzuordnen. Hierzu verwendet man Methoden derso genannten Public-Key-Kryptographie. Der Verfasser signiertdazu seine Nachricht mit einem Schlussel, der von einemAußenstehenden als die personliche Unterschrift identifiziertwerden kann. Dazu wird er in der Regel die Nachricht zum einemals Klartext verschicken und zum anderen in verschlusselter Form.Stimmen die Klartextnachricht und die entschlusselte Nachrichteuberein, ist von einer korrekten Identitat des Senders auszugehen.


Mundliches Abitur

Mogliche mundliche Prufung — II

1 Beschreiben Sie das RSA-Verschlusselungsverfahren(Schlusselerzeugung, Verschlusselung, Entschlusselung) underlautern Sie daran das allgemeine Schema derPublic-Key-Kryptographie.

2 Vergleichen Sie die die Public-Key-Kryptographie mit einemVerfahren der klassischen Kryptographie. Diskutieren Sie Vor-und Nachteile.

3 Beschreiben Sie, wie ein Verfahren zu Erzeugung einerelektronischen Signatur mit dem RSA-Verfahren durchgefuhrtwerden konnte.

4 Analysieren Sie dieses Verfahren auf mogliche Schwachstellen– insbesondere, wenn die versandte Nachricht nicht unbedingtsinnvoll sein muss (z.B. Zufallstext als Schlussel fur eineweitere Kommunikation).


Mundliches Abitur

VIEL ERFOLG !!!

Fragen an: [email protected]


Documents

Zusammenfassung des Grundkurs Informatik Schuljahr 2011/12 ... · Klassische Kryptographie Caesar Vigenere One-Time-Pad DirkBongartz Zusammenfassung GKInformatik2011–2013. Public-Key-Kryptographie