线性代数模型

第四章浙江大学数学建模实践基地基于线性代数与差分方程方法的模型在第三章中，我们有多处对不连续变化的变量采取了连续化的方法，从而建立了相应的微分方程模型。但是由于以下原因：第一，有时变量事实上只能取自一个有限的集合；第二，有时采取连续化方法后建立的模型比较复杂，无法求出问题的解，从而只能求它们的数值解。也就是说，在建模时我们对离散变量作了连续化处理，而在求解时，又对连续变量作了离散化处理，使之重新变为离散变量。所以采取连续化方法的效果有时并不很好，因而是不可取的。电子计算机的广泛应用为我们处理大量信息提供了实现的可能，这就十分自然地提出了一个问题，对具有离散变量的实际问题直接建立一个离散模型是否更为可取？本章介绍的几个模型就是基于这种想法建立起来的。§4.1状态转移问题所谓状态转移问题讨论的是在一定的条件下，系统由一状态逐步转移到另一状态是否可能，如果可以转移的话，应如何具体实现？例4.1人、狗、鸡、米过河问题这是一个人所共知而又十分简单的智力游戏。某人要带狗、鸡、米过河，但小船除需要人划外，最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡要吃米，问此人应如何过河。在本问题中，可采取如下方法：一物在此岸时相应分量为1，而在彼岸时则取为0，例如（1,0,1,0）表示人和鸡在此岸，而狗和米则在对岸。（i）可取状态：根据题意，并非所有状态都是允许的，例如（0,1,1,0）就是一个不可取的状态。本题中可取状态（即系统允许的状态）可以用穷举法列出来，它们是：人在此岸人在对岸(1，1，1，1)(0，0，0，0)(1，1，1，0)(0，0，0，1)(1，1，0，1)(0，0，1，0)(1，0，1，1)(0，1，0，0)(1，0，1，0)(0，1，0，1)总共有十个可取状态，对一般情况，应找出状态为可取的充要条件。（ii）可取运算：状态转移需经状态运算来实现。在实际问题中，摆一次渡即可改变现有状态。为此也引入一个四维向量（转移向量），用它来反映摆渡情况。例如（1，1，0，0）表示人带狗摆渡过河。根据题意，允许使用的转移向量只能有（1，0，0，0，）、（1，1，0，0）、（1，0，1，0）、（1，0，0，1）四个。规定一个状态向量与转移向量之间的运算。规定状态向量与转移向量之和为一新的状态向量，其运算为对应分量相加，且规定0+0=0，1+0=0+1=1，1+1=0。在具体转移时，只考虑由可取状态到可取状态的转移。问题化为：由初始状态（1，1，1，1）出发，经奇数次上述运算转化为（0，0，0，0）的转移过程。我们可以如下进行分析：（第一次渡河）(不可取)(不可取)(可取)(不可取)(0,1,1,1)(0,1,1,0)(0,1,0,1)(0,0,1,1)(1,0,0,0)(1,0,0,1)(1,0,1,0)(1,1,0,0)(1,1,1,1)（第二次渡河）(1,0,0,0)(1,0,0,1)(1,0,1,0)(1,1,0,0)(0,1,0,1)(可取)(不可取)过的状态)(循环,回到原先出现(不可取)(1,1,0,1)(1,1,0,0)(1,1,1,1)(1,0,0,1)＝以下可继续进行下去，直至转移目的实现。上述分析实际上采用的是穷举法，对于规模较大的问题是不宜采用的。例4.2夫妻过河问题这是一个古老的阿拉伯数学问题。有三对夫妻要过河，船最多可载两人，约束条件是根据阿拉伯法律，任一女子不得在其丈夫不场的情况下与其他男子在一起，问此时这三对夫妻能否过河？这一问题的状态和运算与前一问题有所不同，根据题意，状态应能反映出两岸的男女人数，过河也同样要反映出性别故可如下定义：（i）可取状态：用H和W分别表示此岸的男子和女子数，状态可用矢量（H，W）表示，其中0≤H、W≤3。可取状态为（0,i），(i,i)，(3,i)，0≤i≤3。(i,i)为可取状态，这是因为总可以适当安排而使他们是i对夫妻。（ii）可取运算：过河方式可以是一对夫妻、两个男人或两个女人，当然也可以是一人过河。转移向量可取成((－1)im,(－1)in)，其中m、n可取0、1、2，但必须满足1≤m+n≤2。当j为奇数时表示过河。当j为偶数时表示由对岸回来，运算规则同普通向量的加法。问题归结为由状态(3,3)经奇数次可取运算，即由可取状态到可取状态的转移，转化为(0,0)的转移问题。和上题一样，我们既可以用计算机求解，也可以分析求解，此外，本题还可用作图方法来求解。在H~W平面坐标中，以“·”表示可取状态，从A(3,3)经奇数次转移到达O(0,0)。奇数次转移时向左或下移动1-2格而落在一个可取状态上，偶数次转移时向右或上移动1-2格而落在一个可取状态上。为了区分起见,用红箭线表示奇数次转移，用蓝箭线表示第偶数次转移,下图给出了一种可实现的方案,故A(3,3)O(0,0)HW这三对夫妻是可以过河的。假如按这样的方案过河,共需经过十一次摆渡。不难看出,在上述规则下,4对夫妻就无法过河了,读者可以自行证明之.类似可以讨论船每次可载三人的情况,其结果是5对夫妻是可以过河的,而六对以上时就无法过河了。§4.2密码的设计，解码与破译密码的设计和使用至少可从追溯到四千多年前的埃及,巴比伦、罗马和希腊，历史极为久远。古代隐藏信息的方法主要有两大类：其一为隐藏信息载体，采用隐写术等；其二为变换信息载体，使之无法为一般人所理解。在密码学中，信息代码被称为密码，加密前的信息被称为明文，经加密后不为常人所理解的用密码表示的信息被称为密文(ciphertext)，将明文转变成密文的过程被称为加密(enciphering)，其逆过程则被称为解密(deciphering)，而用以加密、解密的方法或算法则被称为密码体制(crytosystem)。记全体明文组成的集合为U，全体密文组成的集合为V，称U为明文空间，V为密文空间。加密常利用某一被称为密钥的东西来实现，它通常取自于一个被称为密钥空间的含有若干参数的集合K。按数学的观点来看，加密与解密均可被看成是一种变换：取一k∈K，u∈U，令，v为明文u在密钥K下的密文，而解码则要用到K的逆变换K-1，。由此可见，密码体系虽然可以千姿百态，但其关键还在于密钥的选取。Vvuk随着计算机与网络技术的迅猛发展，大量各具特色的密码体系不断涌现。离散数学、数论、计算复杂性、混沌、……，许多相当高深的数学知识都被用上，逐步形成了（并仍在迅速发展的）具有广泛应用面的现代密码学。早期密码替代密码移位密码代数密码代替法密码采用另一个字母表中的字母来代替明文中的字母，明文字母与密文字母保持一一对应关系，但采用的符号改变了。加密时，把明文换成密文，即将明文中的字母用密文字母表中对应位置上的字母取代。解密时，则把密文换成明文，即把密文中的字母用明文字母表中对应位置上的字母代回，解密过程是加密过程的逆过程。在代替法加密过程中，密文字母表即代替法密钥，密钥可以是标准字母表，也可以是任意建立的。1.代替法密码明文字母表ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表KLMNOPQRSTUVWXYZABCDEFGHIJ密钥常用一密钥单词或密钥短语生成混淆字母表。密钥单词或密钥短语可以存放在识别码、通行字或密钥的秘密表格中。混合一个字母表，常见的有两种方法，这两种方法都采用了一个密钥单词或一个密钥短语。方法1：a)选择一个密钥单词或密钥短语，例如：constructb)去掉其中重复的字母，得：construc)在修改后的密钥后面接上从标准字母表中去掉密钥中已有的字母后剩下的字母，得：明文字母表ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表CONSTRUABDEFGHIJKLMPQVWXYZ在设计密钥时，也可在明文字母表中选择一个特定字母，然后从该特定字母开始写密钥单词将密钥单词隐藏于其中。例如，对于上例，选取特定字母k，则可得：明文字母表ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表KLMPQVWXYZCONSTRUABDEFGHIJ方法2：a)选择一个密钥单词或密钥短语，例如：constructb)去掉其中重复的字母，得：construc)这些字母构成矩阵的第一行，矩阵的后续各行由标准字母表中去掉密钥单词的字母后剩下的字母构成d)将所得矩阵中的字母按列的顺序排出得：cugmyoahpznbiqsdjvrtekwrflx按照此方法产生的字母表称为混淆字母表。还可以使用混淆数。混淆数由以下方法产生：a)选一密钥单词或密钥短语，例如：constructb)按照这些字母在标准字母表中出现的相对顺序给它们编号，对序列中重复的字母则自左向右编号，得：construct143675928c)自左向右选出这些数字,得到一个混淆数字组:143675928，混淆字母表由从小到大的顺序取矩阵中相应列得出。为增加保密性，在使用代替法时还可利用一些其他技巧，如单字母表对多字母表、单字母对多字母、多重代替等。2.移位密码体制移位密码采用移位法进行加密，明文中的字母重新排列，本身不变，只是位置改变了。早在4000多年前，古希腊人就用一种名叫“天书”的器械来加密消息。该密码器械是用一条窄长的草纸缠绕在一个直径确定的圆筒上，明文逐行横写在纸带上，当取下纸带时，字母的次序就被打乱了，消息得以隐蔽。收方阅读消息时，要将纸带重新绕在直径与原来相同的圆筒上，才能看到正确的消息。在这里圆筒的直径起到了密钥的作用。另一种移位法采用将字母表中的字母平移若干位的方法来构造密文字母表，传说这类方法是由古罗马皇帝凯撒最早使用的，故这种密文字母表被称为凯撒字母表。例如，如用将字母表向右平移3位的方法来构造密文字母表，可得：明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表：DEFGHIJKLMNOPQRTSUVWXYZABC因此“THANKYOU”“WKDQNBRX”以上两种移位较易被人破译，为打破字母表中原有的顺序还可采用所谓路线加密法，即把明文字母表按某种既定的顺序安排在一个矩阵中，然后用另一种顺序选出矩阵中的字母来产生密文表。例如，对明文：THEHISTORYOFZJUISMORETHANONEHUNDREDYEARS.以7列矩阵表示如下：THEHISTORYOFZJUISMORETHANONEHUNDREDYEARS再按事先约定的方式选出密文。例如，如按列选出，得到密文：touthyhrihueeysanahomndrifoorsszrnetjeed使用不同的顺序进行编写和选择，可以得到各种不同的路线加密体制。对于同一明文消息矩阵，采用不同的抄写方式，得到的密文也是不同的。当明文超过规定矩阵的大小时，可以另加一矩阵。当需要加密的字母数小于矩阵大小时，可以在矩阵中留空位或以无用的字母来填满矩阵。移位法也可和代替法结合使用，并使用约定的单词或短语作密钥，以进一步加强保密性，这就是钥控列序加密法。例如，用密钥单词construct对明文MATHEMATICALMODELINGISUSEFUL加密：CONSTRUCT143675928MATHEMATICALMODELINGISUSEFUL按混淆数的顺序选出各列，得到密文：MCNLTLFTLIAAGMDSHMSEOSIIUAEE移位法的使用可重复多次，只进行一次移位加密的称为一次移位法，经多次移位的则称为多次移位法代替法与移位法密码的破译对窃听到的密文进行分析时，穷举法和统计法是最基本的破译方法。穷举分析法就是对所有可能的密钥或明文进行逐一试探，直至试探到“正确”的为止。此方法需要事先知道密码体制或加密算法（但不知道密钥或加密具体办法）。破译时需将猜测到的明文和选定的密钥输入给算法，产生密文，再将该密文与窃听来的密文比较。如果相同，则认为该密钥就是所要求的，否则继续试探，直至破译。以英文字母为例，当已知对方在采用代替法加密时，如果使用穷举字母表来破译，那么对于最简单的一种使用单字母表－单字母－单元代替法加密的密码，字母表的可能情况有26！种，可见，单