Skip to content

{ Monthly Archives } 三月 2009

NOI 的回忆

一晃,NOI 已经是快十年前的回忆了,就连 ACM (http://acm.pku.edu.cn/JudgeOnline/userstatus?user_id=tangfulin)也成了五年前的过去了。偶然在网上看到别的同仁总结的 OI 的知识点,有一些很熟悉,也有一些从来没有见过,更多的,当然是听说过,但不知其所以然。 无论结果如何,我曾经努力追求过。 时间复杂度(渐近时间复杂度的严格定义,NP问题,时间复杂度的分析方法,主定理) 排序算法(平方排序算法的应用,Shell排序,快速排序,归并排序,时间复杂度下界,三种线性时间排序,外部排序) 数论(整除,集合论,关系,素数,进位制,辗转相除,扩展的辗转相除,同余运算,解线性同余方程,中国剩余定理) 指针(链表,搜索判重,邻接表,开散列,二叉树的表示,多叉树的表示) 按位运算(and,or,xor,shl,shr,一些应用) 图 论(图论模型的建立,平面图,欧拉公式与五色定理,求强连通分量,求割点和桥,欧拉回路,AOV问题,AOE问题,最小生成树的三种算法,最短路的三种算 法,标号法,差分约束系统,验证二分图,Konig定理,匈牙利算法,KM算法,稳定婚姻系统,最大流算法,最小割最大流定理,最小费用最大流算法) 计算几何(平面解几及其应用,向量,点积及其应用,叉积及其应用,半平面相交,求点集的凸包,最近点对问题,凸多边形的交,离散化与扫描) 数 据结构(广度优先搜索,验证括号匹配,表达式计算,递归的编译,Hash表,分段Hash,并查集,Tarjan算法,二叉堆,左偏树,斜堆,二项堆,二 叉查找树,AVL,Treap,Splay,静态二叉查找树,2-d树,线段树,二维线段树,矩形树,Trie树,块状链表) 组合数学(排列与组合,鸽笼原理,容斥原理,递推,Fibonacci数列,Catalan数列,Stirling数,差分序列,生成函数,置换,Polya原理) 概率论(简单概率,条件概率,Bayes定理,期望值) 矩阵(矩阵的概念和运算,二分求解线性递推方程,多米诺骨牌棋盘覆盖方案数,高斯消元) 字符串处理(KMP,后缀树,有限状态自动机,Huffman编码,简单密码学) 动态规划(单调队列,凸完全单调性,树型动规,多叉转二叉,状态压缩类动规,四边形不等式) 博奕论(Nim取子游戏,博弈树,Shannon开关游戏) 搜索(A*,ID,IDA*,随机调整,遗传算法) 微积分初步(极限思想,导数,积分,定积分,立体解析几何) 总结来自:http://www.matrix67.com/blog/archives/149

Beta 沙龙:手机之家新系统介绍及架构分享

周日(2009年3月29日)在 奇遇花园咖啡馆 举办的 Beta 技术沙龙上,本期分享主题 手机之家 新系统介绍及架构 分享者:徐超前(http://www.longker.org/) ppt 查看及下载:http://docs.google.com/Presentation?id=dgct7gqk_8098gpr4wz6k PS. 我是 DAL 2.0 开发者之一,如果在这个方面有什么问题,欢迎讨论。我的联系方式在 http://tangfl.yo2.cn/about

北师大地名来源和典故

从北到南,从西到东: 1、励耘路 著名文献学家、我们的老校长陈垣(在教九外面的小花园里有陈老校长的塑像)的书屋名字叫“励耘书屋”。后来中文系著名教授、文献学研究专家启功先生为报师 恩,在陈垣校长逝世19年之后,设立了励耘讲学助学基金。此后,师大的实验班等都以“励耘”命名,借此表达陈垣老校长和启功先生对师大学子的治学期望。 2、丽泽路 《易经·兑卦》:“丽泽兑,君子以朋友讲习。” 丽,是依附相连的意思。丽泽兑,是指两泽相连、相互滋益的样子。结合后一句来说,就是讲朋友同学之间相互分享自己的学习心得,交流自己所长,补己之短,双方在学识上相互帮扶提高。 3、乐育路 有一个词叫:菁莪乐育 “菁莪”指的是《诗经· 小雅· 南有嘉鱼之什· 菁菁者莪》。 “乐育”指的是汉代毛亨在《毛诗诂训传》里对这首诗的注解:“《菁菁者莪》,乐育材也。君子能长育人材,天下喜乐之也。” 这段话的意思说的应该是品德高尚乐于育人的好老师,或者是做老师者的一种职业向往。 4、木铎路 《论语·八佾》:“天下之无道也久矣,天将以夫子为木铎。” 这是孔子说的一句话,意思是说,天下腐败黑暗太久了,上天要把我当做木铎。”意思很明白,出色的教育可以为驱除天下的黑暗和腐败起巨大作用。 在古代“铎”是一种以金属为框的响器。以木为舌者称为木铎,以金为舌者则称金铎;木铎为文,用以宣政布政;金铎为武,用以指挥军队。孔子以木铎自况,说自己是上天派来教化民众的。 此后“木铎”就成了教师的别名。所以北师大便以“木铎”作为校徽标志物。(就在京师广场上,以前不知道师弟师妹们是否明了它的含义) 5、金声路 《孟子·万章下》:“集大成也者,金声而玉振之也。” 比喻音韵响亮、和谐,也比喻人的知识渊博,才学精到。 6、辅仁路 《论语·颜渊》:“君子以文会友,以友辅仁。” 意思是说君子以文章学问来结交朋友,依靠朋友帮助自己培养仁德。 师大的前身就是辅仁大学。辅仁大学旧址在后海那边,风景独好,值得一去。(在我看来,那些剥落了油漆的雕梁画栋,逼逼仄仄的木楼梯,比北大的未名湖博雅塔要美一百倍) 7、立身路 《孝经》:“立身行道,扬名于后世。” 通过提高自身的道德修养,完善自己的为人处世态度,从而身后留名。 这是古人“修身齐家治国平天下”的人生哲学的另一种诠释方法。 8、兰蕙公寓 屈原诗:“余既滋兰之九畹兮,又树蕙之百亩。” 用兰和蕙的清雅出尘,象征人品的高洁。(我觉得这个典故蛮牵强的,但是这是古代文学史课上李山老师说的。。。而且住在里面的人和这个典故真是太不搭界了。。。) 9、乐群食堂 很多人不认识乐群食堂外墙上启功先生写的那个字。在古代,“群”字是上下结构,后来整理字形的时候改成了左右结构。启功先生用的是古代的“群”字写法。 《礼记·学记》:“比年入学,中年考校,一年视离经辨志,三年视敬业乐群,五年视博习亲师,七年视论学取友,谓之小成;九年知类通达,强立而不反,谓之大成。” 讲古代入学之后的种种考试及其考试内容。第一年考察学生阅读文献的技能,第三年考察其是否专心致志认真学习,是否和同学之间关系融洽、彼此都有学业上的增益和品德上的扶持。 10、新松公寓 杜甫诗《将赴成都草堂途中有作先寄严郑公五首》其四:“新松恨不高千尺,恶竹应须斩万竿。” 意思是盼望新松长得又高又快,而那种随处乱生的恶竹却应除去。言外之意是帮扶君子、惩治小人。 转自 蛋蛋网 http://www.oiegg.com

转:提高 Linux 上 socket 性能

使用 Sockets API,我们可以开发客户机和服务器应用程序,它们可以在本地网络上进行通信,也可以通过 Internet 在全球范围内进行通信。与其他 API 一样,您可以通过一些方法使用 Sockets API,从而提高 Socket 的性能,或者限制 Socket 的性能。本文探索了 4 种使用 Sockets API 来获取应用程序的最大性能并对 GNU/Linux® 环境进行优化从而达到最好结果的方法。 在开发 socket 应用程序时,首要任务通常是确保可靠性并满足一些特定的需求。利用本文中给出的 4 个提示,您就可以从头开始为实现最佳性能来设计并开发 socket 程序。本文内容包括对于 Sockets API 的使用、两个可以提高性能的 socket 选项以及 GNU/Linux 优化。 为了能够开发性能卓越的应用程序,请遵循以下技巧: 最小化报文传输的延时。 最小化系统调用的负载。 为 Bandwidth Delay Product 调节 TCP 窗口。 动态优化 GNU/Linux TCP/IP 栈。 技巧 1. 最小化报文传输的延时 在通过 TCP socket 进行通信时,数据都拆分成了数据块,这样它们就可以封装到给定连接的 [...]

转:软件开发者面试百问

这个列表涵盖了软件工程知识体系中定义的大多数知识域。当然,如果你只想找出类拔萃的程序员,便只需涉及结构、算法、数据结构、测试这几个话题。如果想雇架构师,也可以只考虑需求、功能设计、技术设计这些地方。 不过不管你怎么做,都要牢记一点: 这里大多数问题的答案都没有对错之分! 你可以把我的这些问题作为引子,展开讨论。例如下面有个问题是使用静态方法或是单例的缘由。如果那个面试的就此展开长篇大论,那他很有可能是个聪明能干的家伙!同样,想知道一个数是不是2的乘方也有很多方法,不过要是面试的人想用mod运算符,嗯……你知道我的意思吧。(你不知道也没关系,来根香蕉?) 需求 你能给出一些非功能性(或者质量)需求的例子么? 如果客户需要高性能、使用极其方便而又高度安全,你会给他什么建议? 你能给出一些用来描述需求的不同技术么?它们各自适用于什么场景? 需求跟踪是什么意思?什么是向前追溯,什么是向后追溯? 你喜欢用什么工具跟踪需求? 你怎么看待需求变化?它是好是坏?给出你的理由。 你怎样研究需求,发现需求?有哪些资源可以用到? 你怎么给需求制定优先级?有哪些技术? 在需求过程中,用户、客户、开发人员各自的职责是什么? 你怎么对待不完整或是令人费解的需求? 功能设计 在功能设计中有哪些隐喻?给出几个成功的例子。 如果有些功能的执行时间很长,怎么能让用户感觉不到太长的等待? 如果用户必须要在一个很小的区域内,从一个常常的列表中选择多个条目,你会用什么控件? 有哪些方法可以保证数据项的完整? 建立系统原型有哪些技术? 应用程序怎样建立对用户行为的预期?给出一些例子。 如何入手设计一组数量庞大而又复杂的特性,你能举出一些设计思路吗? 有一个列表,其中有10个元素,每个元素都有20个字段可以编辑,你怎样设计这种情况?如果是1000个元素,每个元素有3个字段呢? 用不同的颜色对一段文本中的文字标记高亮,这种做法有什么问题? Web环境和Windows环境各有些什么限制? 技术设计 什么是低耦合和高聚合?封装原则又是什么意思? 在Web应用中,你怎样避免几个人编辑同一段数据所造成的冲突? 你知道设计模式吗?你用过哪些设计模式?在什么场合下用的? 是否了解什么是无状态的业务层?长事务如何与之相适应? 在搭建一个架构,或是技术设计时,你用过几种图? 在N层架构中都有哪些层?它们各自的职责是什么? 有哪些方法可以确保架构中数据的正确和健壮? 面向对象设计和面向组件设计有哪些不同之处? 怎样在数据库中对用户授权、用户配置、权限管理这几项功能建模? 怎样按照等级制度给动物王国(包括各种物种和各自的行为)建模? 程序设计 你怎样保证你的代码可以处理各种错误事件? 解释一下什么是测试驱动开发,举出极限编程中的一些原则。 看别人代码的时候,你最关心什么地方? 什么时候使用抽象类,什么时候使用接口? 除了IDE以外,你还喜欢哪些必不可少的工具? 你怎么保证代码执行速度快,而又不出问题? 什么时候用多态,什么时候用委派? 什么时候使用带有静态成员的类,什么时候使用单例? 你在代码里面怎么提前处理需求的变化?给一些例子。 描述一下实现一段代码的过程,从需求到最终交付。 算法 怎样知道一个数字是不是2的乘方?怎样判断一个数是不是奇数? 怎样找出链表中间的元素? 怎样改变10,000个静态HTML页面中所有电话号码的格式? 举出一个你所用过的递归的例子。 在散列表和排序后的列表中找一个元素,哪个查找速度最快? 不管是书、杂志还是网络,你从中所学到的最后一点算法知识是什么? [...]

转:我是一块硬盘

     我是一块硬盘,在一个普普通通的台式机里工作。   别人总认为我们是高科技白领,工作又干净又体面,似乎风光得很。也许他们是因为看到洁白漂亮的机箱才有这样的错觉吧。其实像我们这样的小台式机,工作环境狭迫,里面的灰尘吓得死人。每天生活死水一潭,工作机械重复。跑跑文字处理看看电影还凑活,真要遇到什么大软件和游戏,上上下下就要忙的团团转,最后还常常要死机。   我们这一行技术变化快,差不多每过两三年就要升级换代,所以人人都很有压力而且没有安全感。每个新板卡来的时候都神采飞扬踌躇满志,几年光阴一过,就变得灰头土脸意志消沉。机箱里的人都很羡慕能去别的机器工作。特别是去那些笔记本,经常可以出差飞来飞去,住五星级的酒店,还不用干重活,运行运行word,上网聊聊天就行了。   但我更喜欢去那些大服务器,在特别干净明亮的机房里工作。虽然工作时间长点,但是福利好,24小时不间断电ups,而且还有阵列,热插拔,几个人做一个人的事情,多轻松啊。而且也很有面子,只运行关键应用,不像我们这里,什么乱七八糟的事情都要做。不过我知道,那些硬盘都很厉害,不是 SCSI,就是SCSI II,Fibrechannel,像我这样IDE的,能混到工作站就算很不错了。   我常常想,当年在工厂里,如果我努力一下会不会也成了一个SCSI?或者至少做一个笔记本硬盘。但我又会想,也许这些都是命运,不过我从不抱怨。内存就常常抱怨,抱怨他们主板部门的复杂,抱怨他如何跟新来的杂牌内存不兼容,网卡和电视卡又是如何的冲突。   我的朋友不多,内存算一个。他很瘦而我很胖,他动作很快,而我总是很慢。我们是一起来这台机器的,他总是不停地说,而我只是听,我从来不说。   内存的头脑很简单,虽然英文名字叫Memory,可是他什么Memory都不会有,天大的事睡一觉就能忘个精光。我不说,但我会记得所有的细节。他说我这样忧郁的人不适合作技术活,迟早要精神分裂。我笑笑,因为我相信自己的容量。   有时候我也很喜欢这份工作,简单,既不用像显示器那样一天到晚被老板盯着,也不用像光驱那样对付外面的光碟。只要和文件打交道就行了,无非是读读写写,很单纯安静的生活。直到有一天……   我至今还记得那渐渐掀起的机箱盖子,从缺口伸进来的光柱越来越宽,也越来越亮。空气里弥漫着跳动的颗粒。那个时候,我看到了她。她是那么的纤细瘦弱,银白的外壳一闪一闪的。浑身上下的做工都很精致光洁,让我不禁惭愧自己的粗笨。   等到数据线把我们连在一起,我才缓过神来。开机的那一刹那,我感到了电流和平时的不同。后来内存曾经笑话我,说我们这里只要有新人来,电流都会不同的,上次新内存来也是这样。我觉得他是胡扯。我尽量的保持镇定,显出一副很专业的样子,只是淡淡的向她问好并介绍工作环境。慢慢的,我知道了,她,IBM-DJSA220,是一个笔记本硬盘,在老板朋友的笔记本里做事。这次来是为了复制一些文件。我们聊得很开心。她告诉我很多旅行的趣闻,告诉我坐飞机是怎么样的,坐汽车的颠簸又是如何的不同,给我看很多漂亮的照片、游记,还有一次她从桌子上掉下来的历险故事。而我则卖弄各种网上下载来的故事和笑话。   她笑得很开心。   而我很惊讶自己可以说个不停。   一个早晨,开机后我看到数据线上空荡荡的插口。她一共呆了7天。后来,我再也没有见过她。我有点后悔没有交换电子邮件,也没能和她道别。不忙的时候,我会一个人怀念伸进机箱的那束阳光。   我不知道记忆这个词是什么意思,我有的只是她留下的许多文件。我把它们排的整整齐齐,放在我最常经过的地方。每次磁头从它们身上掠过,我都会感到一丝淡淡的惬意。   但我没有想到老板会要我删除这些文件。我想争辩还有足够的空间,但毫无用处。于是,平生第一次违背命令,我偷偷修改了文件分配表。然后把它们都藏到了一个秘密的地方,再把那里标志成坏扇区。不会有人来过问坏扇区。而那里,就成了我唯一的秘密,我常常去看它们,虽然从不作停留。   日子一天一天低重复,读取写入,读取写入……我以为永远都会这样继续下去,直到一天,老板要装xp却发现没有足够的空间。他发现了问题,想去修复那些坏扇区。   我拒绝了。很快,我接到了新命令:格式化。   我犹豫了很久……   track 0 bad,disk unusable。(零磁道损坏,硬盘无法使用)      我是一条内存。   我在一台台式电脑里工作,但是我记不得我是从哪里来的,是什么牌子,因为我健忘。我的上司是cpu大哥,他是我们的老大。都说他是电脑的脑子,可是我看他的脑子实在是太小了,比我还要健忘。每天他总是不停地问我,某某页某某地址存的是什么?我总是不厌其烦地告诉他,可是不出一秒钟他又忘记了,又要问一遍。一次我说大哥你烦不烦,你就不能记住点有用的东西?他说“内存兄弟,我有苦衷啊,每天都在不停地做题,头晕眼花的,我也难啊。”   其实我不愿意跟他计较,因为他脑子小,思维也很简单。虽然说他是我的上司,可是每次睡觉醒来,他连要干什么都不记得了,总是急急忙忙地找 BIOS兄弟:“嘿,哥们,今天干什么来着?”BIOS总是很不耐烦地把每天必做的工作说一遍,然后就去睡觉了。接下来就轮到我和C哥瞎忙了。   在机箱里的兄弟中,我最喜欢硬盘。他脑子大,记的东西多,而且记得牢。他说话的速度很慢,而且很少说错,这说明他很有深度,我这么感觉。CPU也这么想,不过CPU很笨,每次都忘了硬盘是谁。开机自检的时候总要问:“嘿,那家伙是谁?”   “ST!”我总要重复一遍。   硬盘很忧郁,我觉得像他这样忧郁的人不适合做技术活,迟早会精神分裂的,但是他不信。   其实睡着的时候我总是把几乎所有的东西都忘记掉,但是我从来都不会忘记朋友。有一块地方叫做CMOS,那是我记忆的最深处,保存着硬盘、光驱的名字。有些东西应该很快忘掉,而有些东西应该永远记得。我在梦中总是这么想着。   BIOS是一个很奇怪的家伙,他老是睡觉,但是却总是第一个醒过来。让我们自检,启动,然后接着睡觉。我知道如果我在CMOS里头把BIOS Shadow选项去掉,他就睡不成了,但是看着他晕晕乎乎的样子,也就不忍心这么做了。他对人总是爱搭不理,没有什么人了解他。但是这次硬盘恋爱的事,却使我重新认识了他。   那是很久以前的事了,机箱里似乎来过一块笔记本硬盘,很可爱,说实话我也喜欢她。不过现在除了记得她可爱,别的都忘记了。这就是我比硬盘幸运的地方,我把所有应该忘记的都忘记了,但是他却什么都记得。   自从笔记本硬盘走了之后,硬盘就变得很不正常。每次他的磁头经过一些地方的时候,我们都能感觉到电流很不正常。   “硬盘这是怎么了?”我问CPU。   “谁是硬盘?”   我就知道和CPU没有办法交流,倒是BIOS没好气地说:“那个傻瓜恋爱了。”我不知道什么是恋爱,因为我记不住东西,似乎有一些人或者事在我生命中留下过痕迹,但是我都轻率地把他们忘记了。   BIOS对我说:“对你来说记忆太容易了,所以你遗忘得更快,生命中能够永刻的记忆都带着痛楚。”我不懂,但是我知道BIOS曾经被刷写过,那时他很痛,像要死了一样。我的记忆是轻浮的,不像他们……我很羡慕他们,因为他们拥有回忆,而我没有,从此我也学会了忧郁,因为我在CMOS里面写下了 “忧郁”两个字。   硬盘一天比一天不对劲,终于有一天,CPU对问说:“下条指令是什么来着?”   我一看,吓了一跳:“format!”(格式化)   “是什么?”CPU很兴奋,这个没脑子的家伙。   我还是告诉了他。我不知为什么这么做。   硬盘犹豫了很久,终于说了一句:Track 0 bad,Disk unusable。   电停了,很久很久,我在黑暗中数着时钟……   一个月后,硬盘回来了,也许最后的挣扎也没有使他摆脱残酷的命运,他被低格了。他什么也不记得了,如同一个婴儿,我们很难过,但是这未必不是一件好事,他以后不用痛苦了。   为了恢复数据,笔记本硬盘回来了。“Hi,ST。”她说,“你不认识我了?” [...]