姓名: 許瑞麟

Size: px

Start display at page:

Download "姓名: 許瑞麟"

侯严
4 years ago
Views:

1 計算機數學的計算理論與圖形第一屆數苗計畫暑期營台北市立第一女子高級中學 0..

2 許瑞麟學經歷 : 台北市立建國高級中學國立清華大學數學系學士美國北卡羅萊納州立大學博士美國紐澤西州 AT&T 貝爾實驗室研究員國立成功大學數學系暨應用數學研究所教授

3 許瑞麟國科會雲嘉南資賦優異高中生培育計畫共同主持人地方 / 全國 / 國際科展評審委員台南一中科學班計畫協同主持人 / 大學端導師大考中心試題評鑑委員教育部公費留學考試委員

4 演講摘要傳統數學教學方法是序列式的. 先講數, 再講函數, 然後三角函數, 指數對數, 空間向量等依序進行. 課綱僅是將一些應用性的題材先教, 基本上還是序列式的. 多年來沒人質疑這些順序的合理性. 也沒有證據指出這些是好的序列. 大家多半就是教 ( 學 ) 習慣了.

5 演講摘要我在高中端演講多年的觀察發現, 學生縱使因此學到數學的結構與邏輯, 卻對所學到的學問沒有感覺. 縱使學到數學的框架與技巧, 對於駕馭數學的能力還是相當薄弱. 換句話說, 這樣的數學教育, 並沒有在學生心中著根!

6 演講摘要本演講提出一套以目標導向的數學教學方法, 用明確主題為討論主軸. 第一單元以加減乘除四則運算帶出計算機數學的核心概念計算複雜度分析 (Computational Complexity). 自然而然的帶出直線, 拋物線, 指數函數, 與對數函數.

7 演講摘要第二單元以最短路徑問題帶出圖論的核心概念計數的方法 (Method of Enumeration). 自然而然的帶出排列組合的核心概念系統性的智慧計數的方法. 讓學生從使用數學去學數學, 將 `` 學和 `` 用結合. 跟傳統先學數學, 日後再找機會應用數學的思維, 截然不同.

8 演講摘要而且, 每一主題, 都一定要講出一個核心價值, 並且以批判性思維加以檢視. 而這是科學的最基本的精神! 我們的目標是一套全新有創見的數學教學教材與教學方法. 我們期望全面提升台灣下一代的數學素養與競爭力. 在此感謝北一女中的邀請, 同時感謝國立成功大學文教基金會支持贊助.

9 加減乘除四則運算

10 給定兩個正整數, 比如, a=, b=. 計算 a+b, a-b, axb, a/b. 這一類的題目, 大部分的學生都曾有計算錯誤的經驗. 會算但是算錯, 是一件相當可惜的事! 但是卻很少學生去正視這個問題. 0

11 我們可以讓學生去查資料, 或上網去 google, 很快就可以發現加減乘除四則運算, 除了國小教過的直式運算外, 從古到今有非常多不同算法. 還不包括中國傳統的珠算. 因此, 可以以計算能力做主題, 教高中生如何以科學的方式去分析各種不同加減乘除計算方法的優缺點.

12 a=, b= 的四則運算這個題目是多位數 (multiple digits) 的四則運算, 是靠一系列的單位數 (single digit) 計算來完成. 比如, 計算 a+b 主要是執行 +, +, + 和 + 四次單位數加法. 會犯錯多半是 + 或 + 這種進位後, 另外產生寫進和寫進的隱形的加法, 以心算來執行.

13 加法運算分析因此, 如果妳用以下的算式, 就相對不容易犯錯.

14 +

15 +

16 +

17 +

18 +

19 +

20 +

21 + 這裡會產生次的進位加法

22 + 以上, 直式加法總共使用次單位數加法與次進位加法, 共 +=x 次單位加法

23 加法運算量分析一個 n 位數加上一個 n 位數, 至多需要執行 n 次的 ( 單位數計算 ). 其中 n 次是一定要做的加法, 外含另一次的 n 位數加上 n 位數最多 n 次的進位加法.

24 直式乘法運算量分析一個 n 位數乘上一個 n 位數, 例如 : *, 至多需要執行 n - 次的 ( 單位數計算 ).

25 x

26 x

27 x

28 x

29 x

30 x

31 x

32 x 位數乘上位數, 總共使用 : 次單位乘法與次位數加位數的至多次單位加法

33 x 也是需要 : 次單位乘法與次位數加位數的至多次單位加法

34 x 也是需要 : 次單位乘法與次位數加位數的至多次單位加法

35 x

36 x

37 x 0 0 0

38 x 0 0 0

39 x 0 0 0

40 x 共需最多次位數加位數的加法, 計算量為至多 x= 個單位數計算.

41 (n 位數乘 n 位數 ) n 位數 x n 位數 n+ 位數 n+ 位數 n+ 位數 n+ 位數 n+ 位數

42 (n 位數乘 n 位數 ) n 位數 x n 位數 n+ 位數 n+ 位數 n+ 位數 n+ 位數每次使用至多 n( 乘 )+n( 加 )=n 次單位運算 n+ 位數

43 (n 位數乘 n 位數 ) n 位數 x n 位數 n+ 位數 n+ 位數 n+ 位數 n+ 位數每次使用至多 n( 乘 )+n( 加 )=n 次單位運算 n+ 位數共 n 次, 需要至多 n*n=n 次單位運算

44 (n 位數乘 n 位數 ) n 位數 x n 位數 n+ 位數 n+ 位數 n+ 位數 n+ 位數 n+ 位數共有 n- 個綠色框, 每個框是 n+ 位數加 n+ 位數, 共需 (n-)*[(n+)]=n - 次單位運算

45 直式乘法運算量分析一個 n 位數乘上一個 n 位數, 分解成 (i) n 位數乘上位數 : 每次運算量 n, 共 n 次至多 n (ii) 乘完以後相加 : (n-) 次的 [(n+) 位數 +(n+) 位數 ], 共 : n - (i) 及 (ii) 合併至多共需要執行 n - 次的 ( 單位數計算 ).

46 直式加法和直式乘法運算量比較 y=n - y=n

47 連加法運算分析既然加法的運算量 ( 一次式 ) 比上乘法 ( 二次式 ) 少那麼多, 那麼像是 * 可以用連加次來算會比較快嗎? ( 我們稱這種方法為連加法 )

48 連加法運算分析

49 實際電腦運算數據使用 CPU :. GHz ( 大約每秒可計算 0^ 次加法 ) ; RAM :.0 GB 利用建構式連加法計算 0*0 共使用了. 秒計算 0*0 共使用了. 秒計算 0*0 使用了分秒計算 0*0 使用分秒

50 0 數字再稍大一些的話, 妳都可以贏過超級電腦! 電腦的確非常快. 但是, 計算的效率, 絕大部分是決定於所使用的方法, 而不在於使用多先進的科技!

51 連加法和直式乘法運算量比較 y=n*0 n y=n -

52 指數函數的圖形

53 e=. 指數函數的成長有多快? 在 x 軸上距離原點 0cm 處, 亦即 x=0, 其 y 軸的對應高度在 e 0. 0 km 冥王星 Pluto (The God of underworld) 距離地球亦僅只有 0 km. 換言之, 以現今人類的太空科技, 是沒有辦法畫出指數函數在 x > 0 cm 之後的指數函數圖形.

54 近百年的氣溫變化 ( 觀測 )

55 百萬分之一有多小?? 一般認為地球歷史有億年. 最古老的埃及中國文明距今千年, 這個比例就是將近百萬分之一. 如果把地球歷史億年縮為年, 那麼分鐘大約等於地球歷史的年. 百萬分之一大約就是一年的最後 0 秒! 夏朝就是在月日時分 0 秒之後才發生. 恐龍大約在月日出現, 月日中午還沒來的及過聖誕夜就滅絕了. 當我們跨年倒數時, 相當於我們從魏晉南北朝開始倒數, 每一兩秒就過一個朝代, 從隋, 唐, 五代十國, 宋, 元, 明, 清, 到現在.

57 目前最快的乘法算法兩個 n 位整數相乘, 目前已知最快的算法需要的計算量是. 最慢也要 order n. 這個要利用到 Fast Fourier Transform 才算得出來的. 要在高中端學快速傅立葉轉換並非不可能. 我們可以不學理論, 但是透過好好觀察例子, 就可以看出最核心的概念是隸美孚定理和同餘概念.

58 目標導向式教學法的特點因為每個人都有使用手機和計算錯誤的經驗, 卻沒料到這些經驗和學過的數學有如此密切的關連. 專注於計算效能這個議題, 可以從國小的加減乘除, 貫穿到高一的直線, 拋物線, 指對數函數, 直通研究所的傅立葉轉換. 我把這樣的學習方法稱為目標導向式. 其特點是知識進程和傳播速度極快! 而目前課本序列式法 : 缺乏明確對應的應用目標, 所舉的例子相當的偏重數學技巧訓練, 無法讓學生引起共鳴.

59 最短路徑法

60 0 上圖是一個網路, 只能沿著箭頭的方向前進我們的問題是找出從到的最短路徑

61 0 搜尋所有可能的路徑, 一般而言有二種搜尋方法方法一為深度搜尋法方法二為廣度搜尋法

62 0 深度搜尋法 : 首先從網路起點

63 0 深度搜尋法 : 首先從網路起點沿著其中一條路徑走到網路終點此即為其中一條可能的路徑, 叫 P=, 路徑長度為 +++=

64 0 接著我們再往回搜尋直到有可以叉開的路為止

65 0 接著我們再往回搜尋直到有可以叉開的路為止當從退回時, 結點沒有叉路, 繼續往回退

66 0 接著我們再往回搜尋直到有可以叉開的路為止當從退回時, 結點沒有叉路, 繼續往回退直到節點時, 有叉路 ( 沿著邊 )

67 0 接著我們再往回搜尋直到有可以叉開的路為止當從退回時, 結點沒有叉路, 繼續往回退直到節點時, 有叉路 ( 沿著邊 ), 我們再從此叉路找出一條路徑此為我們搜尋的第二條路徑 P=, 且路徑長度為 ++++=

68 0 重複剛剛的操作, 可以往回到結點找到叉路, 並找到另一條路徑為 P=, 路徑長度為 +++=

69 0 重複剛剛的操作, 可以往回到結點找到叉路, 並找到另一條路徑為 P=, 路徑長度為 +++= 下一個搜尋到的路徑應為 P=, 路徑長度為 +++0=

70 0 接著為 P=, 路徑長度為 ++++0=

71 0 接著為 P=, 路徑長度為 ++++0= P=, 路徑長度為 +++=

72 0 一開始就沿著邊的所有可能路徑搜尋完後, 就搜尋一開始沿著邊的路徑

73 0 一開始就沿著邊的所有可能路徑搜尋完後, 就搜尋一開始沿著邊的路徑同樣地, 找出一條路徑, 叫 P=, 路徑長度為 ++++=

74 0 再來為 P=, 路徑長度為 +++=

75 0 再來為 P=, 路徑長度為 +++= P=, 路徑長度為 +++0=

76 0 再來為 P=, 路徑長度為 +++= P=, 路徑長度為 +++0= P0=, 路徑長度為 ++++0=

77 0 再來為 P=, 路徑長度為 +++= P=, 路徑長度為 +++0= P0=, 路徑長度為 ++++0= P=, 路徑長度為 +++=

78 0 再來為 P=, 路徑長度為 +++= P=, 路徑長度為 +++0= P0=, 路徑長度為 ++++0= P=, 路徑長度為 +++= P=, 路徑長度為 +++0=

79 0 再來為 P=, 路徑長度為 +++= P=, 路徑長度為 +++0= P0=, 路徑長度為 ++++0= P=, 路徑長度為 +++= P=, 路徑長度為 +++0=

80 0 從深度搜尋法可以搜尋到所有的路徑 : P=, 長 P=, 長 P=, 長 P=, 長 P=, 長 P=, 長 P=, 長 P=, 長 P=, 長 P0=, 長 P=, 長 P=, 長 P=, 長

81 0 用深度搜尋法可知, 此網路的最短路徑為 P=, 路徑長度為 ++++=

82 0 用深度搜尋法可知, 此網路的最短路徑為 P=, 路徑長度為 ++++=, 與最長路徑為 P=, 路徑長度為 ++++0=

83 0 廣度搜尋法 : 同樣從網路起點

84 0 廣度搜尋法 : 同樣從網路起點, 可發現從起點出發, 有二條路徑可選擇, 與

85 0 觀察路徑, 下一個節點可能是或

86 0 觀察路徑, 下一個節點可能是或再從路徑往後看, 發現沒有叉路了, 此即為一個路徑 Q=, 路徑長為 +++=

87 0 觀察路徑, 下一個節點可能是或再從路徑往後看, 發現沒有叉路了, 此即為一個路徑 Q=, 路徑長為 +++= 再從路徑來看, 有四條叉路

88 0 觀察路徑, 下一個節點可能是或再從路徑往後看, 發現沒有叉路了, 此即為一個路徑 Q=, 路徑長為 +++= 再從路徑來看, 有四條叉路從路徑往後看, 沒有叉路了, 即為一個路徑 Q=, 路徑長為 ++++=

89 0 接著是 Q=, 路徑長為 +++=

90 0 接著是 Q=, 路徑長為 +++= Q=, 路徑長為 +++0=

91 0 沿著到後, 有二條叉路

92 0 沿著到後, 有二條叉路這裡有二條路徑 : Q=, 路徑長為 ++++0=

93 0 沿著到後, 有二條叉路這裡有二條路徑 : Q=, 路徑長為 ++++0= Q=, 路徑長為 +++=

94 0 一開始沿著的話, 有二條路徑可以選擇 : 與

95 0 一開始沿著的話, 有二條路徑可以選擇 : 與從路徑來看, 有四條叉路

96 0 如同前面, 我們可以找到路徑 : Q=, 路徑長為 ++++=

97 0 如同前面, 我們可以找到路徑 : Q=, 路徑長為 ++++= Q=, 路徑長為 +++=

98 0 如同前面, 我們可以找到路徑 : Q=, 路徑長為 ++++= Q=, 路徑長為 +++= Q=, 路徑長為 +++0=

99 0 如同前面, 我們可以找到路徑 : Q=, 路徑長為 ++++= Q=, 路徑長為 +++= Q=, 路徑長為 +++0= Q0=, 路徑長為 ++++0=

100 0 如同前面, 我們可以找到路徑 : Q=, 路徑長為 ++++= Q=, 路徑長為 +++= Q=, 路徑長為 +++0= Q0=, 路徑長為 ++++0=

101 0 Q=, 路徑長為 +++0=

102 0 Q=, 路徑長為 +++0= Q=, 路徑長為 ++=

103 0 從深度搜尋法可以搜尋到所有的路徑 : Q=, 長 Q=, 長 Q=, 長 Q=, 長 Q=, 長 Q=, 長 Q=, 長 Q=, 長 Q=, 長 Q0=, 長 Q=, 長 Q=, 長 Q=, 長

104 0 用廣度搜尋法可知, 此網路的最短路徑為 Q=, 路徑長為 ++++=

105 0 用廣度搜尋法可知, 此網路的最短路徑為 Q=, 路徑長為 ++++= 與最長路徑為 Q=, 路徑長為 ++++0=

106 0 然而, 一般常識性的走法, 都會在每一個節點面臨若干種選擇時, 挑選最佳最便捷的走法

107 0 然而, 一般常識性的走法, 都會在每一個節點面臨若干種選擇時, 挑選最佳最便捷的走法比如, 剛開始在出發時, 面臨和兩種選擇, 一般而言會挑

108 0 然而, 一般常識性的走法, 都會在每一個節點面臨若干種選擇時, 挑選最佳最便捷的走法比如, 剛開始在出發時, 面臨和兩種選擇, 一般兒言會挑到了以後, 面對和, 這兩種選擇差距很大, 一般人很難抗拒去挑選

109 0 於是, 到了就選, 最後走

110 0 於是, 到了就選, 最後走用此短視近利法挑選路徑, 竟得到一條路徑長最長的一條

111 0 接著我們討論 Backward 方法 ( 從網路終點往回推得最短路徑法 )

112 0 定義符號 : f(i) 定義 f(i) 為從節點 i 到網路終端 ( 節點 ) 的最短路逕的長度 ( 例如 f()=0) 定義符號 : Cij 定義 Cij 為從節點 i 到節點 j 的距離 ( 例如 C=)

113 0 首先我們可知 f()=0

114 0 首先我們可知 f()=0 接著往回推, 可得 f()=, f()=0

115 0 f()=0 f()=0 f()= f()=min{c+f(),c+f()} =min{,}=(=c+f())

116 0 f()=0 f()=0 f()= f()=min{c+f(),c+f()} =min{,}=(=c+f()) f()=min{c+f()}=0(=c+f())

117 0 f()=0 f()=0 f()= f()=min{c+f(),c+f()} =min{,}=(=c+f()) f()=min{c+f()}=0(=c+f()) f()=min{c+f(),c+f(),c+f(),c+f()} =min{+0,+,+0,+}=(=c+f())

118 0 f()=0 f()=0 f()= f()= (=C+f()) f()=0(=c+f()) f()=(=c+f()) f()=min{c+f(),c+f()} =min{+,+}=(=c+f())

119 0 f()=0 f()=0 f()= f()= (=C+f()) f()=0(=c+f()) f()=(=c+f()) f()=min{c+f(),c+f()} =min{+,+}=(=c+f()) f()=min{c+f(),c+f()} =min{+0,+}=0(=c+f())

120 0 f()=0 f()=0 f()= f()= (=C+f()) f()=0(=c+f()) f()=(=c+f()) f()=min{c+f(),c+f()} =min{+,+}=(=c+f()) f()=min{c+f(),c+f()} =min{+0,+}=0(=c+f()) f()=min{c+f(),c+f()} =min{+0,+}=(=c+f())

121 0 f()= (=C+f()) f()=0 (=C+f()) f()= (=C+f()) f()= (=C+f()) f()=0 (=C+f()) f()= (=C+f()) f()= (=C) f()=0 (=C) f()=0 由此可得知從每個節點到網路終點的最短路徑長, 與最短路徑

122 0 f()= (=C+f()) f()=0 (=C+f()) f()= (=C+f()) f()= (=C+f()) f()=0 (=C+f()) f()= (=C+f()) f()= (=C) f()=0 (=C) f()=0 例如, 由出發, 到的最短路徑上, 下一個節點則為

123 0 f()= (=C+f()) f()=0 (=C+f()) f()= (=C+f()) f()= (=C+f()) f()=0 (=C+f()) f()= (=C+f()) f()= (=C) f()=0 (=C) f()=0 例如, 由出發, 到的最短路徑上, 下一個節點則為再來依序為

124 0 f()= (=C+f()) f()=0 (=C+f()) f()= (=C+f()) f()= (=C+f()) f()=0 (=C+f()) f()= (=C+f()) f()= (=C) f()=0 (=C) f()=0 例如, 由出發, 到的最短路徑上, 下一個節點則為再來依序為

125 0 f()= (=C+f()) f()=0 (=C+f()) f()= (=C+f()) f()= (=C+f()) f()=0 (=C+f()) f()= (=C+f()) f()= (=C) f()=0 (=C) f()=0 例如, 由出發, 到的最短路徑上, 下一個節點則為再來依序為

126 0 f()= (=C+f()) f()=0 (=C+f()) f()= (=C+f()) f()= (=C+f()) f()=0 (=C+f()) f()= (=C+f()) f()= (=C) f()=0 (=C) f()=0 例如, 由出發, 到的最短路徑上, 下一個節點則為再來依序為

127 0 f()= (=C+f()) f()=0 (=C+f()) f()= (=C+f()) f()= (=C+f()) f()=0 (=C+f()) f()= (=C+f()) f()= (=C) f()=0 (=C) f()=0 例如, 由出發, 到的最短路徑上, 下一個節點則為再來依序為, 總路徑長為此方法即為 Backward 方法

128 0 f()= (=C+f()) f()=0 (=C+f()) f()= (=C+f()) f()= (=C+f()) f()=0 (=C+f()) f()= (=C+f()) f()= (=C) f()=0 (=C) f()=0 此 Backward 方法的優點為 : 可直接關察出從任一節點到網路終點的最短路徑與路徑長 ( 如圖為從到的最短路徑 )

129 0 再來我們討論 Forward 方法 ( 從網路起點出發的最短路徑法 )

130 0 類似地, 我們定些符號 : 定義符號 : g(i) 定義 g(i) 為從網路起點到結點 i 的最短路逕的長度 ( 例如 g()=)

131 0 首先可知 g()=0

132 0 首先可知 g()=0 接著往前推, 可得 g()=, g()=

133 0 g()=0 g()= g()= g()=min{g()+c,g()+c} =min{+,+}=(=g()+c)

134 0 g()=0 g()= g()= g()=min{g()+c,g()+c} =min{+,+}=(=g()+c) g()=min{g()+c,g()+c} =min{+,+}=(=g()+c)

135 0 g()=0 g()= g()= g()=min{g()+c,g()+c} =min{+,+}=(=g()+c) g()=min{g()+c,g()+c} =min{+,+}=(=g()+c) g()=min{g()+c,g()+c} =min{+,+}=(=g()+c)

136 0 g()=0 g()= g()= g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=min{g()+c,g()+c} =min{+,+}=(=g()+c)

137 0 g()=0 g()= g()= g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=min{g()+c,g()+c} =min{+,+}=(=g()+c) g()=min{g()+c,g()+c} =min{+,+}=(=g()+c)

138 0 g()=0 g()= g()= g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=min{g()+c,g()+c} =min{+,+}=(=g()+c) g()=min{g()+c,g()+c} =min{+,+}=(=g()+c) g()=min{g()+c,g()+c,g()+c} =min{+,+0,+}=(=g()+c)

139 0 g()=0 g()=(=c) g()= (=C) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) 由此可得知從網路起點到每個節點 i 最短路徑, 與路徑長

140 0 g()=0 g()=(=c) g()= (=C) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) 例如, 由出發, 到的最短路徑上, 節點的前一個節點為

141 0 g()=0 g()=(=c) g()= (=C) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) 例如, 由出發, 到的最短路徑上, 節點的前一個節點為, 再往前為

142 0 g()=0 g()=(=c) g()= (=C) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) 例如, 由出發, 到的最短路徑上, 節點的前一個節點為, 再往前為, 再來依序為

143 0 g()=0 g()=(=c) g()= (=C) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) 例如, 由出發, 到的最短路徑上, 節點的前一個節點為, 再往前為, 再來依序為

144 0 g()=0 g()=(=c) g()= (=C) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) 例如, 由出發, 到的最短路徑上, 節點的前一個節點為, 再往前為, 再來依序為

145 0 g()=0 g()=(=c) g()= (=C) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) 例如, 由出發, 到的最短路徑上, 節點的前一個節點為, 再往前為, 再來依序為, 總路徑長為此方法即為 Forward 方法

146 0 g()=0 g()=(=c) g()= (=C) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) g()=(=g()+c) 此 Forward 方法的優點為 : 可直接關察出從網路起點到任一節點的最短路徑與路徑長 ( 如圖為從到的最短路徑 )

147 0 現在二種演算法中都有個同樣的問題 : 如果一開始挑到的點不夠好呢? 比如說, 在 Forward 演算法中, 假如之後我們挑到的點不是, 反而直接不小心挑到呢? 我們該如何避免這樣的挑選方式?

148 0 現在二種演算法中都有個同樣的問題 : 如果一開始挑到的點不夠好呢? 比如說, 在 Forward 演算法中, 假如之後我們挑到的點不是, 反而直接不小心挑到呢? 我們該如何避免這樣的挑選方式? 答 : 可以先對網路做排序!

149 0 排序原理很簡單, 目的為避免剛剛所提出的問題的發生我們使用分區塊來排序原則有 : 從某節點出發, 下一個節點必須出現在往後的區塊中, 亦不可出現在同一區塊

150 0 排序原理很簡單, 目的為避免剛剛所提出的問題的發生我們使用分區塊來排序原則有 : 從某節點出發, 下一個節點必須出現在往後的區塊中, 亦不可出現在同一區塊以下為其中一種排序方式 :

151 區塊 0 網路起點定為區塊

152 區塊區塊 0 網路起點定為區塊下一個連接到的點定為區塊

153 區塊區塊 0 區塊網路起點定為區塊下一個連接到的點定為區塊再下一個會連接到的點定為區塊

154 區塊區塊區塊 0 網路起點定為區塊下一個連接到的點定為區塊再下一個會連接到的點定為區塊在這裡我們發現, 區塊內有衝突我們的排序原則 ( 下一個節點不可出現在同一區塊 )

155 區塊區塊區塊區塊 0 網路起點定為區塊下一個連接到的點定為區塊再下一個會連接到的點定為區塊在這裡我們發現, 區塊內有衝突我們的排序原則 ( 下一個節點不可出現在同一區塊 ) 因此將區塊拆開為與

156 區塊區塊區塊 0 區塊區塊接著同樣地, 下一個會連接到的點定為區塊

157 區塊區塊區塊區塊接著同樣地, 下一個會連接到的點定為區塊又發現, 區塊內有衝突我們的排序原則 0 區塊

158 區塊區塊區塊區塊區塊接著同樣地, 下一個會連接到的點定為區塊又發現, 區塊內有衝突我們的排序原則因此將區塊拆開為與 0 區塊

159 區塊區塊區塊區塊區塊 0 區塊這樣不論是要用 Backward 還是 Forward, 只要挑選的原則是照區塊來挑選, 則能避免剛剛所提出的問題

160 學生需要被啟發學習的動機是需要慢慢蘊釀以及引導的. 看東西的角度是需要一再調整的. 事情的面向是一層一層撥開. 很多事情的答案是經驗的累積. 多元的經驗, 來自失敗, 嘗試, 與跨界的理解! 這些經驗, 來自先人巨量的時間和智慧, 其過程, 應該是故事性的. 其結果, 應該是動人而肅然的. 我認為這些經驗, 必須要有系統的編進各級數學教材, 而且要與時俱進. 0

161 Thank you!!

0 0 = 1 0 = 0 1 = = 1 1 = 0 0 = 1

0 0 = 1 0 = 0 1 = = 1 1 = 0 0 = 1 0 0 = 1 0 = 0 1 = 0 1 1 = 1 1 = 0 0 = 1 : = {0, 1} : 3 (,, ) = + (,, ) = + + (, ) = + (,,, ) = ( + )( + ) + ( + )( + ) + = + = = + + = + = ( + ) + = + ( + ) () = () ( + ) = + + = ( + )( + ) + = = + 0