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

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