Nov
28
把poj从收藏夹里面删掉, 把关于ACM的一些网页从收藏夹删掉, 很很酱油的ACM就此终结了. 但奇怪的是在这终结之际却有一丝留恋…
早就想写一篇关于ACM结束的日志了, 因为距离成都区域赛结束也已经快有3个星期了. ACM的结局显然是苍白的, 因为自己从来就没努力去搞, 连队名都取成了passerby(路人), 只是草草了事, 为了混一次经历, 但是也还是有一些遗憾的. 比赛中若不是自己在一题中将一个变量多定义了一次, 结局可能并不会这样, 这种错误很早以前, 应该是初些代码的时候就遇到的, 居然在这种时候还遇到了. 教练说这应该会是一个永远的教训吧, 但自己就是没有这样一种感觉, 因为觉得这根本不可能啊, 这种错误怎么可能还会犯, 比赛中犯都已经让我难以置信了. 但事实摆在眼前, 不给力!
之后我也看了一些ACM大神们关于比赛的一些总结, 我真心觉得其实自己真的也可以做到和他们差不多的状态, 如果我明年可以继续搞(很不现实), 很多题不会并不是因为你不如人家聪明, 只是因为你平时没别人练习的多, 比如某种算法, 某种数据结构, 平时没学过怎么可能在短短5个小时里做出来, 而一些需要临场想到的算法很多情况也是平时多练习的结果, 就如中学搞的数学竞赛一样. 所以很佩服那些平时练习的很多的大神们, 也祝所有那些大神都可以圆自己的Final梦!
接下来是近期的一些事情和心情…
朱亮的一封邮件让我知道了他近期的一些状况让我觉得很有感触, 但这感触和那并没有什么实际联系. 近期的自己让我觉得很不像自己, 信心逐渐被摧残着, 不善于和人交流, 到了大学平时最多交流的就只有和姐了. 但是那天和姐谈的时候突然也暴躁起来, 因为姐问的问题好多都让我觉得难受.
看着周围越来越多的同学找到实验室, 看厚厚的论文和书籍, 让自己深深自责, 什么都没干, 还成天玩… 其实我也想学的, 可是就是学不起来. 我也申请了MSRA, 还去面试了两次, 都以失败告终(都没告诉朱亮, 也不好意思告诉, 你看到的话生气了我也理解的). 于是继续堕落的样子. 不过两次面试失败的原因我觉得并不都一样, 第一次那个组面试的时候自己好多问题都没答上来, 才发现自己看的那些论文都没有看懂, 只是皮毛中的皮毛, 所以被T, 第二个组面试问题基本都答上来了但还是没要我应该是因为自己项目经历太少而且时间没那么多, 因为感觉第二个组偏工程方面的更多一些. 所以还是有一些收获的吧, 算是一种经验.
从来都不善于和同学或者朋友交流自己的心事, 最多就是写出来, 现在也不喜欢在什么QQ, renren之类的上面写了, 感觉反正写了也没多大用. 高中的一些关系好的同学知道我是这样一个人, 所以他们会经常联系我一下, 然后双方交流一下, 但是我发现最近好像也变少了, 哈哈, 完全可以理解的, 肯定有很多原因的, 不过我也肯定清楚他们一直都会是自己最好的朋友. 这又让我想起了一件事情, 那天刘导要我们开大学中期德育答辩(极其之扯), 自己草草准备了一下也没准备多讲. 但是答辩的时候有些同学讲了很多, 有些讲到了同学之间关系的, 有些好像特别指出了谁谁谁人特别好(反正就是之类的话), 就像在形容自己最好的朋友一样, 当然他们可能以后就真的会一直是很好的朋友, 我完全相信, 我们宿舍也有一个说到我们寝室并没有成为那种很好很好的朋友. 我当时听了其实也想讲一些, 后来想想也就算了, 因为我不是那样喜欢在很多人面前讲一些自己认为正确的大道理的人. 不过在这里, 我想都说出来, 其实人和人是有很大不同的, 既有性格差异也有地区差异, 就拿我来说, 本身就是一个很慢热的人, 刚来大学的时候就没妄想可以找到那种至交, 但是如果一旦被我认定是一个值得做一辈子好朋友的, 我一定会尽自己全力去让自己维持这样一个朋友的, 就像高中时候的那几个朋友, 哈, 我知道你们一直都在. 虽然有些人的确很好, 但是有些方面我就是看不惯, 而那些方面又是自己的原则所在, 很显然不可能了. 又让我想到高中我的班级来北京的就只有我一个, 好可怜啊. 当然, 现在宿舍里的同学也都挺好的, 至少和谐, 而且可以说是为数不多经常结伴的宿舍了. 但有些时候还是会有一些矛盾, 比如一天我们召集了10人开黑, rdsp, 有些人就会因为被分到相对实力弱的一方, 然后就GG, 退出游戏, 有些就会无缘无故说自己不想玩了(可能也是因为没有分到令自己满意的一方)退出游戏… 这让我很看不惯, 于是后来我也不玩了, 觉得那样没必要, 没意思, 不就是游戏么, 至于么? 那个说不想玩了就退出游戏的同学之后也没给出解释让我很不爽. 嗯, 我就是这样一个在某些方面容易斤斤计较的人, 甚至比女生更敏感, 但在有些方面就完全无所谓了. 当然你不爽人家也不管你, 怎么玩还怎么玩, 可能还会觉得你这人怎么这样, 太计较了吧… 对, 别人这么想我无所谓, 爱怎么想怎么想, 就没奢望有人懂你, 但至少我会做到真诚待人, 这点我始终坚持着.
性格很倔强, 脾气很坏, 动不动就生气, 姐总说让我改改, 我笑着说, 改不了了的, 知道的也就家里人和高中那几个人, 如果哪一天没人知道了也没关系, 因为我也不在乎那个… 哈哈, 好想你们啊~
扯了这么多, 算是一种发泄吧, 回朱亮的邮件中提到, 至少让自己活的开心一点, 没什么大不了的. 我觉得我还是那个乐观积极的我, 一定也可以找回那个自信的我的, 性格什么的改不了也不想改, 其他人就更无所谓了, 做到问心无愧就行了.
睡觉去, 明天早起看书写代码吧!
Nov
3
这是GG同学发邮件问我的, 一开始在网上找答案, 找了很久没找到- .- 断断续续思考了1天后大致有了一些思路..
题目描述:
桌面上有2009根火柴，二人参加游戏。规则是：二人轮流从中取出火柴，每次可取出1—3根，直至取完。取完后清点手中的火柴根数，谁取到奇数根谁获胜。你 为了保证获胜，应选择先取还是后取？如果你先取，第一次应取几根？当对方取了下一步后，你又应相应地采取什么策略？如果将规则改为谁取到偶数根谁赢，保证 获胜的策略又相应有什么改变？
将上面规则中的“每次可取出1—3根”改成“每次可取出1—N根”，N是小于2005的任意数，你又如何保证自己获胜？
这里我先考虑最基本的问题, 2009根火柴两人轮流取火柴, 每次取1~3根, 不能不取, 直到取完的时候, 取到奇数根火柴的人为胜者.
对于一个人取火柴的时候的状态量其实只有两个, 一个是自己手上的火柴的个数, 另一个剩余火柴的个数, 因为两个人手上火柴我们只考虑奇数和偶数的关系, 而且火柴总数一定要为奇数, 所以另一个人手上火柴的个数的奇偶性一定可以根据第一个人手上火柴的奇偶性和剩余火柴个数的奇偶性得出.
于是, 我们设状态的表示方法为(a, b), 其中, a=0或者1, 0表示偶数, 1表示奇数, b表示当前情况下的剩余火柴数. 然后我列出了剩余火柴数为0~15的情况, 见下表
| b
a |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 1 | Y | N | Y | Y | N | Y | Y | Y | Y | N | Y | Y | N | Y | Y | Y |
| 0 | N | Y | Y | Y | Y | N | Y | Y | N | Y | Y | Y | Y | N | Y | Y |
(Y表示赢, N表示输)
具体推导过程, 是通过(1, 1)和(0, 0)(手上奇数根火柴取一个变成偶数, 输; 手上偶数根火柴没火柴取了, 输)两个必输的状态不断推导所得… 从这张表中很容易就可以发现, 这是一个按8循环的状态.
而由于, 火柴总数为奇数, 且一开始两人手上的火柴数为0, 所以只有当火柴数mod 8 = 5的时候先手才必输, 否则先手必胜.
然后, 考虑取火柴的方法. 从表中可以发现, 由于一共只有4个必输状态(这里已经把火柴数模8了)
分别是(0, 8k), (0, 8k+5), (1, 8k+1), (1, 8k+4), 一定要保证对手处在一个必输态, 以及无论对手取1,2或者3, 都取相应的火柴数, 使得对手还是处在必输态(其实上面那张表就是类似推导出来的), 继续定义[x, y] , 1<=x,y<=3, 表示当处在必输态的人取了x个火柴后, 另一个人取y个火柴可以使得那人还是处在必输态. 而这四种必输态情况分别如下
(0, 8k): {->[1, 3]到达 (1, 8k+4)} 或者 {-> [2, 1]到达 (0, 8k+5)} 或者 {-> [3, 1]到达 (1, 8k+4)}
(0, 8k+5): {->[1, 3]到达 (1, 8k+1)} 或者 {-> [2, 3]到达 (0, 8k)} 或者 {-> [3, 1]到达 (1, 8k+1)}
(1, 8k+1): {->[1, 3]到达 (0, 8k+5)} 或者 {-> [2, 3]到达 (1, 8k+4)} 或者 {-> [3, 1]到达 (0, 8k+5)}
(1, 8k+4): {->[1, 3]到达 (0, 8k)} 或者 {-> [2, 1]到达 (1, 8k+1)} 或者 {-> [3, 1]到达 (0, 8k)}
所以取火柴策略步骤就是:
1) 判断总火柴数mod8后的数是否为5, 如果是5, 则让对手先走,否则, 根据之前讨论的规则, 如果是1, 那么取1个火柴, 如果是3, 取3个火柴, 如果是7, 取2个火柴.
2) 当前, 到了对手取火柴, 而且对手处于必输态, 那么就按照上面四种情况取火柴, 这样就能保证最后自己取得奇数.
所以2009根火柴就应该是先手胜. 因为 2009 mod 8 = 1 != 5
取到偶数的情况应该与奇数情况相同, 这里不再赘述.
然后我们考虑 取1~n(n>=2)根火柴, 方法类似… 这里给出结论:
1) 当n为奇数的时候, 如果火柴总数mod(2n+2)=n+2, 那么, 先手必输, 否则必胜..
2) 当n为偶数的时候, 如果火柴总数mod(n+2)=n+1, 那么, 先手必输, 否则必胜..
而且过程中也只出现4种必输态. 而取火柴的方法, 应该也比较容易推得, 这里也不再多写..
欢迎多多交流..
PS. 明天就去SCU了, 保铁争铜! Orz 终于要pass acm by了 T_T
Oct
20
从暑假到现在, 断断续续看论文代码实现了其中的一些, 是时候总结一下了.
首先介绍一下PageRank算法的背景: 比如一个人正在网上冲浪, 到了某个页面后, 可能他会通过该页面中的某个链接来到下个页面, 又或者直接在地址栏中输入一个新的地址来到下个页面, 而该算法就是用来计算到达每一个相关页面的可能性, 用PageRank来表示, PageRank越高, 到达该页面的可能性越高.
其算法的模型类似于投票或者推荐. 这里借投票来简单阐述一下: 如果一个人被很多人投票, 那么这个人的得分就会高, 如果两个人A和B被投票的票数相同, 但是投A的那些人本身的得分就比较高(比投B的那些人得分高), 那么A得分就会比B高.
于是PageRank就根据一个页面的outlinks和inlinks得到一个计算每个页面PageRank的公式:
PR(u) = 1-d + d*∑(PR(v) / N(v)), v∈B(u)
这里: d是一个常数, 通常设为0.85(d的作用在于考虑到了冲浪者可能直接从地址栏重新输入地址进行浏览), B(u)表示指向u的链接集合, N(v)是指从v指向出去的链接集合.
其实我最初阅读的paper叫做TextRank, 其目的是给出一篇文章, 给出这篇文章的tag, 而其中用到的算法就是PageRank, 这个算法的效果在我看来已经是很好了, 但是这个算法用在中文上就会差很多了, 首先因为中文分词的困难性, 其次中文句子结构的复杂性, 所以需要一些改进的算法才行.
这里还有一篇没怎么看懂的论文(The Linear Algebra Behind Google)- -跟线代, 概率什么的很大关系…
于是我又读了Weighted PageRank Algorithm(接下来以WPR简称)这篇paper, 这是对于PageRank算法的一个改进, 考虑到了权值的分配, 在这篇论文中我也了解到了另一种搜索引擎算法HITS.
HITS的算法思想(这段引用了这篇论文中的一些部分):
该将网页分为两个类别, 即权威页(authorities)和中心页( hubs) . 权威页是表达某一主题的页面, 对这一主题它的价值很高, 依赖于指向它的页面. 中心页是指向多个权威页的页面, 它把这些权威页链接在一起, 依赖于它所指向的页面. HITS算法为每个页面引入两个权值, 即authority权值和hub权值, 通过一定的计算可得到针对某个检索提问的最具价值的网页, 即排名最高的权威页.
HITS算法首先通过传统的搜索引擎选取一定数量的页面作为根集(root set), 然后在根集的基础上进行扩展, 把引用根集的页面和被根集引用的页面都加入进来,生成基本集(base set), 再针对基本集中的超链接建立所要处理的子图. 在这个子图上,建立页面authorities 和 hubs的计算公式.
设A(p)表示页面p 的authorities 值, H(p)表示页面p 的hubs值,指向页面p 的集合为B(p) = {q1 ,q2 , ⋯,qn}, 页面p指向的页面的集合为 I (p) ={q1’ ,q2’ , ⋯,qn’ }. 则A(p) = H(q1) + ⋯+ H(qn); H(p) = A(q1’ )+ ⋯+ A(qn’); 通过迭代计算, 最终得到页面p的authorities 值. HITS 算法中的authorities 和 hubs值是互相加强的.
WPR算法思想:
在PageRank Algorithm的基础上, 这里引入了两个系数 W in(v,u) 和 W out(v,u) 分别表示的意思:
u的inlinks总数占 v的所有outlink的inlinks总数 的比例
u的outlinks总数 占 v的所有outlinks的outlinks总数 的比例
这两个系数的积在公式中是作为v分配给u的pagerank的权重, 分别考虑了u在inlink的popular的程度和u在 outlink的popular的程度. 公式由
•原来的PR(u) = 1-d + d*∑(PR(v) / N(v)), v∈B(u)
•变为 PR(u) = 1-d + d*∑(PR(v)*W in(v, u)*W out(v, u)), v∈B(u)
这样就相当于: 对于某条边(v,u), 如果其比较popular(考虑W in和W out的值), 那么在计算u的pagerank的时候v的pagerank就会占有较高的权重…
而这修改的一切都还是考虑了各个点的inlink和outlink的情况, 所以还是基于web structure的
综上, PageRank Algorithm, HITS, WPR都是基于web structure的, 即只根据每个页面的inlink和outlink来确定. 而我跟朱亮正在思考的一个问题是关于给定一篇新闻取tag的算法, 如果用TextRank算法, 发现效果低下, 和中文与英文的区别有很大关系. 于是我们想到了有权重的TextRank算法, 发现用WPR其实也不是很好, 由于我们注意到一篇新闻的有些部分是需要加强的, 比如题目, anchor text, 首段, 等等, 于是我在TextRank算法中, 有意将关键部分的那些词的权重加高了之后计算, 效果有所改善.
这里也又看到了一篇论文基于概念的权重 PageRank改进算法.
基于概念的权重PageRank算法思想:
关键部分:
wi为页面pi的权重.
a.当 K∈Concept (A)时,wi的定义:
初始时令count = 0 ;对于每一个 Out (A) 中的元素 pi ,如果 K∈ Concept (pi) ,则 count + + ;上述操作结束后,
如果 K∈Concept(pi) ,wi = 1/ count ;如果 K∈/Concept (pi) ,wi = 0。
b.当 K∈/Concept (A) ,wi 的定义:
设Ni = | Concept (A) ∩Concept (pi) | (i = 1 ,2 , ⋯,n) ,即页面 A的概念集合和页面pi 的概念集合的交集的元素个数;
令 wi 为页面pi 和页面A的权重值,则可定义wi = Ni/ ∑ Ni (i = 1 ,2 , ⋯,n) 。
而其实这个算法就是我们所需要的, 只是实现的时候觉得他的更为可靠一点, 如果将他的和自己的结合起来就会有一个比较好的结果, 但是最终我觉得如果中文要成功, 分词将会是一个很重要的部分.
随后, 朱亮还提出了启发式算法, 即只考虑题目或者首段内容进行分析, 根据中文句子结构, 比如动宾关系, 偏正关系等等来确定哪些词是重要的, 我觉得这是一个很好的想法, 还在思考中…
总结, 这算是我第一次比较认真试着读一些paper, 然后还实践了一些, 感觉读论文挺需要耐心的, 尤其读国外论文, 有一些术语很难懂, 但是一旦主要思想理解了, 大部分内容就都能看懂了, 可能自己看的论文都比较简单吧.
欢迎各种交流 
Jul
25
“不必执着在这里，我们都是伪善的。不过时间的早晚而已。”
第一篇日志, 会很长.
开这个域名很久了, 一直都没时间好好静下来写一些东西, 因为怕写的东西太水了, 其实这次写的东西就很水… 很懒, 又没东西写, 纯为了写东西写东西, 这次也一样…
考完GRE已经10天了, 意味着颓废10天了!颓废10天了!!! 嗯, 加再多叹号也没用…
和背单词纠结了一个学期了, GRE的背单词, 大作业做的背词软件, 看到背单词就有一种被恶心到了的感觉.
很奇怪, 在考GRE前的那一刻, 我突然觉得自己不想出国了, 突然觉得特别空虚, 不知道接下来该去做什么. 有人暑假会去找教授做研究, 有人会去找实习, 有人会到处旅游, 有人会宅. 我呢? 虽然已经决定好要搞一次ACM, 争取参加一次区域赛, 但也没有完全定下来去搞, 毕竟还是花更多时间找科研更好(出国的话). 显然, 我已经与KWZ学长说过的要做就做到最好越来越远, 心一直都是浮躁着的.
**************以上是好久好久之前写的, 以下开始是2010/7/24写的*************
因为昨天GRE出分了, 说实话真的一点也不算高, 但是自己很满意很满意, 因为自己准备的实在太太不充分了, 除了最后一星期之外… 所以分数比预期要好, 也让我可以静下心来好好开始自己的学习, 找了准备GRE这个借口, 自己的成绩也算差到可以让人接受.
又是一学期, 又是一年过去了, 突然就大三了… 哈哈, 什么都没做成, 没有好成绩, 没有好项目, 没有好研究, 没有好好玩游戏, 没有女朋友…
不过没关系, 还有两年呢, 出不出国也没关系, 我想如果在国外申请不到好学校, 在国内也一样的. 好多要出国的同学都找到老师开始自己的项目或者科研道路, 很羡慕他们, 不过自己也已经决定在接下来的3个月左右的时间好好准备一下ACM, 至少我觉得对以后找研究还是有不少帮助的, 即使没有成绩… 不过我现在身上也算是有一点事情做吧, 除了ACM, 算是接了中科院的一个很和蔼的学长(他让我叫他学长=.=)手上的一个小小项目做, 虽然现在基本还没做什么, 但是还是挺感兴趣的^^ 还有就是在学院里一个老师的项目组里挂了名, 虽然老师不要我们做事, 说是让我们感受一下做项目的情况, 但是感觉自己其实也是很感兴趣的, 跟数学, AI都有很大关系, 有趣的是这两个项目都跟足球有关, 啊哈哈, 上学期做的事都跟单词有关…. 不知道接下去几学期又跟什么有关呢?
不爱看书, 因为很懒, 觉得看书的人都好厉害好厉害, 于是就看看美剧, 看看电影. 话说好久没看了, 准备把”Star Trek”的系列赶紧看完…
回家一星期多了, 还只见了一个同学, 估计最多也就再见一两个吧… 见面的那个同学是女生, 还是她找我出来的, 她跟我说, 跟你说, 别人都是别人约我出来的, 只有你是我来约你的, 你出来还迟到. 我-_-||, 但是我就是这么一个人, 从来不给同学打电话, 从来不找同学玩或者什么… 我想原因大概还是因为懒吧, 我也不想改, 我知道因为这个朋友肯定不会多, 不过我也不在意, 有几个特别好的就足够了, 特别好的也就不会在意这些小事了.. 有些朋友不需要多联系, 碰到了, 有什么事了, 一样会像从前一样. 在这里也谢谢那些同学们, 哈哈, 在遥远北京仅有一个小学同学的情况下不时有你们打来的电话感觉很感动的…
同桌说我们一起去看老师吧, 我不太想去, 不知道为什么, 感觉现在去看老师真没什么可以聊的, 没新发展, 自己还是那个弱弱的没毕业的本科生…
在家吃饭睡觉就让我觉得很爽了, 哈哈, 可惜过不了多久又要回北京了><但选北航还是不后悔的, 正在选择出国也是不后悔的, 至少国内的教育实在已经到了一个让人很难接受的地步了. 就拿现在的本科而言, 我们软件学院的那些课程实在让人蛋疼=.=某些课程讲的东西扯, 有些考的东西扯, 有些评分极其不公正, 有些综合上述特征… 很不喜欢某些老师.
有时候觉得自己去数学系也不错, 虽然自己更喜欢计算机, 那当初怎么填了软件呢-_-||, 搞得现在什么都很业余…
现在想起来这学期其实还是有一些收获的, 自己上台讲东西时候不会像之前那么那么紧张了, 这个现象很好.
机器人的梦还很远很远, 看完电影”AI”后感觉那个机器人很可怜, 但是有同学说觉得人类很可怜, 角度不同吧… 不过我会努力的, 至少为那个梦想贡献一份自己小小的力量…
又想到了大四学长的毕业, 不时想着到时候自己的情形是什么样的, 也想有一个很完美的毕业, 然后一次很美好的旅行, 和同学们一起…
喜欢在失落的时候看看那些伤感的文字, 想寻找到一些共鸣, 然后睡觉, 一直睡..一直睡….睡……..
Recent Comments