Das Entscheidungsproblem der Knotenüberdeckung (Leitprogrammartige Unterrichtsunterlagen)

Autor
Jörg Bader

Die vorliegenden Unterrichtsunterlagen untersuchen das Knotenüberdeckungsproblem von zwei Aspekten aus: als Entscheidungsproblem und als Optimierungsproblem. Bei der Formulierung von Berechnungsproblemen und deren Einordnung in Komplexitätsklassen sind diese beiden Begriffe der theoretischen Informatik von wichtiger Bedeutung. Die Behandlung dieses Themengebiets im Unterricht schult die überfachliche Kompetenz des algorithmischen Denkens. Durch das anschauliche Beispiel der Knotenüberdeckung werden die Formalismen den Schülerinnen und Schülern leichter zugänglich gemacht, während sie an das Begriffsfeld herangeführt werden.

ca. 6 Lektionen

  • Die SuS kennen die grundlegenden Begriffe der Graphentheorie (Knoten und Kanten in ungerichteten einfachen Graphen)
  • Die SuS kennen einzelne effizient lösbare Optimierungsprobleme der Graphentheorie mit entsprechenden Algorithmen,  insbesondere minimale Spannbäume.
  • Die SuS können Komplexitätsbetrachtungen an Pseudocode-Algorithmen anstellen.
  • Die SuS sind vertraut mit einer höheren Programmiersprache (z. B. Pascal, Java oder Python).
JavaScript wurde auf Ihrem Browser deaktiviert