暨南大学经济学院诚聘海归人才 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Economics - 经济

暨南大学经济学院诚聘海归人才

暨南大学经济学院诚聘海归人才# Economics - 经济

w*t2009-01-12 08:01

1 楼

如果在一个边长为D的正方形区域内，随机分布了k个点，那么MSP大概多少？function
（k，D）怎么表示？另外计算MSP有没有什么比较快的实现算法（不是greedy类型的）
？

j*u2009-01-12 08:01

2 楼

因“211工程”重点建设项目以及学科发展和工作需要，我院拟招聘高级留学归国人员
数名。
一、学院简介
暨南大学是中国第一所由国家创办的华侨学府，是中国第一所招收外国留学生的大
学，是目前全国境外生最多的大学，是国家“211工程”重点综合性大学，直属国务院
侨务办公室领导。历史悠久的经济学院目前拥有华南地区唯一的应用经济学一级学科博
士学位授权点，下设11个二级学科博士点，硕士点覆盖了所有的应用经济学科。
二、招聘具体要求
国外著名院校毕业，获得经管类博士学位，科研和学术成绩突出；拥有国外高校教
学科研工作经历者优先，具体招聘计划如下：
专业方向　　招聘人数
宏观经济学 1
国际经济学 1
财政学 1
统计 1
金融学 1
城市经济学 1
三、待遇
待遇从优，具体面议。
四、联系方式
请将应聘材料邮寄到以下联系地址：
联系地址：广州市黄埔大道西601号

l*e2009-01-12 08:01

3 楼

MST
O(D\sqrt{k})
Prim algorithm or kruskal algo

y*z2009-01-12 08:01

4 楼

呵呵，看到母校在这里招人呢
暨大在国内的高校里相对而言环境更为宽松、政治气氛很淡、
老师们都很自由，广东省经济类的项目也算多
想回高校的海龟可以认真考虑咯~~~

v*e2009-01-12 08:01

5 楼

Prim和Kruskal都是greedy algorithm吧

【在 l******e 的大作中提到】

: MST
: O(D\sqrt{k})
: Prim algorithm or kruskal algo

K*n2009-01-12 08:01

6 楼

但是它们都可以被证明, 是greedy又有什么关系?

c*r2009-01-12 08:01

7 楼

用归纳法。第k个点与其余k-1个点的最短距离大概是 D/sqrt(k)。
所以
MSP_k = MSP_{k-1} + D/sqrt(k)
= ...
= D * (1 + 1/sqrt(2) + ... 1/sqrt(k))

c*r2009-01-12 08:01

8 楼

这两个算法只能在图上使用。原文定义在一个平面上。
可以用kd-tree来算MST：
每次插入一个点，然后做nearest neighbor query。
插入和查询需要O(log(k)) time，总共 O(1+log(2)+..+log(k))

【在 v********e 的大作中提到】

: Prim和Kruskal都是greedy algorithm吧

h*e2009-01-12 08:01

9 楼

Construct the Delaunay triangulation of the n points, the result is a
graph with O(n) edges. Then you can run Prim or Kruskal on it and get the
Euclidean MST.

【在 c****r 的大作中提到】

: 这两个算法只能在图上使用。原文定义在一个平面上。
: 可以用kd-tree来算MST：
: 每次插入一个点，然后做nearest neighbor query。
: 插入和查询需要O(log(k)) time，总共 O(1+log(2)+..+log(k))