Inhalte aus dem Kerncurriculum und Umsetzung am Graf-Stauffenberg-Gymnasium:

Allgemein: Ein Schulbuch wird aktuell nicht verwendet. Wir arbeiten ausschließlich mit in der Fachgruppe erstellten Arbeitsblättern für alle Themengebiete. Sämtliche genutzte Software ist Freeware und somit kostenfrei nutzbar.

Qualifikationsphase Halbjahr 1: Algorithmen II / Objektorientierte Modellierung und Programmierung; Abstrakte Datentypen

  • Objekte und Klassen, Vererbung, Objektorientierte Modellierung (UML)
  • Grafische Oberflächen
    • Programmierung von Applets mit dem Java-Editor
  • Einfache Klassen im Java-Editor
  • Datenstrukturen und abstrakte Datentypen (Stapel, Schlange, dynamische Reihung)
  • Algorithmische Standardprobleme der Informatik
    • Sortieren (einfache Sortieralgorithmen: Sortieren durch Einfügen, Sortieren durch Auswählen, Bubblesort; Weiterführende Sortieralgorithmen: Quicksort)
  • Rekursion (einfache rekursive Berechnungen, Quicksort, Türme von Hanoi )

Mit dem Programm Structurizer werden Algorithmen graphisch dargestellt. Die Schülerinnen und Schüler lernen diese Struktogramme zu interpretieren und auch anzufertigen. Grundidee ist hierbei, dass bei einer vernünftigen Anfertigung eines Struktogramms der Algorithmus in jeder Programmiersprache aus diesem implementierbar ist.

q1

Weiterhin wird die Wertbelegung von Variablen in Algorithmen anhand von Trace-Tabellen nachvollzogen.

 q2

Zeile

Zahl x

Zahl Ergebnis

Zahl i

1

3

-

-

2

3

1

-

3

3

1

1

5

3

1

1

6

3

1

2

5

3

2

2

6

3

2

3

5

3

6

3

6

3

6

4

Weiter geht es mit der Modellierung von Klassen und deren Zusammenhängen mit der unified modelling language (UML). Dadurch wird es ermöglicht, größere Problemstellungen in kleinere Teile zu zerstückeln, um bei der Problemlösung arbeitsteilig vorgehen zu können. Bei korrekter Anfertigung, können aus den Klassendiagrammen alle Klassen unabhängig voneinander implementiert werden. Die Modellierung mit UML ist unabhängig von der konkreten Programmiersprache.

q3

Zur Erstellung dieser Diagramme wird die Software yEd-Graphen Editor genutzt.

Im Anschluss an die Modellierungseinheit werden die Schülerinnen und Schüler durch zunächst einfache Beispiele ans textbasierte Programmieren im Rahmen von grafischen Oberflächen, hier Applets in Java, herangeführt.

Durch eigene Veränderungen an den vorgegebenen Beispielen wird sich zunächst ein Überblick über die Bedeutung der einzelnen Java-Anweisungen verschafft, sodass die Lernenden im Anschluss in der Lage sind, selbst einfache Grafiken einzufügen.

In diesem Rahmen werden auch die bisher behandelten Kontrollstrukturen angewendet.

 q4q5

q6

Möchte man bei der algorithmischen Umsetzung eines Problems viele Objekte einer bestimmten Art erstellen, ist eine Art Bauplan für diese Objekte sinnvoll. Diese Klassen und deren algorithmische Umsetzung werden als nächstes unterrichtlich thematisiert.

Klassen und abgeleitete Klassen werden nun mit dem Java-Editor erstellt.

q7

Bisher wurde mit Ganzzahlen, Zeichenketten, Dezimalzahlen und Wahrheitswerten mit sogenannten einfachen Datentypen gearbeitet.

Oft benötigt man jedoch auch Datenstrukturen, die bestimmte Funktionsweisen haben sollen und dynamisch erweiterbar / kürzbar sein sollen. Eine Liste, mit der man z.B. Namen verwaltet, ist solch ein Beispiel.

In der Informatik gibt es die abstrakten Datentypen (ADT). Deren Umsetzung mit sogenannten Verweisen wird sowohl graphisch, als auch algorithmisch behandelt.

q9q8

Als Anwendung der ADT werden Sortieralgorithmen untersucht. Zahlen oder Namen zu sortieren ist ein schnell auftretenden Problem.

Hierfür untersuchen die Schüler die Funktionsweise verschiedener Sortieralgorithmen und fertigen auch Struktogramme dazu an. Vertiefend können diese auch implementiert werden.

q10

In diesem Rahmen lernen die Schülerinnen und Schüler auch Algorithmen kennen, die sich während der Ausführung selbst nutzen. Diese werden als rekursive Algorithmen bezeichnet.

  

Qualifikationsphase Halbjahr 2: Codierung / Kryptologie und Datenbanken

Codierung

  • Fehlererkennende Codes (Repititionscode, (7,4) Hamming-Code)
  • Verlustfreie Datenkompression bei Texten und Grafiken: Huffmann-Code
  • Einsatzgebiete für Verschlüsselungen (z.B. E-Mail), historische Entwicklung
  • Kryptologische Verfahren
    • Caesar und Vigenere
    • symmetrischen und asymmetrischen Verfahren (Diffie-Hellmann Schlüsseltausch

Nachrichten möglichst schnell aber auch mit einer Möglichkeit Übertragungsfehler zu erkennen und zu beheben sind die beiden entgegengesetzten Ziele der Codierungstheorie.

Die Schülerinnen und Schüler erarbeiten diese an einfachen Codierungen (ASCII, Morse und einer eigenen Codierung).

Im Anschluss wird zunächst der Aspekt der Kompression von Dateien betrachtet.

Hierfür lernen die Schülerinnen und Schüler Huffman- und die Lauflängencodierung für Texte und auch Farbbilder kennen.

 q11q12

q13q14

Die Fehlererkennung und Korrektur wird im folgenden Ablauf thematisiert. Hierfür werden erst einfache Repetitionscodes betrachtet und zum Abschluss eine bzgl. Fehlererkennung und Korrektur, wesentlich bessere Codierung, der (7,4)-Hamming-Code.

Den zweite Teil des ersten Quartals bildet die Kryptologie. Nachdem bereits in der E-Phase einfache Verfahren, wie die Caesar-Verschlüsselung, untersucht wurden, wird die Vigenére-Chiffre als ein Beispiel für polyalphabetische Verschlüsselungen betrachtet.

q15

Um ein Beispiel einer modernene Verschlüsselung kennengelernt zu haben, wird im Anschluss an Vigenére eine vereinfachte Variante des Data Encryption Standard (DES) behandelt.

Abschließend zum Themenkomplex Kryptologie wird sich dem Thema Schlüsseltausch genähert. Bei den bishe untersuchten Verschlüsselungsverfahren gibt es für Sender und Empfänger einen gemeinsamen Schlüssel, welcher vor der eigentlichen Kommunikation ausgetauscht werden muss. Dies stellt natürlich eine unschöne Angriffsstelle dar, die es zu beseitigen gilt.

Das Verfahren von Diffie-Hellman-(Merkle), ist das hierfür historisch erste veröffentlichte Verfahren, welches dieses Problem beseitigt. Dieser Schlüsseltausch ermöglicht eine asymmetrische Verschlüsselung. Es gibt einen privaten Schlüssel für den Sender und einen anderen für den Empfänger, sowie einen allgemein bekannten öffentlichen Schlüssel. Beim Austausch der Schlüsselinformationen ist es mit diesem Verfahren nicht mehr möglich, die privaten Informationen zu erhalten, da diese nie gesendet werden.

Datenbanken

  • Einführung in Datenbanken
  • Beschreibung der Wirkungsweise grundlegender SQL-Abfragen zur Datenbankauswertung anhand eines konkreten Satzes von Relationen
  • Entwurf und Anwendung einfacher Abfragen und Verbundabfragen in SQL
  • Entwurf und Anwendung geschachtelter SQL- Abfragen
  • Entwicklung eines ER-Modells für ein vorgegebenes System
  • Analyse eines vorgegebenen ER-Modells bezüglich eines Anwendungsfalls
  • Erweiterung eines vorgegebenen ER-Modells
  • Umsetzung eines ER-Modells in ein relationales Datenbankschema
  • Entwicklung eines relationalen Datenbankschemas unter Berücksichtigung der ersten, zweiten und dritten Normalform

Datenbanken. Das klingt auf jeden Fall sehr unspannend aber ist für die Schülerinnen und Schüler meist tatsächlich ein beliebtes Thema.

Wie muss eine Tabelle oder mehrere Tabellen angelegt sein, damit die Daten darin möglichst effektiv und sinnvoll verwaltet werden können? Diese Fragen werden im zweiten Teil des zweiten Halbjahres geklärt.

Hierfür schaut man sich zunächst einfache Tabellen an und stellt schnell fest, dass diese für eine effektive Datenverwaltung ungeeignet sind.

Die systematische Umwandlung in sogenannte Normalformen ist ein Teil des Themas hier.

q16

Im konkreten Anwendungsbereich werden die Schülerinnen und Schüler an SQL herangeführt.

SQL-Abfragen werden angewendet, um aus Datenbanken Datensätze abzufragen und sich ausgeben zu lassen.

q17

Der dritte Inhalt im Bereich Datenbanken ist die Modellierung mit den Entity-Relationship-Diagrammen (ER-Diagramme).

Diese werden zum Konzipieren von größeren Datenbanken genutzt, analog zu Klassendiagrammen bei der Programmierung.

Die Schülerinnen und Schüler sollen am Ende aus einem Text im Sachzusammenhang, in denen Anforderungen an eine zu erstellende Datenbank stehen, ein solches ER-Modell zu entwickeln. Ebenso sollen sie gegeben ER-Modelle zu Datenbanken umsetzen und aus Datenbanken ER-Modelle aufstellen können. Die Diagramme werden mit dem yED-Graphen-Editor angefertigt.

q18

Qualifikationsphase Halbjahr 3: Grundlagen der Theoretischen Informatik, Grundlagen der Technischen Informatik und Vertiefung Algorithmen und Datenstrukturen

 Grundlagen der Theoretischen Informatik

  • Endliche Automaten
    • DEA und Mealy-Automaten
    • Reguläre Sprachen
    • Zustandsgrapen

Die Funktionsweise von z.B. Getränkeautomaten ist ein gutes Beispiel zur Theorie der endlichen Automaten. Hinter diesen steckt auch immer eine sogenannte formale Sprache, mit welcher Wörter gebildet werden, die der Automat als Eingabe akzeptiert.

Die Schülerinnen und Schüler entwickeln hier aus Sachzusammenhängen Automaten und auch die entsprechenden formalen Sprachen. Am Ende sollen sie in der Lage sein, zu einer regulären Sprache den Zustandsgraph eines solchen Automaten zu erstellen, aus einem solchen Graph die Sprache abzuleiten und gegebene Zustandsgraphen zu minimieren.

Gearbeitet wird hier viel mit dem Programm AtoCC.

q19q20

Grundlagen der Technischen Informatik

  • Wahrheitstabellen und Logikgatter (AND, OR, NOT, XOR, NAND, NOR, XNOR)
  • Elementare Schaltnetze (Halb- und Volladdierer bzw. Subtrahierer, Inkrementierer)
  • Schaltnetze mit TTL-Logikgattern und Steckplatinen bauen

Ja, es wird auch praktisch gearbeitet! Nach einer kurzen Einführung in logische Ausdrücke und dem Umgang mit diesen, werden auf physischer Ebene Schaltungen gebaut.

Die Schülerinnen und Schüler lernen hier mit Hilfe elementarer Logikgatter und den entsprechenden Bauteilen Schaltungen zu bauen, welche auch im Sachzusammenhang bestimmte Probleme lösen.

Schaltterme werden systematisch hergeleitet und minimiert und daraus werden Schaltnetze gebaut.

Als Vorstufe wird die Software LogiSim genutzt, welches virtuelle Schaltungen bauen und diese testen lässt. Im Anschluss werden diese auch auf Steckplatinen zusammengebaut.

Hier kann auch gut arbeitsteilig vorgegangen werden, sodass größere Schaltungen von mehreren Gruppen in Teilen erstellt und anschließend zusammengefügt werden.

Es wird auch thematisiert, inwiefern die Automaten mit Ausgabe aus der vorherigen Einheit physisch umgesetzt werden können.

S1: Schalter 1 ist gedrückt

S2: Schalter 2 ist gedrückt

A: Heckenschere ist eingeschaltet

nein

n

n

nein

j

n

ja

n

n

ja

j

j

q21q22

Qualifikationsphase Halbjahr 4: Vertiefung Algorithmen und Datenstrukturen

  1. Datenstrukturen und abstrakte Datentypen (Liste, Bäume, Graphen)
  2. Algorithmische Standardprobleme der Informatik
    • Suchen (Suche in einer Reihung, Wegesuche: Tiefen- und Breitensuche in Baumstrukturen und Graphen)
    • Minimierungsprobleme in Graphen (kürzeste Wege mit Dijkstra)

Je nach Zeit, wird im letzten Halbjahr das Thema zu Datenstrukturen und Algorithmen vertieft.

Es werden weitere abstrakte Datentypen eingeführt, aber diesmal nichtlineare. Möglich sind hier Bäume oder Graphen.

q23q24

Zum Thema Bäume wird im Rahmen der Algorithmen die Suche in Bäumen nach bestimmten Einträgen (Tiefen- und Breitensuche) behandelt.

Bei den Graphen bietet sich der Dijkstra-Algorithmus an, um kürzeste Wege von einem Knoten zu einem anderen zu bestimmen und den entsprechenden Weg dazu (Routenplaner).