Date post: | 25-May-2019 |
Category: |
Documents |
Upload: | nguyenthuan |
View: | 215 times |
Download: | 0 times |
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
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
GrundlagenSoftware-Lebenszyklus — nicht explizit
Vorgaben
Klasse, Objekt
Attribut, Konstruktor, Methode (Anfrage/Auftrag)
Geheimnisprinzip
UML-Klassendiagramme (Entwurfs- undImplementierungsdiagramme
(gerichtete) Assoziation mit MultiplizitatVererbung
Vererbungskonzept
Abstrakte KlassenPolymorphie
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
GrundlagenSoftware-Lebenszyklus — nicht explizit
Phasenmodell
Problem . . . Problemanalyse
→ Andorderungsdefinition . . . Entwurf
→ Spezifikation . . . Implementierung
→ dokumentiertes Programm . . . Funktionsuberprufung
→ modifiziertes Programm . . . Installation/Abnahme
→ anforderungsgerechtes Produkt Wartung
→ Verschrottung
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
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)
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
DatenstrukturenAlgorithmen
Arrays und Listen
Arrays: statische Große, direkter Zugriff
Einfach verkettete Liste
Implementierung: Element, Liste, (Object)Implementierung: Suchen, Anhangen, Loschen, ...
Erweiterung: Doppelt verkettete Liste
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
DatenstrukturenAlgorithmen
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
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
DatenstrukturenAlgorithmen
Graphen — nicht explizit
Definition aus Knoten und Kanten, G = (V,E)
Beispiele:
Konigsberger Bruckenproblem (Eulerkreis-Problem)Haus vom Nikolaus
Reprasentationsformen: Adjazenzmatrix, Adjazenzliste
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
DatenstrukturenAlgorithmen
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
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
DatenstrukturenAlgorithmen
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.
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
DatenstrukturenAlgorithmen
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
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
DatenstrukturenAlgorithmen
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
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
DatenstrukturenAlgorithmen
Konzept: Dynamische Programmierung
Bottom-Up-Berechnung der Fibonacci-Zahlen
CYK-Algorithmus
Alignment zweier Strings
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
DatenstrukturenAlgorithmen
Sortieralgorithmen
Selectionsort
Bubblesort
Insertionsort
Quicksort
Mergesort
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
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
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
Endliche AutomatenGrammatiken
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)
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
Endliche AutomatenGrammatiken
Nicht-deterministische endliche Automaten (NEA)
Definition: wie DEA – allerdings Ubergangsrelation
statt linearer Berechnung (DEA), Berechnungsbaum
Umwandlung in DEA durch Potenzmengenkonstruktion
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
Endliche AutomatenGrammatiken
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
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
Endliche AutomatenGrammatiken
Grammatiken und endliche Automaten
DEA → Typ-3-Grammatik
Typ-3-Grammatik → NEA
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
Endliche AutomatenGrammatiken
Erganzungen
Kellerautomaten
Wortproblem fur kontextfreie Sprachen und CYK-Algorithmus
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
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
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
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
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
Modellierung
Relationale Datenbanken
Grundlegendes Element: Relationen/Tabellen
Ubersetzung von ER-Diagrammen in Relationen
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
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
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
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)
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
Modellierung
SQL — Anfragesprache
SELECT AttributlisteFROM RelationenWHERE Bedingungen
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
Vorgaben
Modellieren und implementieren kontextbezogenerProblemstellungen als Netzwerkanwendungen
NetzwerkprotokolleClient-AnwendungenClient-Server-Anwendungen
Kryptografie
Symmetrische Verschlusselungsverfahren (Caesar, Vigenere)Asymmetrische Verschlusselungsverfahren (RSA)Schlusselaustausch (Diffie-Hellmann)
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
Klassische Kryptographie
Caesar
Vigenere
One-Time-Pad
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
Public-Key-Kryptographie
Allgemeines Prinzip: Public-Key, Private-Key,Einwegfunktionen
RSA-Verfahren
SchlusselgenerierungVerschlusselungEndschlusselung
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
RSA-Implementierung
Modulare Binare Exponentiation
Erweiterter Euklidischer Algorithmus
Primzahltest
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
Netzwerkprogrammierung
Grundlagen: Aufbau von Netzwerken
Schichtenmodelle (ISO/OSI, TCP/IP)
Time-Client
Nebenlaufige Prozesse/Threads
POP3-Protokoll
Chat-Client/Chat-Server
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
TuringmaschinenBerechenbarkeit
Grundlagen Turingmaschinen
Definition
Vergleich zu endlichen Automaten
Graphische Darstellung
Turingmaschinen zur Berechnung von Funktionen
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
TuringmaschinenBerechenbarkeit
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.
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
TuringmaschinenBerechenbarkeit
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.
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
TuringmaschinenBerechenbarkeit
Berechenbar?
entscheidbar / rekursiv
semi-entscheidbar / rekursiv aufzahlbar
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
TuringmaschinenBerechenbarkeit
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)
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
TuringmaschinenBerechenbarkeit
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 .
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
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
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
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.
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
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).
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013
Mundliches Abitur
VIEL ERFOLG !!!
Fragen an: [email protected]
Dirk Bongartz Zusammenfassung GK Informatik 2011–2013