資夢

離散數學

前言

離散數學是交大資工大一下的必修課程離散數學所涵蓋的範圍非常的廣,而正如維基百科所述:「離散數學近幾十年來因為它在電腦科學上的應用備受關注。由於運算對象是離散的,所以電腦科學的數學基礎基本上也是離散的。我們可以說電腦科學的數學語言就是離散數學。」系上使用的教科書是《Discrete Mathematics and Its Applications》,在資工往後的各種數學課程中都可以看到它的影子。一學期的課程中,涵蓋的內容包括邏輯學集合論演算法組合數學遞迴數論圖論布林代數等等。由於是總括性的課程,很多主題主要是在介紹基本的定義,而不會有太過深入的應用。有些內容也許高中也有提到,但在這門課中會做更嚴謹的推導。

簡介

邏輯學是數學推論證明的基礎,是理解數學的基礎之一,在課程中也會帶到 Mathematical induction 等證明的方法,在其後的數學課程中常會使用,若要深入研究,系上也有數理邏輯的課程可供選修。Sets, Graphs, Functions 這些經常被使用的觀念,也會在這堂課裡教授,其中 Graphs 對新生而言可能較不熟悉,卻是往後課程中大量使用的概念。演算法可說是電腦科學的核心之一,也有自己獨立的一門課程。在離散這堂課裡,會介紹演算法的定義,以及幾種簡單的演算法。遞迴的概念在程式設計中非常常見,而在分析演算法效率時,也會用到解遞迴式的技巧。數論主要會介紹和密碼學有密切相關的部份,像是 Chinese remainder theorem, RSA等等。

這是一門重定義、理解、以及證明的數學課,相對於實做導向的程式課或者是計算為主的微積分等課程有很大的不同,在學習時應將每個概念與證明完整理解。筆者自己以及許多同學在學習這堂課時,經常對所學感到不踏實,直到後來學習更深入的課程時才了解離散數學基礎的重要。若有時間,可嘗試閱讀延伸課程之教科書,或許能對離散的學習帶來一些幫助。

參考