Für die Art, wie Daten gespeichert werden, haben sich Strukturen etabliert – so genannte Datenstrukturen. Die Schülerinnen und Schüler lernen die abstrakt erscheinenden Strukturen Liste, Baum und Graph kennen und entdecken, dass sie sich in zahlreichen Beispielen in unserem Alltag wiederfinden.
Die Graphentheorie ist in der Informatik von großer Bedeutung, um netzartige Strukturen wie Straßen-, Versorgungs- und Computernetze oder soziale Strukturen zu untersuchen. Mit dem so genannten Briefträgerproblem, dem Problem des Handlungsreisenden und dem Problem minimaler Spannbäume lernen die Schülerinnen und Schüler alltagsrelevante Problemstellungen kennen, die mit Hilfe der Graphentheorie gelöst werden können.
Dabei wenden sie mit dem Kruskal-Algorithmus und der Multiple-Fragment-Heuristik zwei Standard-Verfahren der Informatik an.
108 Arbeitskarten DIN A4 im Ordner
