《备战美国数学建模竞赛与论文剖析》由会员分享,可在线阅读,更多相关《备战美国数学建模竞赛与论文剖析(36页珍藏版)》请在金锄头文库上搜索。
1、1. 美国数学建模竞赛概况 2. 竞赛论文剖析3. 一些建议主讲: 龚劬美国数学建模竞赛概况 1 美国大学生数学建模竞赛(MCM) 始于1985年 学生三人一组在四天之内合作完成一个实际问题 参赛者来自美国、中国、加拿大、德国、英国以及印尼等国家或地区 我国于1989年起组织大学生参加MCM 我校从1994年开始组织学生参加MCM 2006年我校共有8个队参赛,3个队获一等奖、2个队获二等奖和3个队获三等奖。2 部分MCM/ICM题目 指纹唯一吗?(2004A) 飓风来临时的疏散问题(2001B) 信息技术安全问题(2004C) 核磁共振切片成像(1998A) 伽玛刀治疗计划(2003B) 机
2、场安全检查(2003C) 特技表演(2003A) 公园快速通道系统(2004B) 风与喷泉(2002A) 过路收费站(2005B) 灌木蜥蜴问题(2002C)3 评阅JudgingwillbecompletedbyMarch31,2008. ThesolutionswillberecognizedasSuccessfulParticipant,HonorableMention,Meritorious,orOutstandingWinner.Youhaveabout43%chanceofbeingrankedhigherthanSuccessfulParticipantThe first(tri
3、age) round Each paper is skimmed by two or three judges,who spend between 5 and 10 minuts each reading the paper. If you survive the triage round, you have about an 80% chance of being ranked higher than Successful Participant.4 OutstandingWinnerINFORMSwinnerThe Institute for Operations Research and
4、 theManagementSciences(INFORMS)willdesignateanOutstandingteamfromeachofthethreeproblemsasanINFORMSwinnerSIAMwinnerTheSocietyforIndustrialandAppliedMathematics(SIAM) will designate one Outstanding team fromeachproblemasaSIAMwinner.MAAwinnerTheMathematicalAssociationofAmerica(MAA)willdesignateoneOutst
5、andingteamfromeachproblemfortheMCMasaMAAwinner.竞赛论文剖析1 SummarySummary (Themostimportantpartofthepaper)provide a brief overview of the problemdescribe clearly the approach taken to modeling the problemstate the most important results and conclusions.mention any recommendations directly relevant to th
6、e problem. If you did anything creative, it must be here. 竞赛论文剖析1 SummarySummary特色和创新之处必须在这里强调(稍夸张地)。长度:理想长度很难说,必须包括上述要点,但简洁也非常重要。一般掌握在半页至2/3页左右。是文章最重要的部分。要保证准确、简明、条理清晰,突出特色和创新点。注:评阅时将首先根据摘要和论文整体结构及概貌对论文优劣进行初步筛选。 Agoodexampleofaclear,conciseandthoroughsummary(2004A) Fingerprintidentificationdependso
7、ntheassumptionthatapersonsfingerprintsareunique.Weassessthetruthofthisassumptionbycalculatingthetotalnumberofdistinctfingerprints.Weassumeaccuratefingerprints(ignoringproceduralerror)aredefinedby12pointsofdetailorminutiae.Thenumberofdistinctfingerprintsdependsalsoonthenumberofpotentialpositionsofthe
8、seminutiae.Twohistoricalmethodsandageometricanalysisestimatetheretobe1,400positions,afigureconfirmedbyouralgorithmforcountingridgesinafingerprint.Wecreatetwomodelstoestimatethenumberofuniquefingerprints:Onemodelcomputesfingerprintsasarrangementsinminutiae;theotherextrapolatesthenumberoffingerprintsf
9、romtheShannonentropyoftheinformationthatdefinesafingerprint.Agoodexampleofaclear,conciseandthoroughsummary(2004A)Thesetwomodelsagreetowithinanorderofmagnitudethatthereare51033uniquefingerprints,acompellingvalidationofourgeneralapproach.Tohandlethelargenumberoffingerprints,weimplementanapproximationf
10、orthecalculationofprobabilities.Givenacumulativeworldpopulationof120billion,theprobabilityoftwopeopleeverhavingthesamefingerprintis1.410-6.Theprobabilityoftwohumanslivingtodaysharingafingerprintis3.510-15,whichsuggeststhatfingerprintsareatheoreticallymorereliablemethodofidentificationthanDNAanalysis
11、,whichhasafalsepositiveprobabilityof10-9.Noneofthesecalculationstakeintoaccountproceduralerrors.竞赛论文剖析2 Introduction 重述问题,用自己的语言陈述你将要做的工作根据自己的理解,用自己的语言清楚简明地阐述问题的背景、条件和要求。Example 1: Thepossibilityofduplicatefingerprints,orfingerprintslikelytobemistakenforeachother,hasledtorecentcriticismoffingerprint
12、sasameansofidentification.Thekeyproblemis:Howmanydistinctfingerprintsarethere?Weapproachthisproblemwithtwogeneralmethods:“building”afingerprintfromthegroundup,usingdifferentmodels;andusingtheinformationcontentofafingerprint到2004A.docExample 2: IntroductionWedevelopsomemodels,apatternmodel,ashapemode
13、landapracticalmodel,toanalyzetheuniquenessoffingerprintsandoddsofmisidentificationbyfingerprintevidence.Throughcomparison,we also develop a sequence model to analyze odds ofmisidentificationbyDNAevidence.Noticingthatthereareseveralpatternsoffingerprints,andtheridgesandfurrowsinfingerprintsarediffere
14、ntfromonetoanother,weusethesecharacteristicstodevelopourmodel.Consideringtheincompletenessofthefingerprints,weanalyzetheprobability ofmisidentificationoffingerprints.Based on our limited knowledge about DNA and genetics, wecreate a sequence model to calculate the odds. Ignoring thosecomplicatedbioch
15、emicalrestrictionsandbiomolecularrequirements,weestablishapuremathematicalmodelrelatedtoourproblem.竞赛论文剖析Example 2: Considering some fundamental assumptions and requirementsofbothfingerprintandDNAidentificationsfortheiraccuracy,weproposeouropinionsonthisidentificationproblem.Background Fingerprintso
16、fhumankindareformedintheperiodofafetus.Weknow that they are decided genetically by genes which areinheritedfromtheirparents.Theridgesandfurrowsformedthepatternsorfeaturesoffingerprints,anditiscommonplacebeliefthat everyone s fingerprints are unique. Even twinborn babies,theirfingerprintsaredifferent
17、.Tillnow,thereisntanycasethattwopersons,eitherChineseorAmericanpeople,havethesamefingerprintsexactlyallovertheworld.Actually,nobodyhasfoundanyrelatedrecordappearedinanygovernmentsintheprocessesoffingerprintmanagement,identification,checkandrecognition.竞赛论文剖析Example 2: In1953,WatsonandCrick5putforwar
18、dtheDNAdoublehelixmodelbasedonbasespairs.In1967,LinandChargaff6foundthatinsinglenucleotidechain,thereisanbalancebasedistributions:and.Ineverychromosomeofhuman,theratiovalueofbasepairs,bothA/TandG/Cvaryin0.9991.001.NowaccordingtoachievementsofHumanGenomeProjection(HGP)8whichhasbeen completed by April
19、 14th 2003, the human DNA sequencecontainsabout3billionorinmoredetails,3164.7millionchemicalnucleotidebases(A,C,T,andG).Almostall(99.9%)nucleotidebasesareexactlythesameinallpeople.Intotalhumangenome,anyDNAconsequenceconsistsofcodingandnoncodingregions,while the coding regions are called genes. Genes
20、 appear to beconcentrated in random areas along the genome, with vastexpansesofnoncodingDNAbetween.BecauseofthepolymorphismofDNAandtherandomarrangementofthebasesinDNAsequence,itisnothardtoimaginethekindsofDNAshouldbeanastronomicalfigureorananoscopicmap.AndthisgivesthefundamentofDNAidentification.竞赛论
21、文剖析3 模型假设假设要合理,在建模时会用到,不要罗列大量无关紧要的假设。 有用的假设主要包括两种:与问题相关的特别信息缺乏且在规定的时间内得不到,因此必须做出假设,才能继续。另外就是为了应用你熟悉的数学或为了避免在给定的时间不能完成你的模型而简化问题的细节所作出的简化假设, 合理假设的作用:简化问题,明确问题,限定模型的适用范围竞赛论文剖析3 模型假设Example1Fingerprintsareofthehighestpossiblequality,withoutdamagefromabrationandinjury.Theridgestructureofafingerprintisino
22、neoffivecategories:Arch,LeftLoop,RightLoop,TentedArch,orWhorl,employedintheautomaticclassificationsystemofCappellietal.1999(derivedfromthoseoftheFBIandWatsonandWilson1992).Eachcategoryhasacharacteristicridgeflowtopology,whichwebreakintohomogeneousdomainsofapproximatelyunidirectionalflow.WhileCappell
23、ietal.1999raisetheissueof“unclassifiable”prints,andtheyandMarcialisetal.2001confuseclassesofridgestructures,weassumethatsuchambiguitiesstemfrompoorprintquality.竞赛论文剖析Eachminutiacanbeclassifiedasabifurcation,atermination,oradot.Pankantietal.2002;StoneyandThornton1986.ThoughGalton1892identifies10minut
24、iastructuresandothersfind13Osterburgetal.1977,wecanignorethesefurtherstructures(whicharecompositionsofthebasicthree)becauseoftheirlowfrequencyOsterburgetal.1977.Locationandorientationofminutiaerelativetoeachotherareindependent.Frequenciesofridgestructureclassesandconfigurationsandminutiaetypesdonotc
25、hangeappreciablywithtime.竞赛论文剖析3 模型假设Example2Athumbprintisdefinedgloaallybyridgepatternsandlocallybyadistributionofminutiae,whichwerefertoalsoasfeatures.Theareaofinteresttypicalthumbprintis20mm20mmsquaregrid.Therearetwosignificanttypesofminutiae,thebifurcationandtheridgeending:allotherminutiaearecom
26、positionsoftheseOsterburgetal.1977.Theprobabilityofaminutiaoccurringinagridboxis0.234Osterburgetal.1977.TheorientationoftheminutiaewasnottakenintoaccountbyOsterburg;weassignaminutiaoneofeightangles,from0oto157.5o,instepsof22.5o.Whencomparingtwoprints,weknowoneprintarbitrarilywell.Thenumberofpeoplewh
27、ohaveeverlivedis1.0641011Haub1995.竞赛论文剖析4.建立模型模型的主要类型:初等模型、微分方程模型、差分方程模型、概率模型、统计预测模型、优化模型、决策模型、排队模型、图论模型等几类常见建模目的:(1)描述或解释现实世界的各类现象,常采用机理分析的方法,探索研究对象的内在规律性(2)预测感兴趣的事件是否会发生,或者事物的发展趋势,常采用数理统计或模拟的方法(3)优化管理、决策或者控制事物,需合理地定义可量化的评价指标及评价方法.4 建立模型建模过程中的几个要点: 模型的整体设计、合理的假设、建立数学结构、建立数学表达式数学模型最好明确、合理、简洁,具有一般性;
28、有些论文不给出明确的模型,只是就赛题所给的特殊情况,用“凑”的方法给出结果,虽然结果大致对,但缺乏一般性,不是数学建模的正确思路鼓励创新,特别欣赏独树一帜、标新立异,但要合理。避免出现罗列一系列模型,又不作评价的现象。可以从简单模型开始,然后改进。竞赛论文剖析5 模型求解最重要的部分之一 算法设计或选择,算法思想依据,步骤;引用或建立必要的数学命题和定理;在不能求出精确解的情况下,需要给出不只一种解法(算法),并进行测试比较,给出评价。为了说明你的算法好,你需要有一个参照与之比较,你可以从最简单、最易得到的算法开始,逐步改进直到得到你的最好解。通常对于离散问题,最简单的解可能只是做随机选择,然
29、后用你的算法得到的解与它比较。竞赛论文剖析6 结果表示、结果分析、模型检验结果表示、结果分析、模型检验结果表示要集中,一目了然,直观,便于比较.结果分析不能少,从计算结果可得出什么结论模型检验特别重要runMULTIPLEtestsandfindoutifyoursolutionisstable!Willitholdupunderslightlydifferentcircumstances?Atthispointyourcodeisdebuggedandgeneratingusefulinformation-takejustanother20minutesandrunafewmorecases
30、,varyingtheparametersjustabit.IfyouredoingtheEscapingaHurricaneproblem,runyourcodewithafewmorecars,orafewless-seehowflexibleyourresultsare.IfyouredoingtheMRIProblem,testyourroutinesonseveraldifferentsimulatedorgans.IfyouredoingtheAirTrafficControlproblem,throwtheplanesatyoursimulatedairportabitfaste
31、r,abitslowerandseehowyourprogramcopes.Provetothejudgesthatyoursolutionisflexibleandstable,orhonestlyadmitthatyoursolutiondoesntworkaswellagainstcertainchallenges.Yourpaperwilllookawholelotbetter!7StrengthsandWeaknessesofthemodel 突出优点,但弱点也不能回避。在写模型弱点时,要对照你建立模型时所作的假设,模型有哪些局限和适用条件。陈述要完整,前后一致。8. 8. Refe
32、rencesReferences列出论文中确实应用了其中的方法或结论的文献;不要列出论文中没有引用的文献。正文中要标出后面的文献序号一些建议1 AnAn skimmable skimmable paper paper your No.1 goal is to beat the five minute read . Thingsthatmaygetnoticedareheadings,bulletizedlists,tables,diagrams,andfigures. Whatyoudontwantarelargeunbrokenblocksoftext,theymakethepaperloo
33、kboring,andmayneverbereadcompletely.Youwantthewordstobeclearandeasytoread,andthetexttobebrokenregularlybyheadings,lists,figures,diagrams,anythingyoucanthinkoftokeepitinteresting.2 HeadingsHeadings are very importantare very important 只读各级标题,就能知道整篇论文的概要;多设置标题。避免大段大段的文字,不见一个标题,正文至少要设置两级标题,使每一小节都有一个清晰的
34、目的目标。每小节不要超过两段。Example:AMethodforTakingCrossSectionsofThree-DimentionalGriddedDataSummaryIntroductionAssumptionsTheModelsCoordinateSystemsandDefinitions一些建议InterpolationAlgorithmsMethod1-ProximityMethod2-DensityMeanMethod3-TrilinearInterpolationMethod4-PolynomialInterpolationMethod5-HybridAlgorithms
35、TestingandResultsGlobulesArmGeneticOrganBrainResidualPlotsOverallResultsStrengthsandWeaknessesFutureWorkReferencesandSupportingDataBulletItems这种列举,无论是否编号,有三个重要目的。1. 将文字分块,使读起来没那么冗长乏味. 2. 能突出重点. 3. 当快速浏览时,更容易被注意到.3.Tables of Data 不要浪费你编写的计算机程序,让输入参数取各种不同的值进行计算,然后用图或表来组织这些结果。这表明你有大量的数据支持你的结论,对参数进行了全面的
36、探究。An example: Are Fingerprints Unique? 一些建议4 Diagrams and Figures 一图胜千言,图形直观形象,一目了然An example: Trade-offs in the fight against HIV/AIDSTrade-offs in the fight against HIV/AIDS 一些建议Fig.2 Trafficstateatbottleneckarea Fig. 3 Stateofmovement一些建议Fig. 5 Therelationshipofmeandelaytimeandnumberoftollbooths
37、一些建议5. Backwards DesignBackwards Design trytodesignwhatyouwantyourpapertolooklike,andspendyourtimeworkingtofillitin.Sometimeearlyinthecontest,writeanoutlineofwhatyouthinktheidealpapershouldlooklike.Findablackboardandoutlinethemajorsectionsandsubsections.Makequicksketchesofallthefiguresanddiagramsyou
38、canthinkofthatmightbeuseful.Brainstormthingstodobulletizedlistsofandotherthingsthatcangointothepaper.Makesureyoualllookatthisoutlineanddiscussit-itwillhelpyouallstayfocusedonthesamegoal.一些建议5. Backwards DesignBackwards Design Whenyouredowninthetrenchestryingtocodeoutsomealgorithmoranalyzesomedataits
39、easytolosesightofthebigpictureandspendseveralhourstryingtodosomethingthatsnotcompletelyessential.Bykeepingtheoutlineofyouridealpaperinyourmind,youcanletthepaperdirectwhereyouspendyourtime.ThereWILLbesomethingsthatyouwanttodothatwouldlookgreatinthepaper,butmayjustbetoohardtodoforonereasonoranother.By
40、workingoutyourpaper,evenbeforeyouveworkedoutthesolutions,youcanstayfocusedanddoonlytheworkthatneedstobedonetomakethepaperlooklikeitshould.一些建议网上的数学建模资源 美国大学生数学建模竞赛美国大学生数学建模竞赛 http:/ 重庆大学重庆大学“数学实验数学实验”网站网站 http:/ UC Berkeley MCM http:/www.ocf.berkeley.edu/ anandk/mcm/index.htm Duke University MCM htt
41、p:/www.math.duke.edu/news/awards/competitions.html网上的数学建模资源 Washington University MCM http:/www.math.washington.edu/ morrow/mcm/mcm.html New York University MCM http:/www.cims.nyu.edu/eve2/mathmod.html Project INTERMATH http:/www.projectintermath.org/ IMA Mathematical Modeling in IndustryIMA Mathematical Modeling in Industry http:/www.ima.umn.edu/modeling/竞赛论文剖析1. Ending 2. Bifurcation 3. Dot 4. Enclosure 5. Ridge Divergence 6. Short Ridge minutiae(指纹细节特征) types竞赛论文剖析Right loopLeft loopDouble looparchTented archWhorlRidge patterns