動(dòng)機(jī)與目標(biāo)
很多大學(xué)都開設(shè)離散數(shù)學(xué)課程。上該課程的學(xué)生來自多個(gè)專業(yè)，其中多的是來自計(jì)算機(jī)科學(xué)專業(yè)的學(xué)生。在國(guó)家科學(xué)基金會(huì)一的支持下，作為達(dá)特茅斯（Dartmouth）學(xué)院跨學(xué)科數(shù)學(xué)項(xiàng)目的一部分，我們提出開設(shè)一門離散數(shù)學(xué)課程來滿足計(jì)算機(jī)科學(xué)專業(yè)學(xué)生的需求。在分析想讓計(jì)算機(jī)科學(xué)專業(yè)的學(xué)生了解哪些離散數(shù)學(xué)主題，以及為什么想讓他們了解這些主題時(shí)，我們得到兩個(gè)結(jié)論。
，我們認(rèn)為一些主題對(duì)于計(jì)算機(jī)科學(xué)專業(yè)很重要，但是沒有被充分地納入傳統(tǒng)的離散數(shù)學(xué)課程中。這些主題包括遞歸樹和解決遞推關(guān)系的主定理，計(jì)算平均運(yùn)行時(shí)間和分析隨機(jī)算法的概率理論，以及強(qiáng)歸納法和結(jié)構(gòu)歸納法。
第二，我們認(rèn)為對(duì)于計(jì)算機(jī)科學(xué)專業(yè)學(xué)生很重要的每個(gè)離散數(shù)學(xué)主題，在計(jì)算機(jī)科學(xué)里都有一個(gè)很有啟發(fā)性的主題，上述門或者第二門計(jì)算機(jī)科學(xué)入門課程的學(xué)生可以理解這些主題。我們感覺這樣安排就能回答在應(yīng)用數(shù)學(xué)課程中學(xué)生經(jīng)常會(huì)問的問題：為什么我們必須學(xué)習(xí)這些？因此，我們決定寫一本針對(duì)計(jì)算機(jī)科學(xué)專業(yè)學(xué)生的教科書，目標(biāo)是為計(jì)算機(jī)科學(xué)專業(yè)學(xué)生提供必要的數(shù)學(xué)基礎(chǔ)，并且通過學(xué)生在計(jì)算機(jī)科學(xué)學(xué)習(xí)的開始階段就能夠理解的計(jì)算機(jī)科學(xué)問題來啟發(fā)他們學(xué)習(xí)這本教科書。
一基金資助號(hào)為DUE-9552462。
二我們的大多數(shù)學(xué)生已經(jīng)學(xué)習(xí)過微積分。在一些地方我們會(huì)使用初級(jí)的導(dǎo)數(shù)，并且在概率部分的選修小節(jié)中，我們使用自然對(duì)數(shù)、指數(shù)函數(shù)和初級(jí)的冪級(jí)數(shù)。如果忽略少數(shù)使用導(dǎo)數(shù)的證明和問題，以及概率部分的選修小節(jié)，教師可以不涉及微積分。

在許多高校的計(jì)算機(jī)科學(xué)系，離散數(shù)學(xué)是學(xué)生的專業(yè)必修課之一，甚至是門計(jì)算機(jī)科學(xué)課程的先修課。在這種情況下，教師面臨一種困境講授純數(shù)學(xué)的概念，很少或者完全沒有顯式的計(jì)算機(jī)應(yīng)用，或者講授計(jì)算機(jī)科學(xué)的例子來營(yíng)造一種針對(duì)計(jì)算機(jī)科學(xué)專業(yè)學(xué)生的語境。對(duì)于種講課方式，學(xué)生會(huì)抱怨在學(xué)習(xí)門計(jì)算機(jī)科學(xué)課程之前被迫學(xué)習(xí)太多不相干的數(shù)學(xué)知識(shí)。對(duì)于第二種講課方式，教師（通常是數(shù)學(xué)家）要嘗試給可能從來沒有寫過程序的學(xué)生解釋相當(dāng)高級(jí)的計(jì)算機(jī)科學(xué)主題，比如散列、二叉樹和遞歸程序等。即使在好的情況下，這種方式也明顯降低了數(shù)學(xué)的深度�；�于我們的分析，產(chǎn)生了一種不同的講課方式，即開設(shè)一門學(xué)生稍后學(xué)習(xí)的課程。盡管我們沒有明確假定學(xué)生已經(jīng)學(xué)過微積分，但是假定學(xué)生了解并且能夠熟練使用求和符號(hào)、對(duì)數(shù)和指數(shù)函數(shù)。因此，熟悉微積分知識(shí)是很有幫助的二。這意味著學(xué)生要在計(jì)算機(jī)科學(xué)的入門課中見過遞歸程序之后再學(xué)習(xí)這門課。這門課好和數(shù)據(jù)結(jié)構(gòu)課程同時(shí)學(xué)習(xí)或者在其之后學(xué)習(xí)，不過我們會(huì)通過例子解釋所使用的數(shù)據(jù)結(jié)構(gòu)。因此，數(shù)據(jù)結(jié)構(gòu)課程不是這門課的先導(dǎo)課程。
我們覺得這樣安排離散數(shù)學(xué)課程有很多優(yōu)勢(shì)，例如：
?學(xué)生已經(jīng)有了較為深入的問題解決、算法和編程的經(jīng)驗(yàn)。
?學(xué)生已經(jīng)學(xué)習(xí)或者準(zhǔn)備學(xué)習(xí)一些重要的計(jì)算機(jī)科學(xué)概念，比如散列、遞歸、排序和搜索，以及基本的數(shù)據(jù)結(jié)構(gòu)。
?學(xué)生對(duì)計(jì)算機(jī)科學(xué)有足夠的了解，已經(jīng)知道一些啟發(fā)性例子，或者這些例子對(duì)于他們而言足夠簡(jiǎn)單易懂。例如：
a散列可以用于啟發(fā)概率的學(xué)習(xí)。a分析遞歸程序，比如歸并和快速排序，可以啟發(fā)學(xué)習(xí)遞推關(guān)系和相應(yīng)的解決方法。
a分析在一個(gè)尋找線性表中小元素的程序中，我們期望多久找到一個(gè)新的小值，可以啟發(fā)學(xué)習(xí)期望的線性性質(zhì)和調(diào)和數(shù)。
a二叉樹可以用于教授結(jié)構(gòu)遞歸法，也可以作為圖的特例啟發(fā)樹的學(xué)習(xí)。
根據(jù)我們自己的授課經(jīng)驗(yàn)，離散數(shù)學(xué)課程是算法課的先導(dǎo)課程，學(xué)生經(jīng)常在結(jié)束離散數(shù)學(xué)課程不久后就開始學(xué)習(xí)算法。這樣，他們會(huì)發(fā)現(xiàn)自己可以直接使用剛學(xué)過的離散數(shù)學(xué)知識(shí)。
教學(xué)理念
這本教科書是以教學(xué)活動(dòng)為驅(qū)動(dòng)，以練習(xí)的形式體現(xiàn)的。教學(xué)內(nèi)容通過說明和教學(xué)活動(dòng)的延伸來形象地呈現(xiàn)。對(duì)于學(xué)生，使用這本書的有效方法是認(rèn)真參與教學(xué)活動(dòng)，而不是只閱讀那些教學(xué)活動(dòng)后面的解釋。這些教學(xué)活動(dòng)在課堂中以小組的形式完成。因此，我們建議學(xué)生形成小組，一起解決安排在課外進(jìn)行的教學(xué)活動(dòng)。我們希望通過這種設(shè)計(jì)來幫助學(xué)生培養(yǎng)數(shù)學(xué)思維。通過了解關(guān)于本科生怎樣學(xué)習(xí)數(shù)學(xué)，我們得出以下幾個(gè)結(jié)論。
?那些主動(dòng)發(fā)現(xiàn)自己所學(xué)內(nèi)容的學(xué)生（從而參與到所謂的主動(dòng)學(xué)習(xí)中）比那些不主動(dòng)學(xué)習(xí)的學(xué)生記住概念的時(shí)間要長(zhǎng)得多，他們也更有可能在課堂之外運(yùn)用這些概念。
?當(dāng)學(xué)生在一個(gè)小組和同學(xué)一起學(xué)習(xí)，而不是在一個(gè)有導(dǎo)師的更大的班級(jí)中學(xué)習(xí)時(shí)，他們更有可能提出問題，直到他們理解一個(gè)主題。（然而，情況并非如此。很多學(xué)生需要適應(yīng)他們的小組之后再提出問題，因?yàn)樗麄儞?dān)心會(huì)拖慢其他人的進(jìn)度。我們嘗試提高舒適度，允許學(xué)生選擇學(xué)習(xí)小組，并且根據(jù)出席情況允許或者要求學(xué)生更換不同的小組。）
?后，通過為他人解釋概念來幫助學(xué)生進(jìn)一步理解概念，并且讓學(xué)生熟悉數(shù)學(xué)語言。
這本書的內(nèi)容可用于一門四個(gè)學(xué)期的課程。在達(dá)特茅斯學(xué)院，我們使用這本書的課程節(jié)奏比較快，一周上三天且僅僅上九周，卻涵蓋了本書除了后幾節(jié)和一部分帶星號(hào)的內(nèi)容之外的所有內(nèi)容。
證明的作