程序设计实习(实验班)2023

时间地点:
每周三 3 - 4节(10:10 - 12:00),单周周五 7 - 8节(15:10 - 17:00),燕园四教502 燕园二教519
上机课:周六下午1:00 - 3:00,理科一号楼1235,请使用46-100号机器

主讲教师: 姜少峰 (shaofeng.jiang at pku.edu.cn)

助教: 楼家宁 (loujn at pku.edu.cn),张宇博 (zhangyubo18 at pku.edu.cn)

课下答疑交流渠道: 上机课、微信群(群二维码见第一次课的slides;若二维码过期可以联系助教进群、在群同学邀请进群)

快速跳转:课程信息 课程材料 作业


课程简介

本课程以C++语言为载体,从工程和科学两个主线介绍一些现代编程方法和算法,并付诸于实验实操。 工程方面,我们主要介绍C++面向对象编程,将具体涉及类与对象、继承与多态、模板类/方法、操作符重载、STL等面向对象的标准库介绍等内容,并选讲若干典型设计模式。 科学方面,我们介绍以近似、随机、大数据、数据科学等为主导的现代算法。具体包含随机算法及其实现,哈希方法及其在大数据上的应用,常见相似度/距离度量及其有效算法,几何近似算法,降维, 压缩感知 & 数学优化,亚线性时间算法/并行算法等内容。由于这部分内容较为前沿、很多都牵涉高深的理论,我们的侧重点是从直觉上非严格地解释这些算法的设计原理,如何编程实现,以及简单的应用。

课程要求: 本课程需要对C++程序设计较为熟悉,具有良好的编程能力。数学上,需要具备基本的概率论、单元函数微积分和线性代数知识(一般高中所涵盖的程度即可)。

成果评估:

学术道德: 鼓励讨论,但绝不允许抄袭等违反学术道德的行为。例如,几个同学可以通过讨论得出相似的解法,但是最后每个同学必须独立完成作业的写作/程序的编写。


课程材料

课堂讲义幻灯片将在课前更新。

日期 讲义
2月22日 课程介绍 & 绪论随机算法概述及其编程实现
2月24日 随机算法概述及其编程实现 (cont.)
3月1日 递归
3月8日 哈希方法
3月10日 哈希方法 (cont.)
3月15日 距离度量及其计算
3月22日 距离度量及其计算:欧氏距离
3月24日 距离度量及其计算:欧氏距离 (cont.)
3月29日 面向对象编程:绪论
4月5日(放假) ---
4月7日 C++面向对象编程:类与对象
4月12日 C++面向对象编程:重载C++面向对象编程:继承与多态
4月19日 C++面向对象编程:继承与多态 (cont.)
4月21日 C++面向对象编程:泛型
4月26日 C++面向对象编程:设计模式选讲
5月3日 (放假) ---
5月5日(放假) ---
5月10日 降维:JL方法
5月17日 降维:PCA方法
5月19日 降维:PCA方法 (cont.)
5月24日 稀疏性、压缩感知与线性规划方法
5月31日 Sparse Recovery与数据流算法
6月2日 Sparse Recovery与数据流算法 (cont.);大数据并行计算模型:MPC
6月7日 大数据并行计算模型:MPC (cont.)总结与期末安排
6月23日 期末考试(上机)

作业

编程作业请提交到openjudge上,实验报告作业请提交电子版到https://course.pku.edu.cn(如只有纸质版本,请拍照/扫描提交图片并确保清晰度)。

大作业 (6月1日截止),辅助测试数据下载
作业一(实验报告)作业二(编程) (3月15日截止)
递归练习题 (选做,不计分数)
作业三(编程) (3月31日截止)
作业四(编程)(4月5日截止)
作业五(编程)作业六(编程)(4月12日截止)
作业七(编程)作业八(编程)(4月19日截止)
作业九(编程)(6月1日截止)
作业十(编程)(6月8日截止)
作业十一(实验报告)(6月15日截止),数据集单纯形法参考实现