摘要
阐述了计算理论(可计算性与计算机复杂性理论)中的几个典型问题,以图灵机模型、停机问题、近似算法及装箱问题等为例从不同角度分析计算理论与计算思维的密切联系,强调计算机专业实践教学中计算思维能力培养的必要性。
Generalized computation theories include algorithms,computational complexity theory,computability theory,automata theory,and formal language theory.This paper discusses several typical problems in computation theory （computability theory and complexity theory） and reveals the importance of computational thinking in practical teaching.We elaborate the relation between computation theory and computer science from different perspectives.And then we describe Turing machine model and reveals the essential relation between Turing machine model and computational thinking.In addition,we discuss time complexity and space complexity in computer science,explain approximation algorithm,using packing problem examples.Finally,we emphasize the importance of computation theory in computer science education.
出处
《计算机工程与科学》
CSCD
北大核心
2014年第A02期88-91,共4页
Computer Engineering & Science
关键词
可计算性
计算复杂性
计算思维
computability
computational complexity
computational thinking
computer science
