Teaching NP completeness in secondary schools

In this paper, we show how the theory of NP completeness can be introduced to students in secondary schools. The motivation of this research is that although there are difficult issues that require technical backgrounds, students are already familiar with demanding computational problems through games such as Sudoku or Tetris. Our intention is to bring together important concepts in the theory of NP completeness in such a way that students in secondary schools can easily understand them. This is part of our ongoing research about how to teach fundamental issues in Computer Science in secondary schools. We discuss what needs to be taught in which sequence in order to introduce ideas behind NP completeness to students without technical backgrounds.

Metadaten
Verfasserangaben:	Seungyon Kim, Seongbin Park
URN:	urn:nbn:de:kobv:517-opus-64476
ISSN:	1868-0844
ISSN:	2191-1940
Titel des übergeordneten Werks (Deutsch):	Commentarii informaticae didacticae : (CID)
Verlag:	Universitätsverlag Potsdam
Verlagsort:	Potsdam
Publikationstyp:	Wissenschaftlicher Artikel
Sprache:	Englisch
Erscheinungsjahr:	2013
Veröffentlichende Institution:	Universität Potsdam
Datum der Freischaltung:	28.02.2013
Ausgabe:	6
Seitenanzahl:	4
Erste Seite:	35
Letzte Seite:	38
Quelle:	Informatics in schools : local proceedings of the 6th International Conference ISSEP 2013 ; selected papers ; Oldenburg, Germany, February 26–March 2, 2013/Diethelm et al. (Eds.)/ Potsdam: Universitätsverlag Potsdam, 2013/ S. 35-38
Organisationseinheiten:	Extern / Extern
DDC-Klassifikation:	0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Sammlung(en):	Universität Potsdam / Schriftenreihen / Commentarii informaticae didacticae (CID) / CID (2013) 06
	Universität Potsdam / Schriftenreihen / Commentarii informaticae didacticae (CID) / CID (2013) 06 / Towards Programming Competences
Lizenz (Deutsch):	Creative Commons - Namensnennung, 3.0 Deutschland