2009年4月27日星期一
2009年4月26日星期日
数据结构与算法学习文摘
2009年4月23日星期四
【推荐阅读】OIERS 必读：计算机科学趋势之我谈。。。
Posted by: 穿靴子的猫 (65.59.219.133)
Date: August 03, 2006 05:33PM
常有热血青年问我计算机科学还有啥搞头。
首先我们回顾一下计算机科学的“机械黄金时代”——5/60 年代。这个年代是研究“简单机械”数学对象的淘金时代。这些数学对象包括：字符串，数列，集合，树，图等等。它们的特点是：1. 最简单、最机械，就像数学里的"一元一次方程"、物理里的“定滑轮动滑轮”一样初等。同时这个时代的大背景是应用数学的大发展（冷战时代两个阵营要拼谁的军事和生产活动达到最优化），因此 2. 这些对象不同于其他纯数学的基本对象在于他们有强烈的现实应用性。有了什么样的研究对象就决定了会有什么样的研究成果（算法/方法/原理/应用）。比如，如果研究对象是字符串，就很容易发现我们有实际需求的操作有 压缩、加密、查找子串 等，于是大浪淘沙，我们有了 ZIP, RSA, KMP 这些堪称经典的结果；而那些有用但没有有效解法的问题，几乎都被证明是 NPC 的。。。这样，走得通的路都走通了，走不通的路都被证明是走不通的。。
除了简单机械对象的相关算法设计外，过去几十年同时也是人工智能基本问题的黄金时代。这些基本成果在它们所在体系中的“根本性”就像牛顿的成果在经典力学体系中的“根本性”一样，是后人无法再超越的。。。人工智能的一个目的是对“模糊”（非形式化）信息"形式"的理解，也就是说我们表达的内容可以有各种表现形式：自然语言文本，语音，图像，影像。对他们的分析（analysis）往往比合成（synthesis）要困难。我举一个非常典型的例子：语音识别（speech recognition）是对语音数据的分析，语音合成（speech synthesis）是合成，后者的实际成功大得多。要分析我们就不可避免要知道牵涉到的背景知识（分为“规则 (rules)”和“案例 (cases/samples/examples)”两种，一个案例就是一个特殊的经验，可以看作一个适用范围最小的规则），还有如何把这些背景知识用于我们要识别的数据，这又分为两种态度：按逻辑推理 (logic-based reasoning) 和不要求有严密逻辑推理关系的模糊式、统计式联系（statistical methods 或叫 connectivism，就是把“因”和“果”用经验联系起来（知其往往然）而不是用逻辑推理关系联系起来（知其所以然）），比如初中里的几何证明就是严密的逻辑推理，而 Google 仅仅找到那些紧密出现你的 keywords 的文章片断就是统计式、模糊式处理，就像总设计师说的“宜粗不宜细”。根据具体问题的具体条件，两种态度各有所长。人工智能的另一个目的是对信息“内容” 的处理和再创造。前面我们说的是把同一个内容的数据从一种形式变到另一种形式，比如把一句话从语音形式变到文本形式、把一句话从中文翻译到英文，其实内容不变。那么对内容本身我们可以做什么有用的操作呢？一方面，我们可以把内容表示成一种形式化的知识表示，用上面提到的 logic-based reasoning 来推出新的有用结论。这种操作的局限性在于计算机只能用我们给出的知识反复演绎；尽管我们可以加入统计性的因素让推理更灵活（同时降低了结果的准确性），但仍然受限于有限的形式化知识。另一方面，我们可以不拘泥于形式化的知识表示与推理，而是让计算机和人混和起来思考问题。这时，我们不要求概念和概念之间的可能关系被完全形式化，但我们往往还是要求“一个概念只有一个命名”。典型的这种知识表示就是 Wikipedia，它的每个文章都是一个概念，有唯一的命名（或明确声明多个命名等价），而文章之间的超链接（不明确表示的关系）使 Wikipedia 成为一个概念的网络。由于概念之间关系的不明确，我们不说它是一个语义网络（semantic network，知识表示的最重要方法，与 first-order logic、frames 等价），而是一个概念网络（ontology，即一些概念的集合，每个概念都有严格的命名）。概念命名形式化而概念关系非形式化的本性决定了这种东西可以让人和计算机相结合完成某些任务。比如，我心里有一个 idea X，我想知道它是否已经被别人提出过了，如果被别人提出过了那么它的命名是什么。这是一个很有实际意义的问题，比如申请专利之前你要查找前人是否已经公布过类似 idea，比如你不知道一个概念在英语中如何表达（如果这个概念在你的母语中没有一个专门的术语 A 或者虽然有 A 但是你的双语词典不能为你直接建立 A 到英语对应表达 A' 的映射。。。）。此时我们就可以基于一个 ontology 如 Wikipedia 来间接寻找 X 的所在。例如我们要找“热插拔”的英文说法（假设不存在“热插拔”的中文条目），我们可以先想象一下它有什么特别相关的概念，我们想到“即插即用” (plug and play)，因为这两个概念是可比较的两种硬件安装规格。于是我们先进入英文 Wikipedia 条目“plug and play”: http://en.wikipedia.org/wiki/Plug_and_play 然后我们发现该文章中比较了即插即用和一个所谓“true hot swapping”的相同和不同。通过文章对这个 hot swapping 的描述，我们有很大把握认为它就是我们要找的“热插拔”。我们可以进一步用这个关键词在其他文献中确定它就是热插拔。这个问题跟查双语字典正好相反，双语字典是你给出一个已知的母语术语 A，它告诉你 A 对应的未知的外语术语 A' 以及 A' 的未知的定义 Def_A'，而我们刚才说的这个问题是已知一个概念的定义 Def_X，如何知道这个概念在某个语言中的的命名 Name_X。这又叫 reverse dictionary lookup.
综合以上两段，我们想想我们当代应该研究什么。显然我们不应该再去研究简单机械对象，那是口枯井（当然如果你不以“有实际用途”为导向去选择研究对象，你完全可以去研究 100 个方块组成的俄罗斯方块图形有几种（这个美国人 60 年代也研究过了，呵呵）、人为设计一个类似五子棋的棋类游戏然后研究其制胜策略（这就是所谓趣味数学成果，因为研究对象可以无穷制造，所以总有研究的空间；这也是为什么某数学家（好像是丘成桐）教育我们要研究自然界的数学模型而不是那些人工制造出来的数学对象。就算 Knuth 这种至少有 KMP 这样经典的有用简单机械成果的大牛，也在 70 年代百无聊赖之际研究过游戏“大智之人”（Mastermind，又叫“猜数字”）；而且比尔盖茨在 70 年代哈佛退学以后还兴致勃勃地研究过翻烧饼的组合数学问题 [1][2]；MIT 有个很年轻的加拿大计算机教授 Erik Demaine，现在华人学者热衷于提起他，他做的最有特色的研究之一是折纸中的计算机学问。。））。就连在简单机械算法世界里浸淫了几十年的 Knuth 也在 2001 年接受采访说：“如果。。。人生从头来过，我现在愿意做一个研究机器人学或生化的研究生。。。理论计算机科学。。。经过五十年的爆炸性发展后，很难想象还有多少发展空间。我不认为现在对以前的经典结果作小的优化有多大意义。当然我不能完全否定计算机科学继续发展的可能性，但这种可能性跟生物学是无法相提并论的。。。计算机科学经过五十年就发展殆尽，而生物学却很容易就提供给我们足够研究 500 年的问题，两者差距是如此巨大。”[10][12] 有人问，那么计算机科学不是还剩那个圣杯——“P?=NP”么？让我们看看 Knuth 2002 年在奥斯陆大学的“All Questions Answered”演讲中是怎么说的：“。。。就算 P==NP，仅仅知道一个问题有多项式时间算法是没有实际意义的，因为那个指数可能大得超过计算能力。因此也许我们从一开始就不应该提出 P?=NP 这个糟糕的问题。”[11]在这次演讲中 Knuth 还特别强调要“阅读大师的思想” (Read the masters)。在 2001 年慕尼黑大学另一次同名的演讲[12]中，Knuth 干脆认为“P?=NP 可能是 Godel 所说的‘不可证明的定理’之一”。
所以我们可以想到，我们当代要研究的对象必然是更复杂的，或者机械的数学世界以外的活生生的现实问题。比如在劳动人民的生活中，自然语言是全球化背景下一个突出的问题，同时也是足够复杂的对象；比如股票市场的预测（按道理说这需要计算机知道足够多的背景知识和内幕消息，因此我对那些统计学者用统计过分简化整个事情是非常鄙视的）；比如宏观经济/社会；比如自然科学如生物、纳米里的复杂结构和功能；比如复杂工程学如导弹防御系统、机器人、航天；比如经济中的供求双方信息不对称问题（你想找某个很窄的领域的知识或真人专家，你如何跟这个知识或专家接上头？特别是当这个“很窄的领域”尚没有特定学名时？这又回归到了我上面说的 reverse dictionary lookup 问题：在对应的 Wikipedia 页面上留下相关知识和真人专家的联系方式。而作为“卖方”，一个真人专家如何拓展他的业务范围？他可以观察自己当前领域周边的 wiki 文章是否也可以让自己去“坐堂”；一个自主学习的学生如何决定自己下一步学什么/研究什么？也是同样道理。）；比如让计算机半自动的穷举、推理、归纳、联想出新的创新机会。
【转载博客园】ACM竞赛须掌握的知识
【转载博客园】ACM相关资料
【重要】ACM相关资料
注：办公室我的笔记本内桌面有ACM目录，内有相关资料（电子书、题解等），需要的同学可以随时去copy。我们的周末讨论暂定用《算法艺术与信息学竞赛》学习指导作为教材问：现在（第三学期）如何准备ACM？
答：先看数据结构，再看算法设计与分析。如果C++基础较好，可直接开始看《算法艺术与信息学竞赛》学习指导 （完全针对竞赛，内含数据结构和算法及数学相关内容）
======================================
重点推荐
一本书：算法艺术与信息学竞赛 （就是网上说的“lrj”，也称“黑皮书”，此书针对中学阶段的国家信息学奥赛，可用作ACM入门）
pdf电子书：http://download.csdn.net/source/438429
学习指导电子书：http://download.csdn.net/source/828907 强烈建议先看学习指导
一个网站：http://www.oibh.org/bbs/
其他书籍：
ACM 程序设计培训教程
数据结构书可以看清华严蔚敏那本（C语言就可以，旧书很多，数据结构在第4学期开课），数据结构网上资料 http://student.zjzk.cn/course_ware/data_structure/web/main.htm （或在谷歌搜索“数据结构自考”）
新编实用算法分析与程序设计
国际大学生程序设计竞赛例题解 一共四本
电子书（一）数论、计算几何、搜索算法专集：http://download.csdn.net/source/243043
电子书（二） 广东省大学生程序设计竞赛试题 http://download.csdn.net/source/704716
其他网站：
http://www.nocow.cn/
浙大在线测试ZOJ：http://acm.zju.edu.cn/
离线题库：http://download.csdn.net/source/829282
题解：http://download.csdn.net/source/829343
北大在线测试POJ：http://acm.pku.edu.cn/
==================================
关于ACM-ICPC竞赛
概况
ACM国际大学生程序设计竞赛(ICPC)的历史可以上溯到1970年，当时美国德州A&M大学举办了首届竞赛，主办方是UPE计算机科学荣誉协会Alpha分会。作为一种发现和培养计算机科学这一新兴领域顶尖学生的全新方式，竞赛很快得到了美国和加拿大多所大学的积极响应。
总决赛整个竞赛为5个小时10道题，由计算机出题，3人一组的参赛队伍必须现场作答。经由裁判评判，根据破解试题数目的多少对参赛队伍进行排名，解题数在中等以下的队伍会得到确认但不会进行排名。根据排名将最终确定全球总决赛铜奖4名、银奖4名、金奖4名，金奖中第1名为此次比赛的全球总冠军。每届ACM/ICPC竞赛都是精英荟萃、新才辈出，因而倍受全球著名信息企业的高度关注，在过去几年中，APPLE、AT&T、MICROSOFT和IBM分别担任了竞赛的赞助商。
ACM/ICPC是世界各地计算机程序设计者大显身手的舞台，也是世界一流大学展现教育成果的最佳窗口。中国大陆高校从1996年开始参加ACM国际大学生程序设计竞赛亚洲预赛，上海交通大学作为最早参加的高校之一，曾七次进军ACM/ICPC全球总决赛，并在2002年赢得了在夏威夷举办的第27届ACM/ICPC全球总决赛冠军，这是中国大学的第一次夺冠，更是亚洲高校的第一次夺冠。上海交大还于2005年获得由上海交大承办的第29届ACM的冠军。
1 背景与历史
1970年在美国texas a &m大学举办了首次区域竞赛，从而拉开了国际大学生程序设计竞赛的序幕。1977年，该项竞赛被分为两个级别——区域赛和总决赛，这便是现代acm竞赛的开始。在亚洲、美国、欧洲、太平洋地区均没有区域赛点。1995至1996年，来自世界各地的一千多支s代表队参加了acm区域竞赛。acm大学生程序设计竞赛由美国计算机协会（acm）举办，旨在向全世界的大学生提供一个展示和锻炼其解决问题和运用计算机能力的机会，现已成为全世界范围内历史最悠久、规模最大的大学生程序设计竞赛。
2 竞赛组织
竞赛在由各高等院校派出的3人一组的队伍间进行，分两个级别。参赛队应首先参加每年9月至11月在世界各地举行的“区域竞赛(regional contest)”。各区域竞赛得分最高的队伍自动进入第二年3月在美国举行的“决赛(final contest)”，其它的高分队伍也有可能被邀请参加决赛。每个学校有一名教师主管队伍，称为“领队”(faculty advisor)，他负责选手的资格认定并指定或自己担任该队的教练(coach)。每支队伍最多由三名选手(contestant)组成，每个选手必须是正在主管学校攻读学位并已读完至少一半时间的学生。每支队伍最多允许有一名选手具有学士学位(就是说至少有两个还没有取得学士学位)，已经参加两次决赛的选手不得再参加区域竞赛。
3 竞赛形式与评分办法
竞赛进行5个小时，一般有6—8道试题，由同队的三名选手使用同一台计算机协作完成。当解决了一道试题之后，将其提交给评委，由评委判断其是否正确。若提交的程序运行不正确，则该程序将被退回给参赛队，参赛队可以进行修改后再一次提交该问题。程序运行不正确是指出现以下4种情况之一：
(1)运行出错(run-time error)；
(2)运行超时〔time-limit exceeded)；
(3)运行结果错误(wrong answer)；
(4)运行结果输出格式错误(presentation error)。
竞赛结束后，参赛各队以解出问题的多少进行排名，若解出问题数相同，按照总用时的长短排名。总用时为每个解决了的问题所用时间之和。一个解决了的问题所用的时间是竞赛开始到提交被接受的时间加上该问题的罚时(每次提交通不过，罚时20分钟)。没有解决的问题不记时。美国英语为竞赛的工作语言。竞赛的所有书面材料(包括试题)将用美国英语写出，区域竞赛中可以使用其它语言。总决赛可以使用的程序设计语言包括pascal，c，c++及java，也可以使用其它语言。具体的操作系统及语言版本各年有所不同。
4 竞赛奖励情况
总决赛前十名的队伍将得到高额奖学金：第一名奖金为12000美元，第二名奖金为6000美元，第三名奖金为3000美元，第四名至第十名将各得到l500美元。除此之外还将承认北美冠军、欧洲冠军、南太平洋冠军及亚洲冠军。
==============
| 浅谈ACM /ICPC的题目风格和近几年题目的发展 |
| 作者：王颖 文章来源：ACM组委会 点击数：359 更新时间：2008-10-9 |
| ACM ICPC的比赛形式一般是五个小时八个题目，综合考察选手的数学能力、算法能力、coding能力和debug能力，还有团队配合能力。数学方面主要强调组合数学、图论和数论这三个方面的能力；而算法的覆盖范围很广，涉及了大部分经典的算法，和少量较前沿的算法。由于每道题目都需要通过所有的测试数据才能得分，并且需要精确解，这限制了Approximation algorithm在一些NP-hard的题目中的运用，从而使得搜索和剪枝策略对于NP-hard的题目非常重要。 Final的题目和Regional题目的比较 ACM ICPC官方的正式比赛可分为World Final和Regional Contest两种。Final的题目更加正统和严谨，强调算法的综合运用，一个题目往往需要几种算法的结合。从这几年的final的题目看，final加大了题目的代码量，对代码能力的要求有所增强。而Regional的题目则更加灵活，同时每个赛区也有自己的出题风格。欧洲赛区的题目以高质量出名，对算法和数学的强调甚至超过了World Final；美国的赛区较多模拟题，强调代码量。而亚洲则介于两者之间，同时由于每年都有一些新的赛区，所以并没有很固定的模式。 下面浅谈一下近几年ACM ICPC的题目的覆盖面。一些常规的算法和题型没什么好讲的，下面主要侧重一些新颖的知识点或题型，或是一些较前沿的内容。 数学的新题型 除了一些基本的组合数学和组合数论的问题，近年来概率和Combinatorial Game Theory的题目逐渐增多。很多有趣的题目都是以Markov Process为背景，需要用到一些相关的知识。 去年国内杭州赛区的一个很有趣的题目是，给出一个字符集（比如{A,B,C}）和一个字符串T（比如ACBBCAC），现在从一个空串S开始，每次等概率的添加A,B,C中的一个字符，直到T是S的一个子串。问得到的字符串S的长度的期望。这是一个典型的Markov Process，其解可以用生成函数很优美的算出来。一个更有趣的版本是，假如还有另一个字串R，当S中出现T或者R就终止，问终止在T和R的概率各是多少。这个问题在Graham, Knuth, 和Patashnik合著的Concrete Mathematics里面有详细的分析，并有着一个优美的结论。 Game theory方面，主要是经典的combinatorial game theory而比较少Zero-sum game和Nash equilibrium的内容。以前甚少选手知道的Sprague-Grundy Value现在已几乎成了必备的知识。虽然大部分题目都是two-person perfect information impartial game，基本都可以用Sprague-Grundy Theorem解决，但也出现过misere play的情况。还有一些题目则是通过找规律和归纳解决。 Graph theory方面，上海赛区在多年前就出了一道Chordal graph recognition的题目，使得许多选手投入弦图和区间图的学习，并了解到完美图理论；IPSC有一年出了consecutive ones problem，从而引起了选手们对PQ树和平面图判定的关注。 除此之外，还有一些零散的non-trivial的题目，甚至是一些非常involved的题目。如刘汝佳给达卡赛区出的一道unbreakable tiling的题目。其中我非常喜欢的一个题目是四年前东北欧赛区的一个floodlight problem：平面上给出n个点代表n盏灯，每个灯可以照亮圆心角为2*∏/n的一个扇形区域。问怎样控制这些灯的角度，使得可以照亮整个平面。 还有一些数学题则考验创造能力。比如有一题：给出n，要求找出一个n*n的方阵，其中每个元素都是1到n之间的整数，并且两两不等，同时使得每行、每列还有两个对角线的和两两不等。这题的构造颇为繁琐，最简单的方法是直接随机生成再判定是否具有这个性质。 近年来几乎每年的final都有一道考察选手微积分能力的题目。而微分方程类题目较少。 大型线性方程组、复杂的矩阵代数、和特征值求解方面的题目较少。 算法的新题型 算法方面的增强主要体现在新的数据结构不断被选手所熟悉，和一些新领域的题目出现在ACM ICPC中。 数据结构方面，一些特殊性质的平衡树逐渐被大家掌握，如splay tree，leftist tree等等。Interval tree则被广泛用于计数。字符串方面，较容易实现的后缀树组也逐渐被接受。 一些算法：网络流方面，不少选手开始掌握push-relabel算法而放弃了经典的ford-fulkerson算法；刘汝佳的书广为传阅后，不少选手又掌握了fractional programming和dinkelbach算法。目前能熟练实现linear programming的选手较少，但可以预计过一段时间这也会成为必备的技能。 计算几何一直是ACM ICPC里面的难题。不仅编程困难，更由于精度问题导致非常难做对。计算几何往往是在比赛时被放弃的题目。即使算法并不非常难，选手也不敢随意去做。 一些零散的经典内容也被拿出来考察，如stable marriage，fft等。 总结和一些预计 基本上，实现起来不算太复杂的多项式时间复杂度的算法都可以出成一道ACM ICPC的题目。而出题者知识面的不停增长，也使得越来越多这样的算法被包括。另一方面，随着算法的发展，一些原本没有简单算法的题目也出现了新的解法，这样的题目也被加入到ACM ICPC中。ACM ICPC经过多年的积累有着大量的题目，其覆盖面也是非常之广。 可以预见一些新的优秀的算法将陆续出现在ACM ICPC中。比如由于任意图匹配的Edmonds-Carp算法实现起来非常繁琐，使得ICPC中一直不出现任意图匹配的题目（即使有也是规模非常小）。而Vijay Vazirani的论文< 而一些新的领域也必将给ACM ICPC的出题者带来灵感。例如已有越来越多Bio-informatics的题目在ICPC中出现。一些有着多项式算法的好题目，如inversion distance of signed permutations，则由于其理论的复杂而尚未出现在题目中。 图论中还有数不胜数的好的题目，比如linear time求minimum cut，还有Gomory-Hu tree的应用，这些也必将在不久的将来出现在ICPC题目中。 我认为将发生的另一个趋势是，随机算法，概率算法和近似算法会在ACM ICPC中占更大的比重，至于对于算法能力和代码能力考验的平衡，我个人非常喜欢数学和算法，我希望Final的题目能向中欧赛区的题目靠拢。 ACM ICPC考察的不仅仅是对经典算法的理解和掌握，创造算法的能力同样非常重要。学那么多算法，必须从中有所领悟，才能在赛场上有灵感去解决实际的问题。 |