集合論與圖論Set Theory and Graph Theory

1、集合論與圖論集合論與圖論Set Theory and Graph Theory主講：主講： 姜守旭姜守旭 博士博士/教授教授/教學(xué)帶頭人教學(xué)帶頭人/博導(dǎo)博導(dǎo)助教：馮誠(chéng)助教：馮誠(chéng)辦公室：綜合樓辦公室：綜合樓808 辦公電話：辦公電話： 86403492-808手機(jī)：手機(jī)mail：課程網(wǎng)站：課程網(wǎng)站：http:/ 答疑地點(diǎn)：青年公寓答疑地點(diǎn)：青年公寓205答疑時(shí)間：星期六答疑時(shí)間：星期六9:0011:00School of Computer Science & Technology Harbin Institute of Technologyn什么是教育？“教育就

2、是當(dāng)你把所學(xué)的東西都忘掉后，最終剩下的東西！ ”“最終剩下的東西就是一個(gè)人的創(chuàng)新意識(shí)和學(xué)習(xí)能力?！备叩冉逃娜蝿?wù)是培養(yǎng)具有創(chuàng)新精神和實(shí)踐能力的高級(jí)專門(mén)人才，發(fā)展科學(xué)技術(shù)文化，促進(jìn)社會(huì)主義現(xiàn)代化建設(shè)。 中華人民共和國(guó)高等教育法第五條因此，我們應(yīng)把教與學(xué)的著眼點(diǎn)集中在掌握科學(xué)基礎(chǔ)知識(shí)和訓(xùn)練創(chuàng)新能力上，著重培養(yǎng)科學(xué)的思維方法，把知識(shí)傳授與能力培養(yǎng)融為一體，激發(fā)學(xué)生的好奇心和創(chuàng)造性。教育的目的教育的目的北京大學(xué)徐光憲院士談創(chuàng)新教育北京大學(xué)徐光憲院士談創(chuàng)新教育 n什么是創(chuàng)新？什么是創(chuàng)新？n學(xué)而不問(wèn)則殆，問(wèn)而不學(xué)則罔。學(xué)而不問(wèn)則殆，問(wèn)而不學(xué)則罔。（孔子：學(xué)而不思則（孔子：學(xué)而不思則罔，思而不學(xué)則殆罔，思而

3、不學(xué)則殆） 。學(xué)而問(wèn)，問(wèn)而思，思而行，。學(xué)而問(wèn)，問(wèn)而思，思而行，行而果，這就是創(chuàng)新。行而果，這就是創(chuàng)新。n怎樣創(chuàng)新？怎樣創(chuàng)新？n在頭腦中建立類似在頭腦中建立類似“中藥鋪中藥鋪”的知識(shí)抽屜，這是的知識(shí)抽屜，這是“學(xué)學(xué)”。 n抽屜中放進(jìn)許多問(wèn)號(hào)，這是抽屜中放進(jìn)許多問(wèn)號(hào)，這是“問(wèn)問(wèn)”。認(rèn)真仔細(xì)地提出。認(rèn)真仔細(xì)地提出科學(xué)問(wèn)題，是創(chuàng)新研究的開(kāi)始，而且是最重要的開(kāi)始?？茖W(xué)問(wèn)題，是創(chuàng)新研究的開(kāi)始，而且是最重要的開(kāi)始。 n大膽假設(shè)，回答提出的問(wèn)題，這是大膽假設(shè)，回答提出的問(wèn)題，這是“思思”。 n小心求證，驗(yàn)證自己的假設(shè)，這是小心求證，驗(yàn)證自己的假設(shè)，這是“果果”。 2022-3-154課程性質(zhì)課程性質(zhì)n484

4、8學(xué)時(shí)學(xué)時(shí)n是一門(mén)專業(yè)基礎(chǔ)課，本專業(yè)最重要的課程是一門(mén)專業(yè)基礎(chǔ)課，本專業(yè)最重要的課程之一之一n需要一些工科數(shù)學(xué)分析、線性代數(shù)的知識(shí)需要一些工科數(shù)學(xué)分析、線性代數(shù)的知識(shí)n是數(shù)學(xué)是數(shù)學(xué)(離散數(shù)學(xué)離散數(shù)學(xué))的一部分，數(shù)學(xué)首先是的一部分，數(shù)學(xué)首先是一些一些工具工具，其次是一門(mén)，其次是一門(mén)語(yǔ)言語(yǔ)言，最后還是一，最后還是一種種素養(yǎng)素養(yǎng)集合論與圖論是數(shù)學(xué)的一部分集合論與圖論是數(shù)學(xué)的一部分n“對(duì)于大自然這本奧秘?zé)o窮的書(shū)，我讀不對(duì)于大自然這本奧秘?zé)o窮的書(shū)，我讀不懂懂”。 莎士比亞莎士比亞安東尼和克里奧安東尼和克里奧帕特拉帕特拉（15641616）n“如果不理解它的語(yǔ)言，沒(méi)有人能讀懂宇如果不理解它的語(yǔ)言，沒(méi)有人能

5、讀懂宇宙這本偉大的書(shū)，它的語(yǔ)言就是數(shù)學(xué)宙這本偉大的書(shū)，它的語(yǔ)言就是數(shù)學(xué)”。 伽里略（伽里略（15641642）n“在任何特定的理論中，只有其中包含數(shù)在任何特定的理論中，只有其中包含數(shù)學(xué)的部分才是真正的科學(xué)學(xué)的部分才是真正的科學(xué)” 康德（康德（17241804）集合論與圖論是數(shù)學(xué)的一部分集合論與圖論是數(shù)學(xué)的一部分n“一門(mén)科學(xué)，只有當(dāng)它能夠運(yùn)用數(shù)學(xué)時(shí)，一門(mén)科學(xué)，只有當(dāng)它能夠運(yùn)用數(shù)學(xué)時(shí)，才算真正發(fā)展了。才算真正發(fā)展了?！?馬克思（馬克思（18181883）n數(shù)學(xué)不專屬自然科學(xué)，也不專屬社會(huì)科學(xué)，數(shù)學(xué)不專屬自然科學(xué)，也不專屬社會(huì)科學(xué)，更不專屬于文學(xué)藝術(shù)。它是一種宇宙語(yǔ)言，更不專屬于文學(xué)藝術(shù)。它是一種宇

6、宙語(yǔ)言，為一切文明生物共有、共享。為一切文明生物共有、共享。2022-3-157主要內(nèi)容主要內(nèi)容 n工大工大80年開(kāi)始將離散數(shù)學(xué)分成三門(mén)課：年開(kāi)始將離散數(shù)學(xué)分成三門(mén)課：集合論與圖論、近世代數(shù)、數(shù)理邏輯集合論與圖論、近世代數(shù)、數(shù)理邏輯n集合論集合論n集合及其運(yùn)算、映射及其合成、關(guān)系及其集合及其運(yùn)算、映射及其合成、關(guān)系及其運(yùn)算、無(wú)窮集合及其基數(shù)。運(yùn)算、無(wú)窮集合及其基數(shù)。n圖論圖論n圖的一些基本概念、一些特殊的圖、樹(shù)及圖的一些基本概念、一些特殊的圖、樹(shù)及其性質(zhì)、割點(diǎn)和橋、連通度、平面圖、圖其性質(zhì)、割點(diǎn)和橋、連通度、平面圖、圖的著色、有向圖。的著色、有向圖。教學(xué)目的教學(xué)目的n該課程的設(shè)置主要是為了培養(yǎng)

7、學(xué)生的該課程的設(shè)置主要是為了培養(yǎng)學(xué)生的抽象思抽象思維維和和邏輯推理能力邏輯推理能力，提高學(xué)生分析問(wèn)題和解，提高學(xué)生分析問(wèn)題和解決問(wèn)題的能力，提高學(xué)生的數(shù)學(xué)修養(yǎng)及計(jì)算決問(wèn)題的能力，提高學(xué)生的數(shù)學(xué)修養(yǎng)及計(jì)算機(jī)科學(xué)素質(zhì)。機(jī)科學(xué)素質(zhì)。 n本課程為后繼的專業(yè)基礎(chǔ)課及專業(yè)課提供必本課程為后繼的專業(yè)基礎(chǔ)課及專業(yè)課提供必要的數(shù)學(xué)工具，為描述離散模型提供數(shù)學(xué)語(yǔ)要的數(shù)學(xué)工具，為描述離散模型提供數(shù)學(xué)語(yǔ)言。言。n要想用計(jì)算機(jī)解決問(wèn)題就要為它要想用計(jì)算機(jī)解決問(wèn)題就要為它建立數(shù)學(xué)模型建立數(shù)學(xué)模型，即描述研究對(duì)象及對(duì)象與對(duì)象之間的聯(lián)系，并即描述研究對(duì)象及對(duì)象與對(duì)象之間的聯(lián)系，并通過(guò)事物之間的聯(lián)系找出事物的運(yùn)動(dòng)規(guī)律。通過(guò)事物

8、之間的聯(lián)系找出事物的運(yùn)動(dòng)規(guī)律。n集合論與圖論為此提供了強(qiáng)有力的集合論與圖論為此提供了強(qiáng)有力的描述工具描述工具與與推理理論推理理論。 2022-3-158基本思想基本思想n我們從我們從“集合集合”這個(gè)基本概念開(kāi)始建立這個(gè)基本概念開(kāi)始建立集合理論。就某種觀點(diǎn)來(lái)看，集合理論。就某種觀點(diǎn)來(lái)看，“集合集合”與與“性質(zhì)性質(zhì)”是同義詞，是基本概念之一。是同義詞，是基本概念之一。 n集合用來(lái)描述事物的性質(zhì)集合用來(lái)描述事物的性質(zhì)我們的研究我們的研究對(duì)象，對(duì)象，映射用來(lái)描述事物之間的聯(lián)系映射用來(lái)描述事物之間的聯(lián)系運(yùn)算、關(guān)系，從而為集合建立了結(jié)構(gòu)。運(yùn)算、關(guān)系，從而為集合建立了結(jié)構(gòu)。于是，于是，為建立系統(tǒng)的數(shù)學(xué)模型提

9、供了數(shù)為建立系統(tǒng)的數(shù)學(xué)模型提供了數(shù)學(xué)描述語(yǔ)言學(xué)描述語(yǔ)言工具，代數(shù)系統(tǒng)就是引入工具，代數(shù)系統(tǒng)就是引入運(yùn)算以后的集合。運(yùn)算以后的集合。 基本思想基本思想n集合論又提供了研究數(shù)學(xué)模型的性質(zhì)，發(fā)現(xiàn)集合論又提供了研究數(shù)學(xué)模型的性質(zhì)，發(fā)現(xiàn)新聯(lián)系的新聯(lián)系的推理方法推理方法，從而找出事物的，從而找出事物的運(yùn)動(dòng)規(guī)運(yùn)動(dòng)規(guī)律律。n圖論是上述思想的一個(gè)具體應(yīng)用，事實(shí)上，圖論是上述思想的一個(gè)具體應(yīng)用，事實(shí)上，圖論為任何一個(gè)包含了一種二元關(guān)系的系統(tǒng)圖論為任何一個(gè)包含了一種二元關(guān)系的系統(tǒng)提供了一個(gè)數(shù)學(xué)模型提供了一個(gè)數(shù)學(xué)模型；部分地，也因?yàn)槭褂茫徊糠值?，也因?yàn)槭褂昧藞D解式表示方法，圖就具有一種直觀的和了圖解式表示方法，圖就具

10、有一種直觀的和符合美學(xué)的外形。符合美學(xué)的外形。 n在圖論中，許多結(jié)果是初等的，但也有大量在圖論中，許多結(jié)果是初等的，但也有大量的十分復(fù)雜的問(wèn)題可以難倒最老練的數(shù)學(xué)家。的十分復(fù)雜的問(wèn)題可以難倒最老練的數(shù)學(xué)家。在計(jì)算機(jī)專業(yè)中的意義在計(jì)算機(jī)專業(yè)中的意義n能形式化就能自動(dòng)化。能形式化就能自動(dòng)化。n對(duì)計(jì)算機(jī)專業(yè)而言，形式化尤為重要。利對(duì)計(jì)算機(jī)專業(yè)而言，形式化尤為重要。利用形式化描述給程序設(shè)計(jì)提供了方便，從用形式化描述給程序設(shè)計(jì)提供了方便，從而實(shí)現(xiàn)了自動(dòng)化。而實(shí)現(xiàn)了自動(dòng)化。在計(jì)算機(jī)專業(yè)中的意義在計(jì)算機(jī)專業(yè)中的意義n集合論可以看成一種集合論可以看成一種通用語(yǔ)言通用語(yǔ)言，一切必要的數(shù)據(jù)，一切必要的數(shù)據(jù)結(jié)構(gòu)都可

11、以由集合這個(gè)原始的數(shù)據(jù)結(jié)構(gòu)而構(gòu)造出結(jié)構(gòu)都可以由集合這個(gè)原始的數(shù)據(jù)結(jié)構(gòu)而構(gòu)造出來(lái)。來(lái)。n實(shí)際上，實(shí)際上，數(shù)學(xué)發(fā)展的歷史可以看成是一個(gè)煞費(fèi)苦數(shù)學(xué)發(fā)展的歷史可以看成是一個(gè)煞費(fèi)苦心或精心制成的數(shù)據(jù)結(jié)構(gòu)。心或精心制成的數(shù)據(jù)結(jié)構(gòu)。首先，我們有整數(shù)，首先，我們有整數(shù)，然后有有理數(shù)、代數(shù)數(shù)，在經(jīng)過(guò)一陣斗爭(zhēng)以后，然后有有理數(shù)、代數(shù)數(shù)，在經(jīng)過(guò)一陣斗爭(zhēng)以后，我們有實(shí)數(shù)、復(fù)數(shù)、函數(shù)的一般概念等等。最后，我們有實(shí)數(shù)、復(fù)數(shù)、函數(shù)的一般概念等等。最后，人們終于明白開(kāi)頭所說(shuō)的思想，計(jì)算機(jī)科學(xué)家或人們終于明白開(kāi)頭所說(shuō)的思想，計(jì)算機(jī)科學(xué)家或許可以利用這個(gè)經(jīng)歷。許可以利用這個(gè)經(jīng)歷。n其次，其次，19世紀(jì)后半期，數(shù)學(xué)家把函數(shù)定義為笛

12、兒世紀(jì)后半期，數(shù)學(xué)家把函數(shù)定義為笛兒乘積的子集，從而把函數(shù)視為集合，這是嚴(yán)格的。乘積的子集，從而把函數(shù)視為集合，這是嚴(yán)格的。但對(duì)計(jì)算機(jī)科學(xué)家是不合適宜的，他們更喜歡用但對(duì)計(jì)算機(jī)科學(xué)家是不合適宜的，他們更喜歡用規(guī)則來(lái)定義函數(shù)。規(guī)則來(lái)定義函數(shù)。在計(jì)算機(jī)專業(yè)中的意義在計(jì)算機(jī)專業(yè)中的意義n集合論是數(shù)學(xué)的基礎(chǔ)，也是計(jì)算機(jī)科學(xué)的集合論是數(shù)學(xué)的基礎(chǔ)，也是計(jì)算機(jī)科學(xué)的基礎(chǔ)。集合論和圖論是算法與數(shù)據(jù)結(jié)構(gòu)、基礎(chǔ)。集合論和圖論是算法與數(shù)據(jù)結(jié)構(gòu)、形式語(yǔ)言與自動(dòng)機(jī)、數(shù)據(jù)庫(kù)原理、計(jì)算的形式語(yǔ)言與自動(dòng)機(jī)、數(shù)據(jù)庫(kù)原理、計(jì)算的復(fù)雜性理論等課的先修課。而圖論的基本復(fù)雜性理論等課的先修課。而圖論的基本知識(shí)則將始終陪伴我們，直到知識(shí)

13、則將始終陪伴我們，直到。n數(shù)學(xué)要教會(huì)人數(shù)學(xué)要教會(huì)人如何進(jìn)行邏輯推理如何進(jìn)行邏輯推理，如何進(jìn)如何進(jìn)行正確的抽象思維行正確的抽象思維，如何在紛繁的事物中如何在紛繁的事物中抓住主要的聯(lián)系抓住主要的聯(lián)系，并，并如何使用明確的概念如何使用明確的概念，等等。這對(duì)計(jì)算機(jī)技術(shù)及應(yīng)用也是至關(guān)重等等。這對(duì)計(jì)算機(jī)技術(shù)及應(yīng)用也是至關(guān)重要的，在其他任何領(lǐng)域同樣重要。要的，在其他任何領(lǐng)域同樣重要。計(jì)算機(jī)系統(tǒng)計(jì)算機(jī)系統(tǒng)硬件硬件軟件軟件組成組成原理原理電子技術(shù)電子技術(shù)體系體系結(jié)構(gòu)結(jié)構(gòu)數(shù)字邏輯電路數(shù)字邏輯電路電路原理電路原理大學(xué)物理大學(xué)物理計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)接口與通訊技術(shù)接口與通訊技術(shù)通訊概論通訊概論安全與保密安全與保密程序

14、設(shè)程序設(shè)計(jì)語(yǔ)言計(jì)語(yǔ)言匯編語(yǔ)言匯編語(yǔ)言高級(jí)語(yǔ)言高級(jí)語(yǔ)言編譯原理編譯原理計(jì)算理論計(jì)算理論C C、C C、JAVAJAVA、PBPB、VBVB系統(tǒng)系統(tǒng)軟件軟件操作系統(tǒng)操作系統(tǒng)DOSDOS、Windows Windows 、UNIXUNIX數(shù)據(jù)庫(kù)數(shù)據(jù)庫(kù)AccessAccess、Sybase Sybase 、OracleOracle數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)人工智能人工智能應(yīng)用應(yīng)用軟件軟件開(kāi)發(fā)開(kāi)發(fā) 離散數(shù)學(xué)：離散數(shù)學(xué)：軟件工程軟件工程算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析集合集合函數(shù)函數(shù)代數(shù)代數(shù)結(jié)構(gòu)結(jié)構(gòu)格與格與布布爾代數(shù)爾代數(shù)圖論圖論形式語(yǔ)言形式語(yǔ)言與自動(dòng)機(jī)與自動(dòng)機(jī)數(shù)理數(shù)理邏輯邏輯二元二元關(guān)系關(guān)系本課程的特點(diǎn)本課程的特點(diǎn)n

15、自給自足，不需要預(yù)先的知識(shí)準(zhǔn)備。學(xué)習(xí)自給自足，不需要預(yù)先的知識(shí)準(zhǔn)備。學(xué)習(xí)本課的前提實(shí)在僅僅是不可捉摸的所謂本課的前提實(shí)在僅僅是不可捉摸的所謂“數(shù)學(xué)上的成熟數(shù)學(xué)上的成熟”。n概念多，但都有實(shí)在的具體的實(shí)物背景，概念多，但都有實(shí)在的具體的實(shí)物背景，最后要落實(shí)到抽象的定義上，概念是第一最后要落實(shí)到抽象的定義上，概念是第一位的。位的。本課程的特點(diǎn)本課程的特點(diǎn)n作為一門(mén)數(shù)學(xué)課，與以往不同的是作為一門(mén)數(shù)學(xué)課，與以往不同的是以證明以證明為主為主而不是以計(jì)算為主。因此，要學(xué)會(huì)證而不是以計(jì)算為主。因此，要學(xué)會(huì)證明技術(shù)，學(xué)會(huì)分析問(wèn)題和解決問(wèn)題的思想明技術(shù)，學(xué)會(huì)分析問(wèn)題和解決問(wèn)題的思想方法。它能培養(yǎng)你誠(chéng)實(shí)！方法。它

16、能培養(yǎng)你誠(chéng)實(shí)！n與計(jì)算機(jī)科學(xué)與計(jì)算機(jī)科學(xué)/技術(shù)聯(lián)系緊密，是最常用、技術(shù)聯(lián)系緊密，是最常用、最有用的數(shù)學(xué)內(nèi)容之一。最有用的數(shù)學(xué)內(nèi)容之一。n沒(méi)有什么公式要你背。需要的僅是智力上沒(méi)有什么公式要你背。需要的僅是智力上的成熟并樂(lè)意進(jìn)行的成熟并樂(lè)意進(jìn)行獨(dú)立思考獨(dú)立思考！2022-3-1517教學(xué)要求教學(xué)要求課程要求課程要求n掌握集合論與圖論的掌握集合論與圖論的基本概念、基本原理、基本概念、基本原理、基本方法基本方法等基本知識(shí)，并且對(duì)其具有比較等基本知識(shí)，并且對(duì)其具有比較全面、系統(tǒng)的認(rèn)識(shí)和正確的理解；全面、系統(tǒng)的認(rèn)識(shí)和正確的理解；n掌握掌握運(yùn)用基本知識(shí)進(jìn)行推理運(yùn)用基本知識(shí)進(jìn)行推理的初步能力，的初步能力，并能

17、將其應(yīng)用到計(jì)算機(jī)科學(xué)領(lǐng)域內(nèi)，分析并能將其應(yīng)用到計(jì)算機(jī)科學(xué)領(lǐng)域內(nèi)，分析和處理一些基本問(wèn)題；和處理一些基本問(wèn)題；n掌握常用的證明方法：掌握常用的證明方法：直接證明法直接證明法、反證反證法法、數(shù)學(xué)歸納法數(shù)學(xué)歸納法、構(gòu)造法構(gòu)造法等，具有一定的等，具有一定的抽象思維和邏輯思維能力，達(dá)到知識(shí)、能抽象思維和邏輯思維能力，達(dá)到知識(shí)、能力、素質(zhì)的協(xié)調(diào)發(fā)展。力、素質(zhì)的協(xié)調(diào)發(fā)展。 教學(xué)要求教學(xué)要求考試要求考試要求n題型題型n選擇、填空、判斷、簡(jiǎn)答、證明、論述、設(shè)計(jì)、選擇、填空、判斷、簡(jiǎn)答、證明、論述、設(shè)計(jì)、計(jì)算等計(jì)算等n重點(diǎn)和難點(diǎn)重點(diǎn)和難點(diǎn)n會(huì)在各章的開(kāi)始點(diǎn)明會(huì)在各章的開(kāi)始點(diǎn)明n考試權(quán)重考試權(quán)重n作業(yè)占作業(yè)占10%

18、n期末考試占期末考試占90%n考前答疑考前答疑n考試前兩天考試前兩天2022-3-1518教學(xué)方法教學(xué)方法n“只有學(xué)生能理解的定義才是令人滿意的。只有學(xué)生能理解的定義才是令人滿意的?！?Poincar于于1909年年n講清講清概念的背景概念的背景，最好先從具體的實(shí)例出發(fā)，直，最好先從具體的實(shí)例出發(fā)，直觀地給出實(shí)在的東西，然后推廣或抽出本質(zhì)得到觀地給出實(shí)在的東西，然后推廣或抽出本質(zhì)得到抽象概念。抽象概念。沒(méi)有抽象就沒(méi)有科學(xué)！沒(méi)有抽象就沒(méi)有科學(xué)！n“從具體到抽象從具體到抽象是數(shù)學(xué)發(fā)展的一條重要大道，因是數(shù)學(xué)發(fā)展的一條重要大道，因此具體例子往往是抽象概念的源泉，而所用的方此具體例子往往是抽象概念的源

19、泉，而所用的方法也往往是高深數(shù)學(xué)里所用的方法的依據(jù)。法也往往是高深數(shù)學(xué)里所用的方法的依據(jù)。n僅僅熟讀了抽象的定義和方法而不知道他們具體僅僅熟讀了抽象的定義和方法而不知道他們具體來(lái)源來(lái)源(從抽象回到具體從抽象回到具體)的數(shù)學(xué)工作者是沒(méi)有發(fā)展的數(shù)學(xué)工作者是沒(méi)有發(fā)展前途的，這樣的人要搞深刻研究是可能會(huì)遇到無(wú)前途的，這樣的人要搞深刻研究是可能會(huì)遇到無(wú)法克服的難關(guān)的法克服的難關(guān)的”。華羅庚：華羅庚：數(shù)論導(dǎo)引數(shù)論導(dǎo)引2022-3-1519教學(xué)方法教學(xué)方法n“難處不在于有公式去證明，而在于沒(méi)公難處不在于有公式去證明，而在于沒(méi)公式之前，怎樣去找出公式式之前，怎樣去找出公式”。華羅庚華羅庚n總之，教育的目的或重

20、點(diǎn)是總之，教育的目的或重點(diǎn)是理解理解概念概念、理理解解方法方法、理解理解定理定理。而今應(yīng)多一個(gè)就是怎。而今應(yīng)多一個(gè)就是怎樣分析、處理這眾多的信息以達(dá)到思考它、樣分析、處理這眾多的信息以達(dá)到思考它、理解理解信息信息，從中獲取知識(shí)，增長(zhǎng)智慧，創(chuàng)，從中獲取知識(shí)，增長(zhǎng)智慧，創(chuàng)造生活。造生活。2022-3-1520教學(xué)方法教學(xué)方法n證明、解題：發(fā)現(xiàn)解法證明、解題：發(fā)現(xiàn)解法n已知的事物和要求的事，已知量和未知量，假設(shè)和結(jié)論，已知的事物和要求的事，已知量和未知量，假設(shè)和結(jié)論，在原先開(kāi)始時(shí)隔開(kāi)的事物和想法，我們就是要在這原先在原先開(kāi)始時(shí)隔開(kāi)的事物和想法，我們就是要在這原先是隔開(kāi)的事物或想法之間是隔開(kāi)的事物或想

21、法之間找出聯(lián)系找出聯(lián)系。n被聯(lián)系的事物原來(lái)離得越遠(yuǎn)，聯(lián)系的發(fā)現(xiàn)者的功績(jī)也就被聯(lián)系的事物原來(lái)離得越遠(yuǎn)，聯(lián)系的發(fā)現(xiàn)者的功績(jī)也就越大。有時(shí)我們發(fā)現(xiàn)這種越大。有時(shí)我們發(fā)現(xiàn)這種聯(lián)系就象一座橋聯(lián)系就象一座橋：一個(gè)偉大的：一個(gè)偉大的發(fā)現(xiàn)使我們強(qiáng)烈地覺(jué)得象是在兩個(gè)離得很遠(yuǎn)的想法的鴻發(fā)現(xiàn)使我們強(qiáng)烈地覺(jué)得象是在兩個(gè)離得很遠(yuǎn)的想法的鴻溝間架上了橋。我們常?？吹竭@種聯(lián)系是由一條鏈來(lái)貫溝間架上了橋。我們常常看到這種聯(lián)系是由一條鏈來(lái)貫穿的：穿的：一個(gè)證明象是一串論據(jù)一個(gè)證明象是一串論據(jù)，象是一條由一系列結(jié)論，象是一條由一系列結(jié)論組成的鏈，也許是一條長(zhǎng)鏈。這條鏈的強(qiáng)度是由它最弱組成的鏈，也許是一條長(zhǎng)鏈。這條鏈的強(qiáng)度是由它最

22、弱的一環(huán)來(lái)代表的。因?yàn)槟呐率侵簧倭艘画h(huán)，就不會(huì)有連的一環(huán)來(lái)代表的。因?yàn)槟呐率侵簧倭艘画h(huán)，就不會(huì)有連續(xù)推理的鏈，也就不會(huì)有有效的證明。對(duì)于思維上的聯(lián)續(xù)推理的鏈，也就不會(huì)有有效的證明。對(duì)于思維上的聯(lián)系，我們更經(jīng)常使用系，我們更經(jīng)常使用線索線索這個(gè)詞。這個(gè)詞。2022-3-1521教學(xué)方法教學(xué)方法n瞻前顧后瞻前顧后n站在新的概念、理論、方法和觀點(diǎn)看已學(xué)過(guò)的知識(shí)站在新的概念、理論、方法和觀點(diǎn)看已學(xué)過(guò)的知識(shí)（在這里是微積分、線性代數(shù)、概率論、（在這里是微積分、線性代數(shù)、概率論、C程序設(shè)程序設(shè)計(jì)語(yǔ)言等）有時(shí)會(huì)更清楚，顯得簡(jiǎn)單，理解會(huì)更深計(jì)語(yǔ)言等）有時(shí)會(huì)更清楚，顯得簡(jiǎn)單，理解會(huì)更深刻；刻；n我們也將隨時(shí)指出

23、我們也將隨時(shí)指出本課的內(nèi)容在計(jì)算機(jī)專業(yè)中的應(yīng)本課的內(nèi)容在計(jì)算機(jī)專業(yè)中的應(yīng)用用，特別是在后繼課，特別是在后繼課數(shù)據(jù)結(jié)構(gòu)與算法、形式語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法、形式語(yǔ)言與自動(dòng)機(jī)、編譯、數(shù)據(jù)庫(kù)原理、計(jì)算復(fù)雜性理論等與自動(dòng)機(jī)、編譯、數(shù)據(jù)庫(kù)原理、計(jì)算復(fù)雜性理論等中的應(yīng)用。但不能詳述，目的是告訴你現(xiàn)在值得花中的應(yīng)用。但不能詳述，目的是告訴你現(xiàn)在值得花點(diǎn)精力學(xué)它。點(diǎn)精力學(xué)它。 2022-3-1522教學(xué)方法教學(xué)方法n基本概念必須抽象化基本概念必須抽象化n要問(wèn)當(dāng)作實(shí)體的這些對(duì)象是什么，這是沒(méi)有意義的，要問(wèn)當(dāng)作實(shí)體的這些對(duì)象是什么，這是沒(méi)有意義的，即使是有的話也不可能在數(shù)學(xué)范圍內(nèi)得到解決。所即使是有的話也不可能在數(shù)學(xué)范

24、圍內(nèi)得到解決。所有適合它們的論斷都不涉及到這些實(shí)體的現(xiàn)實(shí)，而有適合它們的論斷都不涉及到這些實(shí)體的現(xiàn)實(shí)，而只說(shuō)明數(shù)學(xué)上只說(shuō)明數(shù)學(xué)上“不加定義的不加定義的對(duì)象對(duì)象”之間的相互關(guān)系之間的相互關(guān)系以及它們所遵循的運(yùn)算法以及它們所遵循的運(yùn)算法?！翱沈?yàn)證可驗(yàn)證”的事實(shí)只是的事實(shí)只是結(jié)構(gòu)和關(guān)系。結(jié)構(gòu)和關(guān)系。n不要期望百分之百地聽(tīng)懂每個(gè)細(xì)節(jié)，某些細(xì)節(jié)不要期望百分之百地聽(tīng)懂每個(gè)細(xì)節(jié)，某些細(xì)節(jié)應(yīng)獨(dú)立思考自己弄懂，這才會(huì)使你愉快。應(yīng)獨(dú)立思考自己弄懂，這才會(huì)使你愉快。2022-3-1523學(xué)習(xí)方法學(xué)習(xí)方法n基于問(wèn)題的學(xué)習(xí)（基于問(wèn)題的學(xué)習(xí)（What-Why-hoW）n學(xué)習(xí)要以學(xué)習(xí)要以思考思考為基礎(chǔ)為基礎(chǔ)n一般的學(xué)習(xí)只是

25、一種模仿，而沒(méi)有任何創(chuàng)用一般的學(xué)習(xí)只是一種模仿，而沒(méi)有任何創(chuàng)用n思考由懷疑和答案組成，學(xué)習(xí)便是經(jīng)常懷疑，經(jīng)常隨時(shí)思考由懷疑和答案組成，學(xué)習(xí)便是經(jīng)常懷疑，經(jīng)常隨時(shí)發(fā)問(wèn)。發(fā)問(wèn)。懷疑是智慧的大門(mén)懷疑是智慧的大門(mén)，知道得越多，就越會(huì)發(fā)問(wèn)，知道得越多，就越會(huì)發(fā)問(wèn)，而問(wèn)題就越多。所以，而問(wèn)題就越多。所以，發(fā)問(wèn)使人進(jìn)步發(fā)問(wèn)使人進(jìn)步，發(fā)問(wèn)和答案一樣，發(fā)問(wèn)和答案一樣重要。重要。n基礎(chǔ)知識(shí)是研究的工具基礎(chǔ)知識(shí)是研究的工具n在獨(dú)立思考之前，必須先有基礎(chǔ)知識(shí)。所謂在獨(dú)立思考之前，必須先有基礎(chǔ)知識(shí)。所謂“獲得基礎(chǔ)獲得基礎(chǔ)知識(shí)知識(shí)”并不是形式上讀過(guò)某門(mén)課程，而是將學(xué)過(guò)的東西并不是形式上讀過(guò)某門(mén)課程，而是將學(xué)過(guò)的東西完全弄

26、懂完全弄懂(什么叫做精通什么叫做精通C語(yǔ)言？語(yǔ)言？)。n學(xué)習(xí)中，概念是第一位的，概念的背景（直觀原型）、學(xué)習(xí)中，概念是第一位的，概念的背景（直觀原型）、抽象定義的內(nèi)涵和外延要準(zhǔn)確，應(yīng)用時(shí)才能自如。抽象定義的內(nèi)涵和外延要準(zhǔn)確，應(yīng)用時(shí)才能自如。2022-3-1524學(xué)習(xí)方法學(xué)習(xí)方法n要敢于犯錯(cuò)誤要敢于犯錯(cuò)誤n學(xué)習(xí)的一種方法，經(jīng)常還是唯一的方法，就在于首先犯學(xué)習(xí)的一種方法，經(jīng)常還是唯一的方法，就在于首先犯錯(cuò)誤。我們?cè)趯W(xué)習(xí)，多數(shù)時(shí)間在錯(cuò)誤。我們?cè)趯W(xué)習(xí)，多數(shù)時(shí)間在通過(guò)犯錯(cuò)誤學(xué)習(xí)通過(guò)犯錯(cuò)誤學(xué)習(xí)。n教學(xué)、學(xué)習(xí)是一個(gè)過(guò)程教學(xué)、學(xué)習(xí)是一個(gè)過(guò)程n是毛毛雨，需不斷地滋潤(rùn)是毛毛雨，需不斷地滋潤(rùn)n教師在傳授知識(shí)和技術(shù)的

27、過(guò)程中，偶爾會(huì)教師在傳授知識(shí)和技術(shù)的過(guò)程中，偶爾會(huì)傳授教訓(xùn)傳授教訓(xùn)，n但這種教訓(xùn)如果沒(méi)有但這種教訓(xùn)如果沒(méi)有經(jīng)過(guò)你的親身體驗(yàn)經(jīng)過(guò)你的親身體驗(yàn)，不會(huì)變成有用，不會(huì)變成有用的經(jīng)驗(yàn)。的經(jīng)驗(yàn)。n知識(shí)沒(méi)有教訓(xùn)作為根基，只能是紙上談兵。知識(shí)沒(méi)有教訓(xùn)作為根基，只能是紙上談兵。n上課、讀書(shū)、復(fù)習(xí)、做作業(yè)、討論、做實(shí)驗(yàn)、自己編程上課、讀書(shū)、復(fù)習(xí)、做作業(yè)、討論、做實(shí)驗(yàn)、自己編程序、上機(jī)調(diào)試排錯(cuò)序、上機(jī)調(diào)試排錯(cuò)是絕對(duì)必要的是絕對(duì)必要的n那種抄別人作業(yè)、考試作弊、不上課不看書(shū)，那種抄別人作業(yè)、考試作弊、不上課不看書(shū)，是沒(méi)是沒(méi)有希望的。一個(gè)作弊的民族怎么可能進(jìn)步和強(qiáng)大呢？有希望的。一個(gè)作弊的民族怎么可能進(jìn)步和強(qiáng)大呢？n提

28、倡學(xué)習(xí)中互相討論、辯論、提出不同的方法。提倡學(xué)習(xí)中互相討論、辯論、提出不同的方法。 2022-3-1525學(xué)習(xí)方法學(xué)習(xí)方法n記住，數(shù)學(xué)以及其他理論學(xué)科的書(shū)，不能讀記住，數(shù)學(xué)以及其他理論學(xué)科的書(shū)，不能讀得太快，也得太快，也不能期望讀一遍就全弄懂不能期望讀一遍就全弄懂。n生活的根基不僅包括我們得到的所有的答案，生活的根基不僅包括我們得到的所有的答案，而且而且還應(yīng)該包括我們提出的所有問(wèn)題還應(yīng)該包括我們提出的所有問(wèn)題。2022-3-1526學(xué)習(xí)方法學(xué)習(xí)方法n輔導(dǎo)答疑輔導(dǎo)答疑n這是任課教師與學(xué)生這是任課教師與學(xué)生直接交流、溝通思想直接交流、溝通思想的時(shí)間。對(duì)學(xué)的時(shí)間。對(duì)學(xué)生一視同仁應(yīng)當(dāng)是教師的基本心理，

29、而善待每個(gè)學(xué)生是生一視同仁應(yīng)當(dāng)是教師的基本心理，而善待每個(gè)學(xué)生是教師應(yīng)當(dāng)堅(jiān)持的教育原則。教師應(yīng)當(dāng)堅(jiān)持的教育原則。n充分利用好答疑時(shí)間，是與老師交流的機(jī)會(huì)，會(huì)獲得意充分利用好答疑時(shí)間，是與老師交流的機(jī)會(huì)，會(huì)獲得意想不到的東西想不到的東西n教師為你解答經(jīng)你努力尚未弄懂的問(wèn)題。教師為你解答經(jīng)你努力尚未弄懂的問(wèn)題。沒(méi)有經(jīng)你思考沒(méi)有經(jīng)你思考的習(xí)題、問(wèn)題最好暫時(shí)不問(wèn)，否則收獲不大的習(xí)題、問(wèn)題最好暫時(shí)不問(wèn)，否則收獲不大n教師不要立即暴露你的全部秘密教師不要立即暴露你的全部秘密讓學(xué)生在你說(shuō)出來(lái)讓學(xué)生在你說(shuō)出來(lái)之前先去猜之前先去猜盡量讓他們自己去找出來(lái)。你可以給一盡量讓他們自己去找出來(lái)。你可以給一些提示，創(chuàng)造一

30、個(gè)稍好的環(huán)境，讓學(xué)生自己去發(fā)現(xiàn)！增些提示，創(chuàng)造一個(gè)稍好的環(huán)境，讓學(xué)生自己去發(fā)現(xiàn)！增強(qiáng)學(xué)生的信心。強(qiáng)學(xué)生的信心。n把老師看成朋友或者長(zhǎng)者，這時(shí)除談業(yè)務(wù)外，談理想、把老師看成朋友或者長(zhǎng)者，這時(shí)除談業(yè)務(wù)外，談理想、人生、道德、責(zé)任、如何做人人生、道德、責(zé)任、如何做人2022-3-15272022-3-1528教材及主要參考書(shū)目教材及主要參考書(shū)目n王義和王義和, 離散數(shù)學(xué)引論離散數(shù)學(xué)引論, 哈爾濱工業(yè)大學(xué)哈爾濱工業(yè)大學(xué)出版社出版社, 2000.3. nKenneth.Rosen著著,袁崇義袁崇義, 屈婉玲等譯屈婉玲等譯,離離散數(shù)學(xué)及其應(yīng)用散數(shù)學(xué)及其應(yīng)用, ,機(jī)械工業(yè)出版社機(jī)械工業(yè)出版社,2007.6.

31、寄語(yǔ)寄語(yǔ)n要主動(dòng)學(xué)習(xí)要主動(dòng)學(xué)習(xí)n不要苛求課程、老師和環(huán)境，他不要苛求課程、老師和環(huán)境，他/她她/它們只是資源它們只是資源n目標(biāo)確定后要善于利用各種資源目標(biāo)確定后要善于利用各種資源n注重對(duì)自己能力的培養(yǎng)注重對(duì)自己能力的培養(yǎng)n學(xué)會(huì)學(xué)會(huì)做人做人,樂(lè)于助人樂(lè)于助人,多為別人著想多為別人著想,可以獲取友誼可以獲取友誼n朋友是資源，可以終生受益朋友是資源，可以終生受益n學(xué)會(huì)安排自己的時(shí)間學(xué)會(huì)安排自己的時(shí)間n時(shí)間就像海綿里的水，只要肯擠，總會(huì)有的。貴在時(shí)間就像海綿里的水，只要肯擠，總會(huì)有的。貴在恒恒。n學(xué)會(huì)利用各種資源學(xué)會(huì)利用各種資源提高自己提高自己n學(xué)校的、家庭的、社會(huì)的學(xué)校的、家庭的、社會(huì)的n上學(xué)期間利

32、用資源的上學(xué)期間利用資源的唯一目的唯一目的就是提高自己就是提高自己n不要沉迷于網(wǎng)絡(luò)聊天與游戲不要沉迷于網(wǎng)絡(luò)聊天與游戲2022-3-1529第一章第一章 集合及其運(yùn)算集合及其運(yùn)算重點(diǎn)：重點(diǎn)： 概念概念 ：集合、差、對(duì)稱差、笛卡兒乘積、有窮集基數(shù)。：集合、差、對(duì)稱差、笛卡兒乘積、有窮集基數(shù)。 方法方法 ：證明兩個(gè)集合相等的方法必考，必須掌握；：證明兩個(gè)集合相等的方法必考，必須掌握； 基本的計(jì)數(shù)法則及容斥原理在古典概率論中的應(yīng)用?；镜挠?jì)數(shù)法則及容斥原理在古典概率論中的應(yīng)用。 應(yīng)用應(yīng)用 ：古典概率模型、跳舞問(wèn)題的數(shù)學(xué)模型。：古典概率模型、跳舞問(wèn)題的數(shù)學(xué)模型。難點(diǎn)：難點(diǎn)：容斥原理在古典概率論中的應(yīng)用容

33、斥原理在古典概率論中的應(yīng)用。School of Computer Science & Technology Harbin Institute of Technology2022-3-15302022-3-1531第一章第一章 主要內(nèi)容主要內(nèi)容n1集合（集合（set）、屬于關(guān)系）、屬于關(guān)系、集合的表示方法、空集、集合的表示方法、空集n2子集（子集（subset）、兩個(gè)集合相等，冪集（）、兩個(gè)集合相等，冪集（power set）、）、集族（以集為元素的集）、證明兩個(gè)集相等的方法集族（以集為元素的集）、證明兩個(gè)集相等的方法n3集合的運(yùn)算：并集合的運(yùn)算：并(union)、交（、交（inters

34、ection）、差、差（subraction）、對(duì)稱差（、對(duì)稱差（symmetric difference），各，各自的性質(zhì)及相互聯(lián)系自的性質(zhì)及相互聯(lián)系n4求補(bǔ)（求補(bǔ)（complement）運(yùn)算）運(yùn)算C( ，Cs)及及DeMorgan律律n5迪卡爾積（迪卡爾積（Cartesian product）及其性質(zhì)）及其性質(zhì)n6有限集合的基數(shù)（有限集合的基數(shù)（cardinal number）、基本的計(jì)數(shù)）、基本的計(jì)數(shù)法則、容斥原理法則、容斥原理 2022-3-1532第一章小結(jié)第一章小結(jié)n1、概念：集、子集、冪集、概念：集、子集、冪集、 、c c、 ，基數(shù)，基數(shù)n2、結(jié)論：運(yùn)算的性質(zhì)、計(jì)數(shù)法則、容斥原、結(jié)論：運(yùn)算的性質(zhì)、計(jì)數(shù)法則、容斥原理理n*3、方法：證明兩個(gè)集合相等的方法；邏、方法：證明兩個(gè)集合相等的方法；