1、 1 / 4上海交通大学 致远学院 2015 年秋季学期计算机科学导论课程教学说明一. 课程基本信息1开课学院（系）：致远学院2课程名称：计算机科学导论 (Introduction to Computer Science)3学时/学分：48 学时/ 3 学分4先修课程：无5上课时间：第 1 周-第 16 周；星期二第 6 节-第 8 节6上课地点：上院 200 室7任课教师：高晓沨（gao- ）8办公室及电话：电信群楼 3 号楼 328 室（34207407）9助教：朱旭东（）和吴双（）10. Office hour：周五下午 14:00-16:00，电信群楼 3-328 室二. 课程主要内容
2、（中英文）第一章 计算机科学概论（Overview of Computer Science）主要内容：概述计算机科学发展历史，了解现代计算机的发展和应用领域，掌握计算机的特点，介绍计算机科学主要学科与课程内容。重点与难点：突出介绍计算机科学的起源与发展，强调计算机科学对技术的影响，阐述课程主要目标。第二章 集合论，函数，关系（Set, Function, and Relation）主要内容：熟悉集合，函数，关系等基本概念及基本定理，并了解它们在计算机科学中的作用。重点与难点：集合悖论，关系演算，函数中的五个公理。第三章 基数/势（ Cardinality）主要内容：学习基数及其中的基本概念，掌
3、握与之相关的重要原理，并了解它们在计算机科学中的作用。重点与难点：自然数，等势，有限集/无限集，鸽巢原理等。第四章 证明（Proof ）主要内容：了解基本证明技巧，包括一般论述法、逆推法、反证法、数学归纳法等。重点与难点：理解皮亚诺公理与数学归纳法适用范围，学会一般证明方法。第五章 逻辑（Logic）2 / 4主要内容：掌握命题逻辑、谓词逻辑中的相关概念，介绍数理逻辑的发展以及其和计算机科学的关系。重点与难点：命题逻辑，谓词逻辑，迪摩根律，逻辑运算，推理演算，公理化体系。第六章 伪码（Pesudo Code）主要内容：了解程序、程序设计、程序设计语言、伪码。重点与难点：学习各类伪码的写法，包括
4、顺序、循环、选择等基本结构。第七章 图论（Graph Theory）主要内容：掌握图论的基本概念、基本理论、欧拉图与哈密尔顿圈，以及图论中的重要结论和一些基本的图论算法。重点与难点：理解图、简单图、图的度、图的连通性、图的代数表示与匹配。第八章 路（Path）主要内容：介绍路的概念，掌握路、圈、环、欧拉回路、哈密顿回路定理。重点与难点：简单图、欧拉图与哈密尔顿圈、NP 问题。第九章 树（Tree）主要内容：介绍树的概念，掌握割点与割边，理解生成树、平衡树、树的基本定理，以及树的应用和遍历。重点与难点：树的深度与广度遍历、树的六个重要定理、最小生成树、哈夫曼树、以及基本树生成算法。第十章 数据结
5、构（Data Structure）主要内容：了解数据结构及其分类、数据结构与算法的密切关系，熟悉各种常用数据结构并能尝试用数据结构进行简单算法设计。学习文件组织方法与索引技术。重点与难点：线形表、堆栈、数组、排序、递归。第十一章 算法 1（Algorithm 1）主要内容：掌握算法、算法复杂度的基本概念，学习递归与分治算法、二分搜索、Hanoi 塔算法、动态规划重点与难点：递归思想、算法与时间复杂度概念、动态规划的基本要素第十二章 算法 2（Algorithm 2）主要内容：学习贪心算法、局部搜索等常用优化算法。重点与难点：贪心算法基本要素，掌握贪心算法基本思想。局部搜索法的应用范畴第十三章
6、可计算理论（Computability Theory）主要内容：了解可计算的概念，学习抽象计算模型如图灵机、无限注册机、理解丘奇-图灵定理及哥德尔不可完备定理。3 / 4重点与难点：理解可计算的抽象意义、计算模型与可计算的问题三.课程教学进度安排（拟定）Week 教学内容 作业 课程实验1 FundamentalsSyllabus, Organization, Introduction to Computer Science Lab-012 Set, Function, and Relation Grading Policy, Set, Function, Relation, etc. Lab
7、-02FixGroup3 National Holiday.4 CardinalityDefinition, Halting problem, etc Lab-035 ProofProof by Construction/Contrapositive/Cases/Induction Lab-046 Logic (1)Epistemic logic, Muddy children problem, Propositional logic Lab-057 Logic (2)First Order Logic, Boolean Algebra, Calculations. Lab-068 Pseud
8、o CodeProgramming Language, If, While, For, Case Lab-089 GraphGraph representation, Graph coloring, Graph isomorphism, etc Lab-0910 PathEuler Path, Hamiltonian Path, Simple Graph Lab-1011 TreeTree, BFS, DFS, Spanning Tree, Kruskal, Prim, etc. Lab-1112 Data StructureLinear List, Stack, Queue, Array,
9、etc. Lab-1213 Algorithms (1)Greedy Algorithm, Dynamic Algorithm, Divide-and-Conquer Lab-1314 Algorithms (2)Heuristic Algorithm, Local Search, Optimization, etc. Lab-1415 Computational ComplexityP, NP, Reduction, Time Complexity, Space Complexity, etc. Lab-15Project Demo四.课程考核方式及说明课程内容 百分比期中考试 25%期末考
10、试 25%课后作业 30%课堂实验 10%平时成绩 10%总评 100%评分标准：90-100% A4 / 480-89% B70-79% C60-69% D59% and below F五.教材与参考书本课程以课堂笔记为主，辅以如下参考书目： 离散数学：Discrete Mathematics and Its Applications (6th Edition), Kenneth H. Rosen, McGraw-Hill Companies, 2007. 集合论：Elements of Set Theory, Herbert B. Enderton, ACADEMIC PRESS, 197
11、7 逻辑：集论与逻辑，沈恩绍，科学出版社，2001 算法：Algorithm, Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Springer NY, 2006. 自动机：Problem Solving in Automata, Languages, and Complexity, Ding-Zhu Du,Ker-I Ko, John Wiley & Sons, Inc., 2001. 可计算理论：Computability: An Introduction to Recursive Function Theory, Nigel L., Cutland, Cambridge University Press, 1980. 计算复杂性理论：Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak, Cambridge University Press, 2009.
