重点与难点 : 集合悖论, 关系演算, 函数中的五个公理第 3 讲基数 / 势 (Cardinality) 主要内容 : 学习基数及其中的基本概念, 掌握与之相关的重要原理, 并了解它们在计算机科学中的作用重点与难点 : 自然数, 等势, 有限集 / 无限集, 鸽巢原理等第 4 讲实践作业 (

Size: px

Start display at page:

Download "重点与难点 : 集合悖论, 关系演算, 函数中的五个公理第 3 讲基数 / 势 (Cardinality) 主要内容 : 学习基数及其中的基本概念, 掌握与之相关的重要原理, 并了解它们在计算机科学中的作用重点与难点 : 自然数, 等势, 有限集 / 无限集, 鸽巢原理等第 4 讲实践作业 ("

伯融
7 years ago
Views:

1 一课程简介计算机科学导论课程大纲上海交通大学致远学院课程名称 : 计算机科学导论学时 / 学分 : 48 学时 /3 学分英文名称 : Introduction to Computer Science 主讲教师 : 高晓沨阮娜面向对象 : 大学一年级本科生先修课程 : 无教学目标 : 本课程为图灵奖获得者美国康奈尔大学教授 John Hopcroft 博士于 2012 年 1 月在上海交通大学开设的一门基础导论课程, 双语教学, 教学对象为数学物理专业以及理工科非计算机专业大学一年级本科生, 目的是引导学生学习了解计算机科学的发展历史知识结构以及核心科学技术, 使学生初步了解计算机的基础知识, 并掌握理论计算机科学的相关内容整体课程内容广泛浅显, 能够培养学生的计算机文化意识, 使学生掌握在信息社会里更好地工作学习和生活所必须的计算机基础知识与基本技能, 并能深入了解计算机科学的脉络, 激发学生对计算机科学的兴趣主要内容 : 本课程分为理论篇与技术篇两个部分, 第一部分主要介绍计算机科学理论的数学基础, 包括数理逻辑集合论代数数论与密码学, 每个部分按照不同内容进行分类介绍, 延续历史发展的时序, 系统介绍这些学科的发展以及其在计算机科学中的重要影响 ; 第二部分主要介绍计算机科学重要的基础与技术, 包括数据结构网络与图论算法自动机原理以及计算复杂性的概念, 并辅以大量实例介绍计算机科学技术两部分内容顺序递进, 涵盖广泛, 重点突出对计算机科学领域发展最为重要的基础知识与技术, 使学生对计算机科学这一领域有一个全局性了解, 为进一步学习打下坚实的基础本课程亦包含一项实践作业, 通过训练与实践让学生切身学习了解计算机科学技术二教学内容第 1 讲计算机科学概论 (Overview of Computer Science) 主要内容 : 概述计算机科学发展历史, 了解现代计算机的发展和应用领域, 掌握计算机的特点, 介绍计算机科学主要学科与课程内容重点与难点 : 突出介绍计算机科学的起源与发展, 强调计算机科学对技术的影响, 阐述课程主要目标第 2 讲集合论, 函数, 关系 (Set, Function, and Relation) 主要内容 : 熟悉集合, 函数, 关系等基本概念及基本定理, 并了解它们在计算机科学中的作用第 1 页 / 共 5 页

2 重点与难点 : 集合悖论, 关系演算, 函数中的五个公理第 3 讲基数 / 势 (Cardinality) 主要内容 : 学习基数及其中的基本概念, 掌握与之相关的重要原理, 并了解它们在计算机科学中的作用重点与难点 : 自然数, 等势, 有限集 / 无限集, 鸽巢原理等第 4 讲实践作业 (Project in National Holiday) 主要内容 : 根据当前计算机领域的研究热点和关注方向设计三人一组实践作业, 锻炼学生的计算机实践能力与团队合作能力重点与难点 : 解题与报告撰写团队合作第 5 讲逻辑 (Logic) 主要内容 : 掌握命题逻辑谓词逻辑中的相关概念, 介绍数理逻辑的发展以及其和计算机科学的关系重点与难点 : 命题逻辑, 谓词逻辑, 迪摩根律, 逻辑运算, 逻辑等值, 推理演算, 公理化体系, 范式第 6 讲代数 (Algebra) 主要内容 : 理解群, 子群, 循环群, 排列群的概念, 以及抽象代数在计算机科学的应用重点与难点 : 理解伽罗瓦理论, 李代数, 有限域等概念, 以及相关属性第 7 讲概率 (Probabilistic) 主要内容 : 了解概率在计算机科学中的作用, 学习贝叶斯规则, 离散随机变量, 期望, 概率统计方法等知识点重点与难点 : 理解确定多项式, 概率算法, 霍尔问题等第 8 讲数论 (Number Theory) 主要内容 : 了解数论在计算机科学中的作用, 掌握整除理论不定方程同余同余方程二次同余式与平方剩余原根与指标以及连分数等基本概念重点与难点 : 整数的可除性的基本概念和理论, 同余的概念及其基本性质, 欧拉定理费马小定理及其对循环小数的应用第 9 讲安全和密码学 (Security and Cryptology) 主要内容 : 介绍密码学的基本概念, 掌握加密, 解密的基本原理, 以及一些基本的攻击和防御方法重点与难点 : 理解加解密, 攻击 / 检测的基本过程第 2 页 / 共 5 页

3 第 10 讲图论 (Graph Theory) 主要内容 : 掌握图论的基本概念基本理论欧拉图与哈密尔顿圈, 以及图论中的重要结论和一些基本的图论算法重点与难点 : 理解图简单图图的度图的连通性图的代数表示与匹配欧拉图与哈密尔顿圈第 11 讲树 (Tree) 主要内容 : 介绍树的概念, 掌握割点与割边, 理解生成树平衡树树的基本定理, 以及树的应用和遍历重点与难点 : 树的深度与广度遍历树的六个重要定理最小生成树哈夫曼树以及基本树生成算法第 12 讲数据结构 (Data Structure) 主要内容 : 了解数据结构及其分类数据结构与算法的密切关系, 熟悉各种常用数据结构并能尝试用数据结构进行简单算法设计学习文件组织方法与索引技术重点与难点 : 线形表堆栈数组排序递归第 13 讲算法 1(Algorithm 1) 主要内容 : 掌握算法算法复杂度的基本概念, 学习递归与分治算法二分搜索 Hanoi 塔算法动态规划重点与难点 : 递归思想算法与时间复杂度概念动态规划的基本要素第 14 讲算法 2(Algorithm 2) 主要内容 : 学习贪心算法局部搜索等常用优化算法重点与难点 : 贪心算法基本要素, 掌握贪心算法基本思想局部搜索法的应用范畴第 15 讲可计算理论 (Computability Theory) 主要内容 : 了解可计算的概念, 学习抽象计算模型如图灵机无限注册机理解丘奇 - 图灵定理及哥德尔不可完备定理重点与难点 : 理解可计算的抽象意义计算模型与可计算的问题第 16 讲自动机与计算复杂性理论 (Automata and Computational Complexity) 主要内容 : 学习确定型自动机非确定型自动机计算复杂性理论 P 与 NP 的概念和复杂性分类的意义重点与难点 : 理解自动机图灵机与计算复杂性理论的意义, 判断问题的复杂性学习归约技术第 3 页 / 共 5 页

4 三教学进度安排第一部分基础篇 (Part 1: Fundamentals) Week 教学内容作业课程实验 Fundamentals Syllabus, Organization, Introduction to Computer Science Set, Function, and Relation Grading Policy, Set, Function, Relation, etc. Cardinality Definition, Halting problem, etc 4 National Holiday Logic Epistemic logic, Muddy children problem, Propositional logic Algebra Group, Ring, Field, Abel Group, Monoid, etc. Probabilistic Birthday problem, Hashing collision, Union bound, etc. Number Theory Divisibility, Modular Arithmetic, Chinese remainder theorem. Security and Cryptology Encryption, Cryptology, Security, etc. 第二部分技术篇 (Part 2: Technologies) Graph Graph representation, Graph coloring, Graph isomorphism, etc Tree Tree, BFS, DFS, Spanning Tree, Kruskal, Prim, etc. Data Structure Linear List, Stack, Queue, Array, etc. Algorithms (1) Greedy Algorithm, Dynamic Algorithm, Divide-and-Conquer Algorithms (2) Heuristic Algorithm, Local Search, Optimization, etc. Computational Complexity P, NP, Reduction, Time Complexity, Space Complexity, etc. Automata, Language, and Computability, Final Review Turing Machine, Church-Turing Thesis, Recursive Function Lab-01 Lab-02 Lab-03 Lab-04 Lab-05 Lab-06 Lab-07 Lab-08 Lab-09 Lab-10 Lab-11 Lab-12 Lab-13 Lab-14 Lab-15 Fix Group Training Release Project 第 4 页 / 共 5 页

5 四课程考核及说明课程内容百分比期中考试 25% 期末考试 25% 课后作业 20% 课堂实验 20% 平时成绩 10% 总评 100% 评分标准 : % A 80-89% B 70-79% C 60-69% D 59% and below F 五教材与参考书本课程以课堂笔记为主, 辅以如下参考书目 : 离散数学 : Discrete Mathematics and Its Applications (6th Edition), Kenneth H. Rosen, McGraw-Hill Companies, 集合论 :Elements of Set Theory, Herbert B. Enderton, ACADEMIC PRESS, 1977 逻辑 : 集论与逻辑, 沈恩绍, 科学出版社,2001 算法 :Algorithm, Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Springer NY, 自动机 : Problem Solving in Automata, Languages, and Complexity, Ding-Zhu Du,Ker-I Ko, John Wiley & Sons, Inc., 可计算理论 :Computability: An Introduction to Recursive Function Theory, Nigel L., Cutland, Cambridge University Press, 计算复杂性理论 :Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak, Cambridge University Press, 第 5 页 / 共 5 页

XXX专业本科人才培养方案

XXX专业本科人才培养方案计算机科学与技术专业本科人才培养方案 (Computer Science and Technology 080901) 一培养目标本专业培养德智体美全面发展, 具有良好的科学与人文素养, 熟悉经济管理法律等相关基础知识, 系统地掌握计算机硬件软件方面的基