Das Entscheidungsproblem der Knotenüberdeckung (Leitprogrammartige Unterrichtsunterlagen)

Main content

Autor
Jörg Bader

Akkordeon. Mit Tab zu Einträgen navigieren, dann Inhalt mit Enter auf und zuklappen.

 

Inhalt und Lernziele

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.

Dauer

ca. 6 Lektionen

Vorwissen

  • 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).

Download

Weitere Informationen zur Unterrichtseiheit

Schlagwörter Knotenüberdeckung, Entscheidungsproblem, Optimierungsproblem, Graphentheorie, Graphenalgorithmen
Fachgebiet Algorithmen und Datenstrukturen
Schultyp, Schulstufe Gymnasium
Sprache deutsch
Entstehung der Unterrichtseinheit November 2016
 
 
URL der Seite: http://www.educ.ethz.ch/unterrichtsmaterialien/informatik/entscheidungsproblem.html
Sun Apr 23 23:40:26 CEST 2017
© 2017 Eidgenössische Technische Hochschule Zürich