[NOI2013冬令营] 第二天

今天是冬令营的第二天,今天讲的内容有点难。

列举一下今天讲的内容:

  1. 上午: 线性规划与网络流 (北京大学 曹钦翔)
    这一个部分应该是我收获最大的一个部分吧。虽然我现在网络流基础几乎为零(就知道网络流的概念什么的,一个算法也不会),但是我明白了网络流问题从根本上来讲是一种特殊线性规划问题。由于这种特性,一些与网络流看起来完全没有关系的问题可以通过建立线性规划模型,转化为网络流的线性规划模型,然后通过网络流的算法解决。另外,似乎二分图的匹配也可以这样做。
  2. 下午: 浮点误差与误差复杂度 (陈许旻)
    这一部分我几乎完全没有听懂。谁叫我完全没有计算几何的基础呢?不过我也大概了解了一下有关浮点误差的问题的分析方法。
  3. 晚上: Python简介 & 一些其他的内容
    其实晚上开始有一位年轻的教授讲信息技术的未来发展方向,他的名字我不记得了。在他看来,计算资源是一种能量,数据便是材料,而聪明的头脑则是技术。说实话我听到这一些开始很惊讶,后来才慢慢理解他的意思,虽然我有点不太赞同他讲的部分内容,但是我需要学习他的这种前瞻性。关于 Python,这是我一直想学却没有时间去学的一门语言,今天的简介只能是让我见了它一面,在我脑中没有留下什么实质性的内容。后来的其他的内容涉及到了及其高深的数学,我完全不会,也就没有听。
  4. 额外部分: 利用听不懂的课上时间做题
    今天下午的课程我后来没有太听懂,所以便去做昨天留下来的那道 CEOI2012 Circuit,算法是写出来了,但是只的了三十分,实在是让我有点失望,就算是及其朴素的暴力算法似乎得分也比这个高。我打算过几天在改一改。看来,像这种级别的题目,比赛时还是暴力算法最好得分。


今天收获的知识较少,遗留的问题便更多了,需要解决的问题:

  1. 网络流问题(问题类型:最大流最小割、带流量下限的最大流、带点容量的最大流、最小费用最大流;涉及到的算法:Ford-Fulkerson 算法、Dinic 算法、ISAP 算法;有关证明:最大流与最小割相等的证明;有关能力:网络流的线性规划模型及其应用)
  2. 二分图匹配的线性规划模型(我现在连二分图的匹配都不会呢)
  3. 计算几何精度问题(不要用或尽量少用“病态“函数,误差的传递与扩散)

在冬令营的生活似乎越来越有趣了,似乎是由于大家互相熟悉了吧。下面是一些我觉得可以记录下来的事情:

  • 今天早上,我的早餐券落在了教室里,人都到了食堂,我就懒得去拿了,正好我在食堂外面的地上捡到了一份没人要的 24 号的午餐券和晚餐券,便拿捡到的午餐券来充数,居然食堂的阿姨没有发现(或者是没有追究,因为早餐券和午餐券的颜色差别还是蛮大的),看来这回是 RP 爆发了(这就是说我以后的 RP 就会……)。
  • 对于我来说,休息时间还是不够,每天晚上十一点半才能睡觉,而早上六点半就得起床,所以只有七个小时不到的睡眠时间,真是受不了了。
  • 过几天我们还要去参观成都的某个景点,但是我决定不去了,我的 NOI 基础实在太差,有必要补一补基础,刷刷题什么的(虽然我已经对最后的冬令营测试不抱希望了)。要是实在补不了基础,补睡眠时间总可以吧。
此条目发表在算法学习分类目录。将固定链接加入收藏夹。

[NOI2013冬令营] 第二天》有 2 条评论

  1. Kepler说:

    祝学习愉快~~

  2. cjr说:

    google搜索 “网络流 线性规划 曹钦翔”,然后这篇文章出现在了首页

发表评论

电子邮件地址不会被公开。 必填项已用*标注