符号化计算化与自动化.ppt

大学计算机-计算思维导论李旻先南京理工大学计算机科学与工程学院研究计算机的终极目的是解决社会/自然问题，如何解决呢？u将社会/自然问题用符号表达，基于符号进行计算，将计算用软件/硬件来实现，这是解决社会/自然问题的基本思维模式第2讲-符号化、计算化与自动化基本目标:理解0和1的思维内容提要语义符号化符号计算化计算0(和)1化0(和)1自动化分层构造化构造集成化；符号化、计算化与自动化2.1 0和1与易经?0和1与易经-语义符号化表达与计算的一个示例易经是什么?2.1 0和1与易经-语义符号化表达与计算2.1.1 易经是什么?八卦？预测与占卜？算命？自然现象及其变化规律人事现象及其变化规律其他现象及其变化规律天地风雷日月山泽？将现象抽象为符号，进行符号组合，利用符号组合表达自然现象 易经怎样表达自然现象?符号化的六十四卦图更多的组合，更多的语义，更多的变化易经怎样区分各种组合要素?待区分的命名阴阴(六六)阳阳(九九)三个阴阳构成的一个组合卦卦一个组合中的某一位置爻爻三画阴阳可能出现的八种组合乾、坤、坎、离、艮、兑、震、巽乾、坤、坎、离、艮、兑、震、巽一卦中的三个位置一爻、二爻、三爻一爻、二爻、三爻一个位置可能出现阴和阳阳阳(九九)爻，阴爻，阴(六六)爻爻一个位置可能出现阴和阳，结合卦中不同位置组合九一爻、六一爻、九二爻、六二爻、九一爻、六一爻、九二爻、六二爻、九三爻、六三爻九三爻、六三爻 符号化的关键是区分与命名-术语体系冬至一阳生夏至一阴生易经怎样研究自然现象的变化?符号化的目的是基于符号的演算-符号组合的变化方式“卦”之间的变化规律是什么？“卦”及之间变化反映的语义又是什么？生命演化规律气候演化规律阴、阳卦、爻卦变、爻变将符号再赋予语义-“本”与“用”：抽象与具体化 现象 本体 用体天(自然空间)乾(抽象空间)父(家庭空间)，首(身体空间)，马(动物空间)易经中的乾坤和天地?由“易经”看“符号化及符号运算”?01111111000000000111111000自然现象的变化规律符号如何组合如何变化其他现象天地风雷日月山泽？符号化、计算化与自动化2.1.2 0和1与逻辑?0和1与逻辑-语义符号化表达与计算的另一个示例-思维符号化与计算-逻辑运算与0和1逻辑是指事物因果之间所遵循的规律，是现实中普适的思维方式 u 逻辑的基本表现形式是命题与推理，推理即依据由简单命题的判断推导得出复杂命题的判断结论的过程。命题由语句表述，即内容为“真”或为“假”的一个判断语句！例如 在一次中学生测验中，有三位老师做了预测：A.学习委员及格；B.有人不及格；C.全班都不及格。在考试后证明只有一个老师的预测是对的，请问谁对谁错？求解过程：命题A：“学习委员及格(即有人及格)”；命题B：“有人不及格”；命题C：“全班都不及格”；由题目假设和命题之间关系得出“已知”：A、B、C只有一个为真如果A真，则C假；如果C真，则A假；如果B真，而A,C可能有一个为真，与题矛盾，所以B为假。如果B假，则“全班都及格”为真，而由此推断C为假。由上“已知”，推理：A为真。2.1.2 0和1与逻辑-思维符号化表达与逻辑运算 什么是逻辑?2.1.2 0和1与逻辑-思维符号化表达与逻辑运算 什么是逻辑?“与”运算：两把钥匙都有才能开门“或”运算：只要有任何一把钥匙便能开门思维的符号化及其计算-基本逻辑运算一个命题由X,Y,Z等表示，其值可能为“真”或为“假”。则两个命题X,Y之间是可以进行运算的：p“与”运算(AND):当X和Y都为真时,X AND Y也为真;其他情况,X AND Y均为假。p“或”运算(OR):当X和Y都为假时,X OR Y也为假;其他情况,X OR Y均为真。p“非”运算(NOT):当X为真时,NOT X为假;当X为假时,NOT X为真。p“异或”运算(XOR):当X和Y都为真或都为假时,X XOR Y为假;否则,X XOR Y为真。有哪些基本的逻辑运算操作?2.1.2 0和1与逻辑-思维符号化表达与逻辑运算 什么是逻辑?用0和1来表示逻辑运算n“与”运算AND：有0为0，全1为1n“或”运算OR：有1为1，全0为0n“非”运算NOT：非0则1，非1则0n“异或”运算XOR：相同为0，不同为1注:1表示 真，0表示 假 0 AND 0 00 AND 1 0 1 AND 0 01 AND 1 11 OR 1 11 OR 0 10 OR 1 10 OR0 0 NOT 0 1 NOT 1 01 XOR 1 0 1 XOR 0 10 XOR 1 10 XOR 0 0 怎样符号化逻辑并进行计算?命题A：“学习委员及格(即有人及格)”命题B：“有人不及格”命题C：“全班都不及格”已知：(A AND(NOT C)OR(NOT A)AND C)=1 (NOT B)AND (A AND(NOT C)OR(NOT A)AND C)=1 (NOT B)AND(NOT C)=1组合形成所有可能解,，将上述可能解代入已知条件，使所有已知条件都满足的便是问题的解：。1-真 0-假一个命题用A、B等符号表达，其中符号的值可能为0，也可能为1将逻辑表达为0和1及其运算可深入学习1)Aristotle(亚里士多德)(公元前384322)。古希腊哲学家：形式逻辑。典型概念：命题，推理，三段论2)Leibnitz(莱布尼茨)(16461716)。德国数学家：数理逻辑。典型概念：谓词，谓词演算 3)Boole(布尔)(18151864)。英国数学家，布尔代数典型概念：布尔量,布尔值,布尔运算,布尔操作 4)其他：时序逻辑(Temporal Logics)、模态逻辑(Modal Logics)、归纳逻辑(Inductive Logics)、模糊逻辑(Fuzzy Logics)、粗糙逻辑(Rough Logics)、非单调逻辑等 逻辑研究有哪些?符号化、计算化与自动化2.1.3 0和1与数值性信息?0和1与数值性信息-二进制及算术运算-数值的符号与0和1-小数点的处理u进位制：用数码和带有权值的数位来表示有大小关系的数值性信息的表示方法。u二进制2.1.3 0和1与数值-二进制与算术运算怎样用0和1表达数值性信息?数值性信息=127+126+125+124+023+122+021+120+02-1+12-2 =(245.25)十例如：(1 1 1 1 0 1 0 1.0 1)二 7 6 5 4 3 2 1 0.-1-227 26 25 24 23 22 21 20.2-1 2-2数位的权值数位二进制数 基于二进制的算术运算 u计算规则简单,与逻辑运算能够统一起来；元器件容易实现。为什么要用二进制?Ai Bi+CiCi+1 SiSi=(Ai XOR Bi)XOR Ci Ci+1=(Ai XOR Bi)AND Ci)OR(Ai AND Bi)Si=Ai XOR BiCi+1=Ai AND Bi不考虑进位考虑进位ur进制：二进制有什么不足，怎样解决?数值性信息(dn-1dn-2d2d1d0.d-1d-2d-m)r n-1 n-2 2 1 0 .-1-2 -mrn-1 rn-2.r2 r1 r0 .r-1 r-2 r-m=dn-1rn-1+dn-2 rn-2+d2 r2+d1 r1+d0 r0+d-1 r-1+d-2 r-2+d-m r-m-=1nmiiird=数位的权值数位r进制数u 十六进制：0,1,2,3,4,5,6,7,8,9,A(10),B(11),C(12),D(13),E(14),F(15)u 八进制：0,1,2,3,4,5,6,7u 十进制：0,1,2,3,4,5,6,7,8,9(365.2)10,（11011.01)2,（3460.32)八,(596.12)十六(7 5 3.3 7)八=7 5 3.3 7 O=782+581+380+38-1+78-2 =(491.484375)十(7 5 3.3 7)十六=7 5 3.3 7 H=0 x 7 5 3.3 7=7162+5161+3160+316-1+716-2=(1875.2148)十(7 5 3.3 7)十二=7122+5121+3120+312-1+712-2=(1071.2986)十同一个数串，由于进位制不同其所表达的数值大小也是不同的245的十进制表示记为：245245的二进制表示记为：11110101245的八进制表示记为：365245的十六进制表示记为：F5同一个数值，用不同进位制表达，结果也是不同的数值性信息u示例数值的正负符号处理：机器数的原码、反码和补码数值的符号如何表示呢?数值的正负符号也可和数值一样参与运算：补码运算示意0 1010+)1 110111100(10)+(-3)=(7)0 0111+)0 001101010(+7)+(+3)=(+10)1 1001+)1 010010110(-7)+(-12)=溢出 使用补码可使减法变加法,你相信吗?加减乘除都可转换成加法来实现,加法又可由与、或、非、异或等逻辑运算来实现-只要实现了基本逻辑运算，便可实现任何的计算1 1011+)1 100100101(-5)+(-7)=(-12)u机器可以采用移位、逻辑运算等进行加减乘除运算。例1:10111+10011=?10111+)10011010101101010B 例2:00111 00010=?0011101110 左移一位01110特殊的二进制运算?基于二进制的算术运算 数值的小数点的处理：定点数与浮点数 小数点如何处理呢?bit Binary Digit/1位二进制位/0和1 Byte 字节,8位二进制位 1KB =210字节(市场约1,000字节)1MB =210KB (市场约1,000,000字节)1GB =210MB (市场约1,000,000,000字节)1TB =210GB=220MB 1PB=210TB =230MB 1EB=210PB =240MB注意：2的幂次方为计算单位信息的基本度量单位 信息的度量单位是什么?符号化、计算化与自动化2.1.4 0和1与非数值性信息?0和1与非数值性信息-符号编码与0/1编码-用0/1编码，基于0/1计算非数值性信息可以用编码表示u编码：编码是以若干位数码或符号的不同组合来表示非数值性信息的方法，它是人为地将若干位数码或符号的每一种组合指定一种唯一的含义。例如：0-男，1-女再如：000-星期一 001-星期二 010-星期三 011-星期四 100-星期五 101-星期六 110-星期日再如：000-一院 001-二院 010-三院 011-四院 100-五院 101-六院 110-七院 111-其他 2.1.4 0和1与字母符号-编码 为什么要用编码?编码的三个主要特征u 唯一性：每一种组合都有确定的唯一性的含义u 公共性：所有相关者都认同、遵守、使用这种编码u 易于记忆/便于识认性：有一定规律ASCII码-英文字母符号的编码uASCII码是英文字母与符号的0,1型编码方法，是用7位0和的不同组合来表示10个数字、26个英文大写字母、26个英文小写字母及其一些特殊符号的编码方法，是信息交换的标准编码。uASCII码:American Standard Code for Information Interchange B7B6B5B4B3B2B1B0 0 x x x x x x x 英文字母符号如何编码?ASCII码为什么要用8位来编码?0 0 1 1 0 0 0 1 0 1 0 0 1 1 1 0“1”“N”完整的ASCII码表每8位为一个字符，最高位为041H 5AH:“A”“Z”61H 7AH:“a”“z”0AH:换行符号LF0DH:回车符号CR30H 39H:“0”“9”01000001 A 41 H01000010 B 42 H01000110 F 46 H ASCII编码的规律信息存储解析规则We are students01010111 01100101 00100000 01100001 01110010 01100101 00100000 01110011 01110100 01110101 01100100 01100101 01101110 01110100 011100110/1串按8位分隔一个字符，查找ASCII码表映射成相应符号 使用ASCII码有什么好处?十个数字符号的编码-BCD码BCD码：Binary Coded Decimal(二-十进制编码)是用位和的不同组合，按照与进位制保持一致的关系，来表示10个十进制数字的方法。10个数字，只需4位0/1数码即可十进制0 1 2 3 4 BCD码00000001001000110100十进制5 6 7 8 9 BCD码01010110011110001001 还有哪些编码?为什么需要这些编码?245的十进制记为245 245的二进制记为 11110101 245的八进制记为365 245的十六进制记为F5 245的BCD码记为0010 0100 0101 245的ASCII码记为00110010 00110100 00110101同一信息不同表示方法的对比信息在计算机中为什么需要区分不同的类型?“大”u汉字内码：汉字在计算机内部采用汉字内码存储，汉字内码是一两字节且最高位均为1的0,1型编码计算机内部由外到内由内到外b7 b6 b5 b4 b3 b2 b1 b0 b7 b6 b5 b4 b3 b2 b1 b0 用0和1编码汉字,每个汉字在计算机内部由 2个字节表示0 0 1 1 0 1 0 0 0 1 1 1 0 1 1 1 国标码1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 1 (机)内码汉字的编码 汉字如何进行处理?为什么会有那么多种汉字编码?“型”输入码有若干：拼音码、字型码、区位码 拼音码：xing双拼码：x；其中,x表声母x,而；表韵母ing五笔字型码：gajf其中,g表字根“-”,a表开下的草字头,j表右侧立刀,f表下面土字计算机内部由外到内由内到外u汉字输入码是用键盘上的字母符号编码每一汉字的编码,它使人们通过键入字母符号代替键入汉字。汉字的编码“大”用0和1编码无亮点和有亮点形成字形信息,便于显示 汉字字形码是一种字模点阵码。也有不同的处理汉字点阵信息的编码，如向量编码等oooooo11oooooooooooooo11oooooooooooooo11oooooooooooooo11ooooo1oo1111111111111111oooooo11oooooooooooooo11oooooooooooooo11oooooooooooooo11oooooooooooooo111oooooooooooo11oo1oooooooooo11oooo1oooooooo11ooooo11ooooooo1ooooooo11ooooo1ooooooooo111o 11ooooooooooo1oo计算机内部由外到内由内到外大u汉字字形码是用0和1编码无亮点和有亮点像素,形成汉字字形的一种编码。依据字形码通过显示器或打印机输出汉字。汉字的编码“大”da1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 1 oooooo11oooooooooooooo11oooooooooooooo11oooooooooooooo11ooooo1oo1111111111111111oooooo11oooooooooooooo11oooooooooooooo11oooooooooooooo11oooooooooooooo111oooooooooooo11oo1oooooooooo11oooo1oooooooo11ooooo11ooooooo1ooooooo11ooooo1ooooooooo111o 11ooooooooooo1oo计算机内部由外到内由内到外u汉字处理过程:通过汉字外码输入,以汉字内码存储,以汉字字形码输出汉字的编码进一步学习:u标准ASCII码：8位0,1型编码，最高位始终为0u扩展ASCII码：8位0,1型编码，最高位为0时为标准ASCII码；最高位为1时为扩展ASCII码。uUNICODE:Unicode是国际组织制定的可以容纳世界上所有文字和符号的字符编码方案。Unicode用数字0-0 x10FFFF来映射所有的字符(最多可以容纳1114112个字符，或者说有1114112个码位，码位就是可以分配给字符的数字)。具体实现时，再将前述唯一确定的码位按照不同的编码方案映射为相应的编码，有UTF-8、UTF-16、UTF-32等几种编码方案。还有哪些编码?符号化、计算化与自动化2.1.5 0和1与电子元件?0和1与电子元件-0和1与基本硬件实现-计算自动化实现0和1的基本元器件:电信号和继电器开关u用继电器开关实现基本逻辑运算 数字信号：高电平为1,低电平为001“与”运算电路“或”运算电路“非”运算电路2.1.5 0和1与电子元器件-基本硬件实现 如何用电信号及电子元件表达0和1?实现0和1的基本元器件:二极管u二极管的基本特性FKVFLRI(b)KLRVR(b)处理0和1的基本元件?实现0和1的基本元器件:三极管u 三极管的基本特性：l 开关和放大l以较小的b极电流信号可控制较大的e极流过的电流-放大。大水库大坝闸门控制水第一个三极管试验装置用b点的0和1来控制c点产生1和0典型的三极管电路bc处理0和1的基本元件?用二极管、三极管可实现基本的集成电路:与门、或门和非门u这些电路被封装成集成电路(芯片)，即所谓的门电路。“与”门电路“或”门电路“非”门电路如何用基本电子元件实现基本逻辑运算?基本门电路的符号表示及其特性u与门电路：是实现逻辑与运算的集成电路，即：只有当两个输入端为高电平(1)时，则输出端为高电平(1)；否则，输出端为低电平(0)。u或门电路：是实现逻辑或运算的集成电路，即：只有当两个输入端为低电平(0)时，则输出端为低电平(0)；否则，输出端为高电平(1)。u非门电路：是实现逻辑非运算的集成电路，即：当输入端为高电平(1)时，则输出端为低电平(0)；输入端为低电平(0)时，则输出端为高电平(1)。u异或门电路：是实现逻辑异或运算的集成电路，即：当两个输入端同为高电平(1)或同为低电平(0)时，则输出端为低电平(0)；否则，输出端为高电平(1)。=1&11 与门电路符号或门电路符号非门电路符号异或门电路符号如何用电信号及电子元件实现基本逻辑运算?符号化、计算化与自动化2.1.6 0和1与复杂电路?0和1与复杂电路-复杂硬件部件的实现-分层构造化与构造集成化基于门电路的复杂组合逻辑电路u示例1：一位加法器的示例。2.1.6 0和1与电路-复杂部件的硬件实现如何用已实现的基本逻辑运算(门电路)来实现更复杂的运算?101101001 Ai Bi+CiCi+1 Si基于门电路的复杂组合逻辑电路u可验证一位加法器实现的正确性。基于门电路的复杂组合逻辑电路u示例：多位加法器的实现u用已验证正确的一位加法器，来实现更为复杂的多位加法器u用已验证正确的多位加法器，来实现更为复杂的乘法器/除法器等(略)u分层构造：低层电路已验证正确，可被封装起来；用已封装的已验证的低层电路可构造更为复杂的高层电路；如此一层层构造。基于门电路的复杂组合逻辑电路u另一个示例：2-4译码器及其电路实现。&1 1 A1A0Y00Y01Y10Y11&1 1 A1A0Y00Y01Y10Y1110100100101基于门电路的复杂组合逻辑电路u另一个示例：2-4译码器及其电路实现u可依据门电路的特性，输入2位二进制数01,检查是否是第2条线(Y01)为高电平,有效？u 微处理器芯片即是复杂组合逻辑集成在一块板上并封装而成的电路:从Intel4004在12平方毫米的芯片上集成了2250颗晶体管到Pentium 4处理器内建了4200万颗晶体管，以及采用0.18微米的电路再到英特尔的45纳米Core 2至尊/至强四核处理器上装载了8.2亿颗晶体管。复杂部件的硬件实现(芯片、主板)为什么需要如此多的晶体管呢？基本目标:理解0和1的思维本讲小结语义符号化符号计算化计算0(和)1化0(和)1自动化分层构造化构造集成化；第2讲 符号化、计算化与自动化2014Questions&Discussion?