← Übersicht

Lehrplanabdeckung

Was die Kapitel vom Lehrplan abdecken — und was noch fehlt

Lehrplan Informatik · Grundkurs100 % der Unterrichtszeit abgedeckt

25 %Objektorientierte Modellierung / Programmierung100 %

●Objektorientierung und das Message-Passing-Modell2.1 2.3 2.6
●Klassen, Objekte, Attribute2.2 2.4
●Konstruktoren und Methoden2.2.1 2.3

10 %Rekursion100 %

●Rekursion als Problemlösungsstrategie3.1
●lineare/baumförmige Rekursion und ihre Aufrufschemata3.1.2
●Vergleich äquivalenter rekursiver und iterativer Algorithmenvarianten3.1.3
●rekursive Definition der Fakultät und der Fibonacci-Zahlen3.1.1 3.1.2

15 %Suchen und Sortieren100 %

●sequentielle Suche4.1.1
●binäre Suche4.1.2 4.1.3
●einfache Sortierverfahren: bubblesort, selectionsort, insertionsort4.2.2 4.2.3 4.2.4

15 %Dynamische Datenstrukturen: lineare Listen und binäre Bäume100 %

●Definition binärer Bäume sowie der Begriffe Wurzel, linker/rechter Teilbaum, Knoten, Tiefe3.3
●Algorithmik auf binären Bäumen: Suchen, Bestimmen der Tiefe und der Knotenanzahl3.3.1
●Suchbäume3.4
●Algorithmik auf Suchbäumen: Suchen, Einfügen, Löschen3.4.1 3.4.2 3.4.3
●Baumtraversierungen: preorder-/inorder/postorder-Durchläufe3.3.2

20 %Kryptologie100 %

●kryptographische Grundbegriffe: Klartext, Geheimtext, Schlüssel, Prinzip von Kerckhoffs8.2 8.2.1
●Sicherheit: Vertraulichkeit, Authentizität, Integrität8.1
●Chiffrieralgorithmen: Substitutions- und Transpositionsalgorithmen8.3 8.3.1 8.3.2 8.3.3
●klassische symmetrische Verschlüsselungsverfahren: Skytale, Cäsar, Vigenère8.3.1 8.3.2 8.4
●Angriffsarten: Brute-Force, Known-Plaintext, Häufigkeitsanalysen8.2.2 8.3.4 8.4.1
●Schlüsselaustauschverfahren: Diffie-Hellman8.8
●asymmetrische Verschlüsselung: Das RSA-Verfahren8.9 8.10 8.10.1 8.10.2 8.10.3 8.10.4

15 %Formale Sprachen100 %

●Formale SprachenDefinition des Begriffs der formalen Sprache5.3
●Formale SprachenBeschreibungen durch Aufzählung bzw. durch charakterisierende Eigenschaften der Worte5.3
●Endliche Automaten ohne Ausgabeformale Definition deterministischer und nichtdeterministischer endlicher Automaten als 5-Tupel (Akzeptor)5.6 5.6.1
●Endliche Automaten ohne AusgabeBeschreibung der Funktionsweise durch Übergangstabellen sowie durch Übergangsgraphen5.6
●Endliche Automaten ohne AusgabeKonstruktion endlicher Automaten zu vorgegebenen Problemstellungen5.6 5.9
●Endliche Automaten ohne AusgabeTeilmengenkonstruktion5.6.2
●Grammatikenformale Definition einer Grammatik als 4-Tupel5.4
●GrammatikenWortprüfung durch Ableitung5.4.1 5.4.2 5.4.3
●GrammatikenUmwandlung regulärer Grammatiken und zugehöriger akzeptierender Automaten ineinander5.5 5.8

Lehrplan Informatik · Leistungskurs86 % der Unterrichtszeit abgedeckt

15 %Objektorientierte Modellierung / Programmierung100 %

●Objektorientierung und das Message-Passing-Modell2.1 2.3 2.6
●Klassen, Objekte, Attribute2.2 2.4
●Konstruktoren und Methoden2.2.1 2.3
●Vererbung und Polymorphie2.7 2.7.1

10 %Rekursion70 %

●Rekursion als Problemlösungsstrategie3.1
●lineare/baumförmige Rekursion und ihre Aufrufschemata3.1.2
○endständige Rekursion und AkkumulatorenEndständige Rekursion und Akkumulatoren kommen im Skript nicht vor.
●Vergleich äquivalenter rekursiver und iterativer Algorithmenvarianten3.1.3
◐rekursive Definition der Fakultät, der Fibonacci-Zahlen und der ganzzahligen Potenz (square-and-multiply)3.1.1 3.1.2Ganzzahlige Potenz mit square-and-multiply ist nur als Randnotiz erwähnt, nicht ausgeführt.

10 %Suchen und Sortieren88 %

●sequentielle Suche4.1.1
●binäre Suche4.1.2 4.1.3
●einfache Sortierverfahren: bubblesort, selectionsort, insertionsort4.2.2 4.2.3 4.2.4
◐höhere Sortierverfahren: mergesort, quicksort4.2.5Mergesort fehlt; Quicksort ist in 4.2.5 behandelt.

10 %Dynamische Datenstrukturen: lineare Listen und binäre Bäume60 %

◐Definition linearer Listen sowie der Begriffe head, tail, Länge3.2Die Begriffe head, tail und Länge werden nicht als solche eingeführt.
◐Algorithmik auf linearen Listen: Suchen, Löschen, Ersetzen, Einfügen3.2.1 3.2.2Auf Listen fehlen Löschen und Ersetzen; behandelt sind Einfügen und Durchlaufen.
○die Datenstruktur Stack mit den Operationen isEmpty, top, push, popStack als Datenstruktur mit isEmpty, top, push, pop fehlt; der Stapel kommt nur beiläufig in 9.4.2 vor.
○die Datenstruktur Queue mit den Operationen isEmpty, front, enqueue, dequeueQueue als Datenstruktur mit isEmpty, front, enqueue, dequeue fehlt; die Warteschlange kommt nur beiläufig in 9.4.1 vor.
●Definition binärer Bäume sowie der Begriffe Wurzel, linker/rechter Teilbaum, Knoten, Tiefe3.3
●Algorithmik auf binären Bäumen: Suchen, Bestimmen der Tiefe und der Knotenanzahl3.3.1
●Suchbäume3.4
●Algorithmik auf Suchbäumen: Suchen, Einfügen, Löschen3.4.1 3.4.2 3.4.3
●Baumtraversierungen: preorder/inorder-/postorder-Durchläufe3.3.2
○strukturelle InduktionStrukturelle Induktion fehlt vollständig.

5 %Komplexitätstheorie75 %

●der Begriff der Problemgröße4.3.2
●Laufzeit und die Begriffe best-case, average-case, worst-case4.3.2 4.3.3
●der funktionale Zusammenhang zwischen Problemgröße und Laufzeit4.3.2
◐Definition der Landau’schen O-Notation4.3.2Die O-Notation wird anschaulich eingeführt, aber nicht formal definiert.
●Algorithmenklassifizierung anhand der O-Notation4.3.3
○die Klassen P und NP und das P = NP -ProblemDie Klassen P und NP und das P-NP-Problem fehlen.

10 %Berechenbarkeit und ihre Grenzen50 %

●Bestandteile und Aufbau einer Turingmaschine1.2
◐Darstellung von natürlichen Zahlen und Wahrheitswerten1.2.1Unäre Zahlen kommen vor, Wahrheitswerte und die Bandalphabet-Konvention des Lehrplans nicht.
◐Turingmaschinenprogramme: Addition, Subtraktion, Verdopplung, Paritätsprüfung1.2.1 1.2.2Von den vier geforderten Maschinen ist nur die Addition ausgeführt; Subtraktion, Verdopplung und Paritätsprüfung fehlen.
○die busy-beaver-Funktion  und ihre Nicht-BerechenbarkeitDie busy-beaver-Funktion fehlt.
●das Halteproblem für Turingmaschinen4.4.4
○UniversalitätDie universelle Turingmaschine fehlt.

15 %Kryptologie100 %

●Kryptographische Grundbegriffe: Klartext, Geheimtext, Schlüssel, Prinzip von Kerckhoffs8.2 8.2.1
●Sicherheit: Vertraulichkeit, Authentizität, Integrität8.1
●Chiffrieralgorithmen: Substitutions- und Transpositionsalgorithmen8.3 8.3.1 8.3.2 8.3.3
●klassische symmetrische Verschlüsselungsverfahren: Skytale, Cäsar, Vigenère8.3.1 8.3.2 8.4
●Angriffsarten: Brute-Force, Known-Plaintext, Häufigkeitsanalysen8.2.2 8.3.4 8.4.1
●Schlüsselaustauschverfahren: Diffie-Hellman, Man-in-the-middle-Angriffe8.8 8.9.1
●asymmetrische Verschlüsselung und digitale Signatur: Das RSA-Verfahren8.9 8.10 8.10.1 8.10.2 8.10.3 8.10.4 8.11
●die Idee hybrider Verschlüsselungsverfahren8.11

15 %Formale Sprachen100 %

●Formale SprachenDefinition des Begriffs der formalen Sprache5.3
●Formale SprachenBeschreibungen durch Aufzählung bzw. durch charakterisierende Eigenschaften der Worte5.3
●beformale Definition deterministischer und nichtdeterministischer endlicher Automaten als 5-Tupel (Akzeptor)5.6 5.6.1
●beBeschreibung der Funktionsweise durch Übergangs- und Ausgabetabellen sowie durch Übergangsgraphen5.6 5.7 5.7.1 5.7.2
●beKonstruktion endlicher Automaten zu vorgegebenen Problemstellungen5.6 5.9
●beTeilmengenkonstruktion5.6.2
●Grammatikenformale Definition einer Grammatik als 4-Tupel5.4
●GrammatikenWortprüfung durch Ableitung5.4.1 5.4.2 5.4.3
●GrammatikenChomsky-Hierarchie, Beispiele nichtregulärer und nicht-kontextfreier Sprachen5.10
●GrammatikenUmwandlung regulärer Grammatiken und zugehöriger akzeptierender Automaten ineinander5.5 5.8

10 %Graphentheorie100 %

●Definition gerichteter Graphen als Paar aus Knoten und Kanten9.2 9.2.1
●ungerichtete Graphen als Spezialfall gerichteter Graphen9.2.1
●Grundbegriffe: Knotengrad; schlichte, vollständige und zusammenhängende Graphen; gewichtete Graphen9.2.2
●Graphendarstellung: mengentheoretische Darstellung sowie Repräsentation durch Adjazenzlisten und Adjazenzmatrizen9.3 9.3.1 9.3.2 9.3.3
●Bäume als gerichtete, azyklische Graphen9.2.3
●Algorithmik auf Graphen: Breiten- und Tiefensuche, Konstruktion von Spannbäumen, das Kürzeste-Wege-Problem und der Dijkstra-Algorithmus, Hamilton Kreise und das Traveling-Salesman-Problem9.4 9.4.1 9.4.2 9.4.3 9.5 9.6 9.7