《計算與人工智能概論》計算與人工智能概述

計算與人工智能概論計算與人工智能概述

計算的概念1PART1.1.1什么是計算什么是計算？在計算機(jī)科學(xué)領(lǐng)域，計算是根據(jù)設(shè)定的規(guī)則將一串編碼轉(zhuǎn)換成另一串編碼的過程。例如：加法問題，輸入一對數(shù)值，輸出是該對數(shù)值的和。排序問題，排序計算對每個輸入表都賦予一個輸出表，而輸出表的數(shù)據(jù)項與輸入表一樣，只是輸出表的數(shù)據(jù)項是按照升序或降序排列的。在數(shù)學(xué)領(lǐng)域，計算是抽象數(shù)學(xué)思想在具體數(shù)據(jù)上的應(yīng)用，例如用數(shù)字進(jìn)行加、減、乘、除的運(yùn)算。1.1.1什么是計算什么是計算？在計算機(jī)科學(xué)領(lǐng)域，計算是根據(jù)設(shè)定的規(guī)則將一串編碼轉(zhuǎn)換成另一串編碼的過程。例如：加法問題，輸入一對數(shù)值，輸出是該對數(shù)值的和。排序問題，排序計算對每個輸入表都賦予一個輸出表，而輸出表的數(shù)據(jù)項與輸入表一樣，只是輸出表的數(shù)據(jù)項是按照升序或降序排列的。在數(shù)學(xué)領(lǐng)域，計算是抽象數(shù)學(xué)思想在具體數(shù)據(jù)上的應(yīng)用，例如用數(shù)字進(jìn)行加、減、乘、除的運(yùn)算。1.1.1什么是計算計算的歷史1.1.1什么是計算可計算問題計算模型之一：圖靈機(jī)（Turingmachine）阿蘭·麥席森·圖靈于1936年在其發(fā)表的論文《論可計算數(shù)及其在判定問題中的應(yīng)用》中，針對可計算邊界問題提出了一種抽象的計算模型——圖靈機(jī)圖靈將邏輯中的任意命題用圖靈機(jī)來表示和計算，并按照規(guī)則推導(dǎo)出結(jié)論，其結(jié)果是——可計算函數(shù)等價子圖靈機(jī)能計算的函數(shù)圖靈機(jī)的提出證明了通用計算理論，肯定了計算機(jī)實現(xiàn)的可能性，同時它給出了計算機(jī)應(yīng)有的主要架構(gòu)，這為計算機(jī)的誕生和發(fā)展提供了理論基礎(chǔ)可計算邊界問題：哪些問題是可計算的，哪些問題是不可計算的？求解思路：為計算建立一個數(shù)學(xué)模型，稱之為計算模型，然后證明，凡是這個計算模型能夠解決的問題，就是可計算的問題。1.1.2圖靈機(jī)基本原理圖靈機(jī)的基本原理是用機(jī)器來模擬人們用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過程。圖靈機(jī)將一個無限長的帶子作為無限存儲，它有一個讀寫頭，能在帶子上讀、寫和左右移動。圖靈機(jī)開始運(yùn)作時，帶子上只有輸入串，其他地方都是空白，如果需要保存信息，則其可以將相關(guān)信息寫在帶子上。為了讀取已經(jīng)寫下的信息，它可以將讀寫頭往回移動到這個信息所在的位置。機(jī)器不停地計算，直到產(chǎn)生輸出為止。1.1.2圖靈機(jī)圖靈機(jī)執(zhí)行計算的具體案例利用圖靈機(jī)執(zhí)行“1+2=3”的計算。先定義讀頭讀到“+”之后，依次移動讀頭兩次并讀取格子中的數(shù)據(jù)；接著讀頭進(jìn)行計算，最后把計算結(jié)果寫入第二個數(shù)據(jù)的下一個格子里，1.1.3什么是計算機(jī)馮·諾依曼體系結(jié)構(gòu)輸入設(shè)備輸出設(shè)備程序運(yùn)行1.1.3什么是計算機(jī)計算機(jī)系統(tǒng)：硬件層+操作系統(tǒng)層+應(yīng)用軟件層硬件系統(tǒng)軟件操作系統(tǒng)應(yīng)用軟件工具軟件語言處理系統(tǒng)數(shù)據(jù)庫管理系統(tǒng)政務(wù)軟件娛樂軟件學(xué)習(xí)軟件1.1.3什么是計算機(jī)計算機(jī)硬件傳統(tǒng)“計算機(jī)器”多樣化的“計算機(jī)器”，各種設(shè)備的“大腦”系統(tǒng)在探索最短路徑的過程中，首先需要從鍵盤輸入機(jī)器人所處環(huán)境的地圖，然后由操作系統(tǒng)將地圖數(shù)據(jù)傳送到內(nèi)存，由中央處理器對數(shù)據(jù)進(jìn)行運(yùn)算并獲得結(jié)果，最后在顯示器上輸出尋找到的最短路徑。1.1.3什么是計算機(jī)計算機(jī)硬件中央處理器是計算機(jī)的核心硬件，它往往以處理器芯片的形式存在。在現(xiàn)實生活中，各類處理器芯片無處不在，多樣化的計算機(jī)控制著各種機(jī)械設(shè)備運(yùn)行。交通中的汽車、平衡車等，日常生活中的冰箱、洗衣機(jī)等智能家居設(shè)備，都與處理器芯片緊密相關(guān)。1.1.3什么是計算機(jī)計算機(jī)軟件硬件有形，而軟件無形。計算機(jī)軟件多種多樣。它可以是計算機(jī)系統(tǒng)中的各類程序，也可以是用戶與硬件之間的接口程序，還可以是運(yùn)行在硬件上的各種程序的總稱智能終端應(yīng)用軟件軟件供應(yīng)商網(wǎng)上商城商品供應(yīng)商1.1.3什么是計算機(jī)計算機(jī)是什么?認(rèn)知世界的工具各種機(jī)器的大腦各種軟件的載體創(chuàng)建虛擬世界的工具計算的工具1.1.4算法、計算機(jī)語言與程序算法、計算機(jī)語言與程序之間的關(guān)系1.1.4算法、計算機(jī)語言與程序高級語言源程序及其編譯過程示意-以智能機(jī)器人尋路計算兩點間距離為例求智能機(jī)器人在環(huán)境中行走的最短路徑時，需要重復(fù)不斷地求出當(dāng)前位置與下一位置之間的距離。假設(shè)已知機(jī)器人已經(jīng)行走的距離為2cm，機(jī)器人還需要往前走4cm，那么機(jī)器人總共需要行走的路徑長度為多少呢？算法、計算機(jī)語言與程序之間的關(guān)系1.1.4算法、計算機(jī)語言與程序從二進(jìn)制機(jī)器語言到計算機(jī)語言計算機(jī)語言的發(fā)展1.1.4算法、計算機(jī)語言與程序問題求解策略與算法用兩種不同的算法解決求解機(jī)器人行走的最短距路徑問題針對最短距路徑求解問題，我們可以將其抽象為一個組合優(yōu)化問題，即：機(jī)器人從起點走到終點的過程中，有n個節(jié)點需要訪問，按怎樣的次序訪問，才能使機(jī)器人訪問路徑的“權(quán)值和”最小？遍歷算法基本思想：利用遍歷算法求解最短距路徑時，可以把復(fù)雜的路徑分解求解，把可能短的每一條路徑通過窮舉法列舉出來，再比較得出最短距路徑，該最短距路徑即為問題的解。時間復(fù)雜性：O(n!)。貪心算法基本思想：利用貪心算法求解最短距路徑時，從某一個節(jié)點開始，每次選擇一個節(jié)點，直到所有節(jié)點都被選完。時間復(fù)雜性：多項式量級O(n3)。貪心算法犧牲了結(jié)果的精度（即求得的不一定是最優(yōu)解），但換來了時間上可觀的節(jié)約，如將算法復(fù)雜度直接降到多項式量級O(n3)。1.1.4算法、計算機(jī)語言與程序問題求解策略與算法用兩種不同的算法解決求解機(jī)器人行走的最短距路徑問題遍歷算法流程圖貪心算法流程圖什么是計算思維？2PART1.2.1計算思維的概念計算思維的概念周以真教授在美國計算機(jī)權(quán)威期刊《CommunicationsoftheACM》雜志上給出，并定義的計算思維（ComputationalThinking）：計算思維是運(yùn)用計算機(jī)科學(xué)的基礎(chǔ)概念進(jìn)行問題求解、系統(tǒng)設(shè)計、以及人類行為理解等涵蓋計算機(jī)科學(xué)之廣度的一系列思維活動。計算思維教學(xué)改革宣言2013年2006年教育部高等學(xué)校大學(xué)計算機(jī)課程教學(xué)指導(dǎo)委員會發(fā)表旨在大力推進(jìn)以計算思維為切入點的計算機(jī)教學(xué)改革宣言。教育與科學(xué)思維；計算機(jī)教育與計算思維；人才培養(yǎng)與計算思維教學(xué)改革；構(gòu)建多方位、立體化人才培養(yǎng)平臺。CMU計算機(jī)系主任/學(xué)術(shù)事務(wù)副校長NSF信息學(xué)部主任微軟研究院副總裁哥倫比亞大學(xué)數(shù)據(jù)科學(xué)研究院主任1.2.1計算思維的概念計算思維的概念計算思維是人類應(yīng)具備的第三種思維理論思維:假設(shè)/預(yù)設(shè)定義/性質(zhì)/定理證明.---推理和演繹實驗思維:實驗觀察發(fā)現(xiàn)、推斷與總結(jié).---觀察與歸納計算思維:設(shè)計,構(gòu)造與計算.---設(shè)計與構(gòu)造計算思維關(guān)注的是人類思維中有關(guān)可行性、可構(gòu)造性和可評價性的部分當(dāng)前環(huán)境下，理論與實驗手段在面臨大規(guī)模數(shù)據(jù)的情況下，不可避免地要用計算手段來輔助進(jìn)行。1.2.2問題求解方法Google計算思維計算思維（CT）是一個有著諸多特點和要求的問題解決過程?？捎糜诮鉀Q人文科學(xué)、數(shù)學(xué)和科學(xué)等各種學(xué)科的問題。不但能了解各學(xué)科之間的關(guān)聯(lián)，同時也能夠體會到課外生活與課堂內(nèi)的知識之間的聯(lián)系。分解：把數(shù)據(jù)、過程或問題分解成更小的、易于管理的部分。模式識別：觀察數(shù)據(jù)的模式、趨勢和規(guī)律。抽象：識別模式形成背后的一般原理。算法設(shè)計：為解決某一類問題撰寫一系列詳細(xì)步驟1.2.2問題求解方法計算思維與計算機(jī)科學(xué)的區(qū)別1.2.2問題求解方法計算思維案例1：分解分解：分解就是把大問題拆解成小問題，把復(fù)雜問題拆解成簡單問題，把新問題拆分成老問題。對于一塊大蛋糕，如果不切開，吃起來是非常困難的。使用工具把它分成一小塊一小塊來吃，一小塊也不可能一次吃完，還要一口一口吃。1.2.2問題求解方法計算思維案例2：模式識別模式識別：尋找問題內(nèi)或者子問題之間的模式、規(guī)律或者趨勢。簡單來說，就是找規(guī)律。一個蘋果的價格是3元，3個蘋果是9元，即單價乘上數(shù)量，現(xiàn)在知道一個梨子是4元，5個梨子多少錢？模式：單價*數(shù)量=總價1.2.2問題求解方法計算思維案例3：模式歸納模式發(fā)掘就是探索學(xué)科案例中蘊(yùn)含的一些模式，并形成一套您獨有的、借助模式識別方法進(jìn)行問題研究的流程。1.2.2問題求解方法計算思維案例4：抽象抽象：指事物相關(guān)和重要的信息，它涉及從無關(guān)細(xì)節(jié)中分離出核心信息。抽象是計算思維的核心。1.2.2問題求解方法計算思維案例5：算法設(shè)計算法設(shè)計：完成某項任務(wù)的一系列指令，即解決問題的方案（步驟）。步驟中又包含分解，抽象，及模式識別，它就像一條線，串起計算思維在各個領(lǐng)域的應(yīng)用。例如火星機(jī)器人著陸后，如何在無人控制情況下，實現(xiàn)自動尋路呢？1分解：在控制火星機(jī)器人翻越前面障礙的過程當(dāng)中，機(jī)器人要左右移動，可以把它分解成左移或者是右移的動作。2模式：左移的模式與右移類似，左移設(shè)計好了，直接運(yùn)用到右移即可。3抽象：機(jī)器人與障礙物的處理可以將機(jī)器人抽象成多邊形，通過計算多邊形之間是否重疊來判斷其是否撞到障礙物導(dǎo)致游戲失敗。4算法：實現(xiàn)程序，依次完成角色導(dǎo)入（即背景，、火星機(jī)器人、障礙圖標(biāo)等）、設(shè)定機(jī)器人初始位置、控制機(jī)器人上下移動、背景移動，設(shè)計碰撞檢測算法等。1.2.3算法-計算系統(tǒng)的靈魂算法、數(shù)據(jù)和計算能力是人工智能的三大基石，其中算法是非常重要的一個部分。好的算法能節(jié)約很多資源，甚至能夠完成一些不可能完成的任務(wù)。在任何應(yīng)用領(lǐng)域，精心設(shè)計的算法都是解決大型問題最有效的方法。人工智能機(jī)器學(xué)習(xí)算法包括包括監(jiān)督學(xué)習(xí)、無監(jiān)督學(xué)習(xí)、半監(jiān)督學(xué)習(xí)，強(qiáng)化學(xué)習(xí)、深度學(xué)習(xí)、遷移學(xué)習(xí)、強(qiáng)化學(xué)習(xí)等。人工智能機(jī)器學(xué)習(xí)算法分類人工智能之機(jī)器學(xué)習(xí)算法探索人工智能3PART1.3.1智能移動機(jī)器人路徑規(guī)劃智能移動機(jī)器人路徑規(guī)劃路徑規(guī)劃環(huán)境示意圖本質(zhì)智能移動機(jī)器人路徑規(guī)劃是一個集環(huán)境感知、動態(tài)決策與規(guī)劃、行為控制與執(zhí)行等多種問題于一體的綜合人工智能例子，它融合了計算機(jī)技術(shù)、自動控制、傳感器技術(shù)、信息處理以及人工智能等多學(xué)科知識，是目前科學(xué)技術(shù)發(fā)展最活躍的領(lǐng)域之一。問題描述：讓一個智能機(jī)器人從迷宮的起點S出發(fā)，自動繞過迷宮內(nèi)的障礙物，并使用最少的時間走到迷宮終點E。智能機(jī)器人：包含有機(jī)身、電源、傳感器、微處理器、電機(jī)及驅(qū)動等部分，智能機(jī)器人利用傳感器感知檢測前方、左邊、右邊是否有障礙物，在電機(jī)控制下可以執(zhí)行直行、左轉(zhuǎn)、右轉(zhuǎn)等運(yùn)動及避障行為。環(huán)境地圖：有起點與終點，有墻，有墻與墻之間的通道，外圍有邊界。問題描述1.3.1智能移動機(jī)器人路徑規(guī)劃計算思維首先是需要將問題分解成一系列較小可管理的問題過程。智能移動機(jī)器人路徑規(guī)劃問題可以分解為兩個子問題：子問題1

機(jī)器人對地圖的“記憶”子問題2探索機(jī)器人在環(huán)境中行走時可能面對的情況以及該采取的行動

子問題1地圖的構(gòu)建與表示機(jī)器人對環(huán)境的記憶子問題2智能移動機(jī)器人遇到的狀況機(jī)器人的行動

左邊有墻，前邊沒有墻左邊沒墻左邊有墻，前邊也有墻智能移動機(jī)器人路徑規(guī)劃問題分解問題分解1.3.1智能移動機(jī)器人路徑規(guī)劃人（蒙上眼睛）機(jī)器人靠墻行走靠墻行走用手搜索用紅外避障傳感器感知雙手配合用兩個紅外避障傳感器模式識別是要觀察找出問題的模式、趨勢和規(guī)律。人尋路：用兩只手配合并沿著墻壁探索路線的時候，我們能夠在各種狀況下（如拐角）很好地做出相應(yīng)的判斷，并順利找到出口機(jī)器人尋路：將紅外傳感器嵌入機(jī)器人，作為機(jī)器人的“雙臂”，用以感知檢測前方、左邊、右邊是否有障礙物智能移動機(jī)器人尋路與人尋路相似之處模式識別1.3.1智能移動機(jī)器人路徑規(guī)劃模式挖掘（抽象）即探尋模式形成背后的一般原理，尋找一類問題的一般方法。地圖構(gòu)建將地圖劃分成網(wǎng)格，藍(lán)色格子代表墻壁，白色格子代表路地圖抽象把地圖轉(zhuǎn)換為數(shù)學(xué)形式，用1和0分別定義藍(lán)色格子和白色格子機(jī)器人狀態(tài)行為抽象機(jī)器人感知探測不同狀態(tài)時對應(yīng)執(zhí)行不同動作地圖構(gòu)建地圖抽象機(jī)器人狀態(tài)行為抽象抽象1.3.1智能移動機(jī)器人路徑規(guī)劃算法設(shè)計即為解決某一類問題撰寫一系列詳細(xì)的指令。以智能移動機(jī)器人尋路左手定則的算法流程為例：檢測左側(cè)是否有墻：如果沒有則左轉(zhuǎn)，如果有則執(zhí)行②；檢測前方是否有墻；如果沒有則直行，如果有則執(zhí)行③；檢測右側(cè)是否有墻；如果沒有則右轉(zhuǎn)，如果有則左轉(zhuǎn)；直到移動機(jī)器人到達(dá)目的終點，完成任務(wù)。智能移動機(jī)器人尋路（左手定則）算法設(shè)計1.3.2人工智能歷史圖靈測試圖靈測試是區(qū)分人與人工智能設(shè)備的一個測試，測試中要求一個人和一臺擁有智能的機(jī)器設(shè)備在互不相知的情況下，進(jìn)行隨機(jī)的提問交流，如果超過3成的測試者沒有發(fā)現(xiàn)對方是機(jī)器設(shè)備，就代表這臺設(shè)備擁有“人類智能”。聊天機(jī)器人尤金.古斯特曼清華大學(xué)語音與語言實驗中心(CSLT)研發(fā)的作詩機(jī)器人“薇薇”1.3.2人工智能歷史圖靈測試和人工智能的關(guān)系“全部智能行為”對應(yīng)的集合和“全部人類行為”集合之間有相交部分也有不同之處。全部智能行為和全部人類行為之間的交集（如猴媽媽分桃）即可通過圖靈測試。猴媽媽擁有部分智能行為，可以將一堆桃子較為公平的分給3個兒子，但她并不具有全部人類行為，但我們可以說其擁有智能并可通過圖靈測試。類似的機(jī)器人擁有某一項智能行為，比如自然語言處理、圖像識別等，并不一定要擁有全部人類行為，但仍可通過圖靈測試。因此，主流的人工智能是以解決人腦能解決的問題為目標(biāo)，注重解題能力，而不在乎解題行為是否和人類相似。1.3.2人工智能歷史人工智能領(lǐng)域關(guān)鍵事件時間軸1.3.3人工智能相關(guān)研究人工智能近10年“十大人工智能研究熱點”人工智能涉及計算機(jī)科學(xué)、電子、自動控制、機(jī)械、心理學(xué)、倫理學(xué)、哲學(xué)和語言學(xué)等多個學(xué)科，幾乎涵蓋自然科學(xué)和社會科學(xué)的所有學(xué)科，其范圍已遠(yuǎn)遠(yuǎn)超出了計算機(jī)科學(xué)的范疇，它的終極目標(biāo)是使機(jī)器擁有像人類一樣的智力，可以替代人類實現(xiàn)學(xué)習(xí)、推理、思考、規(guī)劃等多種功能。從應(yīng)用的角度看，人工智能的研究主要集中在以下幾個方面：機(jī)器人、語音識別、模式識別、自然語言處理、專家系統(tǒng)、計算機(jī)視覺、計算智能、自動程序設(shè)計、智能控制與智能規(guī)劃等。AMiner評選出的近10年“十大人工智能研究熱點”1.3.3人工智能相關(guān)研究1.3.3人工智能相關(guān)研究人工智能研究案例在航天領(lǐng)域，人工智能已經(jīng)成為中國航天的“探路者”，例如火星探測器?！疤靻栆惶枴笔褂昧嘶谟嬎銠C(jī)視覺、自然語言處理、機(jī)器學(xué)習(xí)、語音識別等技術(shù)的人工智能技術(shù)。人臉檢測的任務(wù)就是判斷給定的圖像上是否存在人臉，如果人臉存在，就給出全部人臉?biāo)幍奈恢眉捌浯笮　?.3.3人工智能相關(guān)研究人工智能研究案例AlphaGo的實現(xiàn)原理給勝率高的點分配更多的計算力任意時間算法，計算越多越精確1、選取2、展開3、評