我的2008年

       现在是2008年12月31号23点25分,再有35分钟就迎来了新的一年-2009年,以前从来没有过写年终总结的习惯,不过今年在同学hj的极力推荐下,决定开始写了,权当以后留作纪念了 :)

       今年总体来说,感觉过的还是很平淡(其实每年都是这感觉,呵呵),我觉得可能和自己的要求有点高也有关系吧,呵呵~。既然作为学生,还是先谈谈学习。刚开学的排名搞得我确实有点郁闷,貌似自己每年都在退步阿。。不过大学我感觉自己也没把学习看得像高中那样重,所以其实也没感觉到什么。。而且大学的考试的性质也不在此。。不说这个了~,其他的,本学年课程感觉都很空乏,就是很没有趣味,算法虽然还行,不过老师的讲课方式和内容让我确实提不起兴趣。。于是自己去找了下mit的算法导论课程开始学习(以前大概也看过一些,不过很粗略),这次打算认真的学习一下,包括做课后习题,然后发现了无数的困难,只能慢慢啃,结果现在只看了1/3,不过看那个mit的视频课程,确实非常赞的说。建议大家有空的话还是多看看吧。

       今年开了门软件项目管理的课,让分组做一个项目,我们在lyc的带领下,在今天结束了项目(意见墙)的验收,虽说这个过程也学习了structs和hibernate,不过感觉技术含量也不是非常高,可能是我至今没有明白web开发的真谛吧,哪位大牛有看法的可以指点一下~

     除了这些,大致搞了一段的acm,做了一些题目,不过没有什么成绩。。。看完了鸟哥的第一册。。开始学习sicp第二章。。。,唯一感觉比较爽的还是下学期的实习抽到了北京,1/3的概率,说明我rp还是可以的嘛,到时候看看能不能见见老同学,呵呵。

   生活上,深深体会到了:身体是革莫道不消魂命的本钱啊,我的身体本来就不好,自己也没有自制力坚持锻炼,所以一旦生病的话,感觉就很严重(现在还在感冒中:)),新的一年,一定要改正了,毕竟搞it的,身体才是最终要的。。

     下学期崭时还没有多想,先考虑把英语学好吧,毕竟我很有可能要考研了,英语是一大关啊。。对今后也很有好处。。最近考试n多,疯狂复习中啊(从来没有感觉这么累。。),呵呵,先写这么多吧,考完试了再补充。。。

Posted in 生活随记 | Leave a comment

计算的美丽–1971年图灵奖获得者John McCarthy

John McCarthy ( 09/04/1927–)

1971 第六位奖获

(Turing Award Citation)

Dr. McCarthy’s lecture “The Present State of Research on Artificial Intelligence” is a topic that covers the area in which he has achieved considerable recognition for his work.

【笔者译:】

“ ( John MacCarthy ) MacCarthy博士的”人工智能研究的现状“一文充分体现了其在人工智能领域有目共睹的杰出的贡献。”

【笔者 :】

关于人工智能的一些介绍可参见:

Artificial Intelligence: http://en.wikipedia.org/wiki/Artificial_intelligence
Brief History of Artificial Intelligence:
http://www.aaai.org/AITopics/bbhist.html
http://www.answers.com/topic/history-of-artificial-intelligence

例外,McCarthy也是著名人工智能语言Lisp的发明者。关于Lisp的一些基本介绍可参见:

Lisp语言的主站: www.lisp.org
Lisp的历史介绍(Brief History of the Lisp Language):
http://www.lisp.org/table/Lisp-History.html

Lisp的人们及其他一些教育资料:

http://www.lisp.org/alu/res-lisp-education
http://www.engin.umd.umich.edu/CIS/course.des/cis400/lisp/lisp.html 

Turing Award Lecture (图灵奖演讲文章):

Generality in Artificial Intelligence. Commun. ACM 30(12): 1029-1035(1987)

笔者注:此文直到1987年才被收集发表。

Abstract:  My 1971 Turing Award Lecture was entitled “Generality in Artificial Intelligence.” The topic turned out to have been overambitious in that I discovered I was unable to put my thoughts on the subject in a satisfactory written form at that time. It would have been better to have reviewed my previous work rather than attempt something new, but such was not my custom at that time. I am grateful to ACM for the opportunity to try again. Unfortunately for our science, although perhaps fortunately for this project, the problem of generality in artificial intelligence (AI) is almost as unsolved as ever, although we now have many ideas not available in 1971. This paper relies heavily on such ideas, but it is far from a full 1987 survey of approaches for achieving generality. Ideas are therefore discussed at a length proportional to my familiarity with them rather than according to some objective criterion. It was obvious in 1971 and even in 1958 that AI programs suffered from a lack of generality. It is still obvious; there are many more details. The first gross symptom is that a small addition to the idea of a program often involves a complete rewrite beginning with the data structures. Some progress has been made in modularizing data structures, but small modifications of the search strategies are even less likely to be accomplished without rewriting. Another symptom is no one knows how to make a general database of commonsense knowledge that could be used by any program that needed the knowledge. Along with other information, such a database would contain what a robot would need to know about the effects of moving objects around, what a person can be expected to know about his family, and the facts about buying and selling. This does not depend on whether the knowledge is to be expressed in a logical language or in some other formalism. When we take the logic approach to AI, lack of generality shows up in that the axioms we devise to express commonsense knowledge are too restricted in their applicability for a general commonsense database. In my opinion, getting a language for expressing general commonsense knowledge for inclusion in a general database is the key problem of generality in AI. Here are some ideas for achieving generality proposed both before and after 1971. I repeat my disclaimer of comprehensiveness.

McCarthy在其Stanford大学的网页上,发布了其原文的修改稿。

http://www-formal.stanford.edu/jmc/generality/generality.html
http://www-formal.stanford.edu/jmc/generality.html

John McCarthy :

McCarthy19279月出身于美国波士顿1948年在加州理工大学(California Institute of Technology) 获得其数学学士位。 1951年资普林斯顿(Princeton University) 获得其数学博士学位。然后,McCarthy分别就职与普林斯顿,斯坦福(www.stanford.edu ), Dartmouth (www.dartmouth.edu )MIT(www.mit.edu ) AI(人工智能)一词通常认为是McCarthy 1955年在DartMouth期间的一个会议上提出来的(http://en.wikipedia.org/wiki/Dartmouth_Conference ) 1962年,McCarthy加入坦福大学,并创建了斯坦福人工智能实验室,并一直领佳节又重阳导着这方面的工作直到2000年退休。 McCarthy也是MIT 人工智能实验室的发起人之一。也是人工智能语言LISP的发明者。McCarthy Standford AI Lab 创办人。John McCarthy  Wiki: http://en.wikipedia.org/wiki/John_McCarthy_%28computer_scientist%29 

Posted in 生活随记 | Leave a comment

Ubuntu安装rpm的方法

1、先安装 alien : sudo apt-get install alie 。

2、转换 RPM 安装包:sudo alien -k name-of-rpm-file.rpm

3、这才开始安装:sudo dpkg -i name-of-rpm-file.deb。

Posted in Linux | Leave a comment

为软件系统建立文档

目标

一个没有良好文档的系统就算能够运行也没有什么价值。对于小型的、不重要的、只使用很短时间的程序,一点注释就够了。但是对于大部分程序,如果唯一的文档 就是代码本身,那么这个程序将很快过时而且难以维护。大多数初学者通常对于在建档方面做出的小小努力就能够获得回报、甚至

影响整个项目感到惊讶。 除非你是永不犯错的,并且生活在一个从不改变的世界中,否则你必然会重新面对你以前所编写的代码,并对你在以前开发中所做的选择感到疑惑。如果你不对你的 选择建立文档,你很可能会犯和以前开发过程中同样的错误,而这些错误很容易就能说明白。缺乏文档不仅会增加额外的工作,而且会损坏代码的质量。例如,假设 你对问题没有一个清晰的描述,那么你就很难开发一个明白的解决方案。

学习如何进行软件系统建档是困难的,而且它要求成熟的基于项目的判断能力。建立文档过少是一个常见的错误,但是如果走向另一个极端也同样会产生问题:如果你的文档太多,那些文档将成为阅读者巨大的障碍,而且它的维护工作将是一个负担。只对正确的事物建模是至关重要的。如果文档的长度令读者望而生怯,那么它就没有什么价值。

初学者常常会被简单的问题所吸引而在上面作出大量的努力,因此比较容易建立文档。但是那只能浪费时间,你从你所做的努力中并不能学到什么,最终得到没有什 么用处的文档。初学者还经常不愿意为问题建档,这样做是目光短浅的:如果你知道你所设计的一些方面并不完善、问题的某些部分并没有说清楚、或者代码中可能 存在一些错误,你就会同意我们的观点了。如果认识到以上问题,你就能够节省读者花在一些令人迷惑的看起来是错误的问题上的时间,在你遇到问题的时候能够记 得该查看什么地方,最终得到一个更加真实的有用的文档。

另一个问题是在什么时候建立文档。虽然有时将建立文档的工作推迟到实验之后是有意义的,但是有经验的开发者一般会在系统开始时建立文 档,甚至对于临时代码、初始问题分析、以及设计草图也会建立文档,因为他们发现这样做可以在实验中得到更多有用的结果。此外,因为他们养成了建立文档的习 惯,对任何问题建立文档就是自然而然的事情了。

本 讲义将针对6.170项目的建档问题给你一些指导。文中给出了一个概要结构以及一些要求做到的要素,但是对于细节问题,文中留出了很大的空间给你自己做决 定。重要的是不要把建立文档当成一件无关紧要的、无聊的事情;如果你这么认为,由你所编写的文档必定会是没有什么用处的、难以阅读的。所以,请有意识的编 写文档:在编写文档的时候问你自己为什么要那样做,你的时间是否达到了最高的使用效率。

你可以随意的将我们提供的讲义粘贴到你的文档中,特别地,你可能会需要使用部分的问题定义讲义来描述你的需求。但是,请记得将你所做的任何改变清楚的标明出来,这样你的助教就不用手动去模拟Unix diff

大纲

你的文档应该有以下结构。一个典型的6.170课程的大概页数已经给出,但是这些只是指导而不是要求。

1. 需求

需求部分描述要解决的问题本身以及它的解决方案。这部分的文档是开发者和使用者都需要关注的,它应该包含一些特殊实现策略的细节。系统其它部分的文档可能对于使用者并没有什么作用,而对开发者、维护者则是必须的。

  1. 概述(大约一页). 一个对于系统目标以及系统所能提供功能的解释。
  2. 修订的规格说明. 如果你已经得到了系统行为的详细规格说明,你必然会发现系统的某些部分并没有说明或者没有说清楚。在这个阶段你应该把你对于需求的任何想法以及你对需求所做的任何改动说清楚。
  3. 用户手册(1-5页). 对于用户该怎样使用系统的详细描述:用户可以进行什么操作、命令行的参数都有哪些、等等。格式的详细说明应该放在附录中。任何假定的外部环境都应该在这里 说清楚:例如,这个程序是否只能在特定平台上运行、假设已经存在了一个相应的目录结构、假设已经安装了相应的其他应用程序、等等。同概述一起,这个手册应 该为用户提供关于系统的所有信息。
  4. 性能(半页). 系统正常运行需要哪些资源,它将要耗费多少时间和空间?
  5. 问题分析(2-10页). 一个对于以下问题的清楚描述。这包括在设计之后的一个概念模型(以及可能的用户接口),如果它们还没有被讨论到。问题分析通常包括一个或多个问题对象模 型,它们的设置和关系的定义,以及任何关于巧妙解决方法的讨论。问题对象模型中的对象并非来自代码,而是来自问题域。对象模型应该包括图和所有关键的文本 约束,它们应该安排的整洁易读。这部分还应该描述被否定掉了的解决方法,包括它们的原因、它们解决了的问题、或者没有完全说清楚将在稍后解决的方面。

你可能会发现使用用例将对你的修订的规格说明以及用户手册的编写大有帮助。一个用例是一个特殊的目标以及用户为达成此目标所做的一系列动作。一个客户可以检查动作列表,从而决定用户接口是否合理。如果用例集合覆盖了所有要求的用户目标,那么客户就有理由相信系统将能够达到它的目标。

2. 设计

你的文档的设计部分给出一个你的实现策略的高层视图。

  1. 概述(0.5-3页). 设计的一概述:顶层组织结构、特殊的设计方案、库和其它第三方模块的使用、以及没有确定的或可能改变的方面的指示。还应包括设计中的问题:可能产生错误的决定,以及在灵活性和高效性两者间可能不恰当的选择。
  2. 运行时结构(1-5页). 一个运行中程序状态结构的描述,以代码对象模型来表示。这个模型应该隐藏抽象数据类型的表示,它的目标是展现各个对象之间的关系。对象模型应该包括图和所 有关键的文本约束,它们应该安排的整洁易读。应该解释特殊的、特别复杂的或者对于整个设计特别重要的数据类型的表示(同它们的抽象函数以及表示不变式 (representation invariants或rep. invariants)一起)。注意,抽象函数和rep. invariants还应该出现在它们在代码中本来应该出现的位置。
  3. 模块结构(1-5页). 一个对于程序文本语法结构的描述,用模块依赖图来表示。这当中应该包括包结构,并展示Java�接口和类。并不需要描述Java橝PI类之间的依赖关系。 你的MDD应该安排的整洁易读。解释为什么要选择这样的语法结构(例如,对于分解接口的介绍-它们分解了什么,以及为什么要这样做),以及特殊的设计模式 是怎样使用的。

要解释分解或其他设计中的决定,从它们对程序简单性、可扩展性(方便添加新功能)、可拆分性(各个的团队成员可以同时进行设计的各个不同部分,而不用常常交流)或相似的软件工程目标来进行讨论。

3.测试

你的文档的测试部分表明了你为了检验和确认系统所做的工作。(对于一个真实的系统,这可能包括用户测试以确定系统是否满足了需求部分所描述的功能,还应包 括通过运行多组测试来检验代码的正确性。)如同不能用代码甚至类的列举来代替你的系统的设计文档,你也不应该仅仅列举你所执行的测试来代替这部分文档。你 应该讨论测试用例是怎样选择的、为什么选择它们就足够了、为什么一个阅读者应该相信没有遗漏重要的测试、以及为什么读者应该相信系统将会按照要求的那样执 行操作。

  1. 策略(1-2页). 一个对于总体测试策略的解释:黑盒和/或白盒测试,自顶向下测试和/或自底向上测试,所使用的测试驱动的种类、测试的数据源、测试用例、覆盖规模、编译时 检查或者运行时断言、你的代码的论证,等等。对程序的不同部分,你可能需要使用不同的技术(或者混和使用不同技术)。对于不同情况,调整你的选择。

    解释通过你所指定的策略你期望找到哪些错误。讨论设计的哪些方面使得它容易或难以确认。

  2. 测试结果(0.5-2页). 总结都进行了哪些测试,以及还有哪些没有进行:测试了哪些模块,有多彻底?指出代码的可信程度:彻底清楚了哪种错误?还可能存在哪种错误?

4.反思

文档中的反思(通常称为�事后剖析�)部分是你能够从开发中特殊部分的失败或成功中得到的对于以后的软件开发有用的规则。什么最令你吃惊?在开始的时候你最想知道什么?在开发时怎样避免你所遇到的问题?

  1. 评价(0.5-1页). 你认为什么开发中的成功或失败:没有解决的设计问题、性能问题,等等。指明你的设计中哪些功能是重要的。指出你在设计或实现中使用的令你感到骄傲的技术。讨论你在设计中犯了哪些错误,以及它们产生的原因。
  2. 教训(0.2-1页). 从开发中你学到了哪些教训:如果在来一次和这次将有什么不同,以及怎样纠正设计和实现中的错误。描述问题产生的原因,例如错过了里程碑或者已知的错误和限制。
  3. 已知的错误和限制:准确描述你的实现中没能满足规格说明的地方。虽然这样会因为错误和缺少功能丢分,但是你将会因为明确标明哪些错误以及问题的根源得到额外的分数。

5.附录

附录包含系统的低层细节,这些细节对于系统的高层理解不是必要的,但是需要通过它们来实践或检验文档中其他部分提出的主张。

  1. 格式. 一个对于程序中用到的所有格式的描述:对于文件I/O、命令行参数、用户对话框、网络交互的消息格式、等等。它们应该被分解为用户可见的格式和内部格式。用户可见格式指用户可以看到的需求和用户手册中的部分,内部格式指你的文档中的其他部分中的格式说明。
  2. 模块规格说明. 你应该从你的代码中提取规格说明并将它们分别表示在这里。如果你按照6.170 doclet的Javadoc风格为你的代码编写注释,你将能够从代码中自动生成规格说明。一个抽象类型的规格说明应该包括它的概述、规格说明域、以及抽象不变式(规格说明约束)。抽象函数和rep invariant不属于一个类型的规格说明。
  3. 试用例. 理想上,你的实验台从一个按照易于读写的格式保存测试用例的文件中读取测试。不需要包括特别大的测试用例;例如,你可能只关心为强度测试产生的随机输入的 大小,以及提供产生测试的程序。指出各组测试的目的(例如,�强度测试,大输入�,�划分测试,对于整型参数,所有+/-/0的组合�)。

为代码建立文档

规格说明层次的注释

抽象数据类型. 每个抽象数据类型(类或者接口)应该有:

  1. 一个概述部分,使用一到两行解释这个类型表示什么对象以及它们是否是可变的。
  2. 一个规格说明域列表。可能只有一个;例如,一组可能有一个elems域表示元素的集合。每个域应该有一个名称、一个类型和一段简短的说明。定义一个派生域可能会使得方法规格说明的编写变得容易很多;对于每个派生域,你应该指出它是派生的以及说明它是如何从其它域中派生出来的。可能会有约束规格说明域可能取值的规格说明不变式,如果有的话,你应该给出它们的说明。

方法规格说明. 类中所有的公有方法都应该有规格说明,有技巧的私有方法也应该说明。方法规格说明遵守规格说明讲义中描述需求、改变、抛出、效果、返回的结构。注意,在6.170课程中如果没有特殊说明,你可以认为所有方法的参数都不能为空。

实现级的注释

执行程序注释. 类的注释应该包括以下要素(对于重要的类,还应包括设计文档中的运行时结构部分):

  1. 一个抽象函数,它使用表示域定义各个规格说明域。只有是抽象数据类型的类才要求抽象函数,对于异常或GUI widgets这样的类并不要求。
  2. 一个表示不变式(representation invariant). 任何有表示的类都需要RIs。如果可以执行,我们强烈推荐你使用checkRep()来测试你的不变式。注意你的不变式假设中哪些可以为空,哪些不能。
  3. 对于表示很复杂的类,一段注解用来解释表示的选择( 也称为表示原理):做出了怎样的折中,什么方案在提出后又被否决了(为什么)。
Posted in 软件工程实验 | Leave a comment

匈牙利算法

        还记得上学期上数学建模课程的时候,有个锁和钥匙匹配的相关问题,当时书上写的匈牙利算法,复杂无比。。顿时让我产生了巨大的恐惧,连看都没看完,今天做usaco的stall4的时候,重新学习了一下,发现代码竟是如此的简单。。

代码模板:

bool 寻找从k出发的对应项出的可增广路
{
while (从邻接表中列举k能关联到顶点j)
{
if (j不在增广路上)
{
把j加入增广路;
if (j是未盖点 或者 从j的对应项出发有可增广路)
{
修改j的对应项为k;
则从k的对应项出有可增广路,返回true;
}
}
}
则从k的对应项出没有可增广路,返回false;
}

void 匈牙利hungary()
{
for i->1 to n
{
if (则从i的对应项出有可增广路)
匹配数++;
}
输出 匹配数;
}

stall4代码:

/*
ID: shyang.2
PROG: stall4
LANG: C++
*/
#include<iostream>
using namespace std;
#define max 210
long N,M;
bool mark[max];
int v[max][max];
int mat[max];
int ans=0;
void input()
{
//freopen("d:\in.txt","r",stdin);
freopen("stall4.in","r",stdin);
freopen("stall4.out","w",stdout);
cin>>N>>M;
for(int i=1;i<=N;i++)
{
cin>>v[i][0];
for(int j=1;j<=v[i][0];j++)
cin>>v[i][j];
}
memset(mark,0,sizeof(mark));
memset(mat,0,sizeof(mat));
}
bool find(int k)
{
for(int i=1;i<=v[k][0];i++)
{
int j=v[k][i];
if(!mark[j])
{
mark[j]=1;
if(mat[j]==0||find(mat[j]))
{
mat[j]=k;
return true;
}
}
}
return false;
}
int main()
{
input();
for(int i=1;i<=N;i++)
{
if(find(i))
ans++;
memset(mark,0,sizeof(mark));
}
cout<<ans<<endl;
//for(; ;) ;
return 0;
}

Posted in 算法 | Leave a comment

奥巴马简历

Biography
Personal
Birthdate: August 4, 1961 (Honolulu, Hawaii)
Hometown: Jakarta, Indonesia; Honolulu, Hawaii
Spouse: Michelle Robinson Obama
Children: Malia Ann Obama, Sasha Obama
Religion: United Church of Christ

Education
Harvard Law School, J.D., 1991
Occidential College/Columbia University, B.A.
Punahou School

Experience
Businesses Owned, Past Careers, Board Memberships, Etc.:
Center for Neighborhood and Technology
Chicago Annenberg Challenge
Cook County Bar
Cook County Bar Association Community Law Project
Board Member, Joyce Foundation
Lawyer's Committee for Civil Rights Under the Law
Leadership for Quality Education
Member, Trinity United Church of Christ
Board Member, Woods Fund of Chicago

Public Service / Elected Offices:
Senator, United States Senate, 2005-present
Senator, Illinois State Senate, 1997-2004

Book(s)
Dreams from My Father: A Story of Race and Inheritance by Barack Obama
The Audacity of Hope: Thoughts on Reclaiming the American Dream by Barack Obama

中文翻译:
个人及家庭情况
生日:1961年8月4日(美国,夏威夷,檀香山)
家乡:雅加达,印度尼西亚;檀香山,夏威夷。
配偶:蜜雪儿· 罗宾逊 ·奥巴马
子女:玛丽 安 奥巴马 萨莎 奥巴马
信仰:联合基薄雾浓云愁永昼督教会

教育经历
哈佛大学法学院, 法律博士,1991
西方学院/哥伦比亚大学, 文学士
普那胡学校

职业经历
邻居和技术中心
库克县律师协会
库克县律师协会社区法项目
乔伊斯基金会董事会成员
芝加哥森林基金会

公共服务:
伊力诺依州,州议会参议员,1997年-2004年
美国国会参议员,代表伊力诺依州,民瑞脑消金兽主党,2005年至今

著作:
《我父亲的梦想:一个关于种族和继承的故事》
《无畏的希望: 重申美国梦》

Posted in 生活随记 | Leave a comment

[转载] 约瑟夫问题的数学方法(O(n))

问题描述:n个人(编号0~(n-1)),从0开始报数,报到(m-1)的退出,剩下的人继续从0开始报数。求胜利者的编号

我们知道第一个人(编号一定是m%n-1) 出列之后,剩下的n-1个人组成了一个新的约瑟夫环(以编号为k=m%n的人开
始):
k  k+1  k+2  ... n-2, n-1, 0, 1, 2, ... k-2
并且从k开始报0。

现在我们把他们的编号做一下转换:
k     --> 0
k+1   --> 1
k+2   --> 2
...
...
k-2   --> n-2
k-1   --> n-1

变换后就完完全全成为了(n-1)个人报数的子问题,假如我们知道这个子问题的解:例如x是最终的胜利者,那么根
据上面这个表把这个x变回去不刚好就是n个人情况的解吗?!!变回去的公式很简单,相信大家都可以推出来:x'
=(x+k)%n

如何知道(n-1)个人报数的问题的解?对,只要知道(n-2)个人的解就行了。(n-2)个人的解呢?当然是先求(n-3)的
情况 ---- 这显然就是一个倒推问题!好了,思路出来了,下面写递推公式:

令f[i]表示i个人玩游戏报m退出最后胜利者的编号,最后的结果自然是f[n]

递推公式
f[1]=0;
f[i]=(f[i-1]+m)%i;  (i>1)

有了这个公式,我们要做的就是从1-n顺序算出f[i]的数值,最后结果是f[n]。因为实际生活中编号总是从1开始,
我们输出f[n]+1

由于是逐级递推,不需要保存每个f[i],程序也是异常简单:

#i nclude <stdio.h>

main()
{
int n, m, i, s=0;
printf ("N M = "); scanf("%d%d", &n, &m);
for (i=2; i<=n; i++) s=(s+m)%i;
printf ("The winner is %d\n", s+1);
}

这个算法的时间复杂度为O(n),相对于模拟算法已经有了很大的提高。算n,m等于一百万,一千万的情况不是问题
了。可见,适当地运用数学策略,不仅可以让编程变得简单,而且往往会成倍地提高算法执行效率。

Posted in ACM/ICPC | 2 Comments

求最小环问题

一种比较差的办法是一次dijkstra后,删除一条边,然后再进行一次,效率很低。
我们可以借助Floyd的变形在O(n^3)内解决次问题。
在floyd的同时,顺便算出最小环g[i][j]=i,j之间的边长
dist:=g;
for k:=1 to n do
begin
for i:=1 to k-1 do
for j:=i+1 to k-1 do
answer:=min(answer,dist[i][j]+g[i][k]+g[k][j]);
for i:=1 to n do
for j:=1 to n do
dist[i][j]:=min(dist[i][j],dist[i][k]+dist[k][j]);
end;

最小环改进算法的证明
一个环中的最大结点为k(编号最大),与他相连的两个点为i,j,这个环的最短长度为g[i][k]+g[k][j]+i到j的路径中,所有结点编号都小 于k的最短路径长度。根据floyd的原理,在最外层循环做了k-1次之后,dist[i][j]则代表了i到j的路径中,所有结点编号都小于k的最短路 径
综上所述,该算法一定能找到图中最小环。

Posted in 算法 | Tagged , , | 2 Comments

皮克定理-求多边形内部的格点数

皮克定理

来自"NOCOW"

给定顶点坐标均是整点(或正方形格点)的简单多边形,皮克定理说明了其面积A和内部格点数目i、边上格点数目b的关系:A = i + b/2 - 1。

证明

因为所有简单多边形都可切割为一个三角形和另一个简单多边形。考虑一个简单多边形P,及跟P有一条共同边的三角形T。若P符合皮克公式,则只要证明P加上TPT亦符合皮克公式(I),与及三角形符合皮克公式(II),就可根据数学归纳法,对于所有简单多边形皮克公式都是成立的。

多边形

PT的共同边上有c个格点。

  • P的面积: iP + bP/2 - 1
  • T的面积: iT + bT/2 - 1
  • PT的面积:
(iT + iP + c - 2) + (bT- c + 2 + bP - c + 2 ) /2 - 1
= iPT + bPT/2 - 1

 三角形

证明分三部分:证明以下的图形符合皮克定理:

  1. 所有平行于轴线的矩形;
  2. 以上述矩形的两条邻边和对角线组成的直角三角形;
  3. 所有三角形(因为它们都可内接于矩形内,将矩形分割成原三角形和至多3个第二点提到的直角三角形)。

 矩形

设矩形R长边短边各有m,n个格点:

  • AR = (m-1)(n-1)
  • iR = (m-2)(n-2)
  • bR = 2(m+n)-4
iR + bR/2 - 1
= (m-2)(n-2) + (m+n) - 2 - 1
= mn - (m + n) +1
= (m-1)(n-1)

直角三角形

易见两条邻边和对角线组成的两个直角三角形全等,且i,b相等。设其斜边上有c个格点。

  • b = m+n+c-3
  • i = ((m-2)(n-2) - c + 2)/2
i + b/2 - 1
= ((m-2)(n-2) - c + 2)/2 + (m+n+c-3)/2 - 1
= (m-2)(n-2)/2 + (m+n - 3)/2
= (m-1)(n-1)/2

 推广

  • 取格点的组成图形的面积为一单位。在平行四边形格点,皮克定理依然成立。套用于任意三角形格点,皮克定理则是A = 2i + b - 2。
  • 对于非简单的多边形P,皮克定理A = i + b/2 - χ(P),其中χ(P)表示P的欧拉特征数。
  • 高维推广:Ehrhart多项式;一维:植树问题。
  • 皮克定理和欧拉公式(V-E+F=2)等价。

定理提出者

Georg Alexander Pick,1859年生于维也纳,1943年死于特莱西恩施塔特集中营。

Posted in ACM/ICPC | Leave a comment

<<美丽心灵>>

本文部分参考杂乱的书桌”(Huge),无意中在一个博客里面看到了这部电影的介绍,虽然是很早的了,仍然把它看了遍,毕竟,有些东西是永恒的,不会随着时间的改变而改变,经典更是如此- -《美丽心灵》的原型是数学家以及经济学家小约翰-福布斯-纳什(Jr.John Forbes Nash),但是电影中更多的却展示的是一种心路历程电影《美丽心灵》开始于一个虚构的 Helinger 教授的演讲,演讲上说美国的数学家在抵御纳粹的战争中发挥了重要作用,现在要把注意力转向抵抗苏联共人比黄花瘦产主义。这也为后来纳什与国防部的合做埋下了伏笔。从普林斯顿大学的迎新会开始,纳什便给人这样的印象:他似乎认为数学可以解释一切。他用数学公式和数学推理来表达生活中的一切。纳什在看到了阳光下玻璃杯和柠檬的影像,和同学的领带图案相似,于是纳什微微一笑,对那个同学说:知道吗?我可以从数学的角度来解释你的领带有多么难看。他 会从数学的角度来看一场橄榄球比赛,他会蹲在那里用数学研究鸽子的活动周期,他会在酒吧里的社交活动中发现了他著名的纳什平衡。一直到后来纳什为国防部工作,成功从无序的数字中找到了密码。这所有的一切,都是以再正常不过的形式在进行,仿佛这所有的一切都是在展现天才的数学家出众的数学天赋,除了后来纳什执著于从报刊的文字中寻找情报,并送到一个很神秘的地方之外,我一直都没有意识到这么多的事情,竟然都是幻觉,直到医生说出纳什在普林斯顿读书的时候,是住在单人宿舍时,我才发现,原来那个和他性格完全相反的室 友竟然只生活在纳什的脑中。纳什的幻觉一天天变得真实,精神分佳节又重阳裂症不会像它所带来的痛苦那样宣告自己的到来。我们也随着电影的进程,慢慢地进入纳什地狱般的生活中,拉塞尔·克洛扮演的纳什让我们渐渐感受到了他在经历什么样的挣扎和斗争。尽管最后的痊愈不仅仅是纳什一个人的功劳,纳什在他1994年发表的自传中也这样写到,我开始理性的避免一些幻觉的影响,其中有些幻 觉已经成为了我生活环境中的一部分。在整个看电影过程中,对在图书馆窗户演算的纳什感到由衷敬佩,也许别人说这是疯狂,是疾病。可是,在我看来那才是对科学的真正的追求- -,正是这个原因,那么多的数学家,却只有一个纳什。也许有人说,他疯了,可是很早我就很认同一句话:”天才和疯子往往只有一步之遥”.除了纳什的疯狂与执着,最让我感动的就是纳什的妻子。珍尼弗·康纳利扮演的妻子艾利西亚。一个漂亮的妻子(呵呵),我认为标题所展示的正是这个伟大的女性。在纳什最疯狂的时刻,也只有她默默的陪在了他的身边,正如最后纳什在诺贝尔颁奖典礼上说的那样:我几乎不相信数据、逻辑、理性,但一直在追求,我问自己什么是逻辑,谁定义了理性,我的问题让我在物理世界里旋转,我不经意有 了发现,但在我的生命中最重要的是我拥有一生的爱,如果有什么理由的话,那就是因为你,我的爱,你是我所有的动力!也许这句话,也揭示了人生的意义。关于纳什的幻象,我想可能是由于人性的原因,每个人的心中都有别人不知道的一面。就像纳什,对科学的过分执着,以及周围的环境,导致了那样的幻象,这本身并没有什么错误,也许就像剧中所说的那样,就像是一场噩梦,谁又能避免的了呢,最重要的是我们如何去看待而已。

Posted in 生活随记 | Leave a comment