为什么要研究代数系统.doc

、为什么要研究代数系统？答：代数是专门研究离散对象的数学，是对符号的操作。它是现代数学的三大支柱之一（另两个为分析与几何）。代数从19世纪以来有惊人的发展，带动了整个数学的现代化。随着信息时代的到来，计算机、信息都是数字（离散化）的，甚至电视机摄像机、照相机都在数字化。知识经济有人也称为数字经济。这一切的背后的科学基础，就是数学，尤其是专门研究离散对象的代数。代数发端于“用符号代替数”，后来发展到以符号代替各种事物。在一个非空集合上，确定了某些运算以及这些运算满足的规律，于是该非空集合中的元素就说是有了一种代数结构。现实世界中可以有许多具体的不相同的代数系统。但事实上，不同的代数系统可以有一些共同的性质。正因为此，我们要研究抽象的代数系统，并假设它具有某一类具体代数系统共同拥有的性质。任何在这个抽象系统中成立的结论，均可适用于那一类代数系统中的任何一个。2、代数的历史代数学历史悠久。代数的发展可分成两个阶段。19世纪这前的代数称为古典代数，19世纪至今的代数称为近世代数（抽象代数）。远在古希腊时期，人们就知道可以用符号代表所解问题中的未知数，并且这些符号可以像数一样进行运算，直到获得问题的解。古典代数的基本研究对象是方程，它是以讨论方程的解法为中心。在古典代数中，每一个符号代表的总是一个数，但这个数可以是整数也可以是实数。古典代数的主要目标是用代数运算解一元多次方程。它成功地解决了一元二次、一元三次和一元四次方程的求解问题。19世纪初，人们逐渐认识到，符号不仅可以代表数，而且可以代表任何事物。在这种思想认识的支配下，人们开始将任意集合上所进行的代数运算作为研究的对象，从而出现了近世代数体系和方法。19世纪30年代，在寻找一元五次方程根式求解方法的过程中，年青的法国数学家伽罗瓦(E. Galois)首次得出了群的概念用置换群的方法彻底证明了高于四次的代数方程的根式不可解性。起初他的奇思妙想和巧妙方法虽然并不被当时人接受和理解，却发展出了一门新的学科-抽象代数学。抽象代数学的研究对象是抽象的，它不是以某一具体事物为研究对象，而是以一大类具有共同性质的事物为研究对象。因此其研究成果适用于这一类事物中的每一个，从而收到事半功倍之效。抽象代数学的主要内容是研究各种各样的代数系统。它把一些形式上很不相同的代数系统，用统一的方法描述、研究和推理，从而得到反映出它们共性的一些本质的结论，然后再把这些结论应用到具体的代数系统中。从而抽象产生了广泛的应用。3、抽象代数学在计算机中的应用100多年来，随着科学的发展，抽象代数越来越显示出它在数学的各个分支、物理学、化学、力学、生物学等科学领域的重要作用。抽象代数的概念和方法也是研究计算科学的重要数学工具。有经验和成熟的计算科学家都知道，除了数理逻辑处，对计算科学最有用的数学分支学就是代数，特别是抽象代数。抽象代数是关于运算的学问，是关于计算规则的学问。在许多实际问题的研究中都离不开数学模型，而构造数学模型就要用到某种数学结构，而抽象世代数研究的中心问题就是一种很重要的数学结构-代数系统：半群、群、格与布尔代数等等。计算科学的研究也离不开抽象代数的应用：半群理论在自动机理论和形式语言中发挥了重要作用；有限域理论是编码理论的数学基础，在通讯中起过重要的作用；至于格和布尔代数则更不用说了，是电子线路设计、电子计算机硬件设计和通讯系统设的重要工具。另外描述机器可计算的函数、研究算术计算的复杂性、刻画抽象数据结构、描述作为程序设计基础的形式语义学，都需要抽象代数知识。4、布尔代数在逻辑线路中的应用19世纪50年代，只受过初级数学教育、自学成才的英国人乔治.布尔（George Boole）先后发表了逻辑之数学分析(The Mathematical Analysis of Logic)和思维规律(The Laws of Thought)这两部杰作。他创造出了一套符号系统，利用符号来表示逻辑中的各种概念。并且建立了一系列的运算法则，利用代数方法研究逻辑问题，初步奠定了数理逻辑的基础。布尔代数从此问世，数学史上树起了一座新的里程碑。布尔将逻辑推理过程简化成极为容易和简单的一种代数运算。他规定在布尔代数中：1)所有可能出现的数只有0和1两个；2)基本运算只有“与”、“或”、“非”三种；在布尔代数中用等式表示命题，把推理过程看作等式的变换。这种变换只依赖于基本运算的性质。在其诞生100多年后才发现其应用和价值。虽然在布尔代数刚刚问世的时间里并没有受到人们应有的重视，但布尔仍然坚信自己的研究会对后世有相当大的帮助。随着布尔的去世，人们对布尔代数的了解也越来越少，直到20世纪初罗素在自己的数学原理中重新提到了布尔代数的名称才引起了世人足够的关注。但是，此时距布尔去世早已相隔多年。对计算科学而言，布尔代数的重要性是不言而喻的。布尔代数也确实是在其诞生100多年后才在计算机的发展中找到了它的用武之地，它为电子数字计算机开关电路设计提供了最重要的数学方法。1938年，美国数学家、信息论创始人香农(C. Shannon)发表了著名的论文继电器和开关电路的符号分析(A Symbolic Analysis of Relay and Switching Circuits)，首次用布尔代数进行开关电路分析。由于布尔代数只有0和1两个值，恰好与二进制数对应，香农把它运用于以脉冲方式处理信息的继电器开关。并证明布尔代数的逻辑运算，可以通过继电器电路来实现，明确地给出了实现加、减、乘、除等运算的电子电路的设计方法，从而从理论到技术彻底改变了数字电路的设计方向。这篇论文成为开关电路理论的开端，在现代电子数字计算机史上具有划时代的意义。 香农在贝尔实验室工作中进一步证明，可以采用能实现布尔代数运算的继电器或电子元件来制造计算机。香农的理论还为计算机逻辑功能的设计奠定了基础，从而使电子计算机既能用于数值计算，又具有各种非数值应用功能，使得以后的计算机在几乎任何领域中，都得到广泛应用。今天，所有的电子计算机芯片里使用的成千上万个微小的逻辑部件，都是由各种布尔逻辑元件逻辑门和触发器组成的。由逻辑元件可以组成各种逻辑网络，这样任何复杂的逻辑关系都可以由逻辑元件经过相应的组合来实现，使其具有复杂的逻辑判断功能。5、半群与文法及形式语言计算机可以完成很多任务。但是给定一个任务，我们面临的第一个问题是：它是否可以用计算机来解决？若可以的话，我们就要考虑第二个问题：如何解决。这些问题的回答都和计算模型有关。一般有三种类型的计算模型：文法(Grammars)、有限状态机(Finite-state Machines)和图灵机(Turing Machines)。其中文法是用来生成一门语言的所有词汇和判断一个词汇是否在一门语言中。方法产生形式语言，而形式语言既为象英语这样的自然语言提供了模型，又为象PASCAL，C，PROLOG和JAVA这样的编程语言提供了模型。在编译原理和汇编程序的创造中，文法有着不可替代的作用。设是一个非空有限集合，称为字母表，由中有限个字母组成的有序集合（即字符串）称为上的一个字，串中的字母个数m称为字长，m=0时，称为空字，记为 。 表示上的字的集合， 上的连接运算 定义为， ， =，则是一个代数系统，而且是一个独异点。 的任一子集就称为语言。我们将利用文法来给定一门语言。一个文法给出了一个字母表（用来产生语言中词的符号集合），和一个产生词的规则集。一个文法是一个四元组G=（，T，s，P），其中是字母表，T是的子集，它的元素是终止符（它不能再被中其它字符代替），s是的一个元素，它是初始符，P是所谓生成规则的集合（生成规则实质上就是语言的短语构成规则，它们决定 中的一个字符串可以被 中的哪个符号串替换）。N=-T中的元素称为非终止符（它能被中其它字符代替），P中的每个产生式的左端至少要有一非终止符。定义了一门语言的文法后，利用产生式，我们就可以从初始符号s出发演绎出一个一个词，从而确定由该文法产生出来的语言。设G=（，T，s，P）是一个文法，则由G产生的语言L（G）就是能由初始符号s演绎出来的所有字符串的集合，即L（G）= T | s 。6、纠错码中的群码由于在计算机中和通讯系统中信号传递非常频繁与广泛，因此如何防止传输错误是一件很重要的事情。当然，要解决这个问题可以有不同的途径。其中的一个途径就是采用纠错码(Error Correcting Code)，即从编码上下功夫，使得二进制数码一旦在传递过程中出错，接收端的纠错码装置就能立即发现错误，并将其纠正。当二进制信号串从发送端发出时，需要按规定具有干扰能力的纠错码，然后才能发送出去。在接收端，当接收到二进制信号串后立即对收到的纠错码进行检查，检查是否失真，若失真则要负责纠正。这就是在计算机和数据通讯系统中被广泛采用的方法。我们先举一个日常生活中的实例。如果你发出一个通知：“明天14：00-16：00开会”，但在通知过程中由于某种原因产生了错误，变成“明天10：00-16：00开会”。别人收到这个错误通知后由于无法判断其正确与否，就会按这个错误时间去行动。为了使收者能判断正误，可以在发通知内容中增加“下午”两个字，即改为：“明天下午14:00-16:00开会”，这时，如果仍错为：“明天下午10:00-16:00开会”，则收到此通知后根据“下午”两字即可判断出其中“10:00”发生了错误。但仍不能纠正其错误，因为无法判断“10:00”错在何处，即无法判断原来到底是几点钟。这时，收者可以告诉发端再发一次通知，这就是检错重发。为了实现不但能判断正误(检错)，同时还能改正错误(纠错)，可以把发的通知内容再增加“两个小时”四个字，即改为：“明天下午14:0016:00两个小时开会”。这样，如果其中“14:00”错为“10:00”，不但能判断出错误，同时还能纠正错误，因为其中增加的“ 两个小时”四个字可以判断出正确的时间为14:0016:00”。 通过上例可以说明，为了能判断传送的信息是否有误，可以在传送时增加必要的附加判断数据；如果又能纠正错误，则需要增加更多的附加判断数据。这些附加数据在不发生误码的情况之下是完全多余的，但如果发生误码，即可利用被传信息数据与附加数据之间的特定关系来检出错误和纠正错误。具体地讲就是：为了使信源代码具有检错和纠错能力，应当按一定的规则在信源编码的基础上增加一些冗余码元(又称监督码)，使这些冗余码元与被传送信息码元之间建立一定的关系，发送端完成这个任务的过程就称为误码控制编码；在接收端，根据信息码元与监督码元的特定关系，实现检错或纠错，输出原信息码元，完成这个任务的过程就称误码控制译码(或解码)。 另外，无论检错和纠错，都有一定的误别范围，如上例中，若开会时间错为“16:0018:00”，则无法实现检错与纠错，因为这个时间也同样满足附加数据的约束条件，这就应当增加更多的附加数据(即冗余码元)。我们已知，信源编码的中心任务是消去冗余，可是为了检错与纠错，又不得不增加冗余，这又必然导致传输效率降低，显然这是个矛盾。我们分析误码控制编码的目的，正是为了寻求较好的编码方式，能在增加冗余不 太多的前提下来实现检错和纠错。设信息以字(Word)为单位进行传输，每个字是一个m二进制数，每个二进制位称为码元(Code Letter)。现在选择整数nm，构造一个一对一函数e:B B (其中B=0,1,B 是所有的m位二进制数集，B 是所有的n位二进制数集)。称e为(m,n)编码函数，通过它我们用一个n位二进制数代表一个m位二进制数。若b B ，则称e(b)是代表b的码字(code word)，e(b)中的冗余码元将有助于检出或纠正传输过程中产生的误码。在B 上定义二元运算 ：X= x x x , Y=y y y B ,Z= X Y=z z z ，其中z =x + y (k=1,2,n)(即 是n位二进制数的按位模2加法)。则（B ； ）是一个群，000是运算 *的单位元，每个元素的逆元是它本身（每个非单位元的阶是2）。同样（B ； ）也是一个群。若(m,n)编码函数e:B B 满足C=e(B )=e(b)|b B =Ran(e)是B 的子群，则称C一个群码(Group Code)。在计算机中经常使用的汉明码(Hamming Code)就是一种群码。它就利用群的性质实现纠错。7、布尔代数在开关电路设计中的应用开关是一种具有一个输入和一个输出的器件，我们将若干个开关的串联与并联构成的电路称为开关电路(Switching Circuits)。整个开关电路从功能上可看作是一个开关，把电路接通记为1，把电路断开记为0。而开关电路中的开关也要么处于接通状态，要么处于断开状态，这两种状态也可以用二值布尔代数来描述。一个具有n个独立开关组成的开关电路称为n元开关电路。整个开关电路是否接通完全取决于这些开关的状态以及连接方式（串联、并联或反