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
مستوى الصوت26
رقم الإصدار2-3
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2 يوليو 2016

ملاحظة ببليوغرافية

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

بصمة

أدرس بدقة موضوعات البحث “Identification and addressing reduction-related misconceptions'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا