北大《计算概论》课程教学大纲

《计算概论》课程教学大纲《计算概论》课程是北京大学面向全校理科专业（理学、工学和医学）一年级学生进行计算机基础教育的特色课程，是北京大学信息科学技术学院开设的选课人数最多的主干基础课（每年有2000余人选修本课程）。针对本课程涉及的专业多、选课学生多的特点，在许卓群、代亚非等老师的主持下，经过十余年的建设，本课程已逐渐形成了“立足基础、因材施教、强化实践”的教学理念。首先，按专业分2个层次建设课程，为“电子信息科学类”专业提供《计算概论A》课程，为其他理科专业提供《计算概论B》课程；不同的层次，课程内容深度会有所不同；同时，面向不同的专业背景，在教学和实习内容设计上也会有不同的针对性。其次，根据学生的基础不同实现分班教学：对于“电子信息科学类”类专业，基础好、领悟力强的学生给予实验班教学，大部分学生在普通班学习，为基础较差的学生开设辅导班个别辅导；对于其他理科专业，则分通选课（供各院系基础好的学生选修）、元培班（北大元培学院学生）和普通班（各院系其他学生）进行教学。与此同时，我们设计和开发了程序设计在线评测系统POJ和编程网格系统PG，来强化学生的动手能力，并与大学生程序设计竞赛结合起来，培养学生的创新能力。早在1996年，许卓群教授就已经在北京大学主持开设面向全校理科学生的《计算概论》课程。经过十余年的建设，北京大学根据学生的基础不同、专业不同提供了不同层次和不同内容的计算机基础教育课程。对于“电子信息类”专业的学生，北京大学设计了“程序设计与算法类”课程群，由《计算概论A》、《程序设计实习》、《数据结构与算法A》、《数据结构与算法实习》、《算法分析与设计》五门课组成。而对于其他理科学生，北京大学为他们设计了《计算概论B》和《数据结构与算法B》课程。北京大学规定所有理科本科生必须修满两学期以上的计算机基础课程，并将该系列课程列为本科生主干基础课进行重点建设。北京大学设计的有关课程群，为理科本科生提供了一个系统的、理论与实践相结合的计算机基础教育框架。其中，《计算概论》课程是这个框架中的基础。作为北京大学覆盖面最广的理科课程之一，《计算概论》课程以北大的网络教学平台为基础，以北京大学国家级计算机实验教学示范中心为依托，辅以多个具有不同专业特点的课程网站，构建了一个多层次开放的网络教学与实验环境。北京大学的网络教学平台为所有老师提供了功能完善、运行稳定的网络教学与互动平台，为学生提供了丰富多彩的教学资源。学生们可以获得整个课程网络教学环境的资源，稳步扎实地完成课程内容的学习。一、授课进度本课程课时安排为5学时/周，共90学时（18周），包括课堂教授和上机，不同的教学班级，可以根据实际的需要适当调整课堂讲授和上机的学时分配。基本学时分配为课程讲授3学时/周，上机2学时/周。章节标题课堂讲授（周3学时）上机（每周2学时）第1章计算机与信息社会2学时操作系统应用软件实习4学时第2章互联网与信息共享2学时第3章计算机的基本组成2学时第4章信息表示与信息输入输出2学时第5章信息存储2学时第6章CPU的信息处理2学时第7章计算机软件与硬件的协同工作2学时第8章程序设计-入门篇4学时4学时第9章程序设计-基本框架8学时(含2学时习题课)6学时第10章程序设计-数组和结构10学时(含2学时习题课)8学时第11章程序设计-函数8学时(含2学时习题课)6学时第12章问题分析与算法设计10学时(含4学时习题课)8学时二、各章重点与要求第1章计算机与信息社会重点：计算机和互联网的发展历程，二进制数制表示、运算及数制编码原理。要求：了解计算机和互联网的发展历程和现状；熟练掌握二进制数制表示、二进制运算及数值二进制编码原理。第2章互联网与信息共享重点：互联网的硬件设施、通信协议和基本应用，动手接入互联网的基本知识。要求：了解互联网的硬件设施和通信协议在互联网中的角色和作用；熟悉互联网中的各类基本应用；了解自己动手组建局域网、接入互联网的相关实践知识。第3章计算机的基本组成重点：计算机的结构及硬件组成，计算机系统的软件层次。要求：掌握计算机的CPU、总线、内存和外设等设备部件之间的硬件组成关系；了解各种类型的计算机部件设备；掌握计算机“硬件、操作系统、系统软件、应用软件”的软硬件层次关系；了解计算机硬件装配过程和软件系统安装过程。第4章信息表示与信息输入输出重点：声音、颜色、图像、文字等信息二进制编码的基本原理。要求：掌握声音、颜色、图像、文字等信息二进制编码的基本原理；了解多媒体信息文件格式及编码与压缩技术，了解常用的多媒体软件；了解人机交互技术。第5章信息存储重点：计算机存储系统从寄存器、高速缓存、内存到外存的层次结构。要求：掌握计算机存储系统层次结构及各层次存储器件的特点；了解磁盘、光盘和闪存（U盘）的存储原理；第6章CPU的信息处理重点：CPU的工作原理、指令及指令周期的概念；CPU访问主存储器的工作原理。要求：了解图灵机计算的原理；掌握CPU的内部组成，及指令在CPU中执行的过程。掌握CPU访问主存储器的工作原理；了解数据（整数、浮点数）在主存储器中存储和表示。第7章计算机软件与硬件的协同工作重点：操作系统的功能和作用，文件系统的概念和使用。要求：了解操作系统引导过程，了解操作系统的主要功能和典型的操作系统的实例；了解文件系统组织文件的原理和方法；了解信息安全的基本概念，初步了解加密技术和计算机病毒防范技术。第8章程序设计-入门篇重点：程序设计的要素和过程，高级程序设计语言的特点，C语言程序示例及程序规范。要求：理解程序设计从问题抽象到程序测试的整个过程；了解设计语言从机器语言到汇编语言再到高级程序设计语言的发展过程；理解示例程序处理问题的过程和程序执行的关系；掌握正确的规范化的程序设计风格。第9章程序设计-基本框架重点：变量、常量、数据类型和表达式；指令流的控制；控制台输入和输出。要求：掌握变量、常量、数据类型和表达式等C语言中的基本概念；掌握语句顺序执行和分支循环语句对程序执行过程的控制；掌握基本的控制台输入输出方法；通过初等算法综合应用本章所学的语言点。第10章程序设计-数组和结构重点：数组、结构、指针、字符串等数据类型；内存动态申请与释放；文件操作；排序和查找问题。要求：熟练掌握数组、结构两种复合数据结构的概念和使用；理解指针的概念和使用指针操作数据的特点，掌握字符串的概念和使用；了解通过指针和动态内存构造运行时刻才确定长度的数组；了解基本的文件操作函数；掌握最基本的排序和查找算法。第11章程序设计-函数重点：函数的参数传递；变量作用域；递归调用的概念及应用。要求：掌握函数的定义与调用，理解值参和形参的差别。理解全局变量和局部变量的生命期，了解变量的作用域范围与代码块的关系；了解模块化程序设计思想（问题分解与抽象）；掌握函数递归调用的原理及特点。第12章问题分析与算法设计重点：程序设计优劣的判断标准（算法的时间复杂性）；递归与分治、搜索与回溯、动态规划等一般的算法设计方法与思想。要求：了解程序设计的一般性经验，了解程序设计优劣的判断标准（即算法的时间复杂性和空间复杂性）。掌握应用递归方法解决具有递归结构的问题，了解分治方法对提高一般递归算法运行速度的作用。掌握应用系统的搜索方法求解问题，了解回溯对提高搜索性能上的作用；掌握应用动态规划的方法求解一般的最优化问题，了解动态规划自顶向下分解问题，自底向上求解问题的程序设计方法。了解NPC问题的性质，认识一些常见的NPC问题。