计算机科学导论cs上海交通大学
上海交通大学 致远学院 2014年季学期
课程教学说明
课程基本信息
学院(系):致远学院
课程名称： ()
学时/学分：学时/学时/学分 学分
上课时间：
上课地点：
任课教师：longhuan@sjtu.edu.cn)
办公室和电话
助教：Office hour：
课程主要内容()
计算机科学概论(Overview of Computer Science)
主要内容：总结计算机科学的发展历史，了解现代计算机的发展和应用领域，掌握计算机的特点，介绍计算机科学的主要学科和课程内容。
重点和难点：突出计算机科学的起源和发展，强调计算机科学对技术的影响，阐述课程的主要目标。
集合论、函数、关系(Set, Function, and Relation)
主要内容：熟悉集合、函数、关系等基本概念和定理，了解它们在计算机科学中的作用。
重点与难点：集合悖论、关系计算、函数中的五个公理。
基数/势(Cardinality)
主要内容：学习基础和基本概念，掌握相关的重要原则，了解其在计算机科学中的作用。
重点和难点:自然数、等势、有限集/无限集、鸽巢原理等。
逻辑(Logic)
主要内容：掌握命题逻辑和谓词逻辑的相关概念，介绍数学逻辑及其与计算机科学的关系。
重点与难点：命题逻辑、谓词逻辑、迪摩根律、逻辑运算、逻辑等值、推理演算、公理化体系、范式。
代数(Algebra)
主要内容：理解计算机科学中抽象代数的概念、子群、循环群、排列群和应用。
重点与难点：了解伽罗瓦理论、李代数、有限域等概念及相关属性。
概率(Probabilistic)
主要内容：了解概率在计算机科学中的作用，学习贝叶斯规则、离散随机变量、期望、概率统计方法等知识点。
重点和难点：理解和确定多项式、概率算法、霍尔问题等。
数论(Number Theory)
主要内容：了解数学理论在计算机科学中的作用，掌握基本概念，如排除理论、不确定方程、同余方程、同余方程、二次同余平方剩余、原根指标和连接分数。
重点和难点：整数可去除性的基本概念和理论Security and Cryptology)
主要内容：介绍密码学的基本概念，掌握加密、解密的基本原理，以及一些基本的攻击和防御方法。
重点和难点：了解加解密、攻击/检测的基本过程。
图论(Graph Theory)
主要内容：掌握图论的基本概念、基本理论、欧拉图和哈密尔顿圈，以及图论中的重要结论和一些基本图论算法。
重点和难点:理解图、简单图、图的程度、图的连接性、图的代数表示和匹配、欧拉图和哈密尔顿圈。
树(Tree)
主要内容：介绍树的概念，掌握切割点和切割边缘，了解生成树、平衡树、树的基本定理，以及树的应用和遍历。
重点和难点：树的深度和广度遍历、六个重要定理、最小生成树、哈夫曼树和基本生成算法。
数据结构(Data Structure)
主要内容：了解数据结构及其分类、数据结构与算法的密切关系，熟悉各种常见的数据结构，并尝试使用数据结构进行简单的算法设计。学习文件组织方法和索引技术。
重点和难点：线形表、堆栈、数组、排序、递归。
算法1(Algorithm 1)
主要内容：掌握算法、算法复杂性的基本概念，学习递归分治算法、二分搜索、Hanoi塔算法，动态规划
重点和难点：递归思想、算法和时间复杂性概念、动态规划的基本要素
算法2(Algorithm 2)
主要内容：学习常用的优化算法，如贪婪算法和局部搜索。
重点和难点：贪婪算法的基本要素，掌握贪婪算法的基本思想。局部搜索法的应用范围
可计算理论(Computability Theory)
主要内容：了解可计算概念，学习图灵机、无限注册机、丘奇图灵定理、哥德尔不完整定理等抽象计算模型。
重点和难点：理解抽象意义、模型和问题
自动机与计算复杂性理论(Automata and Computational Complexity)
主要内容：学习确定型自动机、非确定型自动机、计算复杂性理论P与NP概念和复杂分类的意义。
重点和难点：了解自动机、图灵机和计算复杂性理论的意义，判断问题的复杂性，学习归约技术。
安排课程教学进度
第一部分，基础篇 (Part 1: Fundamentals)Week教学内容作业课程实验1Fundamentals
Syllabus, Organization, Introduction to Computer ScienceLab-01Fix
Group2Set, Function, and Relation
Grading Policy, Set, Function, Relation, etc.Lab-023National Holi