新編計算機導論 課件 第1章 計算機與計算

計算機與計算新編計算機導論計算機概述01計算理論03計算機的產(chǎn)生與發(fā)展02本章CAPACITY內(nèi)容23計算的概念方法1：研究復雜運算的簡化方法；方法2：設計一些簡單規(guī)則，讓機械來完成計算，即考慮能否讓“機械”代替人按照“規(guī)則”自動計算?！坝嬎恪笔侵浮皵?shù)據(jù)”在“運算符”操作下，基于“規(guī)則”進行的數(shù)據(jù)變換。1.計算機概述“規(guī)則”可以學習與掌握，應用“規(guī)則”進行計算則可能超出人的計算能力，從而無法得到結(jié)果。怎么辦？？狹義的計算是指“數(shù)”的狀態(tài)變換，廣義的計算可以是自然界一切具體的狀態(tài)轉(zhuǎn)換計算本質(zhì)上是對輸入數(shù)據(jù)進行處理，得到一定輸出結(jié)果的過程。4計算的基礎ⅰ.從最右邊的數(shù)字開始相加；ⅱ.如果需要則進1；ⅲ.依次對左邊余下的各位數(shù)字重復上述過程?！坝嬎恪笔腔谒惴ǎ╝lgorithm）的，所謂算法就是為解決一個問題而采取的方法和步驟。1.計算機概述比如，最基本的用紙和筆進行的加法也需要算法，其步驟包括：5計算與自動計算一般要解決下述4個問題數(shù)據(jù)的表示1.計算機概述數(shù)據(jù)的存儲與自動存儲計算規(guī)則的表示計算規(guī)則的執(zhí)行及自動執(zhí)行上述問題促進了機械技術與電子技術的結(jié)合，并導致了現(xiàn)代計算機的產(chǎn)生6什么是計算機計算機（Computer）是一種能夠按照事先存儲的程序，自動、高速地進行大量數(shù)值計算和各種信息處理的現(xiàn)代化智能電子設備。由硬件和軟件所組成，兩者不可分割，沒有安裝任何軟件的計算機稱為裸機。1.計算機概述7計算機的特點最大特點是可以不斷重復地執(zhí)行大量相似動作從而獲得結(jié)果，通過計算可以使只會簡單操作的計算機能夠完成復雜的任務1.計算機概述不同于其他機器，計算機具有存儲功能，無需人工干預即可根據(jù)事先存儲的程序自動完成各種計算計算機的各種復雜功能都源于“計算”的威力8計算機算法一個能夠被計算機處理的，有限長的操作序列1.計算機概述計算機算法可分為兩大類數(shù)值運算算法數(shù)值運算的目的是求數(shù)值解非數(shù)值運算算法應用范圍最為廣泛的算法計算機算法可分為幾類？9思考若能明確乘法的本質(zhì)就是若干相同數(shù)據(jù)的重復加法運算過程，那么問題就不難解決，關鍵是編寫合適的指令序列讓她機械地執(zhí)行在紙上寫0，記住結(jié)果；在所記結(jié)果上加第1個a，記住新結(jié)果；在所記結(jié)果上加第2個a，記住新結(jié)果；依此類推，直至在所記結(jié)果上加第b個a，記住新結(jié)果，即為a×b的積琪琪是一個小學一年級學生，她剛剛學習了加法運算，如果給她一個乘法運算任務，如計算a×b，她能夠完成嗎？1.計算機概述人類的思維是用有限的步驟去解決問題，講究優(yōu)化與簡潔計算機則可以進行大量的、重復地精確運算，并樂此不疲計算機通過重復執(zhí)行大量簡單動作即可完成復雜運算新編計算機導論謝謝觀看10計算機與計算新編計算機導論計算機的產(chǎn)生與發(fā)展計算機史前史01計算機的產(chǎn)生與發(fā)展02本節(jié)CAPACITY內(nèi)容1213文字發(fā)明之前的初期計算工具1.計算機史前史結(jié)繩為記，事大，大結(jié)其繩；事小，小結(jié)其繩，之多少，隨物眾寡。--東漢鄭玄《周易注》14手動式計算工具1.計算機史前史特點：手動輔助數(shù)字計算過程，計算過程/方法（即算法）需要使用者來記錄并操作執(zhí)行算籌算籌的擺法算盤納皮爾計算器計算尺15機械式計算工具1.計算機史前史計算鐘——1623年，德國數(shù)學家謝克哈特發(fā)明第一臺機械式計算設備，計算鐘上部附加一套納皮爾算籌能進行6位加減乘除運算，利用一組互相咬合的齒輪的轉(zhuǎn)動來完成計算，鈴聲輸出答案齒輪上有10根輻條分別表示一個數(shù)字，每當一個齒輪轉(zhuǎn)過一周時，其左邊齒輪則移動一格，并刻痕表示進一位加法器——1642年，帕斯卡發(fā)明齒輪式能實現(xiàn)加減法運算的加法器；用齒輪表示和存儲十進制各數(shù)位上的數(shù)字，低位齒輪每轉(zhuǎn)動10圈，高位齒輪轉(zhuǎn)動一圈機器可自動執(zhí)行一些運算規(guī)則，“數(shù)”在計算過程中自動存儲乘法器——1673年萊布尼茨對加法器進行改進，制造了一臺能夠進行加減乘除四則運算的機械式計算器，實現(xiàn)了計算規(guī)則的自動、連續(xù)、重復執(zhí)行，開辟了自動計算的道路；進行乘法運算時采用進位加方法，該方法后來演化為二進制算術運算規(guī)則，被現(xiàn)代計算機采用這些機器都缺乏程序控制的功能16雅各織布機1804年，法國機械師約瑟夫·雅各發(fā)明了可編程織布機雅各織布機雖然不是計算工具，但是它第一次使用了穿孔卡片這種輸入方式通過讀取穿孔卡片上的編碼信息來自動控制織布機的編織圖案，引起了法國紡織工業(yè)革命1.計算機史前史用孔洞位置或其組合表示信息（紙帶上穿孔為1，無孔為0）17差分機由多個直立銅柱組成，每個銅柱垂直裝配有6個齒輪，齒輪對應的字輪上有0~9，不同的字輪代表十進制的不同位，通過齒輪的彼此咬合傳動完成計算。1822年，英國劍橋大學著名數(shù)學家查爾斯·巴貝奇受編織機啟發(fā)，耗時10年，研制成功第一臺差分機1.計算機史前史可用于計算數(shù)的平方、立方、對數(shù)和三角函數(shù)，能進行8位數(shù)運算，計算精度達6位小數(shù)創(chuàng)新之處有三組字輪作為寄存器（Register）來存放計算中涉及的數(shù)據(jù)可以按預先安排好的計算步驟進行一連串的計算，可以看作是“程序自動控制”思想的萌芽18分析機輸入裝置——穿孔卡片輸入數(shù)據(jù)齒輪式的存儲裝置（“倉庫”）——能存儲1000個50位十進制數(shù)的容量資料處理裝置“工廠”——完成加減乘除，還能根據(jù)運算符號改變計算進程控制裝置——使用指令進行控制，指令通過穿孔卡片順序輸入處理裝置輸出裝置——穿孔卡片或者打印機輸出1833年，巴貝奇設計出分析機模型，模型包含現(xiàn)代計算機所具有的5個基本組成部分1.計算機史前史分析機同樣是以蒸汽引擎驅(qū)動，吸收提花織布機的優(yōu)點，使用打孔卡輸入資料，其中的重要創(chuàng)新是用齒輪模擬算盤的算珠巴貝奇在1835年提到，分析機是一部一般用途的可編程化計算機，其思想超越了當時的科學水平，分析機沒有完成。但在巴貝奇的設計中，它擁有可擴展的內(nèi)存、一個中央處理器、微指令、并使用穿孔卡來編程19機電式計算工具1.計算機史前史圖1Z3計算機（1941年）圖3哈佛大學MarkⅠ（1944年）圖2ABC模型機（1940年）圖4COLOSSUS機（1943年）20第一臺計算機ENIAC運算速度為每秒5000次加法，比已有計算工具快1000倍，當時需要100多名工程師花費1年才能解決的計算問題，它只需要2個小時就能給出答案，一度被譽為“比炮彈還要快的計算機”世界上第一臺電子計算機ENIAC（ElectronicNumericalIntegratorAndCalculator，電子數(shù)字積分儀和計算機）于1946年在美國研制成功ENIAC奠定了電子計算機的發(fā)展基礎，開辟了一個計算機科學技術的新紀元。有人將其稱為人類第三次產(chǎn)業(yè)革命開始的標志2.計算機的產(chǎn)生與發(fā)展耗電量驚人，功率為150千瓦存儲容量小，至多只能存20個字長為10位的十進制數(shù)與后來的存儲程序型的計算機不同，它的程序是外插型的，計算某題目前需要先由人工接通數(shù)條線路，使用不方便使用的仍然是十進制，基本結(jié)構(gòu)和機電式計算機沒有什么區(qū)別21馮·諾依曼計算機1944年，美籍匈牙利數(shù)學家馮?諾依曼參加的原子彈研制項目受阻，主要因為遇到了極為困難的計算問題，在得知ENIAC的研制計劃后，馮?諾依曼加入了研發(fā)工作。經(jīng)過對ENIAC不足之處的認真分析和討論，馮?諾依曼提出了重大的改進理論，即EDVAC（ElectronicDiscreteVariableAutomaticComputer，意為“離散變量自動電子計算機”）方案2.計算機的產(chǎn)生與發(fā)展計算機的基本結(jié)構(gòu)應由五大部件組成：運算器、控制器、存儲器、輸入設備和輸出設備，并描述了這五部分的職能和相互關系計算機應采用二進制形式表示數(shù)據(jù)和指令提出了“二進制”與“存儲程序”的設計思想1945年6月，馮?諾依曼發(fā)表計算機史上著名的“101頁報告”，報告對EDVAC計劃進行了描述，馮諾依曼思想的核心要點如下22馮·諾依曼計算機馮·諾依曼思想標志著自動運算的實現(xiàn)和電子計算機的成熟，該思想已成為電子計算機設計的基本原則“存儲程序”概念被譽為“計算機發(fā)展史上的一個里程碑”，它確定了現(xiàn)代電子計算機硬件的基本結(jié)構(gòu)，奠定了現(xiàn)代計算機的基礎2.計算機的產(chǎn)生與發(fā)展計算機科學界把采用0、1符號編碼方法和存儲程序方法設計的計算機稱為馮·諾依曼計算機世界上第一臺存儲程序計算機是劍橋大學研制的電子延遲存儲自動計算機EDSAC（ElectronicDelayStorageAutomaticCalculator），于1949年投入運行23計算機的發(fā)展階段（按照采用的電子器件劃分）第一代計算機（1946——1957年）第二代計算機（1958——1964年）2.計算機的產(chǎn)生與發(fā)展第三代計算機（1965——1970年）第四代計算機（1971s—）新一代計算機電子管計算機，主要邏輯元件采用電子管晶體管計算機，主要邏輯元件采用晶體管中/小規(guī)模集成電路計算機大規(guī)模/超大規(guī)模集成電路計算機1980s年代提出，也稱第五代計算機，是各種未來型計算機的總稱，將改變傳統(tǒng)馮·諾依曼結(jié)構(gòu)，具有利用已有知識進行推理判斷、聯(lián)想和學習功能的新型智能化計算機系統(tǒng)新編計算機導論謝謝觀看24計算機與計算新編計算機導論計算理論可計算性01計算復雜性02本節(jié)CAPACITY內(nèi)容2627可計算性需要計算的問題多種多樣，什么樣的問題才是可計算的？這是關系到計算機能做什么、不能做什么的根本問題。3.計算理論可計算性理論（ComputabilityTheory）是研究計算的一般性質(zhì)的數(shù)學理論，其中心課題就是將算法這一概念精確化，建立計算的數(shù)學模型，研究哪些是可計算的，哪些是不可計算的。下面將列舉若干計算學科的典型實例對上述問題進行說明由于計算與算法相連，因此也將可計算性理論稱為算法理論?？捎嬎銌栴}是指存在算法可解的問題，不可計算問題則是不存在算法可解的問題。通俗來說，若存在一個機械的過程，對給定的某個輸入，若能在有限步內(nèi)給出答案，則該問題就是可計算的。28排序問題目前已知有幾十種排序算法，如最簡單的插入排序和冒泡排序?qū)臻g要求不高，但時間效率低，其時間復雜度為O(n2)3.計算理論歸并排序、希爾排序等對空間要求高，但時間效率穩(wěn)定在較高水平，其時間復雜度為O(nlog2n)排序問題是計算科學中一個十分重要的問題，需結(jié)合具體問題選擇合適的排序算法，但無論何種算法，排序問題都是可以計算的，并且計算代價不高29漢諾塔問題在印度北部的世界中心貝拿勒絲的圣廟里，一個黃銅板上插著三根寶石針A、B、C，印度教主神梵天在創(chuàng)造世界時，將其中一根針由下到上穿好了由大至小排列的64片金片。不分白晝總有一個僧侶按照下述法則移動金片：一次只移動一片，必須保證小片在大片上面。3.計算理論僧侶們預言，當所有的金片都從梵天穿好的那根針上移動到另一根針上時，世界就將在一聲霹靂中消失，梵塔、廟宇和眾生都將同歸于盡！漢諾塔問題求解使用遞歸算法，假設有n片，移動次數(shù)是f(n)。顯然f(1)=1,f(2)=?,f(3)=？f(k+1)=2*f(k)+1可以證明f(n)=2n-1當n=64時，f(64)=18446744073709551615，若每秒移動一次，共需要多久？一年31536000秒，則需584942417335年，即5849億年以上，太陽系的預期壽命不過數(shù)百億年此問題理論上可計算，實際上不可行，屬于算法的時間復雜度問題3731國王的婚姻從前，有個酷愛數(shù)學的年輕國王向鄰國一位美麗聰明的公主求婚，公主給國王出了一道題：求出48770428433377171的一個真因子。國王若在一天內(nèi)求出，公主便會接受他的求婚。3.計算理論國王回去后立刻開始逐個數(shù)進行計算，從早到晚，共算了3萬多個數(shù)，仍未求出結(jié)果。國王向公主求情，公主告訴答案：223092827是一個真因子，公主說：“我再給你一次機會，如果還求不出，將來你只好做我的證婚人了。”國王應該怎么辦？32國王的婚姻問題求解國王請教國內(nèi)時任宰相的大數(shù)學家：數(shù)學家在思考分析后發(fā)現(xiàn)，該數(shù)為17位，其最小的一個真因子不會超過9位，然后給國王出了一個主意。3.計算理論按自然數(shù)順序給全國百姓每人編一個號發(fā)下去，公主給出題目后立即通報全國，讓每個百姓用自己的編號去驗證，除盡則立即上報并賞金萬兩。國王最后求婚成功什么主意？？33國王的婚姻故事帶來的啟示故事就是一個求大數(shù)真因子的問題，由于數(shù)字很大，國王第一次采用的是一種順序的求解算法，其復雜性表現(xiàn)在時間復雜性方面，時間消耗非常大；3.計算理論宰相采用的是并行的方法，國王通過將可能的數(shù)字分發(fā)給百姓，才能在有限的時間內(nèi)求取結(jié)果，復雜性體現(xiàn)在空間資源方面；雖然宰相的方法增加了空間復雜度，但大大降低了時間的消耗，這就是非常典型的分治法，也就是將復雜的問題分而治之，這也是我們面臨很多復雜問題時經(jīng)常會采用的解決方法，也可將該方法作為并行的思想看待，而這種思想在計算機中的應用比比皆是，如現(xiàn)在CPU的發(fā)展。34計算復雜性在實際應用中，對于某個特定問題，需考慮計算的難度有多大、計算所需付出的代價如何？3.計算理論計算復雜性理論將多項式時間復雜性作為易解問題（P類問題）與難解問題（NP類問題）的分界線。35計算復雜性之P類問題P（polynominal，多項式）類問題是指在多項式時間內(nèi)可解的問題類，此類問題為易解問題，如排序問題3.計算理論事實上，典型的多項式（如n3）與典型的指數(shù)（如2n）在增長率上存在巨大的差異比如，當n=1000時，n3是10億，雖然是大數(shù)，但還可以處理，而2n則是一個比宇宙中的原子數(shù)還大得多的數(shù)因此，多項式時間的算法是高效的，指數(shù)時間的算法是低效的36計算復雜性之NP類問題NP（

nondeterministic

polynominal，非確定性多項式）類問題是指在多項式時間內(nèi)可驗證的問題類，或者說可以在多項式時間內(nèi)猜出一個解的問題類，此類問題為難解問題，如漢諾塔問題，TSP問題等3.計算理論非確定性是一種技術表達，指可以猜測到正確答案并在多項式時間內(nèi)驗證經(jīng)驗表明，驗證某個解要比求出某個解容易比如大整數(shù)的因式分解問題，如果求9938550的兩個因數(shù)是比較困難的但若有人很幸運的猜出并告訴你這兩個數(shù)是1123和8850時，為了判斷這個猜想是否正確，你可以很容易的用最簡單的計算器進行驗證對于難解的問題，不可能每次都能幸運的猜到正確解，不知道是否存在一個多項式時間的算法，每次都能解決該問題37難解問題之求解思想弄清問題困難的根源后，可能會做某些改動，使問題變得容易解決；求問題的一個并不完美的解，在某些情況下，尋找問題的近似最優(yōu)解會相對容易一些。面對難解的問題時往往可以有若干選擇3.計算理論比如，課程表的安排必須滿足一些限制（如兩個班不能在同一時間同一教室上課等）如果有1000個班需要排課，即使用一臺超級計算機，也可能需要花費若干世紀的時間才能制定出一份最好的課程表。38經(jīng)典NP類問題-TSP問題物流配送問題歸結(jié)為帶時間窗的TSP；汽車生產(chǎn)線上汽車涂色問題對應為非對稱TSP。TSP問題一直是算法分析與設計領域的一個重要研究內(nèi)容，也是研究算法時經(jīng)常采用的一個經(jīng)典實例。3.計算理論現(xiàn)實世界中很多問題最終都可以歸結(jié)為TSP問題，應用領域遍及傳統(tǒng)的物理、化學、計算機科學、機器人、集成電路布線、工件排序、生產(chǎn)調(diào)度等科技、管理和社會生活等諸多領域。比如：39TSP問題描述TSP問題又稱旅行商問題：一位商人要去n個城市推銷貨物，所有城市走一遍后再回到起點，如何事先確定一條最佳線路，使其旅行費用最少。3.計算理論假設有A、B、C、D四個城市，城市間距離如圖所示：共有多少可能路徑？ABCD224466ABCDA路徑長：4+6+4+6=20ABDCA路徑長：4+2+4+2=12ACBDA路徑長：2+6+2+6=16ACDBA路徑長：2+4+2+4=12ADBCA路徑長：6+2+6+2=16ADCBA路徑長：6+4+6+4=2040旅行商問題求解分析若城市數(shù)為n，則組合路徑數(shù)為(n-1)!3.計算理論隨著城市數(shù)目的不斷加大，組合路線數(shù)將呈指數(shù)級規(guī)律急速增長，以致無法計算，即所謂組合爆炸問題如有20個城市，組合路徑數(shù)為：（20-1）!≈1.216*1017若按計算機以每秒1000萬條路線的速度計算：需386年！！41旅行商問題求解方法（續(xù)）3.計算理論TSP問題屬于NP類問題，本質(zhì)上難以求解，雖然無法找到其有效算法，但在實際應用中必須解決，常采用的方法如精確算法，如割平面法、分支定界法、動態(tài)規(guī)劃法等，此類方法能求解的問題規(guī)模較小，實用性較差；啟發(fā)式算法（或近似算法），如插入算法、最近鄰算法、CW算法等智能算法，如遺傳算法、模擬退火算法、蟻群算法等近些年出現(xiàn)了機器學習算法42計算復雜性與加密技術3.計算理論可計算性理論與計算復雜性理論密切相關，前者把問題分成可解和不可解的；后者則是把問題分成容易計算和難以計算的。受計算復雜性理論直接影響的一個應用領域是密碼技術。在絕大多數(shù)領域中，選擇容易計算的問題比選擇難計算的問題更可取，因為容易問題的求解代價更小。密碼技術則與眾不同，它特別需要難計算的問題，從而加大密碼被破解的難度，公開密鑰密碼系統(tǒng)RSA就是一個典型的例子。43RSA非對稱加密算法3.計算理論RSA是最著名、使用最廣泛的一種公鑰加密算法，1977年由RonRivest、AdiShamirh和LenAdleman在麻省理工開發(fā)，RSA