浙大城院数学建模4讲课稿课件.ppt

1、第四章、线性代数模型第四章、线性代数模型 4.1 4.1 几个数学游戏几个数学游戏 4.2 Drer4.2 Drer魔方魔方(或幻方或幻方)问题问题 4.3 4.3 密码的设计、解码与破译密码的设计、解码与破译 4.44.4考虑年龄结构的人口模型考虑年龄结构的人口模型(Leslie(Leslie模模型型)4.1 4.1 几个数学游戏几个数学游戏 向量、向量空间、矩阵等都是线性代数中的重要概向量、向量空间、矩阵等都是线性代数中的重要概念，本节将通过一些简单的实例来说明它们在实际中的念，本节将通过一些简单的实例来说明它们在实际中的应用。应用。例例4.14.1 人、狗、鸡、米过河问题人、狗、鸡、米过

2、河问题 这是一个人所共知而又十分简单的智力游戏。某人这是一个人所共知而又十分简单的智力游戏。某人要带狗、鸡、米过河，但小船除了需要有人去划以外，要带狗、鸡、米过河，但小船除了需要有人去划以外，最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡要吃米，问此人应如何过河。要吃米，问此人应如何过河。要知道例要知道例4.14.1的答案并不困难。第一次，人只能带的答案并不困难。第一次，人只能带鸡过河。到了对岸，人只有自己回来，将鸡留在对岸，鸡过河。到了对岸，人只有自己回来，将鸡留在对岸，否则，又返回了初始状态。否则，又返回了初始状态。接下来，人可以带狗过河，

3、也可以带米过河，但回接下来，人可以带狗过河，也可以带米过河，但回来时有一定要将鸡带回，来时有一定要将鸡带回，按此推导下去，读者不，按此推导下去，读者不难找到过河方法。我们研究本例的目的不在于找出答案，难找到过河方法。我们研究本例的目的不在于找出答案，而是想设计出一种让计算机自行搜索寻找答案的方法。而是想设计出一种让计算机自行搜索寻找答案的方法。为此目的，我们先把例为此目的，我们先把例1 1转化为状态转移问题。首先，应转化为状态转移问题。首先，应当如何表达状态呢？不同的情况应采取不同的方法，在当如何表达状态呢？不同的情况应采取不同的方法，在本例中，人鸡狗米都只有两种可能状态，即在此岸或在本例中，

4、人鸡狗米都只有两种可能状态，即在此岸或在彼岸（不在此岸）。我们将用向量来表示状态，可采取彼岸（不在此岸）。我们将用向量来表示状态，可采取如下方法：一物在此岸时相应分量取如下方法：一物在此岸时相应分量取1 1，而在彼岸时则相，而在彼岸时则相应分量取为应分量取为0 0，例如（，例如（1,0,1,01,0,1,0）表示人和鸡在此岸，而）表示人和鸡在此岸，而狗和米则在彼岸。狗和米则在彼岸。(i)(i)可取状态：根据题意，并非所有状态都是允许的，可取状态：根据题意，并非所有状态都是允许的，例如（例如（0,1,1,00,1,1,0）就是一个不可取的状态，因为狗会咬鸡。）就是一个不可取的状态，因为狗会咬鸡。

5、本题中可取状态（即系统允许的状态）可以用穷举法列本题中可取状态（即系统允许的状态）可以用穷举法列出来，它们是：出来，它们是：(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)(ii)可取运算：状态转移需要经过状态运算

6、来实现。在可取运算：状态转移需要经过状态运算来实现。在实际问题中，摆一次渡即可改变现有状态。为此再引入一实际问题中，摆一次渡即可改变现有状态。为此再引入一个四维向量个四维向量(转移向量转移向量)，用它来反映摆渡情况。例如，用它来反映摆渡情况。例如(1(1，1 1，0 0，0)0)表示人带狗摆渡过河。根据题意，允许使用的转表示人带狗摆渡过河。根据题意，允许使用的转移向量只能有移向量只能有(1(1，0 0，0 0，0)0)、(1(1，1 1，0 0，0)0)、(1(1，0 0，1 1，0)0)、（、（1 1，0 0，0 0，1)1)四个。四个。为实现本题中的状态转移，规定一个状态向量与转为实现本题

7、中的状态转移，规定一个状态向量与转移向量之间的运算。规定状态向量与转移向量之和为一移向量之间的运算。规定状态向量与转移向量之和为一新的状态向量，其运算为对应分量相加，且规定新的状态向量，其运算为对应分量相加，且规定0+0=00+0=0，1+0=0+1=11+0=0+1=1，1+1=01+1=0。例如。例如(1(1，1 1，1 1，1)+(11)+(1，0 0，1 1，0)=(00)=(0，1 1，0 0，1)1)，其实际意义为人狗鸡米原来均在此岸，其实际意义为人狗鸡米原来均在此岸，人带鸡过河，转变为新的状态此岸仅剩狗和米，人带鸡过河，转变为新的状态此岸仅剩狗和米，(注：此注：此处作这样的运算规

8、定完全是为了与实际情况相符处作这样的运算规定完全是为了与实际情况相符)。在具体转移时，只考虑由可取状态到可取状态的转在具体转移时，只考虑由可取状态到可取状态的转移。问题化为：由初始状态移。问题化为：由初始状态(1(1，1 1，1 1，1)1)出发，经过奇出发，经过奇数次的上述运算能否转化为数次的上述运算能否转化为(0(0，0 0，0 0，0)0)的转化问题，的转化问题，进而，如果能，我们还想知道具体应当如何转化进而，如果能，我们还想知道具体应当如何转化 。由于规定的运算十分容易在计算机上实现，这样一由于规定的运算十分容易在计算机上实现，这样一来就把一个数学游戏转化为了一个可以在计算机上计算来就

9、把一个数学游戏转化为了一个可以在计算机上计算的数学问题的数学问题(即建模即建模)。当然，像本题这样简单的问题，。当然，像本题这样简单的问题，也可通过笔算方法求解，具体可如下进行分析也可通过笔算方法求解，具体可如下进行分析(第一次渡河第一次渡河)(1,1,0,0)(0,0,1,1)()(1,0,1,0)(0,1,0,1)()(1,1,1,1)(1,0,0,1)(0,1,1,0)()(1,0,0,0)(0,1,1,1)()不可取可取不可取不可取(第二次渡河第二次渡河)(1,1,0,0)(1,0,0,1)()(1,0,1,0)(1,1,1,1)(,)(0,1,0,1)(1,0,0,1)(1,1,0,

10、0)()(1,0,0,0)(1,1,0,1)()不可取循环 回到原先出现过的状态不可取可取 以下可继续进行下去，直至转移目的实现。以下可继续进行下去，直至转移目的实现。上述分析实际上采用的是穷举法，对于规模较大上述分析实际上采用的是穷举法，对于规模较大的问题是不宜采用的。的问题是不宜采用的。例例4.2 4.2 夫妻过河问题夫妻过河问题 这是一个古老的阿拉伯数学问题。有三对夫妻要这是一个古老的阿拉伯数学问题。有三对夫妻要过河，船最多可载两人，约束条件是根据阿拉伯法律，过河，船最多可载两人，约束条件是根据阿拉伯法律，任一女子不得在其丈夫不在场的情况下与其他男子在任一女子不得在其丈夫不在场的情况下与

11、其他男子在一起，问此时这三对夫妻能否过河？一起，问此时这三对夫妻能否过河？这一问题的状态和运算与前一问题有所不同，根这一问题的状态和运算与前一问题有所不同，根据题意，状态应能反映出两岸的男女人数，过河也同据题意，状态应能反映出两岸的男女人数，过河也同样要反映出性别，故可如下定义：样要反映出性别，故可如下定义：(i)(i)可取状态：用可取状态：用H H和和W W分别表示此岸的男子和女子数，分别表示此岸的男子和女子数，状态可用矢量状态可用矢量(H H，W W)表示，其中表示，其中00H H、W W33。可取状。可取状态为态为(0,(0,i i)，(i i,i i)，(3,(3,i i)，00i i

12、33。(i i,i i)为可取状为可取状态，这是因为总可以适当安排而使他们是态，这是因为总可以适当安排而使他们是i i对夫妻。对夫妻。(ii)(ii)可取运算：过河方式可以是一对夫妻、两个男人可取运算：过河方式可以是一对夫妻、两个男人或两个女人，当然也可以是一人过河。转移向量可取或两个女人，当然也可以是一人过河。转移向量可取成成(1 1）i im m,(,(1)1)i in n），其中），其中m m、n n可取可取0 0、1 1、2 2，但，但必须满足必须满足11m m+n n22。当。当j j为奇数时表示过河。当为奇数时表示过河。当j j为偶为偶数时表示由对岸回来，运算规则同普通向量的加法。

13、数时表示由对岸回来，运算规则同普通向量的加法。问题归结为由状态问题归结为由状态(3,3)(3,3)经奇数次可取运算，即由可取经奇数次可取运算，即由可取状态到可取状态的转移，转化为状态到可取状态的转移，转化为(0,0)(0,0)的转移问题。和的转移问题。和上题一样，我们既可以用计算机求解，也可以分析求上题一样，我们既可以用计算机求解，也可以分析求解，此外，本题还可用作图方法来求解。解，此外，本题还可用作图方法来求解。关于夫妻过河还可以编出许多其他形式的问题，下关于夫妻过河还可以编出许多其他形式的问题，下面我们来讨论一些同样有趣的问题。为了叙述简便，先面我们来讨论一些同样有趣的问题。为了叙述简便，

14、先约定一些符号，这些符号将被应用于以下的各个问题之约定一些符号，这些符号将被应用于以下的各个问题之中。记想过河的夫妻对数为中。记想过河的夫妻对数为n n，船可载的人数为，船可载的人数为m m，n n对对夫妻过河所需的最少摆渡次数为夫妻过河所需的最少摆渡次数为k k。这三对夫妻是可以过河的。假如按这样的方案过这三对夫妻是可以过河的。假如按这样的方案过河，共需经过十一次摆渡。河，共需经过十一次摆渡。不难看出，在上述规则下，不难看出，在上述规则下，4 4对夫妻就无法过河了，对夫妻就无法过河了，读者可以自行证明之。类似可以讨论船每次可载三人的读者可以自行证明之。类似可以讨论船每次可载三人的情况，其结果

15、是情况，其结果是5 5对夫妻是可以过河的，而六对以上时对夫妻是可以过河的，而六对以上时就无法过河了。假如船每次可以载四人，则任意多对夫就无法过河了。假如船每次可以载四人，则任意多对夫妻均可过河，最易看出的一个方案是让一对夫妻当船员妻均可过河，最易看出的一个方案是让一对夫妻当船员工即可。工即可。(问题问题1)1)2 2对夫妻要过河，船每次只能渡对夫妻要过河，船每次只能渡2 2人，应如何人，应如何过河，最少摆渡几次？过河，最少摆渡几次？(即即n=2n=2，m=2m=2，求，求k=?)k=?)本问题很容易解答，读者可自行完成本问题很容易解答，读者可自行完成(答案为答案为k=5)k=5)。(问题问题2

16、)2)n n对夫妻要过河，船每次可载对夫妻要过河，船每次可载n-1n-1人，应如何过人，应如何过河，最少要摆几次渡？（河，最少要摆几次渡？（n=m-1n=m-1，求，求k=?k=?）。）。答案如下：答案如下：(1)n=3(1)n=3，m=2m=2，k=11;(2)n=4k=11;(2)n=4，m=3m=3，k=9k=9 (3)n5 (3)n5，m=n-1m=n-1，k=7k=7(问题问题3)3)1883 1883年，吕卡斯年，吕卡斯(Rcrations)(Rcrations)提出以下问题：提出以下问题：n n对夫妻要过河，船至少应可载几人对夫妻要过河，船至少应可载几人(m?)(m?)他们才可能

17、他们才可能过河，最少摆渡次数为多少？过河，最少摆渡次数为多少？德兰努瓦德兰努瓦(M.Delannoy)(M.Delannoy)证明：证明：(1)n=2(1)n=2，m=2m=2，k=5k=5；(2)n=3(2)n=3，m=3m=3，k=11k=11(3)n=4(3)n=4，m=3m=3，k=9k=9；(4)n=5(4)n=5，m=3m=3，k=11k=11(5)n6(5)n6，m=4m=4，k=2n-3k=2n-3 有些较为复杂的问题，开始时常常给人以一种有些较为复杂的问题，开始时常常给人以一种变幻莫测的感觉。但经过细微的分析研究，可以发现变幻莫测的感觉。但经过细微的分析研究，可以发现其中存在

18、着某些内在的关系。在使用适当的数学工具其中存在着某些内在的关系。在使用适当的数学工具后，这些内在关系就被一一揭露出来了。后，这些内在关系就被一一揭露出来了。德国著名的艺术家德国著名的艺术家Albrecht Drer(1471-1521)Albrecht Drer(1471-1521)于于15141514年曾铸造了一枚名为年曾铸造了一枚名为“Melencotia I”Melencotia I”的铜币。的铜币。令人奇怪的是在这枚铜币的画面上充满了数学符号、令人奇怪的是在这枚铜币的画面上充满了数学符号、数字及几何图形。这里，我们仅研究铜币右上角的数数字及几何图形。这里，我们仅研究铜币右上角的数字问题

19、。字问题。4.2 Drer4.2 Drer魔方魔方(或幻方或幻方)问题问题1 1、DrerDrer魔方魔方16 3 这是一个由自然数组成的方块，称之为这是一个由自然数组成的方块，称之为DrerDrer魔方，魔方，其数字排列如下：其数字排列如下：什么是魔方？我们来下一个定义。我们所谓的魔方什么是魔方？我们来下一个定义。我们所谓的魔方是指由是指由1 1n n2 2这这n n2 2个正整数按一定规则排列成的一个个正整数按一定规则排列成的一个n n行行n n列的正方形。列的正方形。按不同的要求，它可以具有某些特定的性质，按不同的要求，它可以具有某些特定的性质，n n称称为此魔方的阶。例如，上面给出的为

20、此魔方的阶。例如，上面给出的DrerDrer魔方是魔方是4 4阶的，阶的，它的每一行数字之和为它的每一行数字之和为3434，每一列数字之和为，每一列数字之和为3434，把对，把对角线角线(或反对角线或反对角线)上的数字加起来是上的数字加起来是3434，每个小方块中，每个小方块中的数字之和也是的数字之和也是3434，若把四个角上的数字加起来还是，若把四个角上的数字加起来还是3434，多么奇妙！最后一行中间两个数字恰好是铜币的铸造时多么奇妙！最后一行中间两个数字恰好是铜币的铸造时间间15141514年。年。构造魔方是一个古老的数学游戏，起初它还和神灵构造魔方是一个古老的数学游戏，起初它还和神灵联系

21、在一起，带有深厚的迷信色彩。传说三千二百多年联系在一起，带有深厚的迷信色彩。传说三千二百多年前前(公元前公元前22002200年年)，因治水出名的皇帝大禹就构造了三，因治水出名的皇帝大禹就构造了三阶魔方阶魔方(被人们称被人们称“洛书洛书”)，至今还有人把它当作符咒，至今还有人把它当作符咒用于某些迷信活动，用于某些迷信活动，8 1(被人称为洛书的被人称为洛书的3 3阶魔方阶魔方)大约在十五世纪时，魔方传到了西方，著名的科尼大约在十五世纪时，魔方传到了西方，著名的科尼利厄斯利厄斯阿格里帕阿格里帕(1486-1535)(1486-1535)先后构造出了先后构造出了3 39 9阶的魔阶的魔方。方。如何

22、构造出各种阶数的魔方呢？假如你知道方法，如何构造出各种阶数的魔方呢？假如你知道方法，构造它其实并不困难。构造它其实并不困难。在构造在构造n n阶魔方时，首先要看清阶魔方时，首先要看清n n是奇数还是偶数，是奇数还是偶数，在构造时要巧妙地利用某种形式的对称性。在构造时要巧妙地利用某种形式的对称性。我们先来看我们先来看n n是奇数的情况，奇数阶魔方的构造方法是奇数的情况，奇数阶魔方的构造方法如下：如下：首先，在第一行中间写首先，在第一行中间写1 1；然后每次向右上方移一；然后每次向右上方移一格，依次填由小到大排列的下一个数，格，依次填由小到大排列的下一个数，(注：向上移出注：向上移出界时填下一列最

23、后一行的小方格；向右移出界时填第一界时填下一列最后一行的小方格；向右移出界时填第一列上一行的小方格，就好像上下边是相连的、左右边也列上一行的小方格，就好像上下边是相连的、左右边也是相连的一样是相连的一样)。此外，当下面想填的格已填过数或已。此外，当下面想填的格已填过数或已达到魔方的右上角时，改填刚才填的格子正下方的小方达到魔方的右上角时，改填刚才填的格子正下方的小方格，此后继续按原方法填，直至完全填完所有小方格。格，此后继续按原方法填，直至完全填完所有小方格。例如，按上述方法可构造出下面的例如，按上述方法可构造出下面的5 5阶魔方：阶魔方：作为练习，请你给出一个作为练习，请你给出一个7 7阶阶

24、的魔方的魔方(见习题见习题)。偶数阶的魔方可以利用奇数阶魔方拼接而成，拉偶数阶的魔方可以利用奇数阶魔方拼接而成，拉尔夫尔夫斯特雷奇给出了一种拼接的方法。限于篇幅的斯特雷奇给出了一种拼接的方法。限于篇幅的限止，我们不在此详细介绍了，作为一个例子，我们限止，我们不在此详细介绍了，作为一个例子，我们采用他的方法构造一个采用他的方法构造一个6 6阶的魔方。阶的魔方。第一步第一步 利用利用1-91-9，10-1810-18，19-2719-27及及28-3628-36构造出构造出4 4个个3 3阶的魔方，它们分别是：阶的魔方，它们分别是：第二步第二步 利用图利用图11-911-9中的中的A A、B B、

25、C C、D D容易拼出一个容易拼出一个6 6阶阶的魔方。为了保证性质的成立，还需要作一些调整，的魔方。为了保证性质的成立，还需要作一些调整，如果你有兴趣，不妨可以找一下调整的方法，如果你有兴趣，不妨可以找一下调整的方法，(调整后调整后得到的得到的6 6阶魔方见图阶魔方见图4-24-2所示所示)(图图4-24-2)上述方法并非构造魔方的唯一方法，但不论采用上述方法并非构造魔方的唯一方法，但不论采用什么方法来构造魔方，都应当尽可能利用某种形式的对什么方法来构造魔方，都应当尽可能利用某种形式的对称性。在魔方的构造中包含了许多有趣的数学问题，但称性。在魔方的构造中包含了许多有趣的数学问题，但由于很多人

26、研究过这些问题，我们一般只能把它们当成由于很多人研究过这些问题，我们一般只能把它们当成一些练习题。一些练习题。互不相同的同阶魔方究竟有多少个？人们知道，三互不相同的同阶魔方究竟有多少个？人们知道，三阶魔方只有一个，当然，通过镜面反射和绕中心旋转可阶魔方只有一个，当然，通过镜面反射和绕中心旋转可以产生以产生8 8种不同的表现形式。四阶魔方共有种不同的表现形式。四阶魔方共有880880个，而通个，而通过反射与旋转可有过反射与旋转可有70407040种不同的形式。没有人知道五阶种不同的形式。没有人知道五阶或更高阶魔方的数量。例如，对五阶魔方，人们可用某或更高阶魔方的数量。例如，对五阶魔方，人们可用某

27、种办法作出实质上不同的种办法作出实质上不同的5760057600个个(不含反射与旋转而得不含反射与旋转而得出的出的)，如加上用其他方法构造的，已知的五阶魔方总，如加上用其他方法构造的，已知的五阶魔方总数远远超过了一千三百万个，魔方数量随阶数数远远超过了一千三百万个，魔方数量随阶数n n增长已增长已达到了惊人的速度，令人目瞪口呆。达到了惊人的速度，令人目瞪口呆。2 2、松驰问题的讨论、松驰问题的讨论 假如我们放松对构造魔方的数必须是假如我们放松对构造魔方的数必须是1-n21-n2的要求而的要求而允许它们取任意实数，允许它们取任意实数，(就像将整数规划或就像将整数规划或0-10-1规划松驰规划松驰

28、成相应的线性规划那样成相应的线性规划那样)，问题也许会简单得多。我们，问题也许会简单得多。我们仍要求它们具有某些特定的性质，并不妨仍把它们称为仍要求它们具有某些特定的性质，并不妨仍把它们称为魔方，当然，此时问题已发生了实质性的变化，不再是魔方，当然，此时问题已发生了实质性的变化，不再是原先讨论的问题了。原先讨论的问题了。为简单起见，我们用为简单起见，我们用n n阶方阵来记这样的魔方。易见，阶方阵来记这样的魔方。易见，若若A A与与B B均为具有指定性质的魔方，则对任意的实数均为具有指定性质的魔方，则对任意的实数和和，A+BA+B也是。这一性质表明，具有指定性质的魔方也是。这一性质表明，具有指定

29、性质的魔方全体构成一个线性空间。根据线性代数知识，要刻画一全体构成一个线性空间。根据线性代数知识，要刻画一个线性空间只需指出它的维数并求出此线性空间的一组个线性空间只需指出它的维数并求出此线性空间的一组基底即可。基底即可。不妨仍以不妨仍以4 4阶方阵为例。首先，定义阶方阵为例。首先，定义0-0-方与方与1-1-方如下：方如下：其中其中R R为行和，为行和，C C为列和，为列和，D D为对角线和，为对角线和，S S为小方为小方块和。块和。现在，我们来研究具有性质现在，我们来研究具有性质R=C=D=SR=C=D=S的方阵构成的线的方阵构成的线性空间性空间 ，类似于构造，类似于构造n n维欧氏空间的

30、标准基，我们利用维欧氏空间的标准基，我们利用0 0和和1 1来构造一些来构造一些R=C=D=S=1R=C=D=S=1的最简单的方阵，不难看出，的最简单的方阵，不难看出，1 1在第一行中共有在第一行中共有4 4种排法，为保持上述性质的成立，在种排法，为保持上述性质的成立，在第一行的第一行的1 1取定后，第二行中的取定后，第二行中的1 1尚有两种取法。当第二尚有两种取法。当第二行的行的1 1也取定后，第三行与第四行的也取定后，第三行与第四行的1 1就完全定位了，故就完全定位了，故一共可作出一共可作出8 8个不同的最简方阵，称之为基本魔方并记之个不同的最简方阵，称之为基本魔方并记之为为Q1Q1，Q8

31、Q8。11000001000010100Q21000000101000010Q30001100000100100Q40001010010000010Q50010100001000001Q60100001010000001Q70010010000011000Q80100000100101000Q 显然，显然，D D中任何一个元素都可以用中任何一个元素都可以用Q Q1 1，Q Q2 2，Q Q8 8来来线性表示，它们能否构成线性表示，它们能否构成D D的一组基，关键在于它们是的一组基，关键在于它们是否线性无关。否线性无关。容易看出容易看出145823670QQQQQQQQ 所以所以Q Q1 1，Q

32、 Q2 2，Q Q8 8这这8 8个基本方是线性相关的，即个基本方是线性相关的，即至少存在一个至少存在一个Q Qj j，可以通过其它，可以通过其它7 7个基本方的线性组合个基本方的线性组合得到，这得到，这8 8个基本方的地位是等同的，故可不妨设个基本方的地位是等同的，故可不妨设j=8j=8。下面验证下面验证Q Q1 1，Q Q2 2，Q Q7 7是否线性相关。是否线性相关。令，令，即即 710iiirQ12657343547162462531771324560000000000000000rrrrrrrrrrrrrrrrrrrrrrrrrrrr 等号两边对应元素相比较，得等号两边对应元素相比较

33、，得r r1 1=r=r2 2=r=r7 7=0=0，所以，所以Q Q1 1，Q Q2 2，Q Q7 7是线性无关的。是线性无关的。Q Q1 1，Q Q2 2，Q Q7 7是是D D空间空间的一组基，的一组基，D D中任何元素都可以由中任何元素都可以由Q Q1 1，Q Q2 2，Q Q7 7的线性的线性组合生成。可以这样认为：组合生成。可以这样认为：Q Q1 1，Q Q2 2，Q Q8 8 是是D D的生的生成集，但不是最小生成集，而成集，但不是最小生成集，而 Q Q1 1，Q Q2 2，Q Q7 7 是是D D的的最小生成集。最小生成集。现在，我们回到现在，我们回到Albrecht Drer

34、Albrecht Drer铸造的铜币，以铸造的铜币，以Q Q1 1，Q Q2 2，Q Q7 7的 线 性 组 合 表 示 铜 币 上 的 魔 方，的 线 性 组 合 表 示 铜 币 上 的 魔 方，D=D=d d1 1Q Q1 1+d+d2 2Q Q2 2+d+d7 7Q Q7 7，即解方程组，即解方程组 126573435471624625317713245616321351011896712515141dddddddddddddddddddddddddddd解得解得1234567D=8Q+8Q+7Q+6Q+3Q+3Q+5Q3 3、D D空间的子空间和空间的子空间和D D空间的扩展空间的扩展

35、 改变对改变对DrerDrer魔方数字和的要求，我们可以利用线性魔方数字和的要求，我们可以利用线性子空间的定义，构造子空间的定义，构造D D的子空间或者构造新的空间包含的子空间或者构造新的空间包含D D空间。这里，我们规定仅包含空间。这里，我们规定仅包含0 0方的向量空间维数为零。方的向量空间维数为零。(1)(1)要 求 数 字 方 的 所 有 数 都 相 等。这 是 集 合要 求 数 字 方 的 所 有 数 都 相 等。这 是 集 合G=rE,rRG=rE,rR，G G是以是以G=EG=E为基的一维向量空间，是为基的一维向量空间，是D D的一维子空间。的一维子空间。(2)(2)要求列和，行和

36、及每条主、付对角线上数字和都相要求列和，行和及每条主、付对角线上数字和都相等，得到等，得到5 5维泛对角方的向量空间维泛对角方的向量空间B B。例如：。例如：17211161611223127621126712PH=N=R=C=S=46H=N=R=C=S=46其中其中H H为主对角线和，为主对角线和，N N为付对角线和。为付对角线和。它的基它的基BBBB为为11010101001010101P21001011010010110P30110100101101001P40101101010100101P51100001111000011P(3)(3)要求行和，列和及两条对角线上的元素和相等，要求行

37、和，列和及两条对角线上的元素和相等，得到得到8 8维向量空间维向量空间Q Q，基向量，基向量Q QB B=Q=Q1 1，Q Q2 2，Q Q7 7，N N0 0，其中，其中Q Q1 1，Q Q2 2，Q Q7 7是是D D的基，的基，00110000000000110N例如：例如：679812657510967779TR=C=D=30R=C=D=30(4)(4)仅要求行和与列和相等，可以得到仅要求行和与列和相等，可以得到1010维向量空间维向量空间，它的基，它的基B B=Q=Q1 1，Q Q2 2，Q Q7 7，N N1 1，N N2 2，N N3 3，其中，其中Q Q1 1，Q Q2 2，Q

38、 Q7 7是是D D的基，而的基，而10000100110010000N20101101010010110N30100100000010010N(5)(5)如果我们对数字没任何要求，那么所有的如果我们对数字没任何要求，那么所有的4 44 4数数字方组成的向量空间字方组成的向量空间M M，它的维数是，它的维数是1616，基向量，基向量MBMB中的中的元素应是标准基，元素应是标准基，(即仅有一个元素为即仅有一个元素为1 1，其余元素均，其余元素均为为0 0的方阵的方阵)。Botsch(1976 Botsch(1976年年)证明了可以构造大量的证明了可以构造大量的D D的子空间的子空间或或D D的扩

39、张空间。对于的扩张空间。对于1 1与与1616之间的每一个数之间的每一个数K K，都存在，都存在K K维的维的4 44 4方的向量空间，其中的每一方阵都具有某些方的向量空间，其中的每一方阵都具有某些特定的性质。特定的性质。由上可知，有下式成立由上可知，有下式成立(向量空间向量空间)0GBDQM 0 1 5 7 8 10 160 1 5 7 8 10 16(维数维数)4.3 4.3 密码的设计、解码与破译密码的设计、解码与破译 密码的设计和使用至少可以追溯到四千多年前的埃密码的设计和使用至少可以追溯到四千多年前的埃及及 、巴比伦、罗马和希腊，历史极为久远。古代隐藏信、巴比伦、罗马和希腊，历史极为

40、久远。古代隐藏信息的方法主要有两大类：其一为隐藏信息载体，采用隐息的方法主要有两大类：其一为隐藏信息载体，采用隐写术等；其二为变换信息载体，使之无法为一般人所理写术等；其二为变换信息载体，使之无法为一般人所理解。本节只涉及后者，介绍一些采用数学工具对信息加解。本节只涉及后者，介绍一些采用数学工具对信息加密、解密的方法。密、解密的方法。在密码学中，信息代码被称为密码，加密前的信息在密码学中，信息代码被称为密码，加密前的信息被称为明文，经加密后不为常人所理解的用密码表示的被称为明文，经加密后不为常人所理解的用密码表示的信息被称为密文信息被称为密文(ciphertext)(ciphertext)，将

41、明文转变成密文的过，将明文转变成密文的过程被称为加密程被称为加密(enciphering)(enciphering)，其逆过程则被称为解密，其逆过程则被称为解密(deciphering)(deciphering)，而用以加密、解密的方法或算法则被称，而用以加密、解密的方法或算法则被称为密码体制为密码体制(crytosystem)(crytosystem)。记全体明文组成的集合为记全体明文组成的集合为U U，全体密文组成的集合为，全体密文组成的集合为V V，称，称U U为明文空间，为明文空间，V V为密文空间。加密常利用某一被称为密文空间。加密常利用某一被称为密钥的东西来实现，它通常取自于一个被

42、称为密钥空为密钥的东西来实现，它通常取自于一个被称为密钥空间的含有若干参数的集合间的含有若干参数的集合K K。按数学的观点来看，加密与。按数学的观点来看，加密与解密均可被看成是一种变换解密均可被看成是一种变换(或称映射或称映射)：取一：取一k kK K，u uU U，令，令 ，v v为明文为明文u u在密钥在密钥K K下的密文，下的密文，而解码则要用到而解码则要用到K K的逆变换的逆变换K K-1-1，。由此可见，。由此可见，密码体系虽然可以千姿百态，但其关键还在于密钥的选密码体系虽然可以千姿百态，但其关键还在于密钥的选取。取。kuvV 1kvu 随着计算机与网络技术的迅猛发展，大量各具特色随

43、着计算机与网络技术的迅猛发展，大量各具特色的密码体系不断涌现。离散数学、数论、计算复杂性、的密码体系不断涌现。离散数学、数论、计算复杂性、混沌、混沌、，许多相当高深的数学知识都被用上，逐步，许多相当高深的数学知识都被用上，逐步形成了形成了(并仍在迅速发展的并仍在迅速发展的)具有广泛应用面的现代密码具有广泛应用面的现代密码学。学。早期密码大体可分三类：代替法密码、移位密码和早期密码大体可分三类：代替法密码、移位密码和代数密码。代数密码。代替法密码代替法密码 代替法密码采用另一个字母表中的字母来代替明文代替法密码采用另一个字母表中的字母来代替明文中的字母，明文字母与密文字母保持一一对应关系，但中的

44、字母，明文字母与密文字母保持一一对应关系，但采用的符号改变了。加密时，把明文换成密文，即把明采用的符号改变了。加密时，把明文换成密文，即把明文中的字母用密文字母表中对应位置上的字母取代。解文中的字母用密文字母表中对应位置上的字母取代。解密时，则把密文换成明文，即把密文中的字母用明文字密时，则把密文换成明文，即把密文中的字母用明文字母表中对应位置上的字母代回母表中对应位置上的字母代回,解密过程是加密过程的逆解密过程是加密过程的逆过程。在代替法加密过程中，明文字母表、密文字母表过程。在代替法加密过程中，明文字母表、密文字母表及两者间的对应关系即为代替法密钥，密钥既可以采用及两者间的对应关系即为代替

45、法密钥，密钥既可以采用标准字母表，也可以任意建立。例如，我们可采用以下标准字母表，也可以任意建立。例如，我们可采用以下的明文字母表和密文字母表：的明文字母表和密文字母表：明文字母表明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表密文字母表 KLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJ 密钥还经常用一密钥字或密钥短语生成混淆字母表。密钥还经常用一密钥字或密钥短语生成混淆字母表。密钥字或密钥短语可以存放在识别码、通行字或密钥的密钥字或密钥短语可以存放在识别码、通

46、行字或密钥的秘密表格中。混合一个字母表，常见的有两种方法，这秘密表格中。混合一个字母表，常见的有两种方法，这两种方法都采用了一个密钥字或一个密钥短语。两种方法都采用了一个密钥字或一个密钥短语。方法一：方法一：a)a)选择一个密钥字或密钥短语，例如：选择一个密钥字或密钥短语，例如：constructconstructb)b)去掉其中重复的字母，得：去掉其中重复的字母，得：construconstruc)c)在修改后的密钥字后面接上从标准字母表中去在修改后的密钥字后面接上从标准字母表中去掉密钥中的已有字母后剩下的字母，得：掉密钥中的已有字母后剩下的字母，得：明文字母表明文字母表 ABCDEFGHI

47、JKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表密文字母表 CONSTRUABDEFGHIJKLMPQVWXYZCONSTRUABDEFGHIJKLMPQVWXYZ 在设计密钥时，也可在明文字母表中选择一个特定在设计密钥时，也可在明文字母表中选择一个特定字母，然后从该特定字母开始写密钥字并将密钥字隐藏字母，然后从该特定字母开始写密钥字并将密钥字隐藏于其中。例如，对于上例，选取特定字母于其中。例如，对于上例，选取特定字母k k，则可得：，则可得：明文字母表明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNO

48、PQRSTUVWXYZ密文字母表密文字母表 KLMPQVWXYZCONSTRUABDEFGHIJ KLMPQVWXYZCONSTRUABDEFGHIJ 方法二：方法二：a)a)选择一个密钥字或密钥短语，例如：选择一个密钥字或密钥短语，例如：constructconstruct b)b)去掉其中重复的字母，得：去掉其中重复的字母，得：construconstru c)c)这些字母构成矩阵的第一行，矩阵的后续各行由这些字母构成矩阵的第一行，矩阵的后续各行由标准字母表中去掉密钥字的字母后剩下的字母构成标准字母表中去掉密钥字的字母后剩下的字母构成construab de fghijklm p qv w

49、 xyz d)d)把所得矩阵中的字母按列的顺序选出，得：把所得矩阵中的字母按列的顺序选出，得：caivobjwndkxselytfmzrgpuhqcaivobjwndkxselytfmzrgpuhq按照此方法产生的字母表称为混淆字母表。按照此方法产生的字母表称为混淆字母表。在代替法加密中，除了使用混淆字母表外，还可在代替法加密中，除了使用混淆字母表外，还可以使用混淆数。混淆数由以下方法产生：以使用混淆数。混淆数由以下方法产生：a)a)选一密钥字或密钥短语，例如：选一密钥字或密钥短语，例如：constructconstructb)b)按照这些字母在标准字母表中出现的相对顺序给它们按照这些字母在标

50、准字母表中出现的相对顺序给它们编号，对序列中重复的字母则自左向右编号，得：编号，对序列中重复的字母则自左向右编号，得：construct construct 143675928 143675928c)c)自左向右选出这些数字，得到一混淆数字组：自左向右选出这些数字，得到一混淆数字组：143675928143675928，混淆字母表由从小到大的顺序取矩阵中相，混淆字母表由从小到大的顺序取矩阵中相应列得出应列得出,先取第一列、再取第先取第一列、再取第8 8列、列、，依次得出秘，依次得出秘文字母表。文字母表。为增加保密性，在使用代替法时还可利用一些其他技为增加保密性，在使用代替法时还可利用一些其他技