Informatik d indd

146
9 
Graphen und Bäume
Graphen und unter diesen speziell Bäume (Hierarchien) sind Grundkonzepte der 
Diskreten Mathematik, die in der Informatik unentbehrlich sind. Die Informatik 
braucht sie zur Beschreibung und Modellierung realer Situationen und somit zur 
Problemdarstellung, aber auch zur Darstellung von Daten, Computernetzen und 
Datenbanken und sogar von Lösungsstrategien.
Inhalt:
 Graphen und insbesondere Bäume sowie ihre speziellen Arten bilden nicht 
nur die Basis zur Darstellung von Aufgabenstellungen, sondern auch Hilfsmittel  
zu deren anschaulicher Lösung. Mittels Graphen werden Netze, Beziehungen, Pro­
gramme und viele Abläufe und Lösungsstrategien dargestellt. Die Fachgebiete Al­
gorithmik, Datenstrukturen und Datenbanken sowie Computernetze können ohne 
entsprechende Vorkenntnisse über Graphen nicht unterrichtet werden. Empfeh­
lenswert ist es, in einer kleinen Unterrichtssequenz die Graphen (mit Fokus auf 
Bäume) vorzustellen. Alle weiteren Eigenschaften dieser Strukturen können dort 
entdeckt werden, wo diese gebraucht werden.
10 
Testen und Verifikation
Alle Produkte der technischen Wissenschaften erfordern die Überprüfung ihrer 
 korrekten Funktionalität. Dies bezieht sich besonders auch auf alle Software­  
und kombinierten Software­Hardware­Produkte. Im Softwarebereich wird in diesem 
Zusammenhang von Verifikation gesprochen. Verifikation will die Korrektheit eines 
Programms nachweisen. Dieses Konzept hat die Informatik sorgfältig ausgearbeitet 
und präzisiert und dafür eigene Instrumente entwickelt.
Weil ausser in wenigen, sehr einfachen Fällen die Verifikation nicht automati­
sierbar ist (es gibt keinen Algorithmus, der die Korrektheit anderer Programme 
verifizieren kann), greifen die Informatikfachleute oft auf das Testen zurück. Hier 
ist das Ziel nicht mehr, die Korrektheit der Programme zu beweisen, sondern syste­
matisch und mit hoher Wahrscheinlichkeit mögliche Programmfehler durch viele 
Testläufe aufgrund einer intelligent gewählten Sammlung von Testdaten zu ent­
decken.
Inhalt:
 Das Testen und die Verifikation gehören zu den grundlegenden Konzepten 
aller technischen Wissenschaften. Verifizieren bedeutet zu beweisen, dass die her­
gestellten Produkte die angestrebten Spezifikationen erfüllen oder die gewünsch­
ten Eigenschaften aufweisen. Testen beinhaltet die Fehlersuche mittels gut ge­
Konzepte und Inhalte eines Fachs Informatik

---

147
planter Testläufe. Diese Konzepte können im Rahmen des Programmierens, beim 
Entwurf von Schaltkreisen und endlichen Automaten oder beim Algorithmenent­
wurf eingeführt werden. Für die Verifikation ist die Logik, insbesondere die korrek­
te Beweisführung, das Basisinstrument.
Im Bereich der Programmiersprachen bietet sich für Fortgeschrittene eine Ein­
führung in den Compilerbau an, wo Automaten und kontextfreie Grammatiken zur 
lexikalischen und syntaktischen Analyse ganz einfacher Programmiersprachen ver­
wendet werden.
11 
Modularer Entwurf von komplexen Systemen
Der modulare Entwurf ist ein Grundkonzept aller konstruktiven technischen Diszi­
plinen. Die Idee besteht darin, kleine Einheiten mit einfacher Funktionalität zu 
bauen und deren Korrektheit mit vertretbarem Aufwand zu überprüfen. Danach 
werden diese geprüften Module als Bausteine zum Bau von komplexeren Systemen 
benutzt, die wiederum als Bausteine zum Entwurf noch komplexerer Systeme ver­
wendet werden usw. Die Informatik hat diesen Prozess mathematisch genau formu­
liert und zu einem hohen Grad automatisiert. Die Methode wird zum Beispiel beim 
Programmieren, beim Entwurf von Algorithmen, bei der Softwareentwicklung und 
beim Entwurf von Schaltkreisen eingesetzt.
Inhalt:
 Der modulare Entwurf ist die wichtigste methodische Hilfe für jede Art von 
konstruktiver Tätigkeit, sogar für das Lernen selbst. Das Prinzip des modularen 
Aufbaus zu verstehen und systematisch anzuwenden, ist eine Erkenntnis, die weit 
über das Gebiet der Informatik hinaus von grossem Wert ist. In der Informatik ist 
jedoch die modulare Vorgehensweise besonders leicht greifbar und darstellbar. Sie 
kann bereits beim Programmieren mithilfe von Unterprogrammen eingeführt wer­
den. Später bieten die Automatentheorie, der Schaltkreisentwurf, «Teile und herr­
sche» in Algorithmik und das objektorientierte Programmieren weitere Möglichkei­
ten, dieses Konzept zu prägen. 
12 
Rekursion (rekursive Programme 
 
und «Teile und herrsche»)
Rekursivität bedeutet in einem Programm, dass dieses sich selbst aufruft, dabei 
aber andere (typischerweise kleinere) Datensätze bearbeitet, bis nichts Kleineres 
mehr zu bearbeiten ist. Der rekursive Ansatz ist ein zentrales Instrument der Pro­
Konzepte und Inhalte eines Fachs Informatik

---

148
grammiertechnik und der Algorithmik, insbesondere dann, wenn die Lösung eines 
Problems aus der Lösung seiner Teilprobleme zusammengesetzt werden kann. In 
diesem Spezialfall spricht man von der Methode «Teile und herrsche». Rekursives 
Vorgehen wird auch für eine alternative Definition des Begriffs des Algorithmus 
verwendet. Die Rekursivität ist stark verbunden mit dem Konzept des Stapels, einer 
der wichtigsten Datenstrukturen der Informatik.
Inhalt:
 Rekursive Programme – und ihre Implementierung mithilfe des Stapels als 
Datenstruktur – gehören zum fortgeschrittenen Programmieren sowie zum Ver­
ständnis der Grenzen der Berechenbarkeit. Sie liefern auch gute Verknüpfungen 
zur Darstellung der Funktionen in der Mathematik. Besonders gut eignen sich jene 
Problemstellungen für rekursive Lösungswege, wo eine komplexe Aufgabe mit kur­
zen Programmen gelöst werden kann. Unterrichten kann man die Rekursion in der 
Algorithmik zum Beispiel bei der Implementierung der Methode «Teile und herr­
sche» oder beim Zeichnen von Funktionen.
13 Suche
Ob für das Suchen im Internet, in gut organisierten Datenbanken oder in sortierten 
Folgen, überall sind dafür Suchalgorithmen notwendig, die schnell die gewünsch­
ten Informationen finden. Eine andere Fragestellung sucht nach allen möglichen 
Lösungen für ein gegebenes Problem. Suchverfahren gibt es viele, wobei die binäre 
Suche, die lokale Suche und das Rücksetzverfahren (Backtracking) nebst anderen 
zu Basisalgorithmen in unzähligen Anwendungen geworden sind.
Inhalt:
 Sortieren und Suchen dominieren viele Anwendungen. Keine anderen Algo­
rithmen laufen so häufig wie Such­ und Sortieralgorithmen. Zu den einfachsten 
Verfahren zählt die binäre Suche in sortierten Folgen. Fortfahren kann man mit der 
Suche in gut strukturierten Datenbanken samt Prüfung ihrer Effizienz. Suchstrate­
gien lassen sich aber auch im Internet und bei der Lösung von diskreten Optimie­
rungsproblemen thematisieren.
14 Skalierbarkeit
Die Skalierbarkeit misst die Fähigkeit von Programmen, den mit der Datenmenge 
wachsenden Rechenaufwand für grosse Probleme effizient zu bewältigen. Solche 
Probleme sind typisch für die Softwaretechnik und das wissenschaftliche Rechnen. 
Dieses Konzept ist stark verknüpft mit dem Algorithmenentwurf und der Berech­
Konzepte und Inhalte eines Fachs Informatik

---