程序设计实习(实验班)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++程序设计较为熟悉,具有良好的编程能力。数学上,需要具备基本的概率论、单元函数微积分和线性代数知识(一般高中所涵盖的程度即可)。
成果评估:
- 作业合计50%:含若干次小作业(每次占1单位分数)和一次大作业(占5单位分数),按照单位占比分配到合计50%当中
- 期末上机考试占50%
学术道德: 鼓励讨论,但绝不允许抄袭等违反学术道德的行为。例如,几个同学可以通过讨论得出相似的解法,但是最后每个同学必须独立完成作业的写作/程序的编写。
课程材料
课堂讲义幻灯片将在课前更新。
日期 | 讲义 |
---|---|
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日截止),数据集,单纯形法参考实现