集合論與圖論.ppt

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