集合論與圖論.ppt

集合論與圖論SetTheoryandGraphTheory,主講：姜守旭博士/教授/教學(xué)帶頭人/博導(dǎo)助教：馮誠辦公室：綜合樓808辦公電話：86403492-808手機mail：jsx課程網(wǎng)站：,SchoolofComputerScience&TechnologyHarbinInstituteofTechnology,2019/12/6,2,課程性質(zhì),48學(xué)時是一門專業(yè)基礎(chǔ)課，本專業(yè)最重要的課程之一需要一些工科數(shù)學(xué)分析、線性代數(shù)的知識是數(shù)學(xué)(離散數(shù)學(xué))的一部分，數(shù)學(xué)首先是一些工具，其次是一門語言，最后還是一種素養(yǎng),集合論與圖論是數(shù)學(xué)的一部分,“對于大自然這本奧秘無窮的書，我讀不懂”。莎士比亞安東尼和克里奧帕特拉（15641616）“如果不理解它的語言，沒有人能讀懂宇宙這本偉大的書，它的語言就是數(shù)學(xué)”。伽里略（15641642）“在任何特定的理論中，只有其中包含數(shù)學(xué)的部分才是真正的科學(xué)”康德（17241804）,集合論與圖論是數(shù)學(xué)的一部分,“一門科學(xué)，只有當它能夠運用數(shù)學(xué)時，才算真正發(fā)展了?！瘪R克思（18181883）數(shù)學(xué)不專屬自然科學(xué)，也不專屬社會科學(xué)，更不專屬于文學(xué)藝術(shù)。它是一種宇宙語言，為一切文明生物共有、共享。,2019/12/6,5,主要內(nèi)容,工大80年開始將離散數(shù)學(xué)分成三門課：集合論與圖論、近世代數(shù)、數(shù)理邏輯集合論集合及其運算、映射及其合成、關(guān)系及其運算、無窮集合及其基數(shù)。圖論圖的一些基本概念、一些特殊的圖、樹及其性質(zhì)、割點和橋、連通度、平面圖、圖的著色、有向圖。,教學(xué)目的,該課程的設(shè)置主要是為了培養(yǎng)學(xué)生的抽象思維和邏輯推理能力，提高學(xué)生分析問題和解決問題的能力，提高學(xué)生的數(shù)學(xué)修養(yǎng)及計算機科學(xué)素質(zhì)。本課程為后繼的專業(yè)基礎(chǔ)課及專業(yè)課提供必要的數(shù)學(xué)工具，為描述離散模型提供數(shù)學(xué)語言。要想用計算機解決問題就要為它建立數(shù)學(xué)模型，即描述研究對象及對象與對象之間的聯(lián)系，并通過事物之間的聯(lián)系找出事物的運動規(guī)律。集合論與圖論為此提供了強有力的描述工具與推理理論。,2019/12/6,6,基本思想,我們從“集合”這個基本概念開始建立集合理論。就某種觀點來看，“集合”與“性質(zhì)”是同義詞，是基本概念之一。集合用來描述事物的性質(zhì)我們的研究對象，映射用來描述事物之間的聯(lián)系運算、關(guān)系，從而為集合建立了結(jié)構(gòu)。于是，為建立系統(tǒng)的數(shù)學(xué)模型提供了數(shù)學(xué)描述語言工具，代數(shù)系統(tǒng)就是引入運算以后的集合。,基本思想,集合論又提供了研究數(shù)學(xué)模型的性質(zhì)，發(fā)現(xiàn)新聯(lián)系的推理方法，從而找出事物的運動規(guī)律。圖論是上述思想的一個具體應(yīng)用，事實上，圖論為任何一個包含了一種二元關(guān)系的系統(tǒng)提供了一個數(shù)學(xué)模型；部分地，也因為使用了圖解式表示方法，圖就具有一種直觀的和符合美學(xué)的外形。在圖論中，許多結(jié)果是初等的，但也有大量的十分復(fù)雜的問題可以難倒最老練的數(shù)學(xué)家。,在計算機專業(yè)中的意義,能形式化就能自動化。對計算機專業(yè)而言，形式化尤為重要。利用形式化描述給程序設(shè)計提供了方便，從而實現(xiàn)了自動化。,在計算機專業(yè)中的意義,集合論可以看成一種通用語言，一切必要的數(shù)據(jù)結(jié)構(gòu)都可以由集合這個原始的數(shù)據(jù)結(jié)構(gòu)而構(gòu)造出來。實際上，數(shù)學(xué)發(fā)展的歷史可以看成是一個煞費苦心或精心制成的數(shù)據(jù)結(jié)構(gòu)。首先，我們有整數(shù)，然后有有理數(shù)、代數(shù)數(shù)，在經(jīng)過一陣斗爭以后，我們有實數(shù)、復(fù)數(shù)、函數(shù)的一般概念等等。最后，人們終于明白開頭所說的思想，計算機科學(xué)家或許可以利用這個經(jīng)歷。其次，19世紀后半期，數(shù)學(xué)家把函數(shù)定義為笛兒乘積的子集，從而把函數(shù)視為集合，這是嚴格的。但對計算機科學(xué)家是不合適宜的，他們更喜歡用規(guī)則來定義函數(shù)。,在計算機專業(yè)中的意義,集合論是數(shù)學(xué)的基礎(chǔ)，也是計算機科學(xué)的基礎(chǔ)。集合論和圖論是算法與數(shù)據(jù)結(jié)構(gòu)、形式語言與自動機、數(shù)據(jù)庫原理、計算的復(fù)雜性理論等課的先修課。而圖論的基本知識則將始終陪伴我們，直到。數(shù)學(xué)要教會人如何進行邏輯推理，如何進行正確的抽象思維，如何在紛繁的事物中抓住主要的聯(lián)系，并如何使用明確的概念，等等。這對計算機技術(shù)及應(yīng)用也是至關(guān)重要的，在其他任何領(lǐng)域同樣重要。,計算機系統(tǒng),硬件,軟件,組成原理,電子技術(shù),體系結(jié)構(gòu),數(shù)字邏輯電路,電路原理,大學(xué)物理,計算機網(wǎng)絡(luò),接口與通訊技術(shù),通訊概論,安全與保密,程序設(shè)計語言,匯編語言,高級語言,編譯原理,計算理論,C、C、JAVA、PB、VB,系統(tǒng)軟件,操作系統(tǒng),DOS、Windows、UNIX,數(shù)據(jù)庫,Access、Sybase、Oracle,數(shù)據(jù)結(jié)構(gòu),人工智能,應(yīng)用軟件開發(fā),離散數(shù)學(xué)：,軟件工程,算法設(shè)計與分析,集合,函數(shù),代數(shù)結(jié)構(gòu),格與布爾代數(shù),圖論,形式語言與自動機,數(shù)理邏輯,二元關(guān)系,本課程的特點,自給自足，不需要預(yù)先的知識準備。學(xué)習(xí)本課的前提實在僅僅是不可捉摸的所謂“數(shù)學(xué)上的成熟”。概念多，但都有實在的具體的實物背景，最后要落實到抽象的定義上，概念是第一位的。,本課程的特點,作為一門數(shù)學(xué)課，與以往不同的是以證明為主而不是以計算為主。因此，要學(xué)會證明技術(shù)，學(xué)會分析問題和解決問題的思想方法。它能培養(yǎng)你誠實！與計算機科學(xué)/技術(shù)聯(lián)系緊密，是最常用、最有用的數(shù)學(xué)內(nèi)容之一。沒有什么公式要你背。需要的僅是智力上的成熟并樂意進行獨立思考！,2019/12/6,15,教學(xué)要求課程要求,掌握集合論與圖論的基本概念、基本原理、基本方法等基本知識，并且對其具有比較全面、系統(tǒng)的認識和正確的理解；掌握運用基本知識進行推理的初步能力，并能將其應(yīng)用到計算機科學(xué)領(lǐng)域內(nèi)，分析和處理一些基本問題；掌握常用的證明方法：直接證明法、反證法、數(shù)學(xué)歸納法、構(gòu)造法等，具有一定的抽象思維和邏輯思維能力，達到知識、能力、素質(zhì)的協(xié)調(diào)發(fā)展。,教學(xué)要求考試要求,題型選擇、填空、判斷、簡答、證明、論述、設(shè)計、計算等重點和難點會在各章的開始點明考試權(quán)重作業(yè)占10%期末考試占90%考前答疑考試前兩天,2019/12/6,16,教學(xué)方法,“只有學(xué)生能理解的定義才是令人滿意的?！盤oincar于1909年講清概念的背景，最好先從具體的實例出發(fā)，直觀地給出實在的東西，然后推廣或抽出本質(zhì)得到抽象概念。沒有抽象就沒有科學(xué)！“從具體到抽象是數(shù)學(xué)發(fā)展的一條重要大道，因此具體例子往往是抽象概念的源泉，而所用的方法也往往是高深數(shù)學(xué)里所用的方法的依據(jù)。僅僅熟讀了抽象的定義和方法而不知道他們具體來源(從抽象回到具體)的數(shù)學(xué)工作者是沒有發(fā)展前途的，這樣的人要搞深刻研究是可能會遇到無法克服的難關(guān)的”。華羅庚：數(shù)論導(dǎo)引,2019/12/6,17,教學(xué)方法,“難處不在于有公式去證明，而在于沒公式之前，怎樣去找出公式”。華羅庚總之，教育的目的或重點是理解概念、理解方法、理解定理。而今應(yīng)多一個就是怎樣分析、處理這眾多的信息以達到思考它、理解信息，從中獲取知識，增長智慧，創(chuàng)造生活。,2019/12/6,18,教學(xué)方法,證明、解題：發(fā)現(xiàn)解法已知的事物和要求的事，已知量和未知量，假設(shè)和結(jié)論，在原先開始時隔開的事物和想法，我們就是要在這原先是隔開的事物或想法之間找出聯(lián)系。被聯(lián)系的事物原來離得越遠，聯(lián)系的發(fā)現(xiàn)者的功績也就越大。有時我們發(fā)現(xiàn)這種聯(lián)系就象一座橋：一個偉大的發(fā)現(xiàn)使我們強烈地覺得象是在兩個離得很遠的想法的鴻溝間架上了橋。我們常?？吹竭@種聯(lián)系是由一條鏈來貫穿的：一個證明象是一串論據(jù)，象是一條由一系列結(jié)論組成的鏈，也許是一條長鏈。這條鏈的強度是由它最弱的一環(huán)來代表的。因為哪怕是只少了一環(huán)，就不會有連續(xù)推理的鏈，也就不會有有效的證明。對于思維上的聯(lián)系，我們更經(jīng)常使用線索這個詞。,2019/12/6,19,教學(xué)方法,瞻前顧后站在新的概念、理論、方法和觀點看已學(xué)過的知識（在這里是微積分、線性代數(shù)、概率論、C程序設(shè)計語言等）有時會更清楚，顯得簡單，理解會更深刻；我們也將隨時指出本課的內(nèi)容在計算機專業(yè)中的應(yīng)用，特別是在后繼課數(shù)據(jù)結(jié)構(gòu)與算法、形式語言與自動機、編譯、數(shù)據(jù)庫原理、計算復(fù)雜性理論等中的應(yīng)用。但不能詳述，目的是告訴你現(xiàn)在值得花點精力學(xué)它。,2019/12/6,20,教學(xué)方法,基本概念必須抽象化要問當作實體的這些對象是什么，這是沒有意義的，即使是有的話也不可能在數(shù)學(xué)范圍內(nèi)得到解決。所有適合它們的論斷都不涉及到這些實體的現(xiàn)實，而只說明數(shù)學(xué)上“不加定義的對象”之間的相互關(guān)系以及它們所遵循的運算法。“可驗證”的事實只是結(jié)構(gòu)和關(guān)系。不要期望百分之百地聽懂每個細節(jié)，某些細節(jié)應(yīng)獨立思考自己弄懂，這才會使你愉快。,2019/12/6,21,學(xué)習(xí)方法,基于問題的學(xué)習(xí)（What-Why-hoW）學(xué)習(xí)要以思考為基礎(chǔ)一般的學(xué)習(xí)只是一種模仿，而沒有任何創(chuàng)用思考由懷疑和答案組成，學(xué)習(xí)便是經(jīng)常懷疑，經(jīng)常隨時發(fā)問。懷疑是智慧的大門，知道得越多，就越會發(fā)問，而問題就越多。所以，發(fā)問使人進步，發(fā)問和答案一樣重要?；A(chǔ)知識是研究的工具在獨立思考之前，必須先有基礎(chǔ)知識。所謂“獲得基礎(chǔ)知識”并不是形式上讀過某門課程，而是將學(xué)過的東西完全弄懂(什么叫做精通C語言？)。學(xué)習(xí)中，概念是第一位的，概念的背景（直觀原型）、抽象定義的內(nèi)涵和外延要準確，應(yīng)用時才能自如。,2019/12/6,22,學(xué)習(xí)方法,要敢于犯錯誤學(xué)習(xí)的一種方法，經(jīng)常還是唯一的方法，就在于首先犯錯誤。我們在學(xué)習(xí)，多數(shù)時間在通過犯錯誤學(xué)習(xí)。教學(xué)、學(xué)習(xí)是一個過程是毛毛雨，需不斷地滋潤教師在傳授知識和技術(shù)的過程中，偶爾會傳授教訓(xùn)，但這種教訓(xùn)如果沒有經(jīng)過你的親身體驗，不會變成有用的經(jīng)驗。知識沒有教訓(xùn)作為根基，只能是紙上談兵。上課、讀書、復(fù)習(xí)、做作業(yè)、討論、做實驗、自己編程序、上機調(diào)試排錯是絕對必要的那種抄別人作業(yè)、考試作弊、不上課不看書，是沒有希望的。一個作弊的民族怎么可能進步和強大呢？提倡學(xué)習(xí)中互相討論、辯論、提出不同的方法。,2019/12/6,23,學(xué)習(xí)方法,記住，數(shù)學(xué)以及其他理論學(xué)科的書，不能讀得太快，也不能期望讀一遍就全弄懂。生活的根基不僅包括我們得到的所有的答案，而且還應(yīng)該包括我們提出的所有問題。,2019/12/6,24,學(xué)習(xí)方法,輔導(dǎo)答疑這是任課教師與學(xué)生直接交流、溝通思想的時間。對學(xué)生一視同仁應(yīng)當是教師的基本心理，而善待每個學(xué)生是教師應(yīng)當堅持的教育原則。充分利用好答疑時間，是與老師交流的機會，會獲得意想不到的東西教師為你解答經(jīng)你努力尚未弄懂的問題。沒有經(jīng)你思考的習(xí)題、問題最好暫時不問，否則收獲不大教師不要立即暴露你的全部秘密讓學(xué)生在你說出來之前先去猜盡量讓他們自己去找出來。你可以給一些提示，創(chuàng)造一個稍好的環(huán)境，讓學(xué)生自己去發(fā)現(xiàn)！增強學(xué)生的信心。把老師看成朋友或者長者，這時除談業(yè)務(wù)外，談理想、人生、道德、責任、如何做人,2019/12/6,25,2019/12/6,26,教材及主要參考書目,王義和,離散數(shù)學(xué)引論,哈爾濱工業(yè)大學(xué)出版社,2000.3.Kenneth.Rosen著,袁崇義,屈婉玲等譯,離散數(shù)學(xué)及其應(yīng)用,機械工業(yè)出版社,2007.6.,寄語,要主動學(xué)習(xí)不要苛求課程、老師和環(huán)境，他/她/它們只是資源目標確定后要善于利用各種資源注重對自己能力的培養(yǎng)學(xué)會做人,樂于助人,多為別人著想,可以獲取友誼朋友是資源，可以終生受益學(xué)會安排自己的時間時間就像海綿里的水，只要肯擠，總會有的。貴在恒。學(xué)會利用各種資源提高自己學(xué)校的、家庭的、社會的上學(xué)期間利用資源的唯一目的就是提高自己不要沉迷于網(wǎng)絡(luò)聊天與游戲,2019/12/6,27,第一章集合及其運算,重點：概念：集合、差、對稱差、笛卡兒乘積、有窮集基數(shù)。方法：證明兩個集合相等的方法必考，必須掌握；基本的計數(shù)法則及容斥原理在古典概率論中的應(yīng)用。應(yīng)用：古典概率模型、跳舞問題的數(shù)學(xué)模型。難點：容斥原理在古典概率論中的應(yīng)用。,SchoolofComputerScience&TechnologyHarbinInstituteofTechnology,2019/12/6,28,2019/12/6,29,第一章主要內(nèi)容,1集合（set）、屬于關(guān)系、集合的表示方法、空集2子集（subset）、兩個集合相等，冪集（powerset）、集族（以集為元素的集）、證明兩個集相等的方法3集合的運算：并(union)、交（intersection）、差（subraction）、對稱差（symmetricdifference），各自的性質(zhì)及相互聯(lián)系4求補（complement）運算C(，Cs)及DeMorgan律5迪卡爾積（Cartesianproduct）及其性質(zhì)6有限集合的基數(shù)（cardinalnumber）、基本的計數(shù)法則、容斥原理,2019/12/6,30,第一章小結(jié),1、概念：集、子集、冪集、c、，基數(shù)2、結(jié)論：運算的性質(zhì)、計數(shù)法則、容斥原理*3、方法：證明兩個集合相等的方法；邏輯推理。,第二章映射,重點：概念：映射、單（滿、雙）射、合成運算、置換、逆映射、特征函數(shù)、方法：置換的循環(huán)置換分解應(yīng)用：復(fù)合函數(shù)應(yīng)用概述，建立數(shù)學(xué)模型DFA難點：容斥原理在古典概率論中的應(yīng)用。,SchoolofComputerScience&TechnologyHarbinInstituteofTechnology,2019/12/6,31,2019/12/6,32,第二章主要內(nèi)容,1映射（mapping）、單射（inje