计算机科学与技术是什么？ 计算机的体系结构，新一代计算机， 计算机语言能否简单化或者用自然语言？ 能否推出更方便实用的数据库系统 各种现有算法能否在时间和空间上得到新的改进 TCP/IP虽然应用广泛，但问题也不少，能否推出更好的协议？ 量子计算和量子计算机 这就是具有创新能力的计算机专业学生必须具备的能力和目标

计算学科的学生，建议有机会读下面2本书： ACM图灵奖——计算机发展史的缩影(第四版） IEEE计算机先驱奖——计算机科学与技术的发展史

图灵奖，是国际计算机协会（ACM）于1966年设立的，专门奖励对计算机事业作出重要贡献的个人。是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称。其名称取自计算机科学的先驱、英国科学家阿兰·图灵，这个奖设立目的之一是纪念这位科学家。获奖者的贡献必须是在计算机领域具有持久而重大的技术先进性的。一般每年只奖励一名计算机科学家，只有极少数年度有两名以上在同一方向上做出贡献的科学家同时获奖。目前图灵奖由英特尔公司赞助，奖金为250,000美元。 截止至2012年，获此殊荣的华人仅有一位，他是2000年图灵奖得主姚期智。

介绍了到2011年为止58位ACM图灵奖获得者的工作和事迹。通过对20世纪下半叶及21世纪初有代表性计算机科学家的介绍，多方位、多视角地反映计算机科学技术半个世纪来的发展历程。 在一定程度上反映了计算机体系结构、程序设计语言、算法设计与分析、操作系统和编译程序、数据库设计、计算复杂性理论、软件工程、人工智能、信息安全等计算机科学技术主要分支的形成过程和发展概况。

IEEE—CS的计算机先驱奖(Computer Pioneer Award)设立于1980年, 是世界范围内计算机科学技术领域另一个最重要的奖项,和图灵奖是互为补充的.这个奖项规定获奖者的成果必须是在15年以前完成的。这样一方面保证了获奖者的成果确实已经得到时间的考验，不会引起分歧；另一方面又保证了这个奖的得主是名符其实的“先驱”，是走在历史前面的人。 兼顾了理论与实践，设计与工程实现，硬件与软件，系统与部件。 该书介绍了到2000年为止108位获奖科学家的成就。

1. Email: 实验室: 2. 3.赵一鸣 BBS: zhym Email: zhym@fudan.edu.cn 每周三交作业

传统上，数学是以分析为中心的，在物理，化学，工程上应用的，也以分析为主。 计算机科学分支处理的数学对象与传统的分析有明显的区别： 以前分析研究的对象是连续的，因而微分，积分成为基本的运算； 计算机科学研究的对象是离散的，因而很少进行此类计算。称这些分支为“离散数学”。 以分析为中心的传统数学分支称为“连续数学”。

1) 集合论，数理逻辑。 整个数学的基础，也是计算机科学的基础。 2) 图论，算法图论；组合数学，组合算法。计算机科学，尤其是理论计算机科学的核心是算法，而大量的算法建立在图和组合的基础上。 3) 抽象代数。在计算机科学理论、系统工程、通信理论、计算机系统设计、编码理论、媒体计算和信息安全与密码学中有着广泛应用 为什么进制之间转换是正确的？ 就是代数系统的同构保证的

集合论 组合学 图论 代数结构 数理逻辑

新一代分组迭代加密算法——Rijndael 就 涉及求如(x6+x4+x2+x+1)关于模x8+x4+x3+x+1的逆

代数结构 19世纪以前,代数学的中心是讨论方程式，特别是方程式的求解问题——即一般的根表达式。 5次及以上方程式根的表达式无法找到 19世纪初法国数学家伽罗瓦(1811-1832)(死于决斗)在论文“方程式根式可解性条件”中证明一般5次方程式不存在用参数的加、减乘除、乘方、开方表示的求根公式。

把19世纪以后发展起来的以研究代数体系为内容的代数学称为近世代数， 代数体系是建立在抽象集合基础之上的，所研究的代数系统是抽象的故又称为抽象代数 主要是研究各种类型的代数运算系统，故也称为代数结构。

近世代数在数学和物理学上，而且在计算机学科中起着重要作用 它在计算机科学理论、系统工程、通信理论、计算机系统设计、编码理论和信息安全与密码学中有着广泛应用 代数结构的内容主要包括：群、环、域、格、泛代数 期中考试前：群、环、域 期中考试后：格、泛代数，数理逻辑 期中40％，期终40％，作业10％，小测验10％

参考书 近世代数 吴品三 人民教育出版社 代数结构与组合数学 曲婉玲 北京大学出版社 抽象代数 徐明耀 赵春来 北京大学出版社

第十二章 代数结构预备知识 §1 代数系统 一、运算 第十二章 代数结构预备知识 §1 代数系统 一、运算 设集合 S≠,f为一个SS的映射(本书第一部分又称为函数)。在代数系统中称为S上的一个一元运算。 S×SS的映射则称为S上的二元运算。 SnS的映射称为S上的n元运算。 封闭性

二、运算性质 结合律:任意a,b,cS有:a(bc)=(ab)c 交换律:任意a,bS有:a*b=b*a 实数集上的“加”、“乘”运算满足结合律和交换律，而“减”则不满足结合律和交换律。 n阶矩阵全体关于矩阵乘法满足结合律，但不满足交换律。

单位元(幺元):若S中存在元素e’,使对任意的aS有e’*a=a，称e’为S关于*的左单位元; 同理若有e”,使对任意a S有:a*e”=a，则称e”为S关于*的右单位元。 如果有eS, 使对任意aS有: a*e=e*a=a，则称e为S关于*的单位元。

定理(一)：(1)设*为S上的二元运算，若有左、右单位元el和er，则el=er。 证明: 逆元:对有单位元e的二元运算而言, 如果aS存在bS,使a*b=e,则称b为a的右逆元; 同理如果有cS使c*a=e,称c为a的左逆元 当a*b=b*a=e时,称b为a的逆元,表示成a-1 例:

定理（二）:当S上的二元运算*满足结合律,且a有逆元时,a的逆元是唯一的。 证明: 不满足结合律，逆元是否唯一？思考！ 定义：零元——如果有S, 使对任意aS有: a*=*a=，则称为S关于*的零元。类似可以定义左、右零元。 定理(三)：(1)设*为S上的二元运算，若有左、右零元l和r，则l=r。 (2)若S关于*的零元存在则必唯一。 证明自己思考。

在非负实数集P上定义如下运算“&”：a&b=(a+b)/(1+a*b)。其中“+,/,*”为普通加法、除法和乘法。

分配律:在集合S定义了2个二元运算与,当对任意 a,b,cS有: a(bc)=(ab)(ac),则称 关于满足左分配律, (bc)a=(ba)(ca)时, 称关于满足右分配律。 当关于同时满足左、右分配律时,称关于满足分配律。 例：Z上的“+”、“”运算， 结合律 交换律 单位元 零元 + √ √ 0 无  √ √ 1 0 0是“+”的单位元，是“”的零元。 “”关于“+”满足分配律。 a(b+c)=ab+ac

三、代数系统 定义：一个非空集合S,与一个或若干个定义在S上的运算Q1,…,Qk(k1),就构成了一个代数系统, 表示为 [S;Q1,…,Qk]。 例如,整数集合Z和整数的加法“+”运算, 就构成了一个代数系统[Z;+]。在此基础上再考虑整数的乘法“*”运算, 又得到另一个代数系统[Z;+,*]。 因为“-”不是N上的运算，所以[N;-]不是代数系统。 例:

在代数系统 [S;Q1,…,Qk]中称集合S为该系统的载集合, 简称载集。

§2 同态、同构与商系统 一、同态与同构 定义：设有两个代数系统[S;*]与[T;],其中*与均为二元运算。如果存在映射:ST,使得对任意的a,bS,有:(a*b)=(a)(b)，其中(a),(b)与(a*b)均为T中的元素。此时称为代数系统[S;*]到代数系统[T;]的一个同态映射。 同态象集(S)是T的一个子集。当(S)=T时,为满同态映射,称[S;*]与[T;]两个系统同态。

定理(四)：设两个代数系统[S;*]与[T;]同态,则有： (3)若[S;*]有单位元e，则[T;]也有单位元。 (4)若[S;*]有零元，则[T;]也有零元。 (5)设[S;*]的单位元为e，为[S;*]到[T;]的满同态映射。若对aS有逆元a-1,则在[T;]中， (a-1)为(a)的逆元。 证明(1)(3)其余自己思考. 证明:

两个同态的代数系统在运算性质上有很大的一致性，即在代数结构上有很大的一致性。 但两个同态的代数系统并不一定是完全一致的。 例: 为此引进同构的概念 定义:如果映射是代数系统[S;*]到[T;]的同态映射,当是一一对应时,称两个代数系统是同构的,就是它们的一个同构映射。

由于在同构中要求一一对应，这就意味着2个代数系统中集合的基数相同， 又由定理(四)知2个系统保持运算关系不变，这样2个代数系统在结构上就完全一致了，它们的不同只不过是元素与运算的表现形式不同而已。 两个同构的代数系统S与T就可看作“同一个”代数系统,并表示成[S;*][T;],简写成ST。

证明[S;*]与[T;]两个系统同态或同构,则要找到一个满同态或同构映射 证明[S;*]与[T;]两个系统不同态(不同构),则要证明所有S到T的映射都不是满同态(同构映射) 例1:证明[R;+]与[R+;]同构 例2:证明[Q;+]与[Q-{0};]不同构

二、商结构 [S;*]为代数系统 S的等价类全体用Š表示,即Š={[a]|aS}。这里[a]={x|a~x,xS} 对任意[a],[b]Š, [a][b]=[ab] 定义：设“~”为S上的等价关系，“*” 为S上的二元运算。若对任意a,b,c,dS，当a~b，c~d时，必有ac~bd，则称等价关系~与运算 是相容的，称~为代数系统[S;]的相容等价关系。

对任意[a],[b]Š, [a][b]=[ab]，则由~关于的相容性，保证运算的结果与等价类的选取无关。称[Š;]为 [S;]的商结构或商系统。 例:Z上模5同余关系 与代表元选取无关

作业: P149 1.(4)(5)这里都是模4同余, 2,3,4,7