《计算机科学导论》课程大纲.PDF

《计算机科学导论》课程大纲 上海交通大学致远学院 一、课程简介 课程名称： 计算机科学导论 学时/学分： 48 学时/3 学分 英文名称： Introduction to Computer Science 主讲教师： 高晓沨、阮娜 面向对象： 大学一年级本科生 先修课程： 无 教学目标： 本课程为图灵奖获得者、美国康奈尔大学教授John Hopcroft 博士于2012 年1 月在上 海交通大学开设的一门基础导论课程，双语教学，教学对象为数学、物理专业以及理工科 非计算机专业大学一年级本科生，目的是引导学生学习了解计算机科学的发展历史、知识 结构、以及核心科学技术，使学生初步了解计算机的基础知识，并掌握理论计算机科学的 相关内容。整体课程内容广泛浅显，能够培养学生的计算机文化意识，使学生掌握在信息 社会里更好地工作、学习和生活所必须的计算机基础知识与基本技能，并能深入了解计算 机科学的脉络，激发学生对计算机科学的兴趣。 主要内容： 本课程分为理论篇与技术篇两个部分，第一部分主要介绍计算机科学理论的数学基础， 包括数理逻辑、集合论、代数、数论与密码学，每个部分按照不同内容进行分类介绍，延 续历史发展的时序，系统介绍这些学科的发展以及其在计算机科学中的重要影响；第二部 分主要介绍计算机科学重要的基础与技术，包括数据结构、网络与图论、算法、自动机原 理以及计算复杂性的概念，并辅以大量实例介绍计算机科学技术。两部分内容顺序递进， 涵盖广泛，重点突出对计算机科学领域发展最为重要的基础知识与技术，使学生对计算机 科学这一领域有一个全局性了解，为进一步学习打下坚实的基础。本课程亦包含一项实践 作业，通过训练与实践让学生切身学习了解计算机科学技术。 二、教学内容 第1讲 计算机科学概论 （Overview of Computer Science） 主要内容：概述计算机科学发展历史，了解现代计算机的发展和应用领域，掌握计算机 的特点，介绍计算机科学主要学科与课程内容。 重点与难点：突出介绍计算机科学的起源与发展，强调计算机科学对技术的影响，阐述 课程主要目标。 第2讲 集合论，函数，关系（Set, Function, and Relation） 主要内容：熟悉集合，函数，关系等基本概念及基本定理，并了解它们在计算机科学中 的作用。 第1 页 / 共5 页 重点与难点：集合悖论，关系演算，函数中的五个公理。 第3讲 基数/势 （Cardinality） 主要内容：学习基数及其中的基本概念，掌握与之相关的重要原理，并了解它们在计算 机科学中的作用。 重点与难点：自然数，等势，有限集/无限集，鸽巢原理等。 第4讲 实践作业 （Project in National Holiday ） 主要内容：根据当前计算机领域的研究热点和关注方向设计三人一组实践作业，锻炼学 生的计算机实践能力与团队合作能力。 重点与难点：解题与报告撰写、团队合作。 第5讲 逻辑（Logic ） 主要内容：掌握命题逻辑、谓词逻辑中的相关概念，介绍数理逻辑的发展以及其和计算 机科学的关系。 重点与难点：命题逻辑，谓词逻辑，迪摩根律，逻辑运算，逻辑等值，推理演算，公理 化体系，范式。 第6讲 代数（Algebra ） 主要内容：理解群，子群，循环群，排列群的概念，以及抽象代数在计算机科学的应用。 重点与难点：理解伽罗瓦理论，李代数，有限域等概念，以及相关属性。 第7讲 概率（Probabilistic ） 主要内容：了解概率在计算机科学中的作用，学习贝叶斯规则，离散随机变量，期望， 概率统计方法等知识点。 重点与难点：理解确定多项式，概率算法，霍尔问题等。 第8讲 数论（Number Theory ） 主要内容：了解数论在计算机科学中的作用，掌握整除理论、不定方程、同余、同余方 程、二次同余式与平方剩余、原根与指标以及连分数等基本概念。 重点与难点：整数的可除性的基本概念和理论，同余的概念及其基本性质，欧拉定理、费 马小定理及其对循环小数的应用。 第9讲 安全和密码学 （Security and Cry