图论与算法 - 程龚¶
基本信息¶
- 课程号:
22010810 - 任课教师: 程龚
- 上课专业: 信计,计科
评价 1¶
评价者信息¶
Tag：保研；Rank 5%；2024 Spring修课
Score：97
关于老师¶
由程龚老师授课。程老师比较具有个人特色，主要依靠提问同学完成对知识的讲解，导致课程的主干部分体验比较碎；在一些人名翻译、伪代码呈现的小细节上反而会展现出极大的兴趣。
前置知识¶
算法设计与分析中的图论
课程内容¶
本课程、算法设计的图论、强基离散的图论，这三门课程虽然都是图论，但互相之间基本没有任何重叠。本课程的内容可以视为算法设计的图论的延伸，主要覆盖了一些高阶的概念和算法，但没有像强基离散的图论那样过于偏向数学系的理论方向。
课程内容主要覆盖：
- 最短路
- 图匹配
- 图染色
- 割边与割点
- 网络流
- 可平面性
课程会包含对于以上专题的概念解析、简单理论题目、经典算法介绍及证明；期望同学能够掌握所有算法的运行原理。
作业、考试与得分¶
平时作业为书后习题，大多为简单的理论题目，难度一般。会安排 4 次上机 Lab，要求在 OJ 上完成某个专题的算法的代码编写。最后一次 OJ 难度极其逆天，能过的多多少少都有点抄的成分，但最终处罚的人很少。
期中安排了一次 Pre（占总分 2%），要求针对给定的论文写一个 PPT。可以主动报名上台讲，会加分。
期末为开卷，形式类似于作业，额外包含一些手动模拟给定的算法写过程。
工作量¶
作业：每周约 1 小时。期中的 Pre 可能需要 5 小时左右，如报名上台讲解还需要一些时间打磨 ppt。
实验：共四次 Lab，会分别专门占用一次上课时间；前三次一般能够在上课时间内解决，第四次比较困难，因人而异。
考试：由于是开卷，主要以熟悉概念为主，复习时间约 2 小时。
学习指南¶
课程主页：GTA
这门课的后半部分没啥用。最大的收获其实是学习到：当我把问题建模成一个图问题后，我有没有办法能够解决/我用什么方法也许可以解决；而不是那些具体的算法。属于事非常多、给分中上、收获一般、体验一般的课。
如何贡献¶
请查看评价指南了解如何评价课程！