Identification and addressing reduction-related misconceptions

Judith Gal-Ezer, Mark Trakhtenbrot

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


Reduction is one of the key techniques used for problem-solving in computer science. In particular, in the theory of computation and complexity (TCC), mapping and polynomial reductions are used for analysis of decidability and computational complexity of problems, including the core concept of NP-completeness. Reduction is a highly abstract technique that involves revealing close non-trivial connections between problems that often seem to have nothing in common. As a result, proper understanding and application of reduction is a serious challenge for students and a source of numerous misconceptions. The main contribution of this paper is detection of such misconceptions, analysis of their roots, and proposing a way to address them in an undergraduate TCC course. Our observations suggest that the main source of the misconceptions is the false intuitive rule “the bigger is a set/problem, the harder it is to solve”. Accordingly, we developed a series of exercises for proactive prevention of these misconceptions.

שפה מקוריתאנגלית
עמודים (מ-עד)89-103
מספר עמודים15
כתב עתComputer Science Education
מספר גיליון2-3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2 יולי 2016

הערה ביבליוגרפית

Publisher Copyright:
© 2016 Informa UK Limited, trading as Taylor & Francis Group.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Identification and addressing reduction-related misconceptions'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי