各高校选拔赛试题

xiebo127989 · 发表于 2004-5-14 18:21:51

<

>请问 哈尔滨工业大学2004年数学建模竞赛试题的答案在哪里可以找到

w_er · 发表于 2004-5-15 02:10:41

<

>有答案吗？麻烦快点帮我发一份<

>北京大学首届“江泽涵”杯数学建模与计算机应用竞赛试题
（两道题选一道做）<

>A
医疗保障基金额度的分配的答案给我啊！！！1跪求。发我邮箱吧<a href="mailtblue_wx1@hotmail.com" target="_blank" >blue_wx1@hotmail.com</A>或者是w_er@qianlong.com

HUASHI3483 · 发表于 2004-5-17 02:03:47

EQY52bEP.rar (4.71 KB, 下载次数: 0)

wangshuai · 发表于 2004-5-17 19:11:08

<

>北京大学首届“江泽涵”杯数学建模与计算机应用竞赛试题
（两道题选一道做）<

>A
医疗保障基金额度的分配的答案给我啊！！！谢谢哈<

>我的QQ是156511402，邮箱：<a href="mailtxnjdtx@163.com" target="_blank" >xnjdtx@163.com</A>

Newton1983 · 发表于 2004-5-18 07:19:40

QEf7uVMp.rar (20.34 KB, 下载次数: 0)

kaka · 发表于 2004-5-19 02:04:30

<

align=center>A题：DNA限制性图谱的绘制
<

align=center> 
<

>绘制DNA限制性图谱（restriction mapping）是遗传生物学中的重要问题。由于DNA分子很长，目前的实验技术无法对其进行直接测量，所以生物学家们需要把DNA分子切开，一段一段的来测量。在切开的过程中，DNA片段在原先DNA分子上的排列顺序丢失了，如何找回这些片段的排列顺序是一个关键问题。
为了构造一张限制性图谱，生物学家用不同的生化技术获得关于图谱的间接的信息，然后采用组合方法用这些数据重构图谱。一种方法是用限制性酶（restriction enzyme）来消化DNA分子。这些酶在限制性位点(restriction sites)把DNA链切开，每种酶对应的限制性位点不一样。对于每一种酶，每个DNA分子可能有多个限制性位点，此时可以按照需要来选择切开某几个位点（不一定连续）。DNA分子被切开后，得到的每个片段的长度就是重构这些片段的原始顺序的基本信息。在多种获取这种信息的实验方法中，有一种广泛采用的方法：部分消化（the partial digest, PDP）方法。
在PDP中，采用一种酶，通过实验得到任意两个限制性位点之间片段的长度。假设与使用的酶对应的限制性位点有n个， 通过大量实验，可得到n+2个点（n个位点加上两个端点）中任意两点之间的距离，共<v:shapetype> <v:stroke joinstyle="miter"></v:stroke><v:formulas><v:f eqn="if lineDrawn pixelLineWidth 0"></v:f><v:f eqn="sum @0 1 0"></v:f><v:f eqn="sum 0 0 @1"></v:f><v:f eqn="prod @2 1 2"></v:f><v:f eqn="prod @3 21600 pixelWidth"></v:f><v:f eqn="prod @3 21600 pixelHeight"></v:f><v:f eqn="sum @0 0 1"></v:f><v:f eqn="prod @6 1 2"></v:f><v:f eqn="prod @7 21600 pixelWidth"></v:f><v:f eqn="sum @8 21600 0"></v:f><v:f eqn="prod @7 21600 pixelHeight"></v:f><v:f eqn="sum @10 21600 0"></v:f></v:formulas><v:path gradientshapeok="t" connecttype="rect" extrusionok="f"></v:path><lock v:ext="edit" aspectratio="t"></lock></v:shapetype><v:shape><v:imagedata></v:imagedata></v:shape>个值。然后用这<v:shape> <v:imagedata></v:imagedata></v:shape>个距离来重构n个限制性位点的位置(解不一定唯一，两个端点对应于最长的距离)。若<v:shape> <v:imagedata></v:imagedata></v:shape>是线段上的点集<v:shape> <v:imagedata></v:imagedata></v:shape>中所有点之间距离的集合，PDP就是给定<v:shape> <v:imagedata></v:imagedata></v:shape>求<v:shape> <v:imagedata></v:imagedata></v:shape>。下图给出了一个例子。
 
 2 3 4 5 2
 
<v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line> 
 A a b c d B
图1. A,B是DNA分子的两个端点。 a，b，c和d是限制性位点。 通过实验可以得到 <v:shape><v:imagedata></v:imagedata></v:shape>={2,3,4,5,2,5,9,14,16,7,12,14,9,11,7}. 再通过<v:shape> <v:imagedata></v:imagedata></v:shape>来求<v:shape> <v:imagedata></v:imagedata></v:shape>，对应于上图的<v:shape> <v:imagedata></v:imagedata></v:shape>={0,2,5,9,14,16}是一种解。
 
上述方法要把DNA分子在任意的两个限制性位点处切开，这对于当前的实验技术来说有相当难度，而且，还要对实验数据进行处理，也很复杂。最近研究人员提出了一种新的方法，称为简化的部分消化方法（SPDP）。这个方法与PDP的不同就在于它避免了在任意两个位点切开DNA分子的难题和处理重复数据的困难。仍假设与使用的酶对应的限制性位点有n个。首先DNA分子被复制成n+1份，前n个复制品中的每一个在一个限制性位点处被切开，最后一个复制品在所有的限制性位点处被切开。这样我们分别得到2n个片段长度（称为第一组数据）和n+1个片段长度（称为第二组数据）。在没有误差的前提下，第一组数据中2n个长度可以分成n对，每对的和都等于DNA分子的总长度；第二组数据中n+1个长度的和也等于DNA分子的总长度。 SPDP问题是如何利用这两组数据重构出这n+1个片段在DNA分子上的排列，使得这个排列在n个位点切开后得到的2n个片段长度与实验得到的2n个长度相等。下图给出了一个例子。

kaka · 发表于 2004-5-19 02:05:05

<

0cm 0cm 0pt; LINE-HEIGHT: 20pt; mso-line-height-rule: exactly"> (a)<

0cm 0cm 0pt; TEXT-INDENT: 48pt; LINE-HEIGHT: 20pt; mso-line-height-rule: exactly; mso-char-indent-count: 4.0">2 6 1 4 3<

0cm 0cm 0pt; TEXT-INDENT: 36pt; LINE-HEIGHT: 20pt; mso-line-height-rule: exactly; mso-char-indent-count: 3.0"><v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line> (b)<v:line></v:line> 2 14<v:line></v:line><v:line></v:line><v:line></v:line> 8 8<v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line> 9 7<v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line> 13 3<v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line> 2 1 4 3 6<v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line> <v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line><v:line></v:line> 图2. 这个例子对应的位点有4个。(a) 就是我们希望重构的顺序。 (b)中的前4对为第一组数据，它通过切开一个位点得到，每对长度的和都是16，剩下的为第二组数据，含5个片段长度，它通过切开所有位点得到，它们的长度总和也是16， 但实验结果只告知每段的长度，不知道它们在DNA分子上的排列顺序。 现对上述SPDP问题，建立数学模型，并研究以下问题：（1） 设计求解该问题的算法， 并评估该算法的效率和效果。对下述2个实例给出答案：实例1： 第一组数据：2，14，8，8，9，7，13，3 第二组数据：2，1，4，3，6 实例2: 第一组数据：1，14，12，3，7，8，9，6，11，4，12，3，13，2，5，10第二组数据：1，1，2，1，2，2，1，2，3 （2） 讨论在实验中测量片段长度时的误差，将在多大程度上影响算法的效果，当误差到多大程度时，限制性图谱的重构将无法进行。 B题：通讯卫星上的开关设置 考虑下述卫星通信中的优化设计问题。地面上有n个接收站与n个发送站，通讯卫星上则设置了若干种开关模式。每个开关模式可用矩阵P=(pij)来表示，若卫星可接收发送站i发出的信息并将信息传送回接收站j时，矩阵中的元素pij =1，否则pij =0。通讯卫星上的接收发送任务也可以用一个矩阵T=（tij）来表示，元素tij为信息由发送站i到接收站j的传送时间长度。由于技术上的原因，当发送站i与接收站j传递信息时，它不能同时发送信息给别的接收站；同样，当接收站j在接收发送站i的信息时，也不能同时接收其他发送站发送的信息。你的任务是：（1） 设计一组开关模式<v:shapetype> <v:stroke joinstyle="miter"></v:stroke><v:formulas><v:f eqn="if lineDrawn pixelLineWidth 0"></v:f><v:f eqn="sum @0 1 0"></v:f><v:f eqn="sum 0 0 @1"></v:f><v:f eqn="prod @2 1 2"></v:f><v:f eqn="prod @3 21600 pixelWidth"></v:f><v:f eqn="prod @3 21600 pixelHeight"></v:f><v:f eqn="sum @0 0 1"></v:f><v:f eqn="prod @6 1 2"></v:f><v:f eqn="prod @7 21600 pixelWidth"></v:f><v:f eqn="sum @8 21600 0"></v:f><v:f eqn="prod @7 21600 pixelHeight"></v:f><v:f eqn="sum @10 21600 0"></v:f></v:formulas><v:path gradientshapeok="t" connecttype="rect" extrusionok="f"></v:path><lock v:ext="edit" aspectratio="t"></lock></v:shapetype><v:shape><v:imagedata></v:imagedata></v:shape>，k=1,…,r，r应当尽可能小，使得对任意给定的任务矩阵T，卫星开关设置{<v:shape> <v:imagedata></v:imagedata></v:shape>}均能完成要求的发送接收任务。（2） 设计一个算法，在发送接收任务T给出后，可根据你设计的开关模式<v:shape> <v:imagedata></v:imagedata></v:shape>（k=1, …,r）求出<v:shape> <v:imagedata></v:imagedata></v:shape>的使用时间λk，使得在完成预定任务前提下各开关模式使用的总时间最短。（3） 由于技术上的原因，开关模式的总数r有一个上限。因此当需要传送的任务数量较大时，可能仍无法分派任务。请你想一些办法来解决这一困难，例如增加传送时间等。

kaka · 发表于 2004-5-19 02:05:37

<

>以上是浙江大学的赛题

郭郭 · 发表于 2004-5-21 05:37:15

<

>求以上B题思路
<

>感觉题目有争议之初
<

>尤其是2,3问.不知各位如何考虑

KAKA,怎么和你联系?

hexinghui · 发表于 2004-5-21 06:12:03

<

>我也是

[此贴子已经被作者于2004-5-22 18:20:29编辑过]

		自动登录	找回密码
密码			注-册-帐-号

各高校选拔赛试题

交大选拔题

西南交大2004数模题