In today's information society it has become ordinary for students to use computers to study. Educational software is increasingly being developed for all kinds of subjects and school levels. Although a broad range of computer science areas is covered, topics that admit intuitively meaningful graphic representations are almost exclusively considered. Mathematically abstract topics that are more di±cult to present, as well as to understand, still challenge our ability to create effective computer support. The theory of NP-completeness in particular has been almost neglected by educational software, despite its importance in the theory of computation and in computer science education. Yet it is precisely in such a highly specialized, abstract topic that computer-based learning environments might do their best job.
In this thesis we have developed GraphBench, a highly interactive learning environment for the theory of NP-completeness. GraphBench, as well as the techniques and principles on which it is built, is the main contribution of this dissertation. Our software provides students with an intuitive approach to an otherwise abstract and complex topic. GraphBench features eight different NP-complete problems and nine different polynomial time reductions. Our software offers separate environments for all featured NP-complete problems and polynomial time reductions.
GraphBench combines traditional didactic with new computer-based ap- proaches to foster an intuitive understanding of the basic underlying concepts. In this thesis we identify di±culties that arise when developing educational software for abstract topics and present several didactic concepts and imple- mentation approaches to overcome them.
We have successfully used GraphBench in various courses on the theory of computation at the Swiss Federal Institute of Technology ETH, at the National University of Singapore and at the Free University of Bolzano. The highly positive feedback from professors and students justifies our approach and shows the need for learning environments for highly specialized, abstract topics.

In der heutigen Informationsgesellschaft sind sich Studenten gewohnt mit Hilfe von Computern zu lernen. Die Auswahl an Lernprogrammen nimmt für alle Themen und Schulstufen stetig zu. Obwohl ein breiter Bereich der Informatik abgedeckt ist, werden Themen die intuitive, grafisch aussagekräftige Visualisierungen zulassen bevorzugt. Mathematisch abstrakte Themen, die sowohl anspruchsvoller zu präsentieren, als auch zu verstehen sind, stellen immer noch eine Herausforderung für wirkungsvolle Computerunterstützung dar. Die Theorie der NP-Vollständigkeit ist ein Beispiel eines Themas, welches von Lernsoftware beinahe vollständig vernachlässigt worden ist. Dies trotz ihrer Wichtigkeit in der theoretischen Informatik und in der Informatikausbildung.
Dabei könnten gerade bei einem solchen hochgradig spezialisierten, abstrakten Thema Lernumgebungen die besten Resultate erzielen. Im Rahmen dieser Arbeit haben wir GraphBench entwickelt, eine hochgradig interaktive Lernumgebung für NP-Vollständigkeit. GraphBench, wie auch die zugrunde liegenden Technologien und Prinzipien, stellen die Hauptbeiträge dieser Dissertation. Die Lernumgebung bietet eine intuitive Einführung in ein sonst abstraktes und komplexes Thema. GraphBench beinhaltet acht verschiedene NP-vollständige Probleme und neun verschiedene Reduktionen. Die Lernumgebung bietet separate Umgebungen für alle NP-vollständigen Probleme und Reduktionen.
GraphBench verbindet traditionelle didaktische und neue computergestützte Ansätze um ein intuitives Verständnis grundlegender Konzepte zu vermitteln. Wir haben Schwierigkeiten die beim Entwickeln von Lernumgebungen für abstrakte Themen auftreten identifiziert und präsentieren verschiedene didaktische Konzepte und Implementierungsansätze um diese zu überwinden.
Wir haben GraphBench erfolgreich in Vorlesungen zur theoretischen Informatik an der ETH Zürich, der National University of Singapore und der Freien Universität Bozen eingesetzt. Die sehr positiven Rückmeldungen von Professoren und Studenten bestätigen unseren Ansatz und zeigen die Notwendigkeit von Lernumgebungen für spezialisierte, abstrakte Themen.