Schwierige Probleme in der Informatik

Verfasst von Nicolas Born

Inhalt	Entdeckung von schwierigen (NP-vollständigen) Problemen der theoretischen Informatik
Voraussetzung	Kenntnis des Begriffs Algorithmus, Englischgrundkenntnisse zur Bedienung von GraphBench
Schultyp	Gymnasium, Informatikstudium (Einführung in die theoretische Informatik)
Dauer	3 - 4 Lektionen

Worum geht es?

Die Schüler entdecken mit Hilfe der Software GraphBench NP-vollständige Probleme und mögliche Lösungsalgorithmen. Je nach Interesse untersuchen sie Laufzeitaspekte, Extremfälle, Korrektheit, Anwendungen in der Realität oder entwerfen gar eigene Algorithmen.

Das Material umfasst die Dokumente für das gelenkte entdeckende Lernen sowie einen Lehrtext. Der Lehrtext bietet eine Einführung in die Komplexitätstheorie, ist aber für das entdeckende Lernen nicht notwendig.

Downloads

	Information für die Lehrperson	PDF [181 KB] · Word [199 KB]
	Information für die Schüler/innen	PDF [907 KB] · Word [966 KB]
	Liste der Probleme in GraphBench	PDF [228 KB] · Word [531 KB]

Links