精华内容
下载资源
问答
  • 一、有限状态机 引子 让我们先来看几个简单的概念: 状态 - 系统的基本数学特征。 状态机 - 一个离散数学模型。给定一个输入集合,根据对输入的接受次序来决定一个输出集合。 有限状态机 - 输入...

    一、有限状态机

    引子

    让我们先来看几个简单的概念:

    状态        -  系统的基本数学特征。

    状态机      -  一个离散数学模型。给定一个输入集合,根据对输入的接受次序来决定一个输出集合。

    有限状态机  -  输入集合和输出集合都是有限的,并只有有限数目的状态。

    有限状态机的定义

    课本中的组合电路+时序电路的模型就是一个有限状态机,我们不妨通过它来推测有限状态机应有的组成:

    1. 状态有限集S={S0,S1,S2, ...... }。

    2. 集合S的特殊元素S0,即为起始状态。

    3. 输入字母有限集I={i1,i2, ...... }。

    4. 输出字母有限集O={o1,o2, ...... }。

    5. S×I映至S的函数f,即转换函数。

    6. S映至O的函数g,即为输出函数。

    前四个内容很容易理解,而f与g这两个函数由电路的设计决定,一般是时序电路(存储电路)部分决定f,组合电路部分决定g。

    具体模型可以用下面图示表示


    有限状态机的模型

    常用表示方法

    而对于计算理论或数学中的定义有限状态机M,有如下的五元组定义:有穷状态转换系统M = <S, A, h, S0, F>。

    其中S是M的有穷状态集,初始状态S0S,结束状态F⊆S;M总处在某个状态,开始时在S0;A是有穷符号集,h : S×A → S×(A ⋃ { _ }) 是转换函数(部分函数),_表示无输出,若M在状态S接到输入aA,假设h(S, a) = <S’, b>,(s'S, bA),M就转到状态S'并产生输出b。

    对比我们总结的模型,发现出现了终止状态(由于我们所学电路功能主要是实现计数、分频、输出序列波等持续性功能,所以没有接触到终止状态),这说明我们的模型基本反映了有限状态机的组成,但只是第二个定义无终止状态(即F为空集)的特例,下面我们的讨论就采用后面的经典定义。

     

    有限状态机示例

    有限状态机在现实生活中其实随处可见,伸缩式圆珠笔其实就是一个有限状态机(两种状态互相转换),下面我们用实现一个简单的有限状态机-自动门。

    要求如下:有一自动门,它可以被锁上,也可以开锁。当门锁上时,某人可以在它的槽中塞进一枚硬币。这样,门就会自动开锁,转变到开锁的状态;人通过后,门就会自动锁上。

    对状态进行分析可得下图

     

    仿真代码:

    LIBRARY IEEE;

    USE IEEE.std_logic_1164.ALL;

    ENTITY door_contr IS

    PORT (

         clk,reset,coin,pass:   IN  std_logic;

         door,alarm,thank:    OUT std_logic

    );

    END door_contr;

     

    ARCHITECTURE behavior OF door_contr IS

      TYPE states IS (lock,unlock);

      SIGNAL next_state: states;

      BEGIN

    PROCESS (clk)

      BEGIN

        IF (reset = '1') THEN

          next_state <= lock;

          alarm <= '0';

          thank <= '0';

          door <= '0';

        ELSIF (clk'EVENT AND clk = '1') THEN

          CASE next_state IS     

          WHEN lock =>

            IF (coin = '1') THEN

              next_state <= unlock;

              thank <= '0';

              alarm <= '0';

              door <= '1';

            ELSIF (pass = '1') THEN

              next_state <= lock ;

              thank <= '0';

              alarm <= '1';

              door <= '0';

            END IF;              

          WHEN unlock =>

            IF (coin = '1') THEN

              next_state <= unlock;

              thank <= '1';

              alarm<= '0';

              door <= '1';

            ELSIF (pass = '1') THEN

              next_state <= lock;

              thank <= '0';

              alarm <= '0';

              door <= '0';

            END IF;

          END CASE;

        END IF;

      END PROCESS;

    END behavior;

      

    QuartusⅡ下的仿真结果

    当然,上面讲述的还是一个没有停止状态的有限状态机,而且是由电子电路实现的,接下来的例子是在软件方面具有有限状态的有限状态机。

    这是一个地址识别的算法。日常我们描述地址(指中文)的语句中地址级别是依次降低的,国家、省(直辖市)、市、区县、街道、门牌号(或者从区县之后是乡、村)。而这些就是我们要构造的有限状态机的全部状态。这些状态构成的状态图是单向图,比如,当前的状态是“省”,如果遇到一个词组(即输入)和市名有关,我们就进入状态相应“市”(即状态转换);走到最低级的地址单位(即终止状态),那么这条地址是有效的,否则无效。比如说,“北京市海淀区清华大学紫荆公寓2#”对于上面的有限状态机来讲有效,而“上海市辽宁省石家庄市”则无效(因为无法从市走回到省,即便可以也会由于石家庄市不属于辽宁省而进入错误状态)。

    使用有限状态机识别地址,关键要解决两个问题,即通过一些有效的地址建立状态机,以及给定一个有限状态机后,地址字串的匹配算法,而这两个问题都有现成的算法。有了关于地址的有限状态机后,我们就可又用它分析网页,找出网页中的地址部分,建立本地搜索的数据库。同样,我们也可以在搜索引擎中对用户输入的查询进行分析,挑出其中描述地址的部分,当然,剩下的关键词就是用户要找的内容。

    以上就是有限状态机的实际应用,这让我们感到它的功能的确很强大。其实想想看,无论对连续系统还是离散系统,状态概念无所不在,有限状态机提供了一种描述和控制应用逻辑的非常强大的方法,具有规则简单、可读性和可验证性强等特点。

    有限状态机的弱点

    1、 每一种有限状态机均功能唯一,即设计好之后无法完成其他原理不同的工作;

    2、 因为其状态有限,当所要描述的系统的状态太多时,可能确定的有限状态机无能为力;

    3、 有一些任务是有限状态机无法完成的,比如它可以判断输入的0、1数列中0或1的个数是否为奇数或偶数,但是无法判断0是否比1多或者相反。

    前两个问题表示有限状态机的可扩展性差(或者对比计算机而言是无可编程性),而后者是因为有限状态机状态有限而且不能记下自己需要记录的东西(或者对比图灵机理论是不能写)。

    于是我们发现有限状态机不但状态有限,功能也有限(根据计算理论,这是因为它只能接受正则语言,而正则语言是最低级的语言,所以能够解决的问题是有限的)。

    事实上,最初的计算“机”(其实更应该说是计算器)都是功能单一的,虽然人们不断地试图在一台机器上集成更多的功能,但是相对于下面要讲到通用计算理论,这些行为还是“盲目”的。

     

    二、图灵机

    图灵机理论的提出及相关理论:

    下面我们的主人公将是图灵,也许你现在对他一无所知,但阅读这一节后,你需要深刻的记住他,因为在我看来,是他启发与影响了他之后的整个计算机发展史。为了让大家更好地理解与接受他的理论,我会多穿插一些背景,毕竟天才也不是生活在真空中的。

    图灵早年在剑桥大学求学,在那个年代,剑桥大学的大数学家罗素和怀特海已经创立了“数理逻辑学”。“数理逻辑”这个学科的创建,起源于一个逻辑上的“悖论”。为了非专业人士都能明白逻辑悖论的含义,哲学家或者数学家喜欢用讲故事的办法来解释它。一个经典的故事是:村子里有位理发师,他为而且只为村子里所有那些不给自己理发的人理发。数学的逻辑推理上会出现类似的悖论。数学家们十分担心“数学大厦”会因悖论的存在而坍塌,于是他们都想方设法去修补数学基础。例如,康托发表专著《集合论》,罗素与怀特海联合撰写三卷《数学原理》。

           剑桥大学是“数理逻辑学”的发源地与大本营,一群聪明而勤奋的青年数学家聚集在数学泰斗罗素教授的周围,图灵是其中的佼佼者。1935年,刚刚毕业,年仅23岁的图灵就被剑桥大学国王学院甄选为研究员,成为剑桥大学有史以来最年轻的研究员。正是图灵在数学,尤其是在“数理逻辑学”方面的深厚功底,令他几年后终于厚积薄发,一举奠定了他计算机科学的创始人的地位。

           图灵先知先觉,在电子计算机远未问世之前,他已经想到所谓“可计算性”的问题。物理学家阿基米得曾宣称:“给我足够长的杠杆和一个支点,我就能撬动地球。”类似的问题是,数学上的某些计算问题,是不是只要给数学家足够长的时间,就能够通过“有限次”的简单而机械的演算步骤而得到最终答案呢?这就是所谓“可计算性”问题,一个必须在理论上做出解释的数学难题。

           经过智慧与深邃的思索,图灵以人们想不到的方式,回答了这个既是数学又是哲学的艰深问题。1936年,图灵在伦敦权威的数学杂志上发表了一篇划时代的重要论文《可计算数字及其在判断性问题中的应用》。文章里,图灵超出了一般数学家的思维范畴,完全抛开数学上定义新概念的传统方式,独辟蹊径,构造出一台完全属于想象中的“计算机”,数学家们把它称为“图灵机”。这样的奇思妙想只能属于思维像“袋鼠般地跳跃”的图灵。

           “图灵机”想象使用一条无限长度的纸带子,带子上划分成许多格子。如果格里画条线,就代表“1”;空白的格子,则代表“0”。想象这个“计算机”还具有读写功能:既可以从带子上读出信息,也可以往带子上写信息。计算机仅有的运算功能是:每把纸带子向前移动一格,就把“1”变成“0”,或者把“0”变成“1”。“0”和“1”代表着在解决某个特定数学问题中的运算步骤。“图灵机”能够识别运算过程中每一步,并且能够按部就班地执行一系列的运算,直到获得最终答案。

           “图灵机”是一个虚拟的“计算机”,完全忽略硬件状态,考虑的焦点是逻辑结构。图灵在他那篇著名的文章里,还进一步设计出被人们称为“通用图灵机”的模型,它可以模拟其他任何一台解决某个特定数学问题的“图灵机”的工作状态。他甚至还想象在带子上存储数据和程序。“通用图灵机”实际上就是现代通用计算机的最原始的模型。

    不过图灵在提出图灵机构想之后,又发现了新问题,有些问题图灵机是无法计算的。比如定义模糊的问题,如“人生有何意义”,或者缺乏数据的问题,“明天3D中奖号是多少”,其答案当然是无法计算出来的。但也有一些定义完美的计算问题,它们亦是不可解的,这类问题称为不可计算问题。

    不可计算的问题在实践中几乎碰不到,事实上,很难找到这样的例子,既不可计算但又有人向计算的明确定义的问题。一个罕见的问题是所谓的停机问题。设想要编写一个用于检查并判定另一个程序是否会运行结束的程序,而事实上,不存在一个程序能够判断另一个程序是否与无限循环有染。我们可以来这样设想:假定我们有一个Test程序,此程序把别的测试程序当成输入,我们把它插入另一个程序Paradox(悖论)中,并在Test中使用Paradox函数作为参数(即Paradox() { … ;Test(Paradox);…})。这个Paradox函数的编写思路是这样的,如果Test程序判断Paradox会运行结束,那么Paradox就进入无限循环,如果Test判断Paradox不会结束,则Paradox函数立刻终止。于是Test函数对Paradox函数无效,所以判断函数是否会终止的程序不存在。

    计算机不能解一些问题并不是计算机的弱点,因为停机问题本质上是不可解的,不可能建造出一个解停机问题的机器。通用计算机无法完成的计算,无论什么东西同样无法胜任。

     

    图灵机的定义与举例:

    接下来我们给出图灵机模型的一个严格的形式定义:

    一个图灵机是一个七元组(Q,∑,σ,δ,q0,qaccept,qreject),其中Q,∑,σ都是有穷集合。

    Q是状态集;

    ∑是输入字母表,不包括特殊空白符号;

    σ是带字母表,其中包括∑与空白符号;

    δ:Q×σ→Q×σ×(L,R)是转移函数;

    q0∈Q是起始状态;

    qaccept∈Q是接收状态;

    qreject∈Q是拒绝状态;

    下面是图灵机的图示:

     

    从上述形式定义可以看出模型的关键在于有穷控制器中的状态转换函数,根据图灵的通用计算理论,这个转换函数是灵活可变的(对应于通用图灵机),当然也可以使单一的(对应于专用图灵机,即便如此,它的能力也强于有限状态机,因为图灵机是可以接受0级语言的),不过这并非图灵提出图灵机的意义所在。

    下面我们来比较有限状态机与通用图灵机的区别所在:

    1、 图灵机既能读又能写;

    2、 带子是无限长的(可以无限存储,结合读写头既能左移又能右移的特点,当然就可以解决判断输入的0与1个数谁多的问题),而且带子上不但可以写入数据,还可以写入实现某一具体功能的;

    3、 进入拒绝和接收状态立即停机;

    同有限状态机一样,我们构造一个图灵机来实现一个简单的功能。

    目标:利用二进制来设计一个专门计算“x+1”的图灵机,要求计算完成时,读写头要回归原位。

    状态集合K:

    {start,add,carry,noncarry,overflow,return,halt};

    字母表∑:{0,1,*};

    初始状态s:start;

    停机状态集合H:{halt};

     

    规则集合δ:

     

    实现步骤:

    ----------------------------------------------------------------

    ----------------------------------------------------------------

    ----------------------------------------------------------------

    从这个过程中我们发现,虽然图灵机可以实现x+1的功能,但是他的工作流程理解起来并不是人们日常的计算过程,甚至与现代计算机的计算原理也并无太大相关。这是因为与现代计算机相比,它的计算方式也还是有局限性,由于图灵机每次只能读入一个数据,改写所读入的数据,而不像现代计算机可以同时读入多个数据、改写其他数据,所以相应的算法难理解性也就增加。

     

    图灵机的意义与思想内涵:

    图灵提出图灵机的模型并不是为了同时给出计算机的设计,它的意义我认为有如下几点:

    1、      它证明了通用计算理论,肯定了计算机实现的可能性,同时它给出了计算机应有的主要架构

    2、      图灵机模型引入了读写与算法与程序语言的概念,极大的突破了过去的计算机器的设计理念;

    3、      图灵机模型理论是计算学科最核心的理论,因为计算机的极限计算能力就是通用图灵机的计算能力,很多问题可以转化到图灵机这个简单的模型来考虑。

    对图灵机给出如此高的评价并不是高估,因为从它的设计与运行中,我们可以看到其中蕴涵的很深邃的思想。

    通用图灵机等于向我们展示这样一个过程:程序和其输入可以先保存到存储带上,图灵机就按程序一步一步运行直到给出结果,结果也保存在存储带上。

    另外,我们可以隐约看到现代计算机主要构成(其实就是冯诺依曼理论的主要构成),存储器(相当于存储带),中央处理器(控制器及其状态,并且其字母表可以仅有0和1两个符号),IO系统(相当于存储带的预先输入);

     

    伟大的图灵:

    正是在图灵搭建的理论基础之上,计算机才有了后来的蓬勃发展。美国的阿坦纳索夫在1939年果然研究制造了世界上的第一台电子计算机ABC,其中采用了二进位制,电路的开与合分别代表数字0与1,运用电子管和电路执行逻辑运算等。ABC是“图灵机”的第一个硬件实现。冯·诺依曼不仅在上个世纪40年代研制成功了功能更好、用途更为广泛的电子计算机,并且为计算机设计了编码程序,还实现了运用纸带存储与输入。至此,天才图灵在1936年发表的科学预见和构思得以完全实现。

    明白了图灵那无与伦比的贡献,人们就不难理解,何以冯·诺依曼对于“计算机之父”的桂冠坚辞不受。曾经担任过冯·诺依曼研究助手的美国物理学家弗兰克尔教授这样写道:“许多人都推举冯·诺依曼为“计算机之父”,然而我确信他本人从来不会促成这个错误。或许,他可以被恰当地称为‘计算机的助产士’。依我之见,正是冯·诺依曼使世界认识了由图灵引入的计算机的基本概念。”弗兰克尔教授此言不虚,在1949年,冯·诺依曼发表了一篇题为《自动计算机的一般逻辑理论》的论文,客观而公正地阐述了图灵在计算机理论上的重大贡献。他写道:“大约12年前,英国逻辑学家图灵就开始研究‘可计算问题’,他准确地给出了‘自动计算机’的一般性定义。”冯·诺依曼宁愿把“计算机之父”的桂冠转戴在图灵头上。当然,这已经是在图灵离开普林斯顿十来年以后的事了,他当年在普林斯顿并没有像后来那样受人景仰。图灵曲高和寡,当年就能看明白他那篇文章划时代意义的,仅仅是少数杰出的数学家,如冯·诺依曼者。

     

    三、构建现代计算机

    整理我们的理论基础:

    从人类科技发展的历史来看,当理论成熟或即将成熟之日,也就是人们开始着手实现之时(虽然在理论创立之前也会有人尝试,但还是那句评价,“盲目”)理论指导实践就是这个道理。下面我们就沿着有限状态机、图灵机的这条思路,将自己置身于二十世纪中叶,联系当时的技术能力,来构建出一台我们自己的计算机。

     图灵理论的一个基本要求是所有信息都可用符号编码,包括图灵机本身(相当于对图灵机自身功能的描述)。编码方式使我们首先要考虑的,这主要取决于编码集的元素个数与编码元素之间的关系。在图灵机的实现中我们可以看到图灵采用的是0、1编码,当然,乍看上去我们可能会觉得不太可能,难道我们平时接触的复杂而又多样的种种事物都可以用简单的0、1表示么?就算是表示了出来又通过方式进行运算得到我们想要的结果呢?这些其实都不是我们需要考虑的,因为这些已经被解决,而完成这项工作的人就是乔治·布尔,19世纪的英国逻辑学家,他将人类的逻辑思维简化为一些数学运算,还发明了一种语言用于描写与处理各种逻辑命题和确定其真假与否,这种语言被称作逻辑代数,同图灵机的构想一样,在当时布尔并不认为是在为计算机的发展做出贡献,虽然事后证明的确意义重大。完成将布尔代数引入计算机科学领域的是克劳德·香农,他创立了信息论,并在其中定义了我们称之为“二进制位”的信息度量。采用二进制主要基于以下原因: 
     (1)技术实现简单:当然这与我们后面要讲到的内容有关(最终我们的计算机要由逻辑电路组成,逻辑电路通常只有两个状态,开关的接通与断开,这两种状态正好可以用“1”和“0”表示。  
     (2)简化运算规则:两个二进制数和、积运算组合各有三种,(求和法则3个:0+0=0 , 0+1=1+0=1, 1+1=10;求积法则3个:0×0=0,0×1=1×0=0, 1×1=1)运算规则简单,有利于简化计算机内部结构,提高运算速度。  
     (3)适合逻辑运算:逻辑代数是逻辑运算的理论依据,二进制只有两个数码,正好与布尔代数中的“真”和“假”相吻合。  
     (4)易于进行转换,二进制与十进制数易于互相转换。  
     (5)用二进制表示数据具有抗干扰能力强,可靠性高等优点。 

     

    随后我们遇到的问题是如何将我们想要表达的问题转化为0、1代码,当然,不同的问题经过不同人的处理会有不同的逻辑表示,关键是要保证计算机明白你要表达的真实意思,而这只要你在表示的同时给出一个编码原则。这里最本质的概念是信息,哲学家格雷戈里·贝特森将信息定义为“生异之异(the difference that makes a difference)”,换句话说,信息是一种差异性、可能性,同时它又有影响其它信息的能力,这样看来信息是完全可以用二进制位来表出的。例如,当你和别人谈话时,说的每个字都是字典中所有字中的一个。如果给字典中所有的字从1开始编号,我们就可能精确地使用数字进行交谈,而不使用单词(当然,对话的两个人都需要一本已经给每个字编过号的字典以及足够的耐心) ,人与计算机的交谈也是这个道理。

     

    初步实现计算机:

    那么接下来我们就要考虑如何通过现有(二十世纪中叶)的技术来实现一个二进制系统,是的我们想要实现的运算在里面流动(进行),并最终流出。先不要着急,我们先来看一下前人的研究成果,

    早在17世纪,欧洲一批数学家就已开始设计和制造以数字形式进行基本运算的数字计算机。1642年,法国数学家帕斯卡采用与钟表类似的齿轮传动装置,制成了最早的十进制加法器。1678年,德国数学家莱布尼兹制成的计算机,进一步解决了十进制数的乘、除运算。1834年,英国数学家巴贝奇在研制差分机的工作中,看到了制造一种新的、在性能上大大超过差分机的计算机的可能性。他把这个未来的机器称为分析机。巴贝奇的分析机由三部分构成。第一部分是保存数据的齿轮式寄存器,巴贝奇把它称为“堆栈”,它与差分机中的相类似,但运算不在寄存器内进行,而是由新的机构来实现。第二部分是对数据进行各种运算的装置,巴贝奇把它命名为“工场”。第三部分是对操作顺序进行控制,并对所要处理的数据及输出结果加以选择的装置。为了加快运算的速度,巴贝奇设计了先进的进位机构。他估计使用分析机完成一次50位数的加减只要1秒钟,相乘则要1分钟。计算时间约为第一台电子计算机的100倍。同时,在多年的研究制造实践中,巴贝奇写出了世界上第一部关于计算机程序的专著。

    这台分析机虽然已经描绘出有关程序控制方式计算机的雏型,但限于当时的技术条件而未能实现。

    我们不难总结出这几点:

    1、   先前的计算机大多是专用的,机械式的;

    2、   巴贝奇提出了通用机,并具有程序存储控制的思想雏形;

    3、   巴贝奇的设想在当时的技术条件下,即机械机的条件下是很难实现的。

    此外,在那时,有人制造过模拟机器,即不是用我们已经认同的离散数字信号做处理。我们在介绍采用0、1编码时,并没有明确排除模拟信号计算的可能性,事实上,这确实是可能的,不过现在我们来解释一下我们之所以不那样做的原因。

    在物理世界中,完全意义上的连续流是无法做到的,模拟计算机的问题是其信号只能达到有限的精度。一种模拟信号-无论是电气信号、机械信号或化学信号-都会包含一定程度的噪音,即到某一级分辨率上,信号基本上是随机的。任何模拟信号,必然受到大量无关的、未明噪音源的影响。如果信号中有百万分之一的噪音,那么,杜宇信号来说,只有一百万中有意义的差异。既然如此,那信号中的信息大可用一个20个二进制位组成的十进制信号来表示(220=1048578)。在一个模拟计算机中,是有意义的差异的个数再翻一番,需要使其中每样东西的精度提高一倍,而在数字计算机中,只需增加一个二进制位便可,其实最好的模拟计算机的精度不到30个二进制位。

    那好,现在我们可以充满信心的使用离散数字信号,也应当把目光从机械机上移开,机械及由于其在速度、规模、稳定性、精确度上的缺陷,无法成为我们所要设计的机器的有效载体。再强调一遍,我们处在20世纪中叶,这时候电工学、电子学不断取得重大进展,在元件、器件方面接连发明了真空二极管和真空三极管;在系统技术方面,相继发明了无线电报、电视和雷达。所有这些成就为现代计算机的发展准备了技术和物质条件。相对于机械机而言,电路可以有更高的工作频率(意味着计算速度更快)、更小的规模、更稳定、更加精确(高低电平表示不同状态),而且在存储方面它相对于机械机有更大的优势(而这也是我们的主要需求),所以我们把目标放在电子电路实现上。

    我们已经知道了用0、1表示信息,也想好了用电路的高低电平表示0、1,那么下一步就是如何进行信息存储与简单运算(写到这里可以发现,跟数字电子技术课程的流程是一样的)。

    来看两个比较重要的事件:1904年,John A.Fleming 取得真空二极管的专利权;1947年,英国完成了第一个存储真空管。看来我们可以使用它们的,除了这些东西之外,我们还有一些器件是可以使用的,比如存储器件中,可以的选择有水银延迟线存储器、阴极射线示波管静电存储器、磁鼓和磁心存储器等,好了,有了这些硬件之后,我们就可以专心于电路逻辑上的设计了。

    最初的时候肯定是没有组合电路逻辑电路之分的,更没有《数字电子技术》这本书,可是我们还是根据逻辑式的推导与构想,掌握一些基本电路的设计方法的(注意,不是电路设计的基本方法),我觉得一项新技术或新产品的往往是这样:人们大概有一个方向,抽象出一定的模块与功能,然后一点一点的加以实现,起初人们掌握的是最基础的知识,在实现的过程中,他们要通过摸索去搭配与做修改,与此同时,他们慢慢积累总结出一般方法,最终形成成熟的工艺流程。比如,设计电路的过程中,我们会发现一些区别,有的电路只与当前输入有关,而另一些电路还与过去的输入有关,当然我们可以总结出组合电路与时序电路概念与设计上的区别来。就是这样一点一点,我们可以设计出符合简单运算要求的逻辑电路来,当然这里还是涉及一些理论的东西的,那就是要设计出多少什么功能的基本运算单元才能保证把任何问题分解成的子运算都属于我们的基本运算单元集。这个问题现在(二十一世纪)的争议是要构建简单指令集还是复杂指令集,而且不同种CPU它们的指令集是不同的,这的确是一个复杂的问题,但是我们在二十世纪中叶的时候主要目的还是科学计算与军事应用,需要的指令应该也还不多吧,所以这个问题我们就跳过了。

    最后就是真正的对照设计方案连接我们的计算机了,电子管组成的运算电路、各种器件组成的存储器通过导线的连接(当然,运算电路、存储电路、IO输入的架构还是一个很不容易产生但很伟大的想法的,虽然它在图灵机中已经有所体现。我们在这里把它忽略掉,下面将有介绍),终于可以使用了!

    我们的设计历程到此成功结束,但是我们还是忽略了细节,而且我们还是以自己现在的思维,做出了一些自认为显然的判断与设计,我们还是有必要翻开历史,回顾一下计算机真实的发展历程,虽然有时候看起来笨拙而可笑,但应当说它们都是自身所处时代的最优解,现在的计算机绝不是一蹴而就的,况且,我们现在的计算机也许就是未来人眼中的ENIAC。

     

    计算机真实的发展历史:

        第一代电子管计算机(1945-1956)

        在第二次世界大战中,美国政府寻求计算机以开发潜在的战略价值。这促进了计算机的研究与发展。1944年Howard H. Aiken(1900-1973)研制出全电子计算器,为美国海军绘制弹道图。这台简称 Mark I 的机器有半个足球场大,内含500英里的电线,使用电磁信号来移动机械部件,速度很慢(3-5秒一次计算)并且适应性很差只用于专门领域,但是,它既可以执行基本算术运算也可以运算复杂的等式。

      1946年2月14日,标志现代计算机诞生的ENIAC(Electronic Numerical Integrator and Computer)在费城公诸于世。ENIAC代表了计算机发展史上的里程碑,它通过不同部分之间的重新接线编程,还拥有并行计算能力。ENIAC由美国政府和宾夕法尼亚大学合作开发,使用了18,000个电子管,70,000个电阻器,有5百万个焊接点,耗电160千瓦,其运算速度比Mark I快1000倍,ENIAC是第一台普通用途计算机。

    重大突破是由数学家冯·诺伊曼领导的设计小组完成的。1945年3月他们发表了一个全新的存储程序式通用电子计算机方案—电子离散变量自动计算机(EDVAC),主要设计原则是:

        (1)使用单一的处理部件来完成计算、存储以及通信的工作;

        (2)存储单元是定长的线性组织;

        (3)存储空间的单元是直接寻址的;

        (4)使用机器语言,指令通过操作码来完成简单的操作;

        (5)对计算进行集中的顺序控制。

        随后于1946年6月,冯·诺伊曼等人提出了更为完善的设计报告《电子计算机装置逻辑结构初探》。同年7~8月间,他们又在莫尔学院为美国和英国二十多个机构的专家讲授了专门课程《电子计算机设计的理论和技术》,推动了存储程序式计算机的设计与制造。

    第一代计算机的特点是操作指令是为特定任务而编制的,每种机器有各自不同的机器语言,功能受到限制,速度也慢。

    第二代晶体管计算机(1956-1963)

    1948年,晶体管的发明大大促进了计算机的发展,晶体管代替了体积庞大电子管,电子设备的体积不断减小。1956年,晶体管在计算机中使用,晶体管和磁芯存储器导致了第二代计算机的产生。第二代计算机体积小、速度快、功耗低、性能更稳定。首先使用晶体管技术的是早期的超级计算机,主要用于原子科学的大量数据处理,这些机器价格昂贵,生产数量极少。

    1960年,出现了一些成功地用在商业领域、大学和政府部门的第二代计算机。第二代计算机用晶体管代替电子管,还有现代计算机的一些部件:打印机、磁带、磁盘、内存、操作系统等。计算机中存储的程序使得计算机有很好的适应性,可以更有效地用于商业用途。在这一时期出现了更高级的 COBOL(Common Business-Oriented Language)和FORTRAN(Formula Translator)等语言,以单词、语句和数学公式代替了含混晦涩的二进制机器码,使计算机编程更容易。新的职业(程序员、分析员和计算机系统专家) 和整个软件产业由此诞生。

    第三代集成电路计算机(1964-1971)

    虽然晶体管比起电子管是一个明显的进步,但晶体管还是产生大量的热量,这会损害计算机内部的敏感部分。1958年德州仪器的工程师Jack Kilby发明了集成电路(IC),将三种电子元件结合到一片小小的硅片上。科学家使更多的元件集成到单一的半导体芯片上。于是,计算机变得更小,功耗更低,速度更快。这一时期的发展还包括使用了操作系统,使得计算机在中心程序的控制协调下可以同时运行许多不同的程序。

    第四代大规模集成电路计算机(1971-现在)

    出现集成电路后,唯一的发展方向是扩大规模。大规模集成电路(LSI)可以在一个芯片上容纳几百个元件。到了80年代,超大规模集成电路 (VLSI)在芯片上容纳了几十万个元件,后来的(ULSI)将数字扩充到百万级。可以在硬币大小的芯片上容纳如此数量的元件使得计算机的体积和价格不断下降,而功能和可靠性不断增强。

    70年代中期,计算机制造商开始将计算机带给普通消费者,这时的小型机带有友好界面的软件包,供非专业人员使用的程序和最受欢迎的字处理和电子表格程序。这一领域的先锋有Commodore, Radio Shack和Apple Computers等。

    1981年,IBM推出个人计算机(PC)用于家庭、办公室和学校。80年代个人计算机的竞争使得价格不断下跌,微机的拥有量不断增加,计算机继续缩小体积,从桌上到膝上到掌上。与IBM PC竞争的Apple Macintosh系列于1984年推出,Macintosh提供了友好的图形界面,用户可以用鼠标方便地操作。

    下面的图片展示的是这整个发展历程的一小部分。

    “现代计算机创始人”查尔斯·巴贝奇的分析仪复制品,该分析仪是用于公式演算的多功能计算机,不过这台计算机在他有生之年始终未能问世。

    美国人哈雷里斯利用卡片穿孔,开发了卡片制表系统,这一系统被认为是现代计算机的雏形。1911年,哈雷里斯将这项专利卖给了另外一家公司,13年后这家公司更名为国际商业机器公司,也就是现在的IBM。

     

    ENIAC-世界上第一台现代电子计算机(局部图)

    磁鼓数字微分分析器

    IBM 1956年发行的光盘,图中的最大的光盘是上世纪70年代早期制造的

    Intel 4004

     

     

    Intel 8080

     电子管

     

     晶体管

     

    集成电路

    超大规模集成电路

     

    新一代计算机:

    历经这所有的发展,才有了计算机现在的高性能与广泛应用。不过,虽然计算机芯片的集成度越来越高,元件越做越小,然而由于量子效应的存在,集成电路技术现在正逼近其极限(0.2nm的工艺),科学家们看到传统的计算机结构必将有终结的一天,而且尽管计算机的运行速度与日俱增,但是有一些难题是计算机根本无法解决的,例如大数的因式分解,理论上只要一个数足够大,这个难题够目前最快的计算机忙几亿年的。事实上,计算机从真空管、晶体管、集成电路、超大规模集成电路一路走来,从计算方式的本质来看是没有发生任何改变的,我们一直沿着“电子”计算机的道路行走,而没有在其它采用不同方式进行计算的计算机上有太多考虑,不过这种状况已经开始有所转变,因为量子计算机、光子计算机、生物计算机已经开始为我们所熟知。下面,我们就介绍一下这些“非电子”计算机,从中我们可以发现,计算机科学确实是现代先进科学技术理论的交汇点。

    量子计算机 

    进入20世纪90年代,实验技术和理论模型的进步为量子计算机的实现提供了可能。尤其值得一提的是1994年美国贝尔实验室的Peter W. Shor证明运用量子计算机竟然能有效地进行大数的因式分解。这意味着以大数因式分解算法为依据的电子银行网络等领域的RSA公开密钥密码体系在量子计算机面前不堪一击。于是各国政府纷纷投入大量的资金和科研力量进行量子计算机的研究,如今这一领域已经形成一门新型学科-量子信息学。

    量子计算机具有特大威力的根本原因在于构成量子计算机的基本单元-量子比特(q-bit),它具有奇妙的性质,而这种性质必须用量子力学来解释,因此称为量子特性。我们现在所使用的计算机采用二进制来进行数据的存储和运算,在任何时刻一个存储器位代表0或1。而量子比特是由量子态相干叠加而成,一个具有两种状态的系统可以看作是一个“二进制”的量子比特。在量子世界里物质的状态是捉摸不定的,如电子的位置可以在这里同时也可以在那里,原子的能级在某一时刻可以处于激发态,同时也可以处于基态。我们就采用有两个能级的原子来做量子计算机的q-bit。规定原子在基态时记为 |0〉,在激发态时原子的状态记为 |1〉,而原子具体处于哪个态我们可以通过辨别原子光谱得以了解。微观世界的奇妙之处在于,原子除了保持上述两种状态之外,还可以处于两种态的线性叠加,记为 |φ〉=a |1〉+ b |0〉 ,其中a,b分别代表原子处于两种态的几率幅。如此一来,这样的一个q-bit不仅可以表示单独的“0”和“1”(a=0时只有“0”态,b=0时只有“1”态),而且可以同时既表示“0”,又表示“1”(a,b都不为0时)。举一个简单的例子,假如有一个由三个比特构成的存储器,如果是由经典比特构成则能表示000,001,010,011,100,101,110,111这8 个二进制数,即0~7这8个十进制数,但同一时刻只能表示其中的一个数。若此存储器是由量子比特构成,如果三个比特都只处于 |0〉或 |1〉则能表示与经典比特一样的存储器,但是量子比特还可以处于 |0〉与 |1〉的叠加态,假设三个q-bit每一个都是处于( |0〉+ |1〉) / (√2) 态,那么它们组成的量子存储器将表示一个新的状态,用量子力学的符号,可记做:

    |0〉|0〉|0〉+ |0〉|0〉|1〉+ |0〉|1〉|0〉+ |0〉|1〉|1〉+ |1〉|0〉|0〉+ |1〉|0〉|1〉+ |1〉|1〉|0〉+ |1〉|1〉|1〉

     

    不难看出,上面这个公式表示8种状态的叠加,既在某一时刻一个量子存储器可以表示8个数。 接下来看看量子计算机如何对这些态进行运算。假设现在我们想求一个函数f(n),(n=0~7)的值,采用经典计算的办法至少需要下面的步骤:

    存储器清零→赋值运算→保存结果→再赋值运算→再保存结果……

    对每一个n都必须经过存储器的赋值和函数f(n)的运算等步骤,而且至少需要8个存储器来保存结果。如果是用量子计算机来做这个题目则在原理上要简洁的多,只需用一个量子存储器,把各q-bit制备到( |0〉+ |1〉) / (√2)态上就一次性完成了对8个数的赋值,此时存储器成为态 |φ〉,然后对其进行相应的幺正变换以完成函数f(n)的功能,变换后的存储器内就保存了所需的8个结果。这种能同时对多个态进行操纵,所谓“量子并行计算”的性质正是量子计算机巨大威力的奥秘所在。

    我们怎么把所需要的数据从8个或更多个结果中挑选出来呢?对具体的问题这就要要采用相应的量子算法,例如Shor提出的大数因式分解算法。按照Shor算法,对一个1000位的数进行因式分解只需几分之一秒,同样的事情由目前最快的计算机来做,则需1025年!而Grover的搜索算法则被形象地称为“从稻草堆中找出一根针”!尽管量子算法已经很多了,但是到目前为止真正的量子计算机才只做到5个q-bit,只能做很简单的验证性实验,但是我们有理由期待它的光明前景。

     

    光子计算机

    1990年初,美国贝尔实验室制成世界上第一台光子计算机。

    现有的计算机是由电子来传递和处理信息。电场在导线中传播的速度虽然比我们看到的任何运载工具运动的速度都快,但是,从发展高速率计算机来说,采用电子做输运信息载体还不能满足快的要求,提高计算机运算速度也明显表现出能力有限了。而光子计算机以光子作为传递信息的载体,光互连代替导线互连,以光硬件代替电子硬件,以光 运算代替电运算,利用激光来传送信号,并由光导纤维与各种光学元件等构成集成光路,从而进行数据运算、传输和存储。在光子计算机中,不同波长、频率、偏振态及相位的光代表不同的数据,这远胜于电子计算机中通过电子“0”、“1”状态变化进行的二进制运算,可以对复杂度高、计算量大的任务实现快速的并行处理。光子计算机将使运算速度在目前基础上呈指数上升。

    由于光子比电子速度快,光子计算机的运行速度可高达一万亿次。它的存贮量是现代计算机的几万倍,还可以对语言、图形和手势进行识别与合成。

    光子计算机与电子计算机相比,主要具有以下优点:

    (1) 超高速的运算速度。光子计算机并行处理能力强,因而具有更高的运算速度。电子的传播速度是593km/s,而光子的传播速度却达3×10 5km/s,对于电子计算机来说,电子是信息的载体,它只能通过一些相互绝缘的导线来传导,即使在最佳的情况下,电子在固体中的运行速度也远远不如光速,尽管目前的电子计算机运算速度不断提高,但它的能力极限还是有限的;此外,随着装配密度的不断提高,会使导体之间的电磁作用不断增强,散发的热量也在逐渐增加,从而制约了电子计算机的运行速度;而光子计算机的运行速度要比电子计算机快得多,对使用环境条件的要求也比电子计算机低得多。

    (2) 超大规模的信息存储容量。与电子计算机相比,光子计算机具有超大规模的信息存储容 量。光子计算机具有极为理想的光辐射源——激光器,光子的传导是可以不需要导线的,而且即使在相交的情况下,它们之间也不会产生丝毫的相互影响。光子计算机无导线传递信息 的平行通道,其密度实际上是无限的,一枚五分硬币大小的枚镜,它的信息通过能力竟是全世界现有电话电缆通道的许多倍。

    (3) 能量消耗小,散发热量低,是一种节能型产品。光子计算机的驱动,只需要同类规格的电子计算机驱动能量的一小部分,这不仅降低了电能消耗,大大减少了机器散发的热量,而且为光子计算机的微型化和便携化研制,提供了便利的条件。科学家们正试验将传统的电子转换器和光子结合起来,制造一种“杂交”的计算机,这种计算机既能更快地处理信息,又能克服巨型电子计算机运行时内部过热的难题。

    目前,光子计算机的许多关键技术,如光存储技术、光互连技术、光电子集成电路等都已经获得突破,最大幅度地提高光子计算机的运算能力是当前科研工作面临的攻关课题。光子计算机的问世和进一步研制、完善,将为人类跨向更加美好的明天,提供无穷的力量。

     

    生物计算机

    生物计算机,即脱氧核糖核酸(DNA)分子计算机,主要由生物工程技术产生的蛋白质分子组成的生物芯片构成,通过控制DNA分子间的生化反应来完成运算。运算过程就是蛋白质分子与周围物理化学介质相互作用的过程。其转换开关由酶来充当,而程序则在酶合成系统本身和蛋白质的结构中明显表示出来。上世纪70年代,人们发现DNA处于不同状态时可以代表信息的有或无。DNA分子中的遗传密码相当于存储的数据,DNA分子间通过生化反应,从一种基因代玛转变为另一 种基因代码。反应前的基因代码相当于输入数据,反应后的基因代码相当于输出数据。只要能控制这一反应过程,就可以制成DNA计算机。

    生物计算机以蛋白质分子构成的生物芯片作为集成电路。蛋白质分子比电子元件小很多,可以小到几十亿分之一米,而且生物芯片本身具有天然独特的立体化结构,其密度要比平面型的硅集成电路高五个数量级。生物计算机芯片本身还具有并行处理的功能,其运算速度要比当今最新一代的计算机快10万倍,能量消耗仅相当于普通计算机的十亿分之一。生物芯片一旦出现故障,可以进行自我修复,具有自愈能力。生物计算机具有生物活性,能够和人体的组织有机地结合起来,尤其是能够与大 脑和神经系统相连。这样,植入人体的生物计算机就可直接接受大脑的综合指挥,成为人脑的辅助装置或扩充部分,并能由人体细胞吸收营养补充能量,成为帮助人 类学习、思考、创造和发明的最理想的伙伴。

    生物计算机的优点如下:

    首先,它体积小,功效高。在一平方毫米的面积上,可容纳几亿个电路,比目前的集成电路小得多,用它制成的计算机,已经不像现在计算机的形状了,可以隐藏在桌角、墙壁或地板等地方。

    其次,当它的内部芯片出现故障时,不需要人工修理,能自我修复,所以,生物计算机具有永久性和很高的可靠性。

    再者,生物计算机的元件是由有机分子组成的生物化学元件,它们是利用化学反应工作的,所以,只需要很少的能量就可以工作了,因此,不会像电子计算机那样,工作一段时间后,机体会发热,而它的电路间也没有信号干扰。

    四、尾声

    长舒一口气,讲到这里我们的探索历程也就接近尾声了。从有限状态机到图灵机,从理论构想到具体实现,我们一步一步实现了制造计算机的过程;通过回顾历史,我们了解了整个计算机产业的发展过程。

    理论需要思想上的创新,从而指引实践的方向,实践需要技术上的巨大支持,从而能够切实完成理论构想,也许这就是贯穿计算机科学发展史中的两大主题吧。计算机科学的发展是永无止境的,计算机科学的应用同样如此,怎样能够让计算机更好地造福人类,这当中的责任扛在我们每个人信息学科人的肩头。的确,我们任重而道远,但我也相信,这会是一条光明的道路。


    展开全文
  • (2)在WORKBENCH中对该阶梯轴零件进行有限元仿真,实行两种仿真方案,分别是1.梁模型建模+梁单元网格划分;2.实体模型建模+六面体单元网格划分,观察两种仿真结果并与理论计算结果的对比,对比结果发现解析解与仿真...

    (1)对一个阶梯轴零件进行基于材料力学的理论计算,求解最大应力值;
    (2)在WORKBENCH中对该阶梯轴零件进行有限元仿真,实行两种仿真方案,分别是1.梁模型建模+梁单元网格划分;2.实体模型建模+六面体单元网格划分,观察两种仿真结果并与理论计算结果的对比,对比结果发现解析解与仿真解相差很小。
    (3)可以借此算例学习WB中的梁单元静力分析、三维实体静力分析、理解并施加若干种边界条件,举一反三即可了解此类轴系中轴零件的强度分析。

    在进行阶梯轴零件设计的时候一般会对其进行强度校核,校核方式主要有理论计算和仿真分析两种。轴零件的强度校核计算方式已经标准化,查阅手册即可,仿真分析可使用有限元仿真软件,本文算例将在ANSYS WORKBENCH 进行。

    本文的算例来自于《ANSYS Workbench 工程实例详解》,以校核阶梯轴强度问题为例,探讨使用解析解解法和有限元分析解的差异。

    一、算例描述及其解析解
    图1为阶梯轴的简图,现校核其受载后的静强度,已知直径d1=180mm{d_1=180mm}d2=150mm{d_2=150mm}a=300mm{a=300mm}b=200mm{b=200mm}L=1000mm{L=1000mm}F=300kN{F=300kN},材料为45,弹性模量E=2.1e11Pa{E=2.1e11Pa},泊松比v=0.28{v=0.28},屈服应力δs=355MPa{δ_s=355MPa}。在AB段,轴只受弯矩MAB{M_{AB}},而外伸到加载处的这一段,既受弯矩又有剪力,属于横力弯曲。根据材料力学分析,最大正应力应该产生在C截面的圆边缘处,强度为:
    δmax=δc=MC/WC=32Fb/πd23=181.083MPa{δ_{max}=δ_c={M_C}/{W_C}={32Fb}/{π{d_2}^3}=181.083MPa}
    同理AB段的最大应力大小为:δAB=MAB/WAB=32Fa/πd13=157.19MPa{δ_{AB}={M_{AB}}/{W_{AB}}={32Fa}/{π{d_1}^3}=157.19MPa}

    在这里插入图片描述

    图1 算例的理论解法

    二、有限元仿真分析结果
    为了简化仿真分析难度,考虑到目前ANSYS Workbench已经普及,且其流程化的操作方式也被越来越多的机械工程师所接受,故本文使用该仿真平台。

    在有限元分析的操作过程中,流程可简化为**建模→网格划分→设置边界条件→求解→结果后处理。**就重要性来说,前处理过程包括建模,网格划分和设置边界条件都是非常关键的步骤。网格划分需要考虑网格的类型、形状和尺寸等因素,而在设置边界条件时需确保对模型施加的边界条件与实际加载工况一致,三者均需保证准确无误,否则会导致计算结果与实际情况大相径庭,误导未来的进一步设计。

    梁单元静力学分析:
    当结构长度对横截面的比率超过10:1,沿长度方向的应力为主要分析对象,且横截面始终保持不变时,在WB中默认为铁摩辛柯梁单元,即beam188和beam189,可计算弯曲、轴向、扭转、和横向剪切变形。beam188和beam189两者的区别是形函数种类不同。beam189的精度更高,计算消耗内存也多,所以在仿真时需要权衡计算精度和时间。本文均使用beam188。

    建模:
    很多人在最初学习WB的时候,已经掌握了一种或多种三维绘图软件(例如SW、PRO/E等),并且认为只需使用这些三维软件绘制三维图再转化相应格式并将其导入WB中即可。但是这种导入的模型,在进行前处理划分网格的时候只能使用三维实体单元划分网格,而不能使用梁单元、二维平面单元和三维壳单元。例如本文中的算例,若要使用梁单元划分网格,必须在WB中DM模块中建立line body模型,具体参见《ANSYS Workbench 工程实例详解》。

    划分网格:
    使用line body生成的模型,可以选择自动划分网格的,WB会将以梁单元将其划分完成,例如图2所示。

    在这里插入图片描述

    图2梁模型建模后划分的网格

    使用DM建立的solid模型或者通过其它三维软件绘制并导入的模型,可以划分为六面体网格。例如图3所示。
    在这里插入图片描述

    图3 三维实体建模后划分的网格

    设置边界条件:
    梁模型设置边界条件:需考虑零件的受载和约束,受载即为该轴在两端外侧分别受到大小为300kN的力,方向沿-Y方向。约束需考虑图1中所示的A和B两点:A点是简支约束,在受载后只会产生绕Z轴的旋转,其它自由度均被锁死,故需要在A点施加约束Simply Support和Fixed Rotation(X和Y设置成Fixed,Z设置成Free);B点有X方向上有平移自由度,和绕Z轴的转动,故需在B点施加约束Fixed rotation(X和Y设置成Fixed,Z设置成Free)和Displacement(X方向设置为free,Y和Z设置为0)。如图4所示。注意下图中的字母标识为软件自动生成,与上述算例描述无关。
    加载方式

    图4 梁模型施加边界条件

    三维实体模型设置边界条件:可在两端面加载大小为300kN的力,设置约束时可使用远程边界条件-远程位移,来设置A和B两点的自由度,在添加远程边界条件时可基于remote point。如图5-图7所示,添加基于A和B所在面与轴相交的外圆线生成的remote point。(关于远程边界条件和远程点,感兴趣的同学可以参看ANSYS Workbench Help 文件)

    在这里插入图片描述

    图5 三维实体模型施加的边界条件

    在这里插入图片描述

    图6 A点remote point的设置

    在这里插入图片描述

    图7 B点remote point的设置

    结果和后处理:
    梁模型的后处理需导入 Beam Tool→Maximum Combined Stress,求解零件的在各个位置的最大应力,结果如下所示,如预期所料最大应力值出现在C截面,最大值如左侧的颜色条所示:
    在这里插入图片描述

    图8 梁模型应力分布

    结论:最大应力值为181.46MPa,理论值为181.08MPa,误差为0.1%。

    三维实体模型的von-mises应力云图如图9所示,但是求解的最大的应力值为258.44MPa,与理论计算值不符,这是因为由于有限元计算的特点,在该处会出现应力集中的现象。所以再分析C截面的应力值。
    在这里插入图片描述

    图9 实体模型应力云图

    在这里插入图片描述

    图10 C截面上的路径

    在这里插入图片描述

    图11 应力值随路径位置的变化

    由于应力集中导致峰值应力相差很大,所以反映的总应力相差也很大。

    在这里插入图片描述

    结论:C截面的弯曲应力为173.15MPa,理论值为181MPa,误差小于5%。

    展开全文
  • 有限元分析的基本过程 1 单元 有限元 - 连续体的离散化,将整体结构分割为若干基本单元,每个单元有若干节点。单元中的基本物理量 (结构分析 - 位移;热分析 - 温度;电磁分析 - 电位势,磁通量;流体分析 - 流量...

    二 有限元分析的基本过程
    1 单元
    有限元 - 连续体的离散化,将整体结构分割为若干基本单元,每个单元有若干节点。单元中的基本物理量 (结构分析 - 位移;热分析 - 温度;电磁分析 - 电位势,磁通量;流体分析 - 流量,等) 用单元节点处的值表示,可以写为:
    {u} = [P] {ue}
    其中:
    {u} - 单元中任意点的物理量值,它是坐标的函数:
    {u} = {u (x,y,z)}
    [P] - 形状函数,与单元形状、节点坐标和节点自由度等有关
    {ue} - 单元节点的物理量值;对于结构位移法可以是位移、转
    角或其对坐标的导数。
    常用的大型分析软件中基本上是位移+转角。
    结构分析时一些常用单元的节点自由度 (在单元坐标系中)
    杆元:单元形状为线段,变形形式为拉伸和扭转。
    在单元坐标系中:
    节点自由度为 Tx 和 Rx,其中 x 为杆的轴线。
    在总体坐标系中:
    三个位移和三个转角 (T1,T2,T3,R1,R2,R3)。
    梁元:单元形状为线段,变形形式为拉伸、扭转,以及两个垂
    直于轴线方向的弯曲
    在单元坐标系中:
    节点自由度为 Tx,Ty,Tz,Rx,Ry,Rz。其中 x 为梁的
    轴线,Y,z 为梁截面的两个抗弯惯矩主轴方向。
    在总体坐标系中:
    三个位移和三个转角 (T1,T2,T3,R1,R2,R3)。
    平面单元:三角形或四边形,变形为两个面内位移。
    节点自由度为 T1,T2。单元坐标系与总体坐标系一致。
    轴对称单元:三角形或四边形,变形为两个面内位移。
    节点自由度为 T1,T2。单元坐标系与总体坐标系一致。
    板壳元:三角形或四边形,变形包括两个面内位移,法向位移
    及两个转角 (一般缺少绕法线转角)。
    在单元坐标系中:
    三个位移和三个转角 (Tx,Ty,Tz,Rx,Ry)
    在总体坐标系中:
    三个位移和三个转角 (T1,T2,T3,R1,R2,R3)
    三维实体:四面体~六面体,三个方向的位移,无转角。
    节点自由度为三个位移 (T1,T2,T3),单元坐标系与总
    体坐标系一致。

    结构分析时一些特殊单元
    为了表征结构分析中遇到的一些特殊现象,多数 CAE 软件中都引入了一些特殊的单元,例如:
    弹簧单元 - 模拟拉压或弯扭弹簧连接
    阻尼单元 - 模拟阻尼器等结构件
    质量单元 - 用于处理集中质量
    接触单元 - 用于处理接触非线性问题
    间隙单元 - 用于处理接触非线性问题
    拉索单元 - 用于模拟只受拉不受压的线结构
    各种连接单元 - 用于模拟结构件之间的不同连接方式,如
    铰接、刚性连接等
    刚体单元 - 将结构的某一部分处理为刚体,可减小计算模
    型的规模

    在这里插入图片描述
    单元形状函数举例 (未必是实际使用的单元):
    (1) 一维单元
    a. 杆单元
    轴向拉伸和扭转:节点位移自由度为 Tx,Rx
    对 2 节点单元 (线性单元):
    Tx = a0 + a1 * x
    Rx = b0 + b1 * x
    各有 2 个未知数,可以由 2 个节点的位移值确定;
    对 3 节点单元 (二次单元):
    Tx = a0 + a1 * x + a2 * x2
    Rx = b0 + b1 * x + b2 * x2
    各有 3 个未知数,可以由 3 个节点的位移值确定;

    b. 梁单元
    拉伸和扭转的形状函数与杆的情况相同;
    对于弯曲变形 (以单元坐标系 y 向为例),2 节点单元相应的形状函数为:
    Ty = c0 + c1x +c2x2 + c3x3
    由两个节点的 Ty,Rz 可以确定四个未知数;
    对于 3 节点单元:
    Ty = c0 + c1
    x +c2x2 + c3x3 +c4x4 + c5x5
    由 3 个节点的 Ty,Rz 可以确定 6 个未知数;

    (2) 二维单元
    a. 平面单元 (平面问题,轴对称问题) ,以 Tx 为例
    三节点三角元:
    Tx = a0 + a1x + a2y
    三个未知数可以由三个节点的 Tx 表示;
    6 节点三角元:
    Tx = a0 + a1x + a2y + a3x2 + a4xy + a5y2
    6 个未知数可以由 6 个节点的 Tx 表示;
    4 节点四边形元:
    Tx = a0 + a1
    x + a2y + a3xy
    4 个未知数可以由 4 个节点的 Tx 表示;
    8 节点四边形元:
    Tx = a0 + a1x + a2y + a3x2 + a4xy + a5y2
    + a6
    (x3 + xy2) + a7*(x2y + y3)
    8 个未知数可以由 8 个节点的 Tx 表示;

    上面使用的简单多项式,对于 4 节点或 8 节点四边形 (特别是使用简单多项式的 8 节点单元,三次项缺失较多),使用效果往往不好。
    实际使用的是 “等参数单元”,通过曲线坐标变换,将任意三角形或四边形变换为等参数坐标系中的正三角形或正方形。然后用 “内插函数” 来构造形状函数。
    在这里插入图片描述
    (2) 二维单元 (续)
    b. 弯曲单元 (板、壳问题)
    平面内的变形与平面问题相同,主要考虑法向弯曲变形 - Tz,每个节点有三个弯曲自由度:Tz, Rx, Ry (法向位移和两个转角)。
    三节点三角元:
    Tz = a0 + a1x + a2y + a3x2 + a4xy + a5y2
    + a6
    x3 + a7*(x2y + xy2) + a8y3
    9 个未知数可以由三个节点的 Tz, Rx, Ry 表示。
    这是一个不完整的三次多项式,实际使用的是完整的三次多项式,然后添加约束条件消除多出来的一个未知数。
    4 节点四边形元:
    Tz = a0 + a1
    x + a2y + a3x2 + a4xy + a5y2
    + a6x3 + a7x2y + a8xy2 + a9y3 + 2 个四次项
    12 个未知数可以由四个节点的 Tz, Rx, Ry 表示。这是一个不完整的四次多项式,效果较差,实际使用的是 “等参数单元”。
    同样可以构造 “高阶” 单元 (6 节点三角元、8 节点四边形单元)。

    (3) 三维实体单元
    每个节点三个自由度:Tx,Ty,Tz,一般情况,单元坐标系 x,y,z 与总体坐标系 X,Y,Z 相同。
    a. 四面体单元 (以 Tx 为例)
    4 节点单元:
    Tx = a0 + a1x + a2y + a3z
    四个未知数由四个节点的 Tx 确定。
    10 节点单元 (增加 6 个边的中点):
    Tx = a0 + a1
    x + a2y + a3z + a4x2 + a5y2 +
    a6z2 + a7xy + a8yz + a9zx
    10个未知数由 10 个节点的 Tx 确定。
    b. 六面体单元 (以 Tx 为例)
    8 节点单元 (直观的例子,实际用 “等参数单元”):
    Tx = a0 + a1x + a2y + a3z + a4x2 + a5y2 +
    a6
    z2 + a7*(xy + yz + zx)
    8 个未知数由 8 个节点的 Tx 确定。
    20 节点六面体单元:
    使用完整的三次多项式,共 20 个未知数,由 20 个节点的 Tx 确定。实际中使用的是 “等参数单元”。
    理论上,计算结果应该随着网格的细化而收敛到精确值。但实践发现,单元的形状函数对其计算结果和收敛性有较大影响。经数学界研究发现,单元的构造必须满足相容性 (协调性) 和完备性要求,才能保证计算结果的收敛性。
    (1) 单元的完备性要求:
    对一般的多项式形式的单元形状函数,必须是与所解决问题的 “应变-位移” 关系式中的最高阶导数相同阶数的完整多项式。
    与 “应变-位移” 关系式中的最高阶导数相同阶数的多项式,在 “应变-位移” 关系式中微分后得到常应变项。因此,如果该多项式不完整,就会丢失某些常应变项,导致结果不准确。
    这一条可以归结为:位移函数必须包含全部刚体位移和常应变项。

    (2) 单元的相容性 (协调性) 要求:
    单元的位移函数必须包含所解决问题的 “应变-位移” 关系式中的最高阶导数低一阶的连续性。即,在相邻单元的边界上,该导数必须连续。
    如一般弹性问题 (平面问题、轴对称问题和三维弹性问题),其 “应变-位移” 关系式中只包括位移对坐标的一阶导数,只要求在单元边界上位移连续。因此其位移形状函数只要包含坐标的一次多项式即可 (Tx = a0 + a1x + a2y + a3*z …)。
    对板弯曲问题,“应变-位移” 关系式包含位移对坐标的二次导数,在单元边界上需要位移和转角都连续,因而板弯曲单元的节点自由度至少需要三个自由度:Tz,Rx,Ry。这也造成了难以构造简单而又满意的板弯曲单元。
    在满足相容性 (协调性) 要求的情况下,随着网格的细化,结果是单调收敛的。如果只满足完备性,而不满足相容性 (如板弯曲问题),解有时也能收敛,但一般不是单调收敛。

    2 单元特性的推导 (略)

    3 单元组集
    将所有单元的应变能求和,得到整个结构的应变能:
    U = S Ue = 1/2 {u}T [K] {u}
    其中 {u} 是整个结构所有节点的总体位移自由度按顺序排列所成,称为结构位移矢量;[K] 是将各单元的刚度矩阵对应相同总体自由度的元素叠加后得到。
    考虑两个杆单元的情况 (下页图),各单元的节点位移矢量和单元刚度矩阵用总体自由度序号表示如下:
    在这里插入图片描述
    在计算整个结构的应变能时,将两个单元刚度矩阵中具有相同下标的元素进行求和,例如 K4,4 ~ K4,6、K5,4 ~ K5,6、K6,4 ~ K6,6,从而得到整个结构的刚度矩阵。
    在这里插入图片描述
    如果单元中作用有外力,可以根据静力等效原理把它们分配到单元的节点上:
    在这里插入图片描述
    然后可以求出节点外力在节点位移上所做的功:
    V = [F] {u}
    其中 [F] 为所有节点的外力矢量 (每个节点三个分量),{u} 为所有节点的位移矢量 (每个节点三个分量)。
    然后,根据最小势能原理,真实位移应该使总势能取极小值:
    总势能为:
    P = U - V = 1/2 {u}T [K] {u} - [F] {u}
    对 {u} 取极值,即总势能对 {u} 的一次导数为零:
    在这里插入图片描述
    由此得到:
    [K] {u} - {F} = 0

    [K] {u} = {F}
    这就是待求解的有限元代数方程。由于将复杂的微分方程转换为有限个数的代数方程,从而使问题的求解变得容易。
    不过,现在还不能马上求解,因为数学上已经证明,没有约束的结构的刚度矩阵是一个奇异矩阵 (行列式为零),从物理上来说,即存在刚体运动,及时很小的外力也能够造成无穷大的位移。为了求解,必须对结构施加足够的约束以消除所有可能的刚体运动。
    常用的约束条件有:
    指定节点位移 (通常是零);
    弹性约束 (弹性地基)
    等。
    缺乏足够的约束常常是求解失败的主要原因之一。
    在约束自由度上会产生约束反力,对于结构而言,约束反力也是一种外力,以 {R} 表示约束反力,整个结构的方程可以写成:
    [K] {u} = {F} + {R}
    其中反力 {R} 仅在约束自由度上不为零。
    对整个结构的位移自由度重新排序,将已知位移自由度放到最后,分别以下标 f 和 r 代表未知和已知的自由度,则有:
    在这里插入图片描述
    展开后分解为两个方程:
    [Kff] {uf} = {Ff}
    [Krf] {uf} + [Krr] {ur} = {Fr} + {R}
    第一个方程用来求解未知的位移自由度,第二个方程改写为:
    {R} = {Fr} - [Krf] {uf} - [Krr] {ur}
    用来计算约束反力。
    在求出整个结构的节点位移后,可以回到各单元,计算单元的应力、应变等其它所需的物理量 (通常称为数据恢复)。至于节点应力、应变等物理量,通常用与节点相邻的单元的平均值代表。

    展开全文
  • 计算机科学技术数学理论浅谈

    千次阅读 2010-11-04 22:17:00
    计算机自从其诞生之日...我们先来看一下下面的一个流程图:      上图揭示了利用计算机解决科学计算的步骤,实际问题转换为程序,要经过一个对问题抽象的过程,建立起完善的数学模型,只有这样

    计算机自从其诞生之日起,它的主要任务就是进行各种各样的科学计算。文档处理,数据处理,图像处理,硬件设计, 软件设计等等,都可以抽象为两大类:数值计算与非数值计算。作为研究计算机科学技术的人员,我们大都对计算数学对整个计算机科学的重要性有一些了解。但是 数学对我们这些专业的研究和应用人员究竟有多大的用处呢?我们先来看一下下面的一个流程图:

     

     

      上图揭示了利用计算机解决科学计算的步骤,实际问题转换为程序,要经过一个对问题抽象的过程,建立起完善的数学模型,只有这样,我们才能建立一个设计良好的程序。从中我们不难看出计算数学理论对用计算机解决问题的重要性。下面我们将逐步展开对这个问题的讨论。
      计算机科学的数学理论体系是相当庞杂的,笔者不敢随意划分,参考计算机科学理论的学科体系,我们谈及的问题主要涉及:数值计算,离散数学,数论,计算理论四大方向。


    (一)数值计算(Numerical Computation)
      主要包括数值分析学、数学分析学、线性代数、计算几何学、概率论与数理统计学。

    数值分析学
      又常被称为计算方法学,是计算理论数学非常重要的一个分支,主要研究数值型计算。研究的 内容中首先要谈谈数值计算的误差分析,误差是衡量我们的计算有效与否的标准,我们的算法解决问题如果在误差允许的范围内,则算法是有效的,否则就是一个无 效的问题求解。另外就是数值逼近,它研究关于如何使用容易数值计算的函数来近似地代替任意函数的方法与过程。感觉应用比较广的不得不提切雪比夫逼近和平方 逼近了。笔者曾经尝试过的就是通过最佳平方逼近进行曲线的拟合,开发工具可以选择VC++或者Matlab。插值函数是另外一个非常重要的方面,现代的计 算机程序控制加工机械零件,根据设计可给出零件外形曲线的某些型值点,加工时走刀方向及步数,就要通过插值函数计算零件外形曲线及其他点函数值。至于方程 求根、线性方程组求解,一般的计算性程序设计问题都会多多少少的涉及一些,我们这里就不赘述了。关于数值分析学的一个学习误区就是仅仅学习理论知识,而很 难和程序设计结合起来,实际上通过上面的论述,大家已经能够初步地认识到这个学科是应当与程序设计紧密联系才能够体现它的重要性的。关于理论的学习,推荐 华中科技大学李庆扬老师的《数值分析》。然而理论学习毕竟是个过程,最终的目标还是要用于程序设计解决实际的计算问题,向这个方向努力的书籍还是挺多的, 这里推荐大家高等教育出版社(CHEP)和施普林格出版社(Springer)联合出版的《计算方法(Computational Methods)》,华中理工大学数学系写的(现华中科技大学),这方面华科大做的工作在国内应算是比较多的,而个人认为以这本最好,至少程序设计方面涉 及了:任意数学函数的求值,方程求根,线性方程组求解,插值方法,数值积分,场微分方程数值求解。

    数学分析学
      很多学校在近 些年已经替代高等数学被安排到了本科教学当中。原因是很简单的,高等数学虽然也是非常有用的工程数学,介绍的问题方法也被广泛的应用,但是正如大家所知道 的,高等数学不太严格的说,基本上就是偏向于计算的数学分析,当然省去了数学分析非常看重的推理证明,然而我们认为这一部分正是我们最需要的。这对我们培 养良好的分析能力和推理能力极有帮助。我的软件工程学导师北工大数理学院的王仪华先生就曾经教导过我们,数学系的学生到软件企业中大多作软件设计与分析工 作,而计算机系的学生做初级程序员的居多,原因就在于数学系的学生分析推理能力,从所受训练的角度上要远远在我们平均水平之上。谈到这方面的书籍,公认北 京大学张筑生老师的《数学分析新讲》为最好。张筑生教授一生写的书并不太多,但是只要是写出来的每一本都是本领域内的杰作,这本当然更显突出些。这种老书 看起来不仅是在传授你知识,而是在让你体会科学的方法与对事物的认识方法。现在多用的似乎是复旦大学的《数学分析》,高等教育出版社的,也是很好的教材。 但关于如何去利用从中获得的推理证明能力,我们在遇到具体问题的时候,可以在今后的文章详细讨论。

    线性代数
      线性代数是我们在工科本科学习的必修课程,似乎大家找不到到底这个有什么用,其实很明显,线性代数作为工程数学的重要分支,在计算机领域的研究有相当广泛的应用。最为突出的可以谈谈数组和矩阵的相关知识:
      下面谈一个我经常作为例子和同学讨论的问题:四个城市之间的航线如图所示:

     

      令aij=1,表示从i市到j市有1条航线
      令aij=0,表示从i市到j市没有单项航线
      则图可用矩阵表示:                       
      A= (aij) =
      我们可以采用程序设计实现这个问题,如果辅以权值,可以转化为最短路径的问题,再复杂化一点还可以转化为具有障碍物的最短路径问题,这就会涉及一些如 Dijkstra算法等高级程序设计算法话题。这些都依靠着数组、矩阵的基本知识。数组的应用主要在图像处理以及一些程序设计理论。矩阵的运算领域极为广 泛,比如在计算机图形学当中曲线曲面的构造,图像的几何变换,包括平移、镜像、转置、缩放。在高级图像问题更有广泛应用,例如在图像增强技术,投影技术中 的应用。

    计算几何学
      计算几何学研究的是几何外形信息的计算机表示。包括几何查找、多边形、凸包问题、交与并、几何体的排列、 几何拓扑网络设计、随机几何算法与并行几何算法。它构成了计算机图形学中的基本算法,是动画设计,制造业计算机辅助设计的基础。如果从事这方面的深入研 究,可以参考中国计算机学会周培德先生的《计算几何——算法分析与设计》。

    概率论与数理统计学
    概率论与数理统计学是这个领域最后一门关键的课程。概率论部分提供了很多问 题的基本知识描述,比如模式识别当中的概率计算,参数估计等等。数理统计部分有很多非常经典的内容,比如伪随机数、蒙特卡罗法、回归分析、排队论、假设检 验、以及经典的马科夫过程。尤其是随机过程部分,是分析网络和分布式系统,设计随机化算法和协议非常重要的基础。

     

    (二)离散数学(Discrete Mathematics)
    随着计算机科学的出现与广泛应用,人们发现利用计算机处理的数学对象与传统的分析有明显的区别:分析研究的问题解决方案是连续 的,因而微分,积分成为基本的运算;而这些分支研究的对象是离散的,因而很少有机会进行此类的计算。人们从而称这些分支为"离散数学"。离散数学经过几十 年发展,方向上基本上稳定下来。当然不同时期还有很多新内容补充进来。就学科方向而言,一般认为,离散数学包含:集合论、逻辑学、代数学、图论、组合学。

    逻辑学(Logics)
    主要指数理逻辑,形式逻辑在推理问题中也有比较广泛的应用。(比如我们学校还为此专门开设了选修课程)这方面的参考推荐中科院软件所陆钟万教授的《面向计算机科学的数理逻辑》。现在可以找到陆钟万教授的讲课录像,http://www.cas.ac.cn/html/Dir/2001/11/06/3391.htm。总的来说,学集合/逻辑一定要站在理解的高度上去思考相关的问题。集合论(Set Theory)和逻辑学构成了计算机科学最重要的数学问题描述方式。

    代数学(Algebra)
      包括:抽象代数、布尔代数、关系代数、计算机代数
      (1) 抽象代数(Abstract Algebra)研究的主要内容涵盖群、环、域。抽象代表的是将研究对象的本质提炼出来,加以高度概括,来描述其形象。“欧 式环”就是在将整数和多项式的一些相同的特点加以综合提炼引入的。抽象代数提供的一些结论为我们研究一些具体问题时所需使用的一些性质提供了依据。推荐一 个最简单的,最容易学的材料:http://www.math.miami.edu/~ec/book/这本 《Introduction to Linear and Abstract Algebra》非常通俗易懂,而且把抽象代数和线性代数结合起来,对初学 者来说非常理想。
      (2)布尔代数(Boolean Algebra)是代数系统中最为基础的部分,也是最核心的基本理论。主要包括了集合的基本概念与运算,自对偶的公理系统。是数据表示的重要基础。相信大家都很清楚它的重要性。
      (3)关系代数(Relational Algebra)应用也是极为广泛,比如数据库技术中的关系数据库的构建就要用到关系代数的相关理论。
      (4) 计算机代数(Computer Algebra)大家可能比较生疏,其实它研究的主要内容即是围绕符号计算与公式演算展开的。是研究代数算法的设计、分 析、实现及其应用的学科。主要求解非数值计算,输入输出用代数符号表示。计算机代数的开发语言主要有:ALTRAN,CAMAL,FORMAL。主要应用 于:射影几何,工业设计,机器人手臂运动设计。

    图论(Graph Theory)
    主要研究的内容包括:图的基本概念、基本运算、矩阵表示,路径、回路和连通性,二部图、平面图,树,以及网络流。图论的 应用领域太过广泛,仅举两个例子:比如在计算机网络拓扑图的设计与结构描述中,就必须用到相当多的图的结构和基本概念。关于网络流更是在电流网络与信息网 络的流量计算当中广泛应用。树的相关应用则无须多言了。

    组合学(Combinatorics)
    有两部分单独的研究领域:组合数学与组 合算法。组合学问题的算法,计算对象是离散的、有限的数学结构。从方法学的角度,组合算法包括算法设计和算法分析两个方面。关于算法设计,历史上已经总结 出了若干带有普遍意义的方法和技术,包括动态规划、回溯法、分支限界法、分治法、贪心法等。应用是相当广泛的,比如旅行商问题、图着色问题、整数规划问 题。关于组合数学,主要研究的内容有:鸽巢原理、排列与组合、二项式系数容斥原理及应用,递推关系和生成函数、特殊计数序列、二分图中的匹配、组合设计。 推荐Richard A.Brualdi的《Introductory Combinatorics》作为参考。

     

    (三)数论(Number Theory)
    数论这门学科最初是从研究整数开始的,所以叫做整数论。后来更名为数论。它包括以下几个分支:
      初等数论是不求助于其他数学学科的帮助,只依靠初等方法来研究整数性质的数论分支。比如在数论界非常著名的“中国剩余定理”,就是初等数论中很重要的内 容。对于程序设计来说这部分也是相当有价值的,如果你对中国剩余定理比较清楚,利用它,你可以将一种表达式经过简单的转换后得出另一种表达式,从而完成对 问题分析视角的转换。
      解析数论是使用数学分析作为工具来解决数论问题的分支。是解决数论中比较深刻问题的强有力的工具。我国数学家陈景润在尝试解决“哥德巴赫猜想”问题中使用的就是解析数论的方法。以素数定理为基础解决计算素数的问题及其算法实现应是我们多多关注的。
      代数数论是把整数的概念推广到一般代数数域上去,建立了素整数、可除性等概念。程序设计方面涉及的比较多的是代数曲线的研究,比如说椭圆曲线理论的实现。 
      几何数论研究的基本对象是“空间格网”。空间格网就是指在给定的直角坐标系上,坐标全是整数的点,叫做整点;全部整点构成的组就叫做空间格网。空间格网对计算几何学的研究有着重大的意义。几何数论涉及的问题比较复杂,必须具有相当的数学基础才能深入研究。
      总的说来,由于近代计算机科学的发展,数论得到了广泛的应用。比如在计算方法、代数编码、组合学理论等方面都广泛使用了初等数论范围内的许多研究成果;现 在有些国家应用“孙子定理”来进行测距,用原根和指数来计算离散傅里叶变换等。如果你曾经系统的学习过数论算法,你会发现这个分支学科研究的一些基本问题 对程序设计是相当有用的,比如说素数问题、素性测试、因子分解、最大公约数、模取幂运算、求解同余线性方程。其中的很多问题都是程序设计的基本问题。但这 些问题都不能小视,举个例子来说吧,关于求最大公约数的程序,笔者曾经尝试的就可以采用循环语句结构和递归结构。另外,以大素数为基础的密码体系的建立是 近些年数论算法广泛应用的一个重要的原因。原理是大素数的乘积重新分解因数十分困难。RSA公钥加密系统的构建就是基于这个原理的(三位发明人因此也获得 了2002年美国计算机协会颁发的图灵奖)。

     

    (四)计算理论(Theory of Computation)
    涉及的内容是科学计算非常重要的一部分分支,也是大家研究相当多的一部分。主要包括:算法学,计算复杂性,程序理论。

    算法学 (Algorithms)
    算法学在计算机科学理论中有着举足轻重的地位。是解决很多数值型,非数值型问题的基础。记得一次学校接收招标项目,很多中小型软件厂商 都无法完成一个软件的功能模块,就是因为当时他们对一个具体问题的算法不能做出正确的抽象,最后由我们学校数理学院的一支软件团队承担了这项任务,他们的 最终报告体现出来,问题的解决策略只有通过人工神经元网络的反向传播算法。可见在比较有深度的程序设计中,算法的重要性更为突出。学习算法学要有一个长期 的理论和实践的过程。遇到一个具体算法问题时,首先要通过自己描述的数学抽象步骤,看看自己以前有没有处理过这种问题。如果没有,很可能这个问题是多个算 法的综合,或者是需要我们自己去构造算法。这就需要我们有扎实的算法功底,为了打好这个功底,推荐两套圣经级的书籍首先是Thomas H.Cormen 等著的《Introduction to Algorithms》。对算法学习而言,这一本内容相当的全面。再深一点的就是大家作为常识都知道的 《The Art of Computer Programming》,目前已经出版3册。两本书的价值大家应当都是清楚的。

    计算复杂性
    计算复 杂性研究的内容很广,其中包括NP完全性理论,可计算性理论,自动机理论,形式语言理论(包括广泛应用于编译原理领域的文法,还包括Petri网论的相关 内容)以及大家熟知的复杂性度量。时间复杂度、空间复杂度的计算是度量算法非常重要的参数,也是我们衡量程序优劣程度的重要依据。

    程序理论(Theory of programs)
    程序理论包含了形式语义学,程序验证和并发模型的研究。关于程序验证学习的重要性大家都很清楚,学习的方法自然也 是多多结合具体的问题去分析。关于并发模型,主要研究的就是进程代数,通信系统演算,通信顺序进程。这部分是研究操作系统理论与实现的重要基础。

     

    (五)最后
    上面按照计算机科学数学理论的架构来谈了各方面的内容和一些应用,下面我们再单独来看一些上面没有涉及到的学科与这些理论的具体结合情况:
      设计方面的应用刚才谈的很多,我只再说说数据库原理与技术,这方面用到的重要数学基础主要包括:集合论,二元关系及其推理(尤其是研究关系数据库),研究数据分布与数据库结构又涉及相当多的图论知识。
      计算机科学的发展有赖于硬件技术和软件技术的综合。在设计硬件的时候应当充分融入软件的设计思想,才能使硬件在程序的指挥下发挥极致的性能。在软件设计的 时候也要充分考虑硬件的特点,才能冲破软件效率的瓶颈。达到硬件和软件设计的统一,严格的说这并不轻松,一般的程序设计者很难将这样的思想贯穿在其程序设 计当中。仅举个简单的例子:我们在写一些C语言的程序,必要的时候都会采取内嵌一段汇编指令,这就是比较充分地考虑了硬件的工作情况,从而能够提高程序运 行的效率。所以我们也有必要了解一些硬件的基础知识。关于学习硬件的时候常会用到的基本数学思想也是相当多的,拿电路基础与模拟电路来说,我们就经常要利 用多元函数,不等式计算进行电流电压的计算。能量的计算还常常涉及微积分学的很多计算。在数字电子技术当中(有时也称数字逻辑学)数理逻辑,尤其是逻辑演 算部分运用相当广泛,数制转换更是非常重要的基础,各种数字电路参数的计算则是多元函数,不等式的计算解决的问题。
      从事计算机硬件程 序设计的程序员,则不可回避的就是数字信号处理。这门科学所用到的数学基础主要有:三角函数、微积分、高次方程求解、数值逼近,傅里叶变换。在滤波器的设 计当中还会用到矩阵运算。笔者曾经研究过一个VC++环境下开发的滤波器的模拟软件,就是利用莱文逊-杜宾递推算法,在较大规模的矩阵运算基础上进行的。 当然,开发的环境不一定是这个,你也可以选择MATLAB或者纯C语言编译器。如果我们不了解相关的数学基础,不要说程序设计,就算是建立运算模型都是相 当困难的。
      一些周围的同学和一些在职的程序员,大家经过一段时间的学习,普遍都觉得数学对学习计算机和研究计算机程序设计等 问题来说非常重要,但是又苦于无从下手。上面比较全面地谈及了计算机科学数学理论的相关内容。需要特别指明的是,我们研究问题的精力是有限的,如果您是在 校的计算机系学生,则可以对上面的方方面面都有所涉及,以尝试计算数学这个强大的理论工具。为今后的工作奠定一个坚实的基础。但是如果您研究的是比较具体 的工作,我们并不推荐您研究所有的内容,最好的方法就是对上面的数学基础都有些了解,然后遇到具体工作,需要哪部分内容,再进行深入的学习与研究。这样针 对性比较强的学习效果是会比较显著的。对于上面推荐的一些参考材料,除非你要花相当长的一段时间来提高你的计算机数学理论。否则也没必要每一页,每一本都 字字精读,还是那个原则,按需索取其中的内容。学习的方法描述起来就一句话:结合具体的问题,深入的理解数学理论知识,将理论程序化,尝试用程序设计实现 理论原理。达到这样的程度,问题基本上都可以解决的。(限于篇幅,很多问题不能展开,您可以通过zengyi@cstc.net.cn与我联系)

     

    参考文献:
    《计算机科学技术百科全书》中国计算机学会 清华大学出版社
    《工程数学—线性代数》同济大学数学教研室 同济大学出版社
    《数值分析》李庆扬 华中科技大学出版社

    本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/jakee304/archive/2008/03/21/2201437.aspx

    展开全文
  • ANSYS 有限元分析 加载/求解/输出

    千次阅读 2020-05-28 10:01:19
    ANSYS 有限元分析 概述 ANSYS 有限元分析 坐标系/工作平面 ANSYS 有限元分析 几何建模 ANSYS 有限元分析 网格划分 ANSYS 有限元分析 选择与组件 ANSYS 有限元分析 修改与编辑 ANSYS 有
  • 《UG NX 8.5有限元分析入门与实例精讲》介绍了在典型工程实例中采用有限元进行分析的...本书注重解题思路、操作流程和分析方法,操作步骤详细,随书光盘包含所有实例的操作演示视频、素材模型和对应的有限元计算结果文
  • 并行计算机未来发展前景

    千次阅读 2016-11-24 20:37:47
    20世纪60年代初期, 由于晶体管以及磁芯...现代计算机的发展历程可以分为2个时代:串行计算时代和并行计算时代。并行计算是在串行计算的基础上发展起来的。并行计算将一项大规模的计算任务交由一组相同的处理单元共同完
  • 计算机本质

    万次阅读 2017-02-16 15:49:56
    ”我的专利不仅仅能实现加法操作,也能实现减法操作,计算具有普遍性,具有划时代的意义,可以把人类从复杂的计算中解救而出来...“ 至此,我们实现了一个简单的计算器实现,不难吧?然而这才只是万里长征的第一...
  • 书中参照国外有限元分析标准,介绍了螺栓连接、焊接等分析的各种有限元处理方法,修正了国内有限元计算过程中易出现的错误。 全书共5章。第1章说明CAE分析步骤;第2章讲解ANSYS Workbench主界面,举例说明ACT插件...
  • 计算机发展历程

    千次阅读 2019-03-16 22:04:27
    计算机(computer)俗称电脑,是一种用于高速计算的电子计算机器,可以进行数值计算,又可以进行逻辑计算,还具有存储记忆功能。是能够按照程序运行,自动、高速处理海量数据的现代化智能电子设备。由硬件系统和软件...
  • 有限状态机、图灵机到现代计算机 转自:http://blog.sina.com.cn/s/blog_64ac3ab10100ges2.html   一、有限状态机 引子 让我们先来看几个简单的概念: 状态 - 系统的基本数学特征。 状态机 - 一个...
  • 有限状态机图灵机到现代计算机

    千次阅读 2014-12-13 10:55:01
    一、有限状态机 引子 让我们先来看几个简单的概念: 状态 - 系统的基本数学特征。 状态机 - 一个离散数学模型。给定一个输入集合,根据对输入的接受次序来决定一个输出集合。 有限状态机 - 输入集合和...
  • 本节书摘来自异步社区《ANSYS Workbench有限元分析实例详解(静力学)》一书中的第1章,第1.1节,作者: 周炬 , 苏金英 更多章节内容可以访问云栖社区“异步社区”公众号查看。 第1章 CAE分析步骤 在现代工程领域,...
  • 计算机视觉是否已经进入瓶颈期?

    千次阅读 2020-09-27 09:33:57
    ~ 从我看的这几年的情况来看 视频方面,尤其是远机位的视频处理上,始终都还是使用范围比较有限的dataset,一旦跨库之后非常不鲁棒 然后基于视频质量的一些工作也可以做(质量评价、低码率处理),基于视频处理的...
  • 本节书摘来自异步社区《ANSYS Workbench有限元分析实例详解(静力学)》一书中的第2章,第2.1节,作者: 周炬 , 苏金英 更多章节内容可以访问云栖社区“异步社区”公众号查看。 第2章 ANSYS Workbench主界面设置 ...
  • 附录A 计算机的0和1

    千次阅读 2017-09-13 14:29:49
    计算程序拟定“算法”,写作的第一份“程序设计流程图”,被珍视为“第一位给计算机写程序的人”。为了纪念阿达·奥古斯塔对现代电脑与软件工程所产生的重大影响,美国国防部将耗费巨资、历时近20年研制成功的高级...
  • 5G及移动边缘计算(MEC)学习笔记(3)

    万次阅读 多人点赞 2018-06-27 15:15:14
    移动边缘计算中的任务迁移方向相关。
  • 利用高性能计算加速深度学习算法

    千次阅读 2018-02-07 16:09:42
    1. 深度学习  深度学习是机器学习研究中的一个新...(由于本人不是深度学习专业人士,对深度学习理论知识不多介绍,说多了就班门弄斧了,后面主要介绍下这些深度学习算法如何进行并行化设计和优化) 2. CPU+GP
  • 1.1 什么是计算机视觉 1.2 计算机视觉发展的四个主要阶段 1.3 计算机视觉的若干发展趋势 1.4 几种典型的物体表达理论(Object representation theories)
  • 然后,通过系统化的流程解决问题,而在这个流程之前,理论就已经确保了它必定会成功(在有限步骤内终止)。现在的软件通过这样的流程来设计,那不是很好吗? 达令顿的研究表明,任何正有理实函数,都可以实现为一...
  • 【引言】计算材料学:“定做”材料的高级理论阶段 计算材料学(Computational Materials Science)是近年来飞速发展的一门新兴交叉学科。它综合了凝聚物理、材料物理学、理论化学、材料力学和工程力学、计算机算法等多...
  • 前面放完建设四个现代化大数据平台乌托邦理想的大卫星,接下来的文章得谈谈具体...本文重点谈理论,会先从大的场景划分的角度对市面上的各种调度系统进行分类讨论,然后再针对具体的作业调度系统,探讨一下各自的优缺点
  • 该量子系统只用了 200 秒完成一个计算,而同样的计算用当今最强大的超级计算机 Summit 执行,需要约 10000 年。 为了详细介绍谷歌的量子成就,谷歌CEO桑德尔·皮查伊在公司网站上发表了题为“我们的量子计算里程碑...
  • 数据可视化平台理论与实践

    万次阅读 2017-08-02 09:32:26
    首先在大数据领域里,底层的存储和计算引擎差异巨大,远还没有达到标准检索方式能一统天下的局面,各种业务组件和流程往往需要定制和灵活适配处理逻辑。 其次,现有的比较成熟的产品,其封闭的逻辑思维要打破,首先...
  • 计算机等级考试--二级Java的知识点大全

    万次阅读 多人点赞 2019-03-16 20:42:59
    第一章 数据结构与算法 【考点1】算法的基本概念 ...2)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止; 3)可行性,算法原则上能够精确地执行; 4)拥有足够的情报。 3、算法的组成...
  • 计算机组成原理题库(唐朔飞)

    万次阅读 多人点赞 2019-04-13 16:51:32
    ^^用于科学计算的计算机中,标志系统性能的主要参数是( )。 A、主时钟频率 B、主存容量 C、MFLOPS D、MIPS ^^C ~~02|01|1|2|A0400047_010_31|901 ^^计算机主频的倒数指的是( )。 A、指令周期 B、机器周期 C...
  • 在推进深度学习的学习理论计算理论的同时,我们是否可以提出新的分层模型,使其不但具有传统深度模型所具有的强大表示能力,还具有其他的好处,比如更容易做理论分析。另外,针对具体应用问题,我们如何设计一个最...
  • 408计算机学科专业基础综合——计算机组成原理

    万次阅读 多人点赞 2018-11-12 20:59:00
    8.用于科学计算的计算机中,标志系统性能的最有用的参数是(C MFLOPS)(科学计算:评估浮点运算的性能) A 主时钟频率 B 主存容量 C MFLOPS D MIPS 9.若一台计算机的机器字长为4字节,则表明该机器(在CPU中能够...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,330
精华内容 6,132
关键字:

有限元理论计算流程