《数据结构与算法设计》第十、十一章习题课ppt课件.ppt

《《数据结构与算法设计》第十、十一章习题课ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十、十一章习题课北京理工大学计算机学院刘琼昕1第十章习题课主要内容半群、独异点与群的定义群的基本性质子群的判别定理陪集的定义及其性质拉格朗日定理及其应用循环群的生成元和子群置换群与Polya定理环的定义与性质特殊的环2基本要求判断或证明给定集合和运算是否构成半群、独异点和群熟悉群的基本性质能够证明G的子集构成G的子群熟悉陪集的定义和性质熟悉拉格朗日定理及其推论，能够简单应用会用Polya定理进行计数熟悉循环群的生成元及其子群性质熟悉n元置换的表示方法、乘法以及n元置换群能判断给定代数系统是否为环和域3练习1判断下列集合和运算是否构成半群、独异点和群.(1)a是正整

2、数，G={an

3、nZ},运算是普通乘法.(2)Q+是正有理数集，运算为普通加法.(3)一元实系数多项式的集合关于多项式加法.4练习1解答(1)是半群、独异点和群(2)是半群但不是独异点和群(3)是半群、独异点和群方法：根据定义验证，注意运算的封闭性5练习2设V1=,V2=,其中Z为整数集合,+和分别代表普通加法和乘法.显然V1和V2是半群和独异点.判断下述集合S是否构成V1和V2的子半群和子独异点.(1)S={2k

4、kZ}(2)S={2k+1

5、kZ}(3)S={1,0,1}6练习2解答(1)S关于V1构成子半群和子独异点，但是关于V2仅构

6、成子半群。(2)S关于V1不构成子半群也不构成子独异点，S关于V2构成子半群和子独异点。(3)S关于V1不构成子半群和子独异点，关于V2构成子半群和子独异点。78练习3判断下列集合和给定运算是否构成环、整环和域,如果不构成,说明理由.(1)A={a+bi

7、a,b∈Q},其中i2=1,运算为复数加法和乘法.(2)A={2z+1

8、z∈Z},运算为实数加法和乘法(3)A={2z

9、z∈Z},运算为实数加法和乘法(4)A={x

10、x≥0∧x∈Z},运算为实数加法和乘法.(5)9练习3解答解：(1)是环,是整环,也是域.(2)不是环,因为关于加法不封闭.(3)是环,不是整环和域,

11、因为乘法没有么元.(4)不是环,因为正整数关于加法的负元不存在.(5)不是环,因为关于乘法不封闭.练习4设Z18为模18整数加群,求所有元素的阶.解：

12、0

13、=1

14、9

15、=2

16、6

17、=

18、12

19、=3

20、3

21、=

22、15

23、=6

24、2

25、=

26、4

27、=

28、8

29、=

30、10

31、=

32、14

33、=

34、16

35、=9

36、1

37、=

38、5

39、=

40、7

41、=

42、11

43、=

44、13

45、=

46、17

47、=181011说明群中元素的阶可能存在，也可能不存在.对于有限群，每个元素的阶都存在，而且是群的阶的因子.对于无限群，单位元的阶存在，是1；而其它元素的阶可能存在，也可能不存在.（可能所有元素的阶都存在，但是群还是无限群）.12练习5(1)设G为模12加群

48、,求<3>在G中所有的左陪集(2)设X={x

49、xR,x0,1},在X上如下定义6个函数：f1(x)=x，f2(x)=1/x,f3(x)=1x,f4(x)=1/(1x),f5(x)=(x1)/x,f6(x)=x/(x1),则G={f1,f2,f3,f4,f5,f6}关于函数合成运算构成群.求子群H={f1,f2}的所有的右陪集.13练习5解答解：(1)<3>={0,3,6,9},<3>的不同左陪集有3个，即0<3>=<3>,1<3>={1,4,7,10}=4<3>=7<3>=10<3>2<3>={2,5,8,11}=5<3>=8<3>=11<3>(2){f1

50、,f2}有3个不同的陪集，它们是：H，Hf3={f3,f5},Hf4={f4,f6}.14练习6设i为虚数单位，即i2=1,令则G关于矩阵乘法构成群.找出G的所有子群.15练习6解答解令A,B,C,D分别为则运算表为G的子群有6个，即平凡子群：={A},G2阶子群：<-A>={A,-A},4阶子群：={A,B,-A,-B},={A,C,-A,-C},={A,D,-A,-D},17练习7设群G的运算表如表所示，问G是否为循环群？如果是，求出它所有的生成元和子群。解：G=是循环群

51、b

52、=

53、f

54、=6,b和f是生成元.

55、c

56、=

57、e

58、=3,

59、

60、d

61、=2,c,d,e不是生成元.子群：阶数1,2,3,61阶：={a}2阶：={d,a}3阶：={c,e,a}6阶：G*练习8试证：任何一个四阶群只可能是四阶循环群或者Klein四元群。证明：设四阶群为<{e,a,b,c},*>。其中e是单位元。当四阶群含有一个四阶元素时，这个群就是循环群。当四阶群不含有四阶元素时，则由Lagrange定理的推论1可知，除单位元e外，a,b,c的阶一定都是2。练习8（续）a*b不可能等于a,b,e,否则将导致b=e,a=e或a=b的矛盾，所以a*b=c。同样可以证明b*a=c,a*c=c*a=b,b