Lehrplan Informatik · Grundkurs100 % der Unterrichtszeit abgedeckt
25 %Objektorientierte Modellierung / Programmierung100 %
| ● | Objektorientierung und das Message-Passing-Modell | 2.1 2.3 2.6 |
| ● | Klassen, Objekte, Attribute | 2.2 2.4 |
| ● | Konstruktoren und Methoden | 2.2.1 2.3 |
10 %Rekursion100 %
| ● | Rekursion als Problemlösungsstrategie | 3.1 |
| ● | lineare/baumförmige Rekursion und ihre Aufrufschemata | 3.1.2 |
| ● | Vergleich äquivalenter rekursiver und iterativer Algorithmenvarianten | 3.1.3 |
| ● | rekursive Definition der Fakultät und der Fibonacci-Zahlen | 3.1.1 3.1.2 |
15 %Suchen und Sortieren100 %
| ● | sequentielle Suche | 4.1.1 |
| ● | binäre Suche | 4.1.2 4.1.3 |
| ● | einfache Sortierverfahren: bubblesort, selectionsort, insertionsort | 4.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, Tiefe | 3.3 |
| ● | Algorithmik auf binären Bäumen: Suchen, Bestimmen der Tiefe und der Knotenanzahl | 3.3.1 |
| ● | Suchbäume | 3.4 |
| ● | Algorithmik auf Suchbäumen: Suchen, Einfügen, Löschen | 3.4.1 3.4.2 3.4.3 |
| ● | Baumtraversierungen: preorder-/inorder/postorder-Durchläufe | 3.3.2 |
20 %Kryptologie100 %
| ● | kryptographische Grundbegriffe: Klartext, Geheimtext, Schlüssel, Prinzip von Kerckhoffs | 8.2 8.2.1 |
| ● | Sicherheit: Vertraulichkeit, Authentizität, Integrität | 8.1 |
| ● | Chiffrieralgorithmen: Substitutions- und Transpositionsalgorithmen | 8.3 8.3.1 8.3.2 8.3.3 |
| ● | klassische symmetrische Verschlüsselungsverfahren: Skytale, Cäsar, Vigenère | 8.3.1 8.3.2 8.4 |
| ● | Angriffsarten: Brute-Force, Known-Plaintext, Häufigkeitsanalysen | 8.2.2 8.3.4 8.4.1 |
| ● | Schlüsselaustauschverfahren: Diffie-Hellman | 8.8 |
| ● | asymmetrische Verschlüsselung: Das RSA-Verfahren | 8.9 8.10 8.10.1 8.10.2 8.10.3 8.10.4 |
15 %Formale Sprachen100 %
| ● | Formale SprachenDefinition des Begriffs der formalen Sprache | 5.3 |
| ● | Formale SprachenBeschreibungen durch Aufzählung bzw. durch charakterisierende Eigenschaften der Worte | 5.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 Übergangsgraphen | 5.6 |
| ● | Endliche Automaten ohne AusgabeKonstruktion endlicher Automaten zu vorgegebenen Problemstellungen | 5.6 5.9 |
| ● | Endliche Automaten ohne AusgabeTeilmengenkonstruktion | 5.6.2 |
| ● | Grammatikenformale Definition einer Grammatik als 4-Tupel | 5.4 |
| ● | GrammatikenWortprüfung durch Ableitung | 5.4.1 5.4.2 5.4.3 |
| ● | GrammatikenUmwandlung regulärer Grammatiken und zugehöriger akzeptierender Automaten ineinander | 5.5 5.8 |
Lehrplan Informatik · Leistungskurs86 % der Unterrichtszeit abgedeckt
15 %Objektorientierte Modellierung / Programmierung100 %
| ● | Objektorientierung und das Message-Passing-Modell | 2.1 2.3 2.6 |
| ● | Klassen, Objekte, Attribute | 2.2 2.4 |
| ● | Konstruktoren und Methoden | 2.2.1 2.3 |
| ● | Vererbung und Polymorphie | 2.7 2.7.1 |
10 %Rekursion70 %
| ● | Rekursion als Problemlösungsstrategie | 3.1 |
| ● | lineare/baumförmige Rekursion und ihre Aufrufschemata | 3.1.2 |
| ○ | endständige Rekursion und Akkumulatoren | Endständige Rekursion und Akkumulatoren kommen im Skript nicht vor. |
| ● | Vergleich äquivalenter rekursiver und iterativer Algorithmenvarianten | 3.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 Suche | 4.1.1 |
| ● | binäre Suche | 4.1.2 4.1.3 |
| ● | einfache Sortierverfahren: bubblesort, selectionsort, insertionsort | 4.2.2 4.2.3 4.2.4 |
| ◐ | höhere Sortierverfahren: mergesort, quicksort | 4.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änge | 3.2Die Begriffe head, tail und Länge werden nicht als solche eingeführt. |
| ◐ | Algorithmik auf linearen Listen: Suchen, Löschen, Ersetzen, Einfügen | 3.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, pop | Stack 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, dequeue | Queue 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, Tiefe | 3.3 |
| ● | Algorithmik auf binären Bäumen: Suchen, Bestimmen der Tiefe und der Knotenanzahl | 3.3.1 |
| ● | Suchbäume | 3.4 |
| ● | Algorithmik auf Suchbäumen: Suchen, Einfügen, Löschen | 3.4.1 3.4.2 3.4.3 |
| ● | Baumtraversierungen: preorder/inorder-/postorder-Durchläufe | 3.3.2 |
| ○ | strukturelle Induktion | Strukturelle Induktion fehlt vollständig. |
5 %Komplexitätstheorie75 %
| ● | der Begriff der Problemgröße | 4.3.2 |
| ● | Laufzeit und die Begriffe best-case, average-case, worst-case | 4.3.2 4.3.3 |
| ● | der funktionale Zusammenhang zwischen Problemgröße und Laufzeit | 4.3.2 |
| ◐ | Definition der Landau’schen O-Notation | 4.3.2Die O-Notation wird anschaulich eingeführt, aber nicht formal definiert. |
| ● | Algorithmenklassifizierung anhand der O-Notation | 4.3.3 |
| ○ | die Klassen P und NP und das P = NP -Problem | Die Klassen P und NP und das P-NP-Problem fehlen. |
10 %Berechenbarkeit und ihre Grenzen50 %
| ● | Bestandteile und Aufbau einer Turingmaschine | 1.2 |
| ◐ | Darstellung von natürlichen Zahlen und Wahrheitswerten | 1.2.1Unäre Zahlen kommen vor, Wahrheitswerte und die Bandalphabet-Konvention des Lehrplans nicht. |
| ◐ | Turingmaschinenprogramme: Addition, Subtraktion, Verdopplung, Paritätsprüfung | 1.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-Berechenbarkeit | Die busy-beaver-Funktion fehlt. |
| ● | das Halteproblem für Turingmaschinen | 4.4.4 |
| ○ | Universalität | Die universelle Turingmaschine fehlt. |
15 %Kryptologie100 %
| ● | Kryptographische Grundbegriffe: Klartext, Geheimtext, Schlüssel, Prinzip von Kerckhoffs | 8.2 8.2.1 |
| ● | Sicherheit: Vertraulichkeit, Authentizität, Integrität | 8.1 |
| ● | Chiffrieralgorithmen: Substitutions- und Transpositionsalgorithmen | 8.3 8.3.1 8.3.2 8.3.3 |
| ● | klassische symmetrische Verschlüsselungsverfahren: Skytale, Cäsar, Vigenère | 8.3.1 8.3.2 8.4 |
| ● | Angriffsarten: Brute-Force, Known-Plaintext, Häufigkeitsanalysen | 8.2.2 8.3.4 8.4.1 |
| ● | Schlüsselaustauschverfahren: Diffie-Hellman, Man-in-the-middle-Angriffe | 8.8 8.9.1 |
| ● | asymmetrische Verschlüsselung und digitale Signatur: Das RSA-Verfahren | 8.9 8.10 8.10.1 8.10.2 8.10.3 8.10.4 8.11 |
| ● | die Idee hybrider Verschlüsselungsverfahren | 8.11 |
15 %Formale Sprachen100 %
| ● | Formale SprachenDefinition des Begriffs der formalen Sprache | 5.3 |
| ● | Formale SprachenBeschreibungen durch Aufzählung bzw. durch charakterisierende Eigenschaften der Worte | 5.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 Übergangsgraphen | 5.6 5.7 5.7.1 5.7.2 |
| ● | beKonstruktion endlicher Automaten zu vorgegebenen Problemstellungen | 5.6 5.9 |
| ● | beTeilmengenkonstruktion | 5.6.2 |
| ● | Grammatikenformale Definition einer Grammatik als 4-Tupel | 5.4 |
| ● | GrammatikenWortprüfung durch Ableitung | 5.4.1 5.4.2 5.4.3 |
| ● | GrammatikenChomsky-Hierarchie, Beispiele nichtregulärer und nicht-kontextfreier Sprachen | 5.10 |
| ● | GrammatikenUmwandlung regulärer Grammatiken und zugehöriger akzeptierender Automaten ineinander | 5.5 5.8 |
10 %Graphentheorie100 %
| ● | Definition gerichteter Graphen als Paar aus Knoten und Kanten | 9.2 9.2.1 |
| ● | ungerichtete Graphen als Spezialfall gerichteter Graphen | 9.2.1 |
| ● | Grundbegriffe: Knotengrad; schlichte, vollständige und zusammenhängende Graphen; gewichtete Graphen | 9.2.2 |
| ● | Graphendarstellung: mengentheoretische Darstellung sowie Repräsentation durch Adjazenzlisten und Adjazenzmatrizen | 9.3 9.3.1 9.3.2 9.3.3 |
| ● | Bäume als gerichtete, azyklische Graphen | 9.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-Problem | 9.4 9.4.1 9.4.2 9.4.3 9.5 9.6 9.7 |