Jahrgangsstufe 11

Inf 11.1 Rekursive Datenstrukturen

In Jahrgangsstufe 10 haben die Schüler im Rahmen der objektorientierten Modellierung schwerpunktmäßig am Erstellen geeigneter Methoden von Objekten sowie am Erkennen und Umsetzen von Objektbeziehungen gearbeitet. Verschiedenartige Aufgabenstellungen aus der Praxis verdeutlichen den Schülern nun, dass immer wieder Strukturen von Daten auftreten, die mit den bisher bekannten Datentypen nicht effizient beschrieben werden können. Die Schüler beschäftigen sich daher eingehend mit typischen rekursiven Datentypen, lernen deren Vorteile und breites Spektrum von Einsatzmöglichkeiten kennen und wenden sie an; dabei nutzen sie erstmals rekursive Methoden.

Inf 11.1.1 Listen (ca. 29 Std.)

Die Schüler untersuchen die grundlegenden Eigenschaften der Datenstruktur Schlange, deren grundsätzlichen Aufbau sie bereits aus ihrem Alltag, z. B. von Warteschlangen, kennen. Eine erste Implementierung mit einem Feld zeigt schnell die Grenzen dieser statischen Lösung auf und führt die Jugendlichen zu einer dynamischen Datenstruktur wie der einfach verketteten Liste. Sie erarbeiten deren prinzipielle Funktionsweise sowie deren rekursiven Aufbau und wenden hierbei das Prinzip der Referenz auf Objekte an. Die Jugendlichen erkennen, dass die rekursive Struktur der Liste für viele ihrer Methoden einen rekursiven Algorithmus nahelegt. Sie verstehen, dass eine universelle Verwendbarkeit der Klasse Liste nur möglich ist, wenn auf eine klare Trennung von Struktur und Daten geachtet wird. An einfachen Beispielen aus der Praxis und deren Implementierung vertiefen die Schüler ihr Wissen und erfahren die flexible Verwendbarkeit dieses Datentyps.

• Methoden der Datenstruktur Schlange: Anfügen am Ende, Entfernen am Anfang

• allgemeines Prinzip und rekursive Struktur einer einfach verketteten Liste; graphische Veranschaulichung der Methoden zum Einfügen (auch an beliebiger Stelle), Suchen und Löschen

• rekursive Abläufe: rekursiver Methodenaufruf, Abbruchbedingung, Aufrufsequenz

• Implementierung einer einfach verketteten Liste als Klasse mittels Referenzen unter Verwendung eines geeigneten Softwaremusters (Composite); Realisierung der Methoden zum Einfügen, Suchen und Löschen

• Einsatz der allgemeinen Datenstruktur Liste bei der Bearbeitung eines Beispiels aus der Praxis: Verwaltung von Elementen verschiedener Datentypen mittels Vererbung

• Stapel und Schlange als spezielle Formen der allgemeinen Datenstruktur Liste

Inf 11.1.2 Bäume als spezielle Graphen (ca. 29 Std.)

In Erweiterung ihrer Grundkenntnisse über das hierarchische Ordnungsprinzip lernen die Schüler den Baum als effiziente dynamische Datenstruktur kennen. Sie stellen fest, dass damit viele Strukturen aus anderen Gebieten abgebildet werden können. Am Beispiel der Suche in umfangreichen Datenbeständen wird den Jugendlichen deutlich, dass sich auch hier sehr oft Baumstrukturen einsetzen lassen, um die Effizienz der Informationsverarbeitung zu steigern. Bei der sprachlichen bzw. graphischen Darstellung und insbesondere bei der Implementierung dieser Datenstruktur vertiefen sie ihr Verständnis für das Prinzip der Rekur­sion. Im Rahmen praktischer Fragestellungen, z. B. zur Planung von Verkehrsrouten, wenden die Schüler auch die Datenstruktur Graph als Erweiterung der Struktur Baum an.

• allgemeines Prinzip und Struktur eines Baums (insbesondere Wurzel, Knoten, Kanten, Blatt) und des Spezialfalls geordneter Binärbaum

• Veranschaulichung und Implementierung der Methoden zum Einfügen und Suchen von Elementen in einem geordneten Binärbaum unter Verwendung der Rekursion

• Verfahren zur Auflistung aller Elemente eines geordneten Binärbaums: Preorder-, Inorder- und Postorder-Durchlauf; Realisierung der Methode zum Ausgeben mithilfe eines dieser Verfahren

• Implementierung der Klasse geordneter Binärbaum mit einer geeigneten Programmiersprache; Verwenden und Testen der Methoden an einem Anwendungsbeispiel (z. B. erweiterbares Wörterbuch als Suchbaum)

• die Datenstruktur Graph als Verallgemeinerung des Baums; Eigenschaften (gerichtet/ungerichtet, bewertet/unbewertet); Adjazenzmatrix

• Algorithmus zum Graphendurchlauf (z. B. Tiefensuche) bei einer Aufgabenstellung aus der Praxis

Inf 11.2 Softwaretechnik (ca. 26 Std.)

Das Arbeiten in Projekten ist die typische Vorgehensweise bei der Entwicklung großer Systeme. Mit den bisher erworbenen Kenntnissen und Fertigkeiten sind die Schüler nun in der Lage, größere Softwaresysteme (z. B. Geschäftsabläufe einer Bank, Autovermietung) eigenständig zu gestalten. Hierbei bauen sie auch ihre Fähigkeit zur Planung und Durchführung von Projekten aus. Die Jugendlichen übernehmen verstärkt persönliche Verantwortung und erfahren die Notwendigkeit, eigene Ansichten und Ideen vor anderen darstellen und vertreten zu können. Sie setzen alle bisher erlernten Beschreibungstechniken der Informatik ein und machen sich damit deren Zusammenwirken in einem größeren Kontext bewusst. Die Schüler erkennen, dass sie bei einigen Teilproblemen auf bereits vorgefertigte Standardlösungen in Form von Softwaremustern zurückgreifen können.

Inf 11.2.1 Planung und Durchführung kooperativer Arbeitsabläufe

Die Schüler systematisieren und vertiefen am konkreten Beispiel ihre Kenntnisse über die verschiedenen Schritte bei der Planung und Durchführung eines Softwareprojekts. Zur Koordinierung paralleler Arbeitsgruppen nutzen sie das Semaphorprinzip.

• Projektplanung: Zielsetzung, Arbeitsteilung, Arbeitsgruppen und deren organisatorische Schnittstellen, Ablauf mit Zwischenergebnissen (Meilensteinen)

• Phasen der Softwareentwicklung: Analyse mit Erstellung des Pflichtenhefts, Entwurf, Implementierung, Test, Bewertung und Abnahme

• Problematik der Koordination nebenläufiger Arbeitsabläufe beim Zugriff auf gemeinsame Ressourcen: kritischer Abschnitt, Semaphorprinzip, Verklemmung und Lösungsmöglichkeiten

• Reflexion des Projektverlaufs, Aufwandsabschätzung

Inf 11.2.2 Praktische Softwareentwicklung

Bisher haben die Schüler verschiedene Modellierungstechniken der Informatik einzeln angewandt. Nun erkennen sie, dass eine angemessene Beschreibung größerer Systeme nur durch die kombinierte Verwendung aller bisher erlernten Modellierungstechniken möglich ist. Bei der Implementierung ihrer Modelle setzen sie bekannte Datenstrukturen situationsgerecht ein und achten bei der Gestaltung der Bedieneroberfläche insbesondere auf Benutzungsfreundlichkeit.

• Zusammenspiel der verschiedenen Beschreibungstechniken beim Systementwurf: Datenmodellierung – Ablaufmodellierung – funktionale Modellierung – Objektmodellierung

• Implementierung des Systementwurfs unter Nutzung rekursiver Datenstrukturen; Anwendung des Softwaremusters „Model-View-Controller“

• Test der Komponenten und des Gesamtsystems, Überprüfung der Vollständigkeit und Korrektheit des Systementwurfs

• Dokumentation des Softwareprodukts

Jahrgangsstufe 12

Inf 12.1 Formale Sprachen (ca. 16 Std.)

Bisher kennen die Schüler Sprachen vor allem als Mittel zur Kommunikation zwischen Menschen. Ihnen ist bekannt, dass eindeutiges gegenseitiges Verstehen nur dann gewährleistet ist, wenn sich die Kommunikationspartner auf eine gemeinsame Sprache einigen und die zu deren Gebrauch festgelegten Regeln einhalten. Im Rückblick auf das bisherige Arbeiten mit dem Computer wird ihnen deutlich, dass die Verständigung zwischen Mensch und Maschine ebenfalls einen Kommunikationsprozess darstellt, der ähnlichen Regeln unterliegt. Daher betrachten sie zunächst den strukturellen Aufbau einer ihnen bereits bekannten natürlichen Sprache sowie den Aufbau einer künstlichen Sprache. Die Jugendlichen lernen dabei, die Begriffe Syntax und Semantik einer Sprache zu unterscheiden.

Anhand einfacher Beispiele wie Autokennzeichen, E-Mail-Adressen oder Gleitkommazahlen lernen die Schüler den Begriff der formalen Sprache als Menge von Zeichenketten kennen, die nach bestimmten Regeln aufgebaut sind. Zur Beschreibung dieser Regeln verwenden sie Textnotationen oder Syntaxdiagramme und können damit analog zu den natürlichen Sprachen Grammatiken für formale Sprachen definieren. Die Zweckmäßigkeit der streng formalen Beschreibung zeigt sich den Jugendlichen bei der automatischen Überprüfung der syntaktischen Korrektheit von Zeichenketten mithilfe von endlichen Automaten.

Den Schülern wird bewusst, dass nur Vorgänge, die sich mit Mitteln einer formalen Sprache ausdrücken lassen, von einem Computer bearbeitet werden können. Somit stoßen sie über die Theorie der formalen Sprachen auf eine prinzipielle Grenze des Computereinsatzes.

• einfache Beispiele für formale Sprachen über einem Alphabet; Zeichen, Zeichenvorrat (Alphabet), Zeichenkette

• Unterscheidung zwischen Syntax und Semantik, Vergleich zwischen natürlichen und formalen Sprachen

• syntaktischer Aufbau einer formalen Sprache: Grammatik (Terminal, Nichtterminal, Produktion, Startsymbol)

• Notation formaler Sprachen: Syntaxdiagramm, einfache Textnotation (z. B. Backus-Naur-Form)

• erkennender, endlicher Automat als geeignetes Werkzeug zur Syntaxprüfung für reguläre Sprachen; Implementierung eines erkennenden Automaten

Inf 12.2 Kommunikation und Synchronisation von Prozessen (ca. 20 Std.)

Aus vielen Bereichen der Computernutzung wie beispielsweise dem Homebanking oder einem Buchungssystem für Reisen ist den Schülern die Notwendigkeit zur Zusammenarbeit mehrerer Computer bekannt. Sie sehen ein, dass zur korrekten Verständigung von Computern spezielle formale Regeln (Protokolle) existieren müssen. Anhand der Kommunikation in Rechnernetzen erfahren die Jugendlichen, dass es sinnvoll ist, Kommunikationsvorgänge in verschiedene, aufeinander aufbauende Schichten aufzuteilen.

Die Schüler erkennen z. B. bei der Analyse der Aufgaben eines Mailservers, dass Rechner anfallende Aufträge oft parallel bearbeiten und dennoch einen geordneten Ablauf gewährleisten müssen. Sie erarbeiten Lösungsansätze für die Synchronisation derartiger Vorgänge an Beispielen aus dem täglichen Leben wie der Regelung des Gegenverkehrs durch eine einspurige Engstelle. Beim Übertragen dieser Ansätze auf die Prozesse im Computer wird ihnen bewusst, dass es bei jedem dieser Verfahren bestimmte Sequenzen gibt, die nicht von mehreren Prozessen gleichzeitig ausgeführt werden dürfen.

• Kommunikation zwischen Prozessen, Protokolle zur Beschreibung dieser Kommunikation; Schichtenmodell

• Topologie von Rechnernetzen (Bus, Stern, Ring); Internet als Kombination von Rechnernetzen

• Modellierung einfacher, nebenläufiger Prozesse, z. B. mithilfe eines Sequenzdiagramms; Möglichkeit der Verklemmung

• kritischer Abschnitt; Monitorkonzept zur Lösung des Synchronisationsproblems

• Implementierung eines Beispiels für nebenläufige Prozesse

Inf 12.3 Funktionsweise eines Rechners (ca. 17 Std.)

Am Modell der Registermaschine lernen die Schüler den grundsätzlichen Aufbau eines Computersystems und die Analogie zwischen den bisher von ihnen verwendeten Ablaufmodellen und Maschinenprogrammen kennen. So wird ihnen auch bewusst, dass Möglichkeiten und Grenzen theoretischer algorithmischer Berechnungsverfahren für die reale maschinelle Verarbeitung von Information ebenfalls gelten.

Beispiele zeigen den Schülern, wie einfache Algorithmen auf systemnaher Ebene durch Maschinenbefehle realisiert werden können. Dabei beschränken sich Anzahl und Komplexität der benutzten Maschinenbefehle auf das für die Umsetzung der gewählten Beispiele Wesentliche. Für das Verstehen des Programmablaufs ist insbesondere die in Jahrgangsstufe 10 erlernte Zustandsmodellierung eine große Hilfe. Zur Überprüfung ihrer Überlegungen setzen die Schüler eine Simulationssoftware für die Zentraleinheit ein, die die Vorgänge beim Programmablauf veranschaulicht.

• Aufbau eines Computersystems: Prozessor (Rechenwerk, Steuerwerk), Arbeitsspeicher, Ein- und Ausgabeeinheiten, Hintergrundspeicher; Datenbus, Adressbus und Steuerbus

• Registermaschine als Modell eines Daten verarbeitenden Systems (Datenregister, Befehlsregister, Befehlszähler, Statusregister); Arbeitsspeicher für Programme und Daten (von-Neumann-Architektur), Adressierung der Speicherzellen

• ausgewählte Transport-, Rechen- und Steuerbefehle einer modellhaften Registermaschine; grundsätzlicher Befehlszyklus

• Zustandsübergänge der Registermaschine als Wirkung von Befehlen

• Umsetzung von Wiederholungen und bedingten Anweisungen auf Maschinenebene

Inf 12.4 Grenzen der Berechenbarkeit (ca. 10 Std.)

Nachdem die Jugendlichen bereits erkannt haben, dass sich nicht formalisierbare Aufgabenstellungen der Bearbeitung durch eine Rechenanlage entziehen, bauen sie nun ihre Fähigkeit zur Beurteilung der Einsatzmöglichkeiten maschineller Informationsverarbeitung weiter aus. Sie vertiefen dabei ihr Bewusstsein für grundlegende Einschränkungen, denen jede auch noch so leistungsfähige Rechenanlage unterworfen ist.

Einen Einblick in die praktischen Grenzen der Berechenbarkeit gewinnen die Schüler mithilfe von Aufwandsbetrachtungen an Aufgabenstellungen wie der Wegesuche, die algorithmisch zwar vollständig lösbar sind, bei denen die Ausführung des jeweiligen Algorithmus aber nicht mit vertretbarem Zeitaufwand realisierbar ist. Den Jugendlichen wird deutlich, dass die Sicherheit moderner Verschlüsselungsverfahren auf den praktischen Grenzen der Berechenbarkeit beruht.

Anhand des Halteproblems lernen die Schüler schließlich auch prinzipielle Grenzen der Berechenbarkeit kennen. Sie sehen ein, dass es mathematisch exakt definierbare Probleme gibt, die algorithmisch und damit auch technisch unlösbar sind.

• experimentelle Abschätzung des Laufzeitaufwands typischer Algorithmen und die damit verbundenen Grenzen der praktischen Anwendbarkeit

• hoher Laufzeitaufwand als Schutz vor Entschlüsselung durch systematisches Ausprobieren aller Möglichkeiten (Brute-Force-Verfahren)

• prinzipielle Grenzen der Berechenbarkeit anhand von Plausibilitätsbetrachtungen zum Halteproblem