MCM 练习，康奈尔大学，2002.11.20

这个模拟的MCM提出的两个问题涉及到Planet Ares（在遥远的银河系）勘探项目的不同阶段。不必说，在我们的行星系统内部也提出了类似的问题，只是可能没那么有趣：）

请牢记，你的整篇手稿不得超过10页（真正的比赛没有这样的限制）。一个简单、简洁、容易理解的模型要比一个较实际但却难以理解或难以计算的模型更受欢迎。如果作为一个整体这个问题难以处理，你可以把精力集中在它的某个方面或有限的部分，这样可以在规定的时间内完成。

你的解决方案（包括恰当的算法描述）须在2002年11月27日星期三的下午5：15前上交。鼓励提交电子版本。把你的解决方案和/或相关问题发送到vlad@math.cornell.edu。

祝你好运！

 

您的探险队正在为第一个着陆任务做准备，并且需要一张选定区域的可靠的三维地图，以便选择最佳的着陆点，以及为自动机器人探险家设计以后的活动。所选定的区域大约是一个边长为60km的正方形。你要为加工空中数码照片提出（并实施）一种方法，以获得该地区所有位置的海拔高度。Ares的表面大部分是沙漠，它在自然的色彩上没有太多变化，但景观方面却有很多种类（如许多山脊，峡谷，裂痕等）。该地区的海拔从低于那个长期干涸的海平面的100米变化到其上1900米；这张三维地图需要精确到和真实的海拔相差在1米以内。

用模拟的景观或（如果你有足够的时间）用一些真实（地球上的）地形的空中照片来验证下你的方法。

你也应该回答以下问题：

*至少需要多少张空中拍摄的照片？

*这些照片从什么海拔高度拍摄最为理想？

*一天的哪段时间（或日照环境）最适合去拍摄这些照片？

*任何其它能提高原始资料的质量和/或地图效果的建议？

 

 

着陆后，考古学家发现了据称是由（现已灭绝）文明社会遗留下来的大批外星文物。在外星的地下城市发现的磁存储设备包含了许多资料，其中一个重要的部分似乎是关于10000个伟人图表（每一项都包含1到1000万个节点，并且从1000万到1亿没有指定的边界）。我们的语言学家为了解读出所附的图案日夜工作，但到目前为止收效甚微（我们甚至不知道外星人的语言是否是以某个字母为基础的）。在这种情况下，对该图真实性质的毫无根据的猜测在你的探险队里猖獗起来。有些人怀疑，这些图将Ares上以前的沙漠河流和小溪网状系统译成电码，有些人认为这些都是星际贸易路线图，然而还有些人猜想，我们正处理着全Aresian世界范围内网站的大规模备份，此外，少数消息灵通的人确信，这些是关于DukeNukem3D先进的奖金水准遗失了很久的地图。

你（和你的考察队中另外的两位图形分析家）决定利用图表自身的性质排除其中一些荒谬的猜测。基于他们以下的创建方式，你着手分析图表的一些可能特征（有关系部分的数量，节点度数的分布等）：

**通过一个瞬间的过程，或者通过持续的增长（节点和/或边界随着时间的推移的增加），或通过一个“复合式”增长（连接良好的节点将来可能有更好的连接），也或者通过“合并”的增长（几张大规模的子图合并以创造出一副超大规模的图形）；

**由一个创造者单独完成或者创造者间相互合作（或竞争？）；

**模拟一个文明的人造物体或者一些自然现象；

**模拟一些随机的（或混乱的）的事情。

你应当

1）设计一些模型并尽可能多的测定一下与上述“图形创造模式”相应的“识别特征”（即图性状的收集）；

2）设计一些算法以确定一张给定图形的可能创建模式（注：鉴于大尺寸的图形的问题，如果能够迅速地排除一些创建模式（通过随机选择的子图），那将是一个很大的优势。）；

3）利用模拟图（举例说明不同的创建模式）和在网上得到的大规模的图表测验一下你的算法（例如，与一个特定的关键字有关的网站图；见

http://www.cs.cornell.edu/Courses/cs685/2002fa/data/gr0.California）。