徽章问题.doc

2004-2005第二学期数学模型课程设计2005年6月20日6月24日题目 徽章问题 组员1组员2组员3姓名学号专业成绩摘要根据参加会议的名单及得到的徽章，知徽章的分类方法是由会议代表的姓名和得到的章徽来确定的。因为题中信息涉及到拉丁字母，我们可以想到该徽章分类方法是由姓名中的某个字母的相关性质（清浊辅音、元音、字母在字母表中的排序的奇偶数位等）来决定的。由于题中所给的信息杂乱无章，在建立模型之前应将280位会议代表的名字及各自所对应的徽章的标记列为一张表格，遵循一定的规律，再加上我们的常规思路，不妨分别按照姓名的第一个字母、第二个字母、第n个字母进行排序，这样能够更容易地找出徽章的分类方法。一旦得到较精确的分类方法，立即结束排序。在模型建立中，我们排除了模型1，因为它不能正确地确定徽章标记的分类，从而建立了模型2以及表1。它确定徽章标记分类的标准为：参加会议的代表们的名字的第二个字母为元音字母，基本上能确定他们得到的徽章标记为“+”号。为了能更容易地觉察这个标准，进而我们建立了模型3，将表1先按照徽章标记的正负号排序，然后依据各个名字的第二个字母来排序，这样就得到了表2。由表2易得出徽章标记的分类方法：代表们的名字的第二个字母是元音字母并且为小写时，他们将得到带“+”号的徽章；否则均得到带“-”号的徽章。最后依照模型3来求解问题（1）（2）（3）。最后我们提出了模型改进，模型1、3均可以利用VC+6.0编程，达到先按照徽章标记的正负号排序，然后依据各个名字的第N（N1，2，）个字母来排序的目的，这样更容易看出其规律。另外，我们可以将每个人的名字用二进制数表示（表示方法见正文），进而通过相互对比和统计，以便发现其中的规律（非本文重点，不做正文部分），由此可以建立模型。一、问题的提出在1994年的“机器学习与计算学习理论”的国际会议上，参加会议的280名代表都收到会议组织者发给的一枚徽章，徽章的标记为“”或“”（参加会议的名单及得到的徽章见附表）。会议组织者声明：每位代表得到徽章“”或“”的标记只与他们的姓名有关，并希望代表们能够找出徽章“”与“”的分类方法。问题如下：1请你帮助参加会议的代表找出徽章的分类方法；2对你的分类方法进行分析，如分类的理由、分类的正确与错误率等；3、由于客观原因，有名代表（见附表）没能参加此次会议。按照你的方法，如果他们参加会议，他们将得到什么类型的徽章？附表：参加会议的名单及得到的徽章（略）附表2：没能参加此次会议的名单（略）二、模型假设 题中所给的信息杂乱无章，似乎毫无规律，因此我们按照名字进行排序，当然按照一定的原则进行相当操作。根据得出的徽章分类方法，若得出的结果与题中给出的代表们所得到的徽章标记大多数相符，那就结束排序。显然，与代表们得到的徽章标记符合得越多，那该徽章分类方法越精确。原则as follows :(1)题中所给的人名是英文名字，即涉及到拉丁字母，因此我们不难想到，徽章的标记跟人名的第一个字母、第二个字母、第三个字母以及最后一个字母有关的概率相对较大。(2)由英语知识可知，外国人的姓名顺序与中国人相反，即名在前，姓在后。我们进行排序时，应先确定名字中的用于排序的某一位字母，然后再按照字母表的顺序进行排序。(3)一旦得出的徽章分类方法的正确率较高时（不妨为95%以上），那就采取这种分类方法。三、模型建立为了方便起见，将代表们的姓名按照上述给出的原则进行排序，模型如下：模型1：按照名字的第一个字母进行排列建立表格如下，按照代表们名字中的第一个字母在字母表的顺序进行排列：徽章记号名字中的第一个字母代表的名字代表的姓氏+AAuroraPerez-AAlmaWhitten+BBirBhanu-BBrianTester-ZZhixiangChen由上述表格得知：代表们的名字的第一个字母相同，例如表中的以A、B开头的名字，他们所得到的徽章既有带“+”号的，又有带“”号的，无法区分徽章的正负标记，故该模型不能作为徽章分类的标准，舍弃。因此，我们建立第二模型如下：模型2：按照代表们名字的第二个字母进行排列，表1如下：徽章标记名字中的第二个字母代表们的名字代表们的姓氏+aNaokiAbe+aDavidW. Aha+a-bR. BharatRao-cScottE. Decatur-dOdedMaron-dEddyMayoraz-d+ePeterBartlett+eGeorgeBerg-hPhilipChan-hZhixiangChen+iTimothyP. Barber+iMichaelW. Barley-nAnselmBlumer-nAntoineCornuejols+oTomBylander+oJohnCase-rEricAllender+uSusanL. Epstein+uJudyA. Franklin-yMyriamAbramson-yJyrkiKivinen由上述表格可以看出：(1) 当代表们名字中的第二个字母相同时，他们所得到的徽章的标记都是一样的。(2) 当代表们名字中的第二个字母为a、e、i、o、u时，他们所得到的徽章标记基本上是正号；否则都为负号。 (3)正负号的改变应该是由字母的改变引起的。综上分析，可得：模型二已具有确定徽章标记的较高水平。下面我们再建立一个模型来说明引起正负号变化的真正原因基本上是由名字中的第二个字母是否为元音及大小写来决定的。模型3：首先根据徽章的“+“-”进行排序，然后在此基础上按名字中的第二个字母的顺序进行排序，建立表2如下：徽章符号名字中的第二个字母代表们的名字代表们的姓氏+aNaokiAbe+aDavidW. Aha+a+ePeterBartlett+eGeorgeBerg+e+iTimothyP. Barber+iMichaelW. Barley+i+oTomBylander+oJohnCase+o+uSusanL. Epstein+uJudyA. Franklin+u-bR. BharatRao-cScottE. Decatur-dOdedMaron-除a、e、i、o、u字母外注：当名字的第二个字母为大写时，则他们得到的徽章均为“-”号，例如：R. Andrew McCallum L. Thorne McCarty 等等。从上述表格容易看出：当代表们名字的第二个字母为元音（a、e、i、o、u）并且为小写字母时，他们得到的徽章标记均为“+”号；否则全为“-”号。比较模型1、2、3，易知模型3为最佳分类方法。四、模型求解（1） 徽章的分类方法：参加会议的代表们的名字中的第二个字母为元音字母并且为小写时，他们均得到带“+”号的徽章；否则均得到带“-”的徽章。（2） A、分类的理由：代表们的姓名均由拉丁字母组成，所以我们能确定徽章的分类方法是由某一位字母的相关性质（大小写、轻浊辅音、元音等）来决定的。此外，题中所给的信息“杂乱无章”，根据常识，我们按照名字的第N位字母在字母表中的顺序进行排序，经过排序与比较，最终得到分类的方法，见模型3。B、分类的正确与错误率：参加会议的代表们的总人数为280，他们已得到的徽章的标记均可由（1）来确定，并且全部符合（1）给出的分类方法，所以分类的正确率为100%，从而错误率为0%。（3）没参加会议的代表们得到徽章的标记如下表：徽章标记名字中的第二个字母代表的名字代表的姓氏+eMerrickL. Furst+eJeanGabriel Ganascia+iWilliamGasarch+iRicardGavalda+eMelindaT. Gervasio+oYolandaGil+aDavidGillman-tAttilioGiordana+aKateGoelz+aPaulW. Goldberg+aSallyGoldman+iDianaGordon+eGeoffreyGordon+oJonathanGratch五、模型评价及改进从题中给出的人名中任意挑选，利用模型3检验，其检验结果与实际的相当吻合，但该模型存在着随机性（即这种规律出现的概率极小，而且我们根据经验进行这种排序，得出最终方法）。这种方法笨拙，不具有普遍性。因此，我们可以利用VC+6.0编程，先根据徽章的标号，然后根据字母表顺序，对各个名字的第一个字母进行排序，以便发现规律。程序如下：#include#includemain()int i=0,j=1;char string30= ;char str28030=+Naoki Abe, -Myriam Abramson, +David W. Aha,+Kamal M.Ali, -Eric Allender, +Dana Angluin,-Chidanand Apte, +Minoru Asada, +Lars Asker,+Javed Aslam, +Haralabos Athanassiou, +Jose L.Balcazar,+Timothy P.Barber, +Michael W.Barley, -Cristina Baroglio,+Peter Bartlett, -Eric Baum, +Welton Becket,-Shai Ben-David, +George Berg, +Neil Berkman,+Malini Bhandaru, +Bir Bhanu, +Reinhard Blasig,-Avrim Blum, -Anselm Blumer, +Justin Boyan,+Carla E. Brodley, +Nader Bshouty, -Wray Buntine,-Andrey Burago, +Tom Bylander, +Bill Byrne,-Claire Cardie, +Richard A. Caruana, +John Case,+Jason Catlett, +Nicolo Cesa-Bianchi, -Philip Chan,+Mark Changizi, +Pang-Chieh Chen, -Zhixiang Chen,+Wan P. Chiang, -Steve A.Chien, +Jeffery Clouse,+William Cohen, +David Cohn, -Clare Bates Congdon,-Antoine Cornuejols, +Mark W.Craven, +Robert P.Daley,+Lindley Darden, -Chris Darken, -Bhaskar Dasgupta,-Brian D.Davidson, +Michael de la Maza, -Olivier De Vel,-Scott E.Decatur, +Gerald F. DeJong, +Kan Deng,-Thomas G.Dietterich, +Michael J. Donahue, +George A. Drastal,+Harris Drucker, -Chris Drummond, +Hal Duncan,-Thomas Ellman, +Tapio Elomaa, +Susan L. Epstein,+Bob Evans, -Claudio Facchinetti, +Tom Fawcett,-Usama Fayyad, +Aaron Feigelson, +Nicolas Fiechter,+David Finton, +John Fischer, +Paul Fischer,+Seth Flanders, +Lance Fortnow, -Ameur Foued,+Judy A. Franklin, +Yoav Freund, +Johannes Furnkranz,+Leslie Grate, +William A.Greene, +Russell Greiner,+Marko Grobelnik, +Tal Grossman, +Margo Guertin,+Tom Hancock, +Earl S.Harris Jr., +David Haussler,+Matthias Heger, +Lisa Hellerstein, +David Helmbold,+Daniel Hennessy, +Haym Hirsh, +Jonathan Hodgson,+Robert C. Holte, +Jiarong Hong, -Chun-Nan Hsu,+Kazushi Ikeda, +Masayuki Inaba, -Drago Indjic,+Nitin Indurkhya, +Jeff Jackson, +Sanjay Jain,+Wolfgang Janko, -Klaus P.Jantke, +Nathalie Japkowicz,+George H. John, +Randolph Jones, +Michael I. Jordan,+Leslie Pack Kaelbling, +Bala Kalyanasundaram, -Thomas E. Kammeyer,-Grigoris Karakoulas, +Michael Kearns, +Neela Khan,+Roni Khardon, +Dennis F. Kibler, +Jorg-Uwe Kietz,-Efim Kinber, -Jyrki Kivinen, -Emanuel Knill,-Craig Knoblock, +Ron Kohavi, +Pascal Koiran,+Moshe Koppel, +Daniel Kortenkamp, +Matevz Kovacic,-Stefan Kramer, +Martinch Krikis, +Martin Kummer,-Eyal Kushilevitz, -Stephen Kwek, +Wai Lam,+Ken Lang, -Steffen Lange, +Pat Langley,+Mary Soon Lee, +Wee Sun Lee, +Moshe Leshno,+Long-Ji Lin, -Charles X.Ling, +Michael Littman,+David Loewenstern, -Phil Long, +Wolfgang Maass,-Bruce A. MacDonald, +Rich Maclin, -Sridhar Mahadevan,-J. Jeffrey Mahoney, +Yishay Mansour, +Mario Marchand,-Shaul Markovitch, -Oded Maron, +Maja Mataric,+David Mathias, +Toshiyasu Matsushima, -Stan Matwin,-Eddy Mayoraz , -R.Andrew McCallum, -L.Thorne McCarty,-Alexander M. Meystel, +Michael A.Meystel, -Steven Minton,+Nina Mishra, +Tom M.Mitchell, +Dunja Mladenic,+David Montgomery, -Andrew W.Moore, +Johanne Morin,+Hiroshi Motoda, -Stephen Muggleton, +Patrick M. Murphy,-Sreerama K.Murthy, +Filippo Neri, -Craig Nevill-Manning,-Andrew Y. Ng, +Nikolay Nikolaev, -Steven W. Norton,+Joseph OSullivan, +Dan Oblinger, +Jong-Hoon Oh,-Arlindo Oliveira, +David W. Opitz, +Sandra Panizza,+Barak A.Pearlmutter, -Ed Pednault, +Jing Peng,+Fernando Pereira, +Aurora Perez, +Bernhard Pfahringer,+David Pierce, -Krishnan Pillaipakkamnatt, +Roberto Piola,+Leonard Pitt, +Lorien Y. Pratt , -Armand Prieditis,+Foster J.Provost, -J. R. Quinlan , +John Rachlin,+Vijay Raghavan, -R. Bharat Rao, -Priscilla Rasmussen,+Joel Ratsaby, +Michael Redmond, +Patricia J. Riddle,+Lance Riley, +Ronald L. Rivest, +Huw Roberts,+Dana Ron, +Robert S. Roos, +Justinian Rosca,+John R. Rose, +Dan Roth, +James S. Royer,+Ronitt Rubinfeld, -Stuart Russell, +Lorenza Saitta,+Yoshifumi Sakai, +William Sakas, +Marcos Salganicoff,-Steven Salzberg, -Claude Sammut, +Cullen Schaffer,+Robert Schapire, +Mark Schwabacher , +Michele Sebag,+Gary M. Selzer, +Sebastian Seung, -Arun Sharma,+Jude Shavlik, +Daniel L. Silver, -Glenn Silverstein,+Yoram Singer, +Mona Singh, +Satinder Pal Singh,+Kimmen Sjolander, +David B. Skalak, +Sean Slattery,+Robert Sloan, +Donna Slonim, +Carl H. Smith,+Sonya Snedecor, +Von-Wun Soo, -Thomas G. Spalthoff,+Mark Staley, -Frank Stephan, +Mandayam T. Suraj,+Richard S. Sutton, +Joe Suzuki, -Prasad Tadepalli,+Hiroshi Tanaka, -Irina Tchoumatchenko, -Brian Tester,-Chen K. Tham, +Tatsuo Unemi, -Lyle H. Ungar,+Paul Utgoff, +Karsten Verbeurgt, +Paul Vitanyi,+Xuemei Wang, +Manfred Warmuth +Gary Weiss,-Sholom Weiss, -Thomas Wengerek, -Bradley L. Whitehall,-Alma Whitten, +Robert Williamson, +Janusz Wnek,+Kenji Yamanishi, +Takefumi Yamazaki, +Holly Yanco,+John M. Zelle, -Thomas Zeugmann, +Jean-Daniel Zucker,+Darko Zupan ;for(i=0;i=279;i+) for(j=i+1;j0) strcpy(string,stri); strcpy(stri,strj); strcpy(strj,string);for(i=0;i=279;i+) puts(stri);return 0; 运行结果见附表。此外，我们可以对该程序做适当改动，即可得出先按照徽章标记，然后按名字的某一位字母进行排序的结果。模型3的结果即可通过改动这一程序来实现的。此外，我们可建立另外一个模型:将26个字母用1或0表示，排在奇数位的字母用1表示，否则用0表示。这样代表们的姓名均可用二进制数表示，通过对比这些二进制数（可自身对比），统计1和0的出现的规律，进而建立模型。这种方法虽然普遍但在转化二进制数显得麻烦，毕竟人数太多了。参考文献1姜启源、叶俊等，数学模型第三版，高等教育出版社，北京，20042康博创作室，VC+6.0高级编程，清华大学出版社，北京，1999附表：+Aaron Feigelson +Aurora Perez+Bala Kalyanasundaram+Barak A.Pearlmutter+Bernhard Pfahringer+Bill Byrne+Bir Bhanu+Bob Evans+Carl H. Smith+Carla E. Brodley+Cullen Schaffer+Dan Oblinger+Dan Roth+Dana Angluin+Dana Ron+Daniel Hennessy+Daniel Kortenkamp+Daniel L. Silver+Darko Zupan+David B. Skalak+David Cohn+David Finton+David Haussler+David Helmbold+David Loewenstern+David Mathias+David Montgomery+David Pierce+David W. Aha+David W. Opitz+Dennis F. Kibler+Donna Slonim+Dunja Mladenic+Earl S.Harris Jr.+Fernando Pereira+Filippo Neri+Foster J.Provost+Gary M. Selzer+George A. Drastal+George Berg+George H. John+Gerald F. DeJong+Hal Duncan+Haralabos Athanassiou+Harris Drucker+Haym Hirsh+Hiroshi Motoda+Hiroshi Tanaka+Holly Yanco+Huw Roberts+James S. Royer+Janusz Wnek+Jason Catlett+Javed Aslam+Jean-Daniel Zucker+Jeff Jackson+Jeffery Clouse+Jiarong Hong+Jing Peng+Joe Suzuki+Joel Ratsaby+Johanne Morin+Johannes Furnkranz+John Case+John Fischer+John M. Zelle+John R. Rose+John Rachlin+Jonathan Hodgson+Jong-Hoon Oh+Jorg-Uwe Kietz+Jose L.Balcazar+Joseph OSullivan+Jude Shavlik+Judy A. Franklin+Justin Boyan+Justinian Rosca+Kamal M.Ali+Kan Deng+Karsten Verbeurgt+Kazushi Ikeda+Ken Lang+Kenji Yamanishi+Kimmen Sjolander+Lance Fortnow+Lance Riley+Lars Asker+Leonard Pitt+Leslie Grate+Leslie Pack Kaelbling+Lindley Darden+Lisa Hellerstein+Long-Ji Lin+Lorenza Saitta+Lorien Y. Pratt+Maja Mataric+Malini Bhandaru+Mandayam T. Suraj+Manfred Warmuth+Gary Weiss+Marcos Salganicoff+Margo Guertin+Mario Marchand+Mark Changizi+Mark Schwabacher+Mark Staley+Mark W.Craven+Marko Grobelnik+Martin Kummer+Martinch Krikis+Mary Soon Lee+Masayuki Inaba+Matevz Kovacic+Matthias Heger+Michael A.Meystel+Michael I. Jordan+Michael J. Donahue+Michael Kearns+Michael Littman+Michael Redmond+Michael W.Barley+Michael de la Maza+Michele Sebag+Minoru Asada+Mona Singh+Moshe Koppel+Moshe Leshno+Nader Bshouty+Naoki Abe+Nathalie Japkowicz+Neela Khan+Neil Berkman+Nicolas Fiechter+Nicolo Cesa-Bianchi+Nikolay Nikolaev+Nina Mishra+Nitin Indurkhya+Pang-Chieh Chen+Pascal Koiran+Pat Langley+Patricia J. Riddle+Patrick M. Murphy+Paul Fischer+Paul Utgoff+Paul Vitanyi+Peter Bartlett+Randolph Jones+Reinhard Blasig+Rich Maclin+Richard A. Caruana+Richard S. Sutton+Robert C. Holte+Robert P.Daley+Robert S. Roos+Robert Schapire+Robert Sloan+Robert Williamson+Roberto Piola+Ron Kohavi+Ronald L. Rivest+Roni Khardon+Ronitt Rubinfeld+Russell Greiner+Sandra Panizza+Sanjay Jain+Satinder Pal Singh+Sean Slattery+Sebastian Seung+Seth Flanders+Sonya Snedecor+Susan L. Epstein+Takefumi Yamazaki+Tal Grossman+Tapio Elomaa+Tatsuo Unemi+Timothy P.Barber+Tom Bylander+Tom Fawcett+Tom Hancock+Tom M.Mitchell+Toshiyasu Matsushima+Vijay Raghavan+Von-Wun Soo+Wai Lam+Wan P. Chiang+Wee Sun Lee+Welton Becket+William A.Greene+William Cohen+William Sakas+Wolfgang Janko+Wolfgang Maass+Xuemei Wang+Yishay Mansour+Yoav Freund+Yoram Singer+Yoshifumi Sakai-Alexander M. Meyst