MyPaper.dvi

Size: px
Start display at page:

Download "MyPaper.dvi"

Transcription

1 國立交通大學 應用數學系 碩士論文 以連通控制集做為無線感測網路虛擬骨幹之研究 Using a Connected Dominating Set as the Virtual Backbone of a Wireless Sensor Network 研究生 : 羅健峰指導教授 : 陳秋媛 中華民國九十九年六月

2 以連通控制集做為無線感測網路虛擬骨幹之研究 Using a Connected Dominating Set as the Virtual Backbone of a Wireless Sensor Network 研究生 : 指導教授 : 羅健峰陳秋媛 Student: Cheng-Feng Lo Advisor: Chiuyuan Chen 國立交通大學 應用數學系 碩士論文 A Thesis Submitted to Department of Applied Mathematics College of Science National Chiao Tung University in Partial Fulfillment of the Requirements for the Degree of Master in Applied Mathematics June 2010 Hsinchu, Taiwan, Republic of China 中華民國九十九年六月

3 以連通控制集做為無線感測網路虛擬骨幹之研究 研究生 : 羅健峰指導老師 : 陳秋媛教授 國立交通大學 應用數學系 中文摘要 在無線感測網路中, 節點以及節點之間的連接關係可以用圖來表示, 如此一來, 此圖的連通控制集就可以對應當成原本的無線感測網路的骨幹, 此一骨幹可用以提升訊息傳遞的效率 因此找出一個給定的圖的最小連通控制集是許多學者們探討的問題, 文獻中已證明了找出一個給定的圖的最小連通控制集是 NP- 難的問題, 於是退而求其次的有近似演算法的提出 在 1999 年,Wu 和 Li 提出了一個近似演算法 ( 為方便, 稱其為 Wu 和 Li 的演算法 ), 在 2006 年,Cokuslu 等人提出了一個近似演算法 ( 為方便, 稱其為 Cokuslu 的演算法 ) Cokuslu 等人的文章中只分析了演算法的效益 訊息複雜度 以及時間複雜度, 並未證明演算法的正確性 在這篇論文中, 我們將證明 Cokuslu 的演算法的正確性, 換句話說, 我們將證明 Cokuslu 的演算法所得的結果是一個連通控制集 此外, 我們還做了 Wu 和 Li 的演算法及 Cokuslu 的演算法的比較 關鍵詞 : 無線感測網路 連通控制集 虛擬骨幹 演算法 i

4 Using a Connected Dominating Set as the Virtual Backbone of a Wireless Sensor Network Student:Cheng-Feng Lo Advisor:Chiuyuan Chen Department of Applied Mathematics National Chiao Tung University Hsinchu, Taiwan Abstract In a wireless sensor network, the relationship between nodes can be modeled by using a graph. Consequently, a connected dominating set of such a graph is usually used to serve as a virtual backbone of the original wireless sensor network. Thus finding a minimum connected dominating set of a graph becomes a problem discussed by many researchers. It has been proven that this problem is NP-hard. Hence many researchers consider finding approximation solutions instead of the optimal solution and many approximation algorithms have been proposed. In particular, in 1991, Wu and Li proposed an approximation algorithm (call it Wu and Li s algorithm for convenience). In 2006, Cokuslu et al. proposed another approximation algorithm (call it Cokuslu s algorithm for convenience), which is an improvement of Wu and Li s algorithm. Notice that Cokuslu et al. only provided the performance, the time complexity, and the message complexity analyses; they did not prove the correctness of their algorithm. In this thesis, we will prove the correctness of Cokuslu s algorithm (i.e., we will prove that Cokuslu s algorithm obtains a connected dominating set. Also, we will give a comparison between Wu and Li s algorithm and Cokuslu s algorithm. Keywords:wireless sensor network, connected domminated set, virtual backbone, algorithm. ii

5 誌謝 在這裡我想感謝一些老師 首先是感謝陳秋媛老師, 感謝一路走來她都耐心的陪著我, 當我犯錯時, 老師都一一指出, 很仔細地告訴我要注意出錯的問題在哪, 有哪些細節要注意 感謝翁志文老師在我修習代數課時給我很多的幫助, 讓我建立正確的觀念 感謝黃大原老師, 在修大原老師的課時, 老師都很親切的回答我所有的問題 然後, 感謝藍國元和邱鈺傑學長, 常常在我出現問題的時候, 給我一些意見讓我在解決問題時參考 最後感謝我的同學, 吳思賢 黃思綸, 不厭煩的花時間陪我在研究室中一起討論我遇到的問題 iii

6 目錄 中文摘要 Abstract 誌謝目錄圖目錄表目錄 i ii iii iv v vi 1 簡介 1 2 相關定義 3 3 前人結果 5 4 Wu 和 Li 的演算法以及 Cokuslu 的演算法 Wu 和 Li 的演算法 Cokuslu 的演算法 證明 Cokuslu 的演算法的正確性 證明 Cokuslu 的演算法之輸出為控制集 證明 Cokuslu 的演算法所輸出的控制集為連通 結語 14 參考文獻 15 附錄 17 iv

7 圖目錄 1 Wu 和 Li 的演算法範例 Cokuslu 的演算法範例 v

8 表目錄 vi

9 1 簡介 無線感測網路是由一堆的感測器組成, 感測器們一起執行特定任務 每個感測器可以獨立工作, 感測器的功能是感測研究者有興趣的事件, 可能是溫度 聲音 溼度等等 由感測器所形成的網路不同於一般的有線網路, 無線感測網路沒有階層, 沒有固定的網路設施, 感測器都執行一樣的功能, 感測器利用無線的傳輸媒介直接互相交換訊息, 但是訊息傳輸距離是有限的, 所以兩個不在彼此傳輸距離內的感測器要傳送訊息時, 必須透過路徑上多個中間感測器轉送 因此, 一個感測器除了扮演終端系統的角色, 同時也要扮演轉送訊息的角色 因為要知道如何轉送訊息, 每個感測器需要儲存一些路由資訊 感測器在收集路由資訊的過程, 廣播 (broadcast) 是最直接且常使用的方式 廣播的目的是讓網路中節點都收到資訊 有一種廣播的方式是 : 感測器收到一個廣播訊息, 感測器檢查是否已經收過, 若是第一次收到的廣播資訊就繼續傳送給所有傳送距離內的感測器, 否則不傳送, 這種方式稱為泛洪式廣播 但是利用廣播傳遞資訊的方式會造成資料重複 頻道使用的競爭 及訊息的碰撞的問題, 這三個問題就是所謂的廣播風暴問題 在無線網路中感測器能源通常是有限的, 廣播也可能造成能源的浪費 因此為了讓訊息的傳送負載在無線感測網路中降低, 降低廣播風暴所帶來的影響, 有人提出了虛擬骨幹的概念, 就是找出一組感測器, 讓資訊轉送的工作交給這些感測器, 並且資訊的傳遞在到達目的地之前, 僅在這些節點中流傳, 而不是讓資料流竄在整個網路, 藉以減輕整個網路的負擔 用來當做虛擬骨幹的感測器必須要滿足幾個條件 : (1) 網路中不屬於骨幹的感測器傳輸半徑內至少要有一個在骨幹內的感測器 ; (2) 在骨幹內, 感測器間的訊息要能夠不靠骨幹外的感測器就能互傳 在無線感測網路中找出虛擬骨幹的問題如果用數學中的圖論來敘述的話, 就是圖論中的連通控制集 (connected dominating set) 的問題, 所以將無線感測網路就對應到一個圖 (graph), 在網路中找虛擬骨幹的問題就等同於在找一個圖中的連通控制集 (connected dominating set) 的問題, 但是這個集合內的點越少越好, 因此要找的是最小連通控制集 (minimum connected dominating set) 因為這個緣故, 在無線網路蓬勃發展的同時, 找出連通控制集的演算法陸續被提出, 同時也研究控制集的變化及限制, 證明關於控制集在某些特定條件下的性質等等 在這篇論文中, 我們將介紹連通控制集的相關研究歷程以及整理相關研究結果 在這些已知的結果之中, 文獻 [12] 所提出的演算法是最有名的, 這是一個分散式演算法 (distributed algorithm), 我們會對這個演算法做較多的說明, 以下並稱其為 Wu 和 Li 的演算法 文獻 [4] 所提出的演算法是改進 Wu 和 Li 的演算法, 以下稱 Cokuslu 的演算法 文獻 [4] 只分析了演算法的效益 訊息複雜度 以及時間複雜度, 並未證明演算法的正確性 本論文的目的在於證明 Cokuslu 的演算法的正確性, 換 1

10 句話說, 我們將證明 Cokuslu 的演算法所得的結果是一個連通控制集 ; 此外, 我們還做了 Wu 和 Li 的演算法及 Cokuslu 的演算法的比較 本論文的章節安排如下 : 在第二小節中, 我們將介紹相關定義 ; 在第三小節中, 我們將介紹前人結果 ; 在第四小節中, 我們將介紹 Wu 和 Li 的演算法及 Cokuslu 的演算法 ; 在第五小節中, 我們將證明 Cokuslu 的演算法的正確性 ; 第六小節為結論 2

11 2 相關定義 以下我們將介紹本論文中所要用到的名詞定義 定義 1. 一個圖 (graph) G 由點集合 (vertex set) V (G) 和邊集合 (edge set) E(G) 組成, 邊集合內的元素稱為邊, 一個邊就是一對點 (u, v), 其中 u 和 v 都屬於 V (G), 簡記作 uv 定義 2. 當 u 跟 v 是圖 G 某個邊上的點時, 則說 u 跟 v 相鄰 (adjacent) 或者 u 跟 v 是鄰居 (neighbor), 以 u v 表示, 反之, 以 u v 表示 u 在 G 中的所有鄰居以 N(u) 表示 ; N[u] = N(u) {u} N(u) 的元素個數稱為 u 的分支度 (degree), 以 degree(u) 表示 定義 3. 若圖 G 中的點 v, 其分支度為一, 則稱此點 v 為葉子 (leaf) 定義 4. 若一個圖 G 的任兩點都相鄰, 則 G 為一個完全圖 (complete graph) 定義 5. H 和 G 為兩個圖 H 滿足 V (H) V (G) 且 E(H) E(G), 則 H 為一個圖 G 的子圖 (subgraph), 以 H G 表示 定義 6. 對於一個圖 G 中的兩點 u 和 v, 一個 u, v-walk 是一個序列 u = v 0, e 1, v 1,...,e k, v k = v, 使得 e i = v i 1 v i, 其中 v i 屬於 V (G),e i 屬於 E(G), 對 1 i k 若一個 u, v-walk 上沒有重複的點, 則稱為 u, v-path, 簡記為 u = v 0, v 1,...,v k = v 若一個 u, v-walk,u = v 0, e 1, v 1,...,e k, v k = v, 所有的點中, 只有 u 和 v 相同, 則稱此 u, v-walk 為一個 cycle 一個 u, v- walk,u, v-path 或一個 cycle 的長度 (length) 是指在序列中邊的個數, 所有 u, v-path 中邊數最少者為 u 到 v 的最短路徑 定義 7. 一個圖 G 中, 所有點 u, v V (G) 都存在一條 u, v-path, G 稱為連通圖 (connected graph), 或說 G 是連通的 (connected); 一個子圖是連通的, 則稱為連通子圖 定義 8. 一個圖 G 是一個樹 (tree) 表示 G 是一個沒有 cycle 的連通圖 定義 9. 考慮一個圖 G 的子圖 T, 若 V (T) = V (G) 且 T 為一個樹, 則稱 T 為 G 的擴張樹 (spanning tree) 定義 10. G 是一個圖, 若 H G 是一個連通子圖, 且沒有任何連通子圖 H G 使得 H H, 則 H 為一個圖 G 的連通元件 (connected component), 特別的是, 一個連通圖只有一個連通元件 3

12 定義 11. 對一個圖 G, 令 e E(G) v V (G) M E(G) S V (G) G M 表示 G 扣掉 M 的子圖, 其中 V (G M) = V (G),E(G M) = E(G) M, 而 G {e} 直接表示成 G e G S 表示 G 扣掉 S 的子圖, 其中 V (G S) = V (G) S, E(G S) = E(G) {(x, y) x 或 y 屬於 S}, 而 G {v} 直接表示成 G v G[S] 稱為 S 的生成子圖, 表示 G S, 其中 S = V (G) S 定義 12. 在一個圖 G 中, 令 S V (G) 若 G[S] 沒有邊, 也就是 E(G[S]) 是空集合, 則稱 S 為 G 中一個獨立集 (independent set) 若 S 為 G 中的一個控制集 (dominating set), 則每一個不屬於 S 的點都有一個鄰居在 S 若 S 為 G 中的一個控制集且 G[S] 連通, 則 S 是 G 的一個連通控制集 (connected dominating set) 4

13 3 前人結果 連通控制集這個名詞是在七零到八零年代時被提出, 在無線感測網路的發展中, 繼續了這部份的研究 不幸的是, 找出一個圖的最小連通控制集已被證明是 NP- 難的問題 [5], 換句話說, 不太可能有在多項式時間內找出最小連通控制集 ; 所以, 目前的研究傾向於找出近似解, 也就是提出一個圖的連通控制集的近似演算法 顧名思義, 近似演算法所找出來的解並不一定是最小的, 只是接近最小的, 所以還必須要考慮近似因子 (approximation ratio) 假設一個圖的點數為 n, 此圖的最小連通控制集的大小是 C, 由近似演算法找出來的連通控制集的大小是 C, 如果有一函數為 ρ(n), 使得 ρ(n) max(c/c, C /C), 則稱 ρ(n) 為近似演算法的近似因子, 也就是近似演算法所找出來的連通控制集的大小 C 保證不會超過 ρ(n)c 這些演算法可以分為兩大類 : 分散式, 集中式 在 1998 年,Guha 等人 [6] 提出了兩個集中式的近似演算法, 都是使用貪婪法則 (greedy strategies) Guha 等人的第一個演算法想法如下 : 一開始圖中的點都是標為白色, 第一步驟先挑白色鄰居最多的點, 然後將這個點標為黑色, 這個點的鄰居全都標為灰色, 接著, 重複的挑選有最多白色鄰居的灰色點, 將這個灰色的點標為黑色, 鄰居標為灰色 ; 或者是挑選有最多白色鄰居的一對點 ( 一個灰點和一個白點 ), 將這兩個點都標為黑色, 鄰居標為灰色 當圖中不再存在有白色的點的時候, 演算法結束 這個演算法的近似因子是 2(1 + H(δ)), 其中 H 表示調和函數,δ 表示所有點的最大分支度 對於無線感測網路來說, 因為感測器的能源有限, 若是網路感測器數量較多的時候, 由一個感測器來做集中式的計算並不實用, 所以就考慮分散式的演算法 在 1999 年,Wu 和 Li[12] 提出了一個僅需要局部相鄰訊息就足夠的分散式演算法, 這個演算法假設每個點都有唯一的識別碼 在整個演算法的執行過程中, 每個節點只需要知道鄰居 ( 所謂的鄰居, 是指在傳輸距離內的節點 ) 的資訊, 只需要和鄰居互傳訊息就夠了 Wu 和 Li 的演算法一開始所有的節點都標示為白色, 然後節點和鄰居互傳彼此的鄰居清單, 每個節點就可以知道鄰居之間的相鄰關係, 當一個節點它有鄰居不相連時, 則此節點標為黑色 當所有節點都執行結束後,Wu 和 Li 證明了所有的黑色節點所形成的集合是一個連通控制集 Wu 和 Li 也觀察出兩個可以讓連通控制集的元素減少的剔除規則, 如下 考慮 Wu 和 Li 的演算法所產生的連通控制集, 一個黑色節點 u 可以從連通控制集中剔除, 只要 u 有一個擁有較大識別碼的鄰居 v 使得 N[u] N[v], 或者是 u 有兩個擁有較大識別碼的鄰居 v 和 w, 使得 N(u) N(v) N(w) Wu 和 Li 針對模擬結果表示, 在沒有使用剔除規則時, 結果相當的不好, 使用了剔除規則後, 大幅改善了結果, 不過 Wu 和 Li 在文章中並沒有分析其演算法的近似因子 Guha 等人的第二個演算法用了兩個階段, 在 2004 年,Ruan 等人 [9] 就根據這一點做改進, 提出了一個使用一個階段的集中式演算法, 同樣是使用貪婪法則 演算法會將節點標為黑色, 灰色或白色 5

14 其中一種, 最後黑色點所形成的集合就是連通控制集 Ruan 等人定義幾個函數, 根據函數值來做為如何選擇節點加入連通控制集 ( 標為黑色 ) 的準則 考慮一個圖 G,C V (G), 令 p(c) 為 G[C] 中由黑色節點所形成的連通元件 (connected components) 個數 ; 令 D(C) = {uv E(G) u C 或 v C}; q(c) 表示一個圖 G G 的連通元件的個數, 其中 V (G ) = V (G), E(G ) = D(C); f(c) = p(c) + q(c) Ruan 等人的演算法如下 : 一開始所有的點都是白色, 由黑色點所形成的集合 C 為空集合, 接著反覆的挑點, 挑加入 C 後能夠讓 f 減少最多的點, 將挑出來的點標為黑色, 鄰居標為灰色, 當沒有點可以讓 f 減少的時候演算法結束 Ruan 等人證明由演算法標為黑色的點所形成之集合為連通控制集, 及演算法的近似因子為 (2 + ln δ) 在有些無線感測網路上, 感測節點的傳輸距離都相同, 所以就可以考慮比較特殊的圖, 單位圓盤圖 (unit disk graph) 單位圓盤圖的相鄰關係是根據點在歐氏平面上的距離來定義, 考慮圖中兩點, 若在歐氏平面上的距離不超過一個單位長度, 則此兩點有邊相連 於是就有了在單位圓盤圖上找最小連通控制集的研究, 而且單位圓盤圖有一個特性 [8]: 每一個點最多只有五個彼此不相連的鄰居 不過, 即使是單位圓盤圖, 找最小連通控制集的問題被證明仍然是 NP- 難的問題 [1] Guha 等人和 Ruan 等人的演算法都是集中式且都是針對一般圖, 演算法的近似因子較高 2004 年,Alzoubi 等人 [10] 指出 Wu 的錯誤, 分析了 Wu 的演算法, 提出了一個針對單位圓盤圖的分散式近似演算法, 以及找出獨立集和最小連通控制集的大小關係 : 任意一個單位圓盤圖 G 中, 令 opt 為最小連通控制集的個數, 則對所有的獨立集 S, S 4opt [10] 的演算法要利用演算法的輸入, 圖 G, 的擴張樹 T, 所以先找出一個點來當 T 的根, 利用 T 替每個節點標上顏色,Alzoubi 等人證明所有被標上黑色的點會是一個獨立集 S, 滿足以下特性 : (A1) S 加入任何點 v, v V (G) S 都不是獨立集 ; (A2) 若 S = S 1 S 2 and S 1 S 2 =, 則存在 u S 1, v S 2 使得 u 到 v 在 G 中的最短路徑長度為 2 再根據這個特性, 產生另一個擴張樹 T, 而 T 所有不是葉子的點就會是一個連通控制集 最後,Alzoubi 等人證明了演算法的近似因子為常數 : 年 Cheng 等人 [3] 針對單位圓盤圖, 提出一個可以得出任意近似因子的多項式演算法的策略 一個多項式演算法的策略可以給定一個圖和指定的值,ǫ, 產生一個近似因子為 (1 + ǫ) 的近似演算法 若要得到較小的近似因子, 這個演算法將會執行較多的時間 2005 年,Yingshu 等人 [7] 針對單位圓盤圖提出了一個近似演算法 這個演算法會將圖中的點標為黑色, 灰色, 或藍色其中一種顏色, 另外還要考慮藍 - 黑元件, 藍 - 黑元件就是由黑點和藍點所形成的子圖的連通元件, 但是不考慮藍點間的相鄰關係 演算法的想法如下 : 令 G 為輸入的圖, 利用 Alzoubi 6

15 等人 [10] 的演算法先找出一個滿足條件 A1 和 A2 的獨立集 S, 將所有在 S 內的點標為黑色, 所有 G S 的點標為灰色, 反覆的挑出連接最多不同藍 - 黑元件內黑點的灰點標為藍色, 因為 [8], 一個灰點最多只有五個黑色鄰居, 所以從連接在不同藍 - 黑元件的五個黑點開始找, 直到沒有灰點連接至少兩個不同藍 - 黑元件內的黑點時結束 Yingshu 等人證明所有藍色和黑色的點就是一個連通控制集, 演算法的近似因子是 ln 5 在 2006 年 Cokuslu 等人 [4] 提出了一個改進 Wu 和 Li 的分散式演算法, 但是在文章中並未證明演算法所找出來的集合是一個連通控制集, 以下證明其結果是正確的 7

16 4 Wu 和 Li 的演算法以及 Cokuslu 的演算法 這兩個演算法都分兩個階段 這兩個演算法都假設網路對應的圖 G 是連通圖, 但不是完全圖, G 中每一個點 v 都有一個唯一的識別碼, 記成 id(v); 每一個點都知道自己的鄰居成員, 可以分享彼此的鄰居成員資訊, 也就是可以知道每個鄰居的鄰居成員 4.1 Wu 和 Li 的演算法 現在介紹由 Wu 和 Li 在 1999 年所提出的演算法 [12] 目標是要找任一給定圖 G 的連通控制集, 演算法會為節點標上一種顏色, 黑色或白色, 最後所有黑色的點所成的集合就會是連通控制集 這個演算法的基本想法就是將所有 可能需要的點 都挑出來 也就是說, 若圖 G 中一個點 u 有兩個鄰居不相連, 則 u 就是 可能需要的點, 因為只要 u 有鄰居 v,w 不相連,v,w 就可能需要透過 u 來傳遞訊息 但是將所有 可能需要的點 都挑出來, 有些會是多餘的, 多餘的點就必須要透過一些規則剔除 以下是 Wu 和 Li 的演算法的敘述 在演算法第一階段的開始, 每個節點都是標為白色, 然後檢查有沒有不相連的鄰居, 若是有, 則節點標為黑色 第二階段的目的是在不破壞連通的性質下, 減少第一階段選出來的黑色節點 Wu 和 Li 證明經過演算法第一階段, 所有黑色的節點所形成的集合就是連通控制集 第二階段的剔除規則就是, 若一個黑點 v 滿足以下兩個條件之一, 則 v 改標為白色 : 1. v 存在一個標為黑色的鄰居 u, 使得 id(v) < id(u) 且 N[v] N[u]; 2. v 存在兩個標為黑色的鄰居 u 和 w, 使得 id(v) = min{id(v), id(u), id(w)} 且 N(v) N(u) N(w) 以圖 1 為例子, 圖 1 (a) 中黑色節點是根據 Wu 和 Li 的演算法第一階段的規則挑出來 可能需要的點, 圖 1 (b) 是根據第二階段的剔除規則, 減去不必要的點之後的情形 4.2 Cokuslu 的演算法 現在介紹由 Cokuslu 等人所提出的演算法 [4] 這個演算法是以 Wu 和 Li 的演算法為基礎, 一樣是以顏色來區分節點, 但是比 Wu 和 Li 的演算法多使用了一種顏色 : 灰色 Cokuslu 等人觀察到在 Wu 和 Li 的演算法中, 一定是標為白色的點有 : 樹葉節點以及所有鄰居都兩兩相連的點 ; 此外,Cokuslu 等人也觀察到樹葉節點的鄰居一定是標為黑色, 因為樹葉節點沒有辦法不透過這個唯 8

17 v 7 v 1 v 7 v 1 v 3 v 3 v 6 v 0 v 4 v 6 v 0 v 4 v 5 v 5 v 2 v 2 (a) (b) 圖 1.Wu 和 Li 的演算法範例 (a) 第一階段執行後,(b) 第二階段執行後 一的鄰居和其他節點傳遞訊息 上述節點只要一決定顏色, 就不需要再改變顏色了 除了樹葉節點 樹葉節點的鄰居 所有鄰居都兩兩相連的節點, 其他節點有可能在 Wu 和 Li 的演算法第二階段中改變顏色 Cokuslu 等人利用這個性質, 設計出和 Wu 和 Li 的演算法一樣是兩個階段的演算法 Cokuslu 的演算法第一階段先找出所有在 Wu 和 Li 的演算法第一階段決定後就不會變更顏色的節點, 這些不會變更顏色的節點會被標為黑色或白色, 其餘則會被標為灰色 在第二階段,Cokuslu 等人想出了四個判斷條件, 灰色節點根據這四個判斷條件來決定最終顏色是黑色或白色 這四個判斷條件使用了分支度的資訊, 灰色節點決定改標為黑色或白色的時候, 除了 id 識別碼以外還以分支度大的節點優先考慮 下面是 Cokuslu 等人的演算法的敘述 一開始, 每一個點都沒有標上顏色 在第一階段, 每個點 v 會先收集所有鄰居的資訊, 等到收集完後就根據兩個條件來決定自己的顏色 : 1. 如果 v 存在鄰居 u, 且 u 為葉子, 則 v 標為黑色 ; 2. 如果 v 的鄰居皆彼此相鄰, 或者 v 為葉子, 則 v 標為白色 若 v 不滿足第一階段的兩個條件, 則 v 標為灰色 只有標上灰色的點才會再依據第二階段的條件改變顏色, 否則不再改變顏色 ; 灰色的點將會被改標為黑色或白色 在第二階段中, 每一個灰色的點 v 會收集所有鄰居的顏色資訊, 收集完後就根據四個條件來決定最終的顏色 : 1. v 存在一個標為黑色的鄰居 u, 使得 N[v] N[u]; 2. v 存在兩個標為黑色的鄰居 u 和 w, 使得 N(v) N(u) N(w); 9

18 3. v 存在一個標為灰色的鄰居 u, 使得 N[v] N[u] 且 degree(v) < degree(u), 或者是 degree(v) = degree(u) 但 id(v) < id(u); 4. v 存在兩個鄰居 u 和 w, 顏色標為黑色或灰色, 使得 N(v) N(u) N(w) 且 degree(v) < min{ degree(u), degree(w) }, 或者是 degree(v) = min{ degree(u), degree(w) } 但 id(v) < min{ id(u), id(w) } 只要 v 滿足其中一個條件, 則 v 標為白色, 否則 v 就標為黑色 以圖 2 為例子, 圖 2 (a) 中白色節點是根據 Cokuslu 的演算法第一階段的規則挑出來不會再變更顏色的節點, 這個圖沒有樹葉節點, 所以沒有任何的點在第一階段被標為黑色, 灰色節點 ( 在圖中用斜線表示 ) 則是要再依據第二階段的四個判斷條件決定最終顏色 圖 2 (b) 是根據第二階段的四個判斷條件, 將所有灰色節點改標為黑色或白色 v 0, v 6 在這個例子中並不滿足第二階段中所有的判斷條件, 所以被標為黑色 v 1, v 3, v 5, v 7 都至少滿足第二階段四個判斷條件之一, 所以標為白色 v 7 v 1 v 7 v 1 v 3 v 3 v 6 v 0 v 4 v 6 v 0 v 4 v 5 v 5 v 2 v 2 (a) (b) 圖 2.Cokuslu 的演算法範例 (a) 第一階段執行後,(b) 第二階段執行後 10

19 5 證明 Cokuslu 的演算法的正確性 根據 Cokuslu 的演算法假設, 輸入的圖 G 是一個連通圖, 但不是完全圖 Cokuslu 的演算法執行完後,G 中的每一點只有可能標為黑色和白色兩色的其中一色 令 D 為所有標為黑色的點所成之集合 以下證明分兩個部分, 先證明 Cokuslu 的演算法之輸出, 即 D, 在 G 中具有控制集的性質, 再證明這個 D 在 G 中的生成圖 G[D] 是連通的 5.1 證明 Cokuslu 的演算法之輸出為控制集 定理 1. D 是一個控制集 証明. 欲證 D 是控制集, 相當於要證 : 演算法結束後 G 中任一點的顏色是被標為黑色, 或者有一個鄰居是被標為黑色 由於 Cokuslu 的演算法執行完後,G 中的每一點只有可能標為黑色或白色, 因此, 證明以下敘述 (*) 成立就足夠了 (*) G 中標為白色的點有一個鄰居是黑色 ; 令 v 是 G 中任意一個標為白色的點 v 被標為白色的只有兩可能 : 根據第一階段的條件 或根據第二階段的條件 以下證明 : 不論是根據第一階段或第二階段的條件,v 都有一個鄰居是黑色 Case 1: 假設 v 是根據第一階段的條件被標為白色 此時還有兩種可能 : v 是葉子 或者 v 的鄰居彼此互相直接連接 Case 1-a: 假設 v 是葉子 此時,v 只有一個鄰居 ( 設為 x ), 因為圖 G 不是完全圖, 所以 x 不是葉子 ; 根據 Cokuslu 的演算法,x 會標為黑色 ; 所以 (*) 成立 Case 1-b: 假設 v 的鄰居彼此互相直接連接 此時, 因為圖 G 是連通圖但不是完全圖, 所以 v 至少有一個鄰居其 degree 比 v 大, 令 u 為這樣的鄰居中 degree 最大且 id 最大者 因為 degree(u) > degree(v), u 不會是葉子,u 的鄰居也沒有彼此互相直接相連 ; 所以根據演算法, u 在第一階段不會被標為白色,u 在第一階段只會是被標為黑色或灰色 若 u 在第一階段被標為黑色, 則 (*) 成立 若 u 在第一階段被標為灰色, 表示 u 是在第二階段決定顏色白或黑 如果 u 在第二階段被標為黑色的話, 則 v 有一個黑色鄰居,(*) 成立 若 u 是在第二階段被標為白色, 則 u 滿足第二階段的四個條件之一 11

20 如果 u 在第二階段被標為白色是因為條件 1 或條件 2, 而不論條件 1 或條件 2 都表示 u 有一個黑色鄰居, 因為 N(v) N(u), 所以這個黑色鄰居也同時是 v 的鄰居, 也就是 v 有一個黑色鄰居,(*) 成立 考慮第二階段中的條件 3 和條件 4 如果 u 滿足這兩個條件, 表示 u 存在一個鄰居 x, 使得 x 也是 v 的鄰居且 x 的分支度大於 u 的分支度, 或者是 x 的分支度等於 u 的分支度但 x 的 id 大於 u 的 id 但是 v 是 u 的鄰居中分支度最大且 id 最大者, 所以不存在這種鄰居, 也就是 u 不會滿足第二階段的條件 3 或條件 4 Case 2: 現在假設 v 是根據第二階段的條件被標為白色 考慮 v 在第二階段被標為白色的情況, 亦即 v 滿足第二階段的四個條件之一 若 v 在第二階段被標為白色是因為條件 1 或條件 2, 表示 v 有一個黑色鄰居 若 v 在第二階段被標為白色是因為條件 3 或條件 4, 則觀察其中分支度最大且 id 最大的鄰居, 稱 w 由條件 3 或條件 4 都可推知 degree(v) < degree(w), 或者是 degree(v) = degree(w) 但 id(v) < id(w) 因此, 如同說明 v 在第一階段的情況中的鄰居 u, w 也不會在第一階段中被標為白色, 只會在第一階段中決定為黑色或灰色 或在第二階段中決定為黑色或白色 w 也不滿足第二階段中的條件 3 和條件 4 w 不論在哪一個階段被標為黑色, 都表示了 (*) 成立, 所以只剩下要考慮 w 在第二階段中決定為白色的情況, 但這個情形也跟討論 v 在第一階段的的鄰居 u 一樣,w 只有可能滿足第二階段的條件 1 或條件 2, 但這些條件都代表 (*) 成立 引理 2. [11] 如果 G 為一個圖,u,v V (G), 則每一個 u, v-walk 中包含一個 u, v-path 5.2 證明 Cokuslu 的演算法所輸出的控制集為連通 定理 3. G[D] 是連通的 証明. 將所有在第一階段標為黑色或灰色的點所形成的集合稱為 C, 因為 D 是 C 扣掉所有在第二階段改標為白色的灰色點, 所以要證明 G[D] 為連通, 只要證明下面兩點就足夠 : (1) G[C] 會是連通的 (2) 令 S 為 G 中由標為黑色和標為灰色的點所形成的集合,G[S] 為連通 若 v 為 G[S] 中一個滿足第二階段其中一個條件的點, 且讓 v 滿足第二階段的條件的點也屬於 S, 則 G[S] v 仍然為連通 要證明 (1) 就是要證明任取 G[C] 中沒有邊相連的兩點都存在至少一條路徑在 G[C] 12

21 令 v, u 為 G[C] 中沒有邊相連的兩點 因為 G 是連通,G 中存在一條 v, u-path, 令 P = (v = v 0, v 1,, v k = u), 為 G 中 v 到 u 最短路徑的其中一條 因為 v, u 沒有邊相連, 所以 k > 1 任取 P 上一點 v i,k > i 1 v i 1 和 v i+1 沒有邊相連, 否則就和 P 是最短路徑矛盾, 所以 v i 有不相連的鄰居 根據第一階段的條件, 在 G 中, 有鄰居不相連的節點就只可能標為黑色或灰色, 因此 v i 在第一階段只會標為黑色或灰色, 所以 v i 屬於 G[C] 因為 v i 是 P 上任意不等於 v, u 的點, 所以 P 是由標為黑色或灰色的點所形成, 也就是 P 屬於 G[C] 因為 v, u 為 G[C] 中任意沒有邊相連的兩點, 所以 G[C] 是連通 要證明 (2), 只要證明 G[S] 中任意兩點 x 和 y, 如果 x, y 在 G[S] 有路徑經過 v, 則 x, y 在 G[S] 也會有路徑不經過 v 即可 以下假設 P = (x = v 0, v 1,, v i = v,, v k, v k+1 = y) 為 G[S] 中一條 x 到 y 經過 v 的路徑 (2-a): 若 v 滿足第一個或第三個條件, 則 G[S] 中存在點 u, 使得 N[v] N[u], 因此可知 v i 1 和 v i+1 是 u 的鄰居 考慮 u 的可能 u 可能在 P 上, 也可能不在 P 上 如果 u 在 P 上, 則 u = v m, m i 如果 m < i, 則 (x = v 0, v 1,, v m, v i+1,, v k, v k+1 = y) 為 G[S] 中一條 x 到 y 的路徑 ; 如果 m > i, 則 (x = v 0, v 1,, v m, v i 1, v m,, v k, v k+1 = y) 為 G[S] 中一條 x 到 y 的路徑 如果 u 不在 P 上, 則 (x = v 0, v 1,, v i 1, u, v i+1,, v k, v k+1 = y) 為 G[S] 中一條 x 到 y 的路徑 以上情況表示 x, y 在 G[S] 有路徑不經過 v (2-b): 若 v 滿足條件 2 或條件 4, 則 G[S] 中存在點 u w N(v), 使得 N(v) N(u) N(w), 因此 P 中 v i 1, v i+1 是 u 或 w 的鄰居, 不失一般性, 可以假設 v i 1 是 u 的鄰居 若 v i+1 也是 u 的鄰居, 則 (x = v 0, v 1,, v i 1, u, v i+1,, v k, v k+1 = y) 是一個 x, y-walk, 根據引理 2, 存在一條 x 到 y 的路徑 ; 若 v i+1 是 w 的鄰居, 則 (x = v 0, v 1,, v i 1, u, w, v i+1,, v k, v k+1 = y) 是一個 x, y-walk, 根據引理 2, 存在一條 x 到 y 的路徑 因此不論 v 是滿足第二階段的哪一個條件,x, y 在 G[S] 都有路徑不經過 v 所以 G[D] 為連通 13

22 6 結語 在 1999 年,Wu 和 Li 提出了一個近似演算法, 在 2006 年,Cokuslu 等人改進了 Wu 和 Li 的演算法而提出了一個近似演算法 由於 Cokuslu 等人的文章中只分析了演算法的效益 訊息複雜度 以及時間複雜度, 並未證明演算法的正確性, 在這篇論文中, 我們證明了 Cokuslu 的演算法的正確性 為了知道 Cokuslu 的演算法到底比 Wu 和 Li 的演算法好多少, 我們還實際跑程式做兩者的比較 在模擬的結果內,N 代表點數,trans. range 代表傳輸半徑, W-Algo 代表 Wu 和 Li 的演算法產生的點數,C-Algo 代表 Cokuslu 的演算法產生的點數, difference 表示 C-Algo 減 W-Algo 以下是模擬的方式 在一個 m 2 的範圍中, 我們利用隨機的方式產生點的座標, 再根據給定的 trans. range 來決定圖中點的相鄰關係, 每造一個圖, 就對這個圖執行兩個演算法 在附錄中我們列出了執行的結果, 大多數的情形下,C-Algo 優於 W-Algo, 出乎意料的是 C-Algo 可能比 W-Algo 來的差, 當 N=140,trans. range=450 時, 以及 N=200,trans. range=600 時, 都有這樣的情形 14

23 參考文獻 [1] Brent N. Clark, Charles J. Colbourn, David S. Johnson, Unit Disk Graphs, Discrete Mathematics, vol. 86, 1990, pp [2] Xiuzhen Cheng, Ding-Zhu Du, Virtual Backbone-based Routing in Ad Hoc Wireless Networks, Technical report, Department of Computer Science and Engineering, University of Minnesota, [3] Xiuzhen Cheng, Xiao Huang, Deying Li, Weili Wu, Ding-Zhu Du, A Polynomial Time Approximation Scheme for the Minimum Connected Dominating Set in Ad Hoc Wireless Networks, Networks, vol. 42, 2003, pp [4] Deniz Cokuslu, Kayhan Erciyes, Orhan Dagdeviren A Dominating Set Based Clustering Algorithm for Mobile Ad Hoc Networks, in in Proc. ICCS 2006, LNCS 3991, 2006, pp [5] Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, [6] S. Guha, S. Khuller, Approximation Algorithms for Connected Dominating Sets, Algorithmica, vol. 20, 1998, pp [7] Yingshu Li, My T. Thai, Feng Wang, Chih-Wei Yi, Peng-Jun Wan, Ding-Zhu Du, On Greedy Construction of Connected Dominating Sets in Wireless Networks, Wireless Communications and Mobile Computing, vol. 5, 2005, pp [8] Madhav V. Marathe, Heinz Breu, Harry B, Hunt III, S. S. Ravi, Daniel J. Rosenkrantz, Simple Heuristics for Unit Disk Graphs, Networks, vol. 25, 1995, pp [9] Lu Ruan, Hongwei Du, Xiaohua Jia, Weili Wu, Yingshu Li, Ker-I Ko, A Greedy Approximation for Minimum Connected Dominating Sets, Theoretical Computer Science, vol. 329, 2004, pp

24 [10] Peng-Jun Wan, Khaled M. Alzoubi, Ophir Frieder, Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks, Mobile Networks and Applications, vol 9, 2004, pp [11] Douglas B. West, Introduction to Graph Theory 2E, Prentice Hall, [12] Jie Wu and Hailan Li, On Calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks, Proceedings of the 3rd International Workshop On Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 7 14, Seattle, USA, August

25 附錄 N trans. range W-Algo C-Algo difference 表 1. N trans. range W-Algo C-Algo difference 表 2. 17

26 N trans. range W-Algo C-Algo difference 表 3. N trans. range W-Algo C-Algo difference 表 4. N trans. range W-Algo C-Algo difference 表 5. 18

27 N trans. range W-Algo C-Algo difference 表 6. N trans. range W-Algo C-Algo difference 表 7. N trans. range W-Algo C-Algo difference 表 8. 19

28 N trans. range W-Algo C-Algo difference 表 9. N trans. range W-Algo C-Algo difference 表 10. N trans. range W-Algo C-Algo difference 表

29 N trans. range W-Algo C-Algo difference 表 12. N trans. range W-Algo C-Algo difference 表 13. N trans. range W-Algo C-Algo difference 表

30 N trans. range W-Algo C-Algo difference 表 15. N trans. range W-Algo C-Algo difference 表 16. N trans. range W-Algo C-Algo difference 表

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

More information

(Microsoft Word - \261M\256\327\272\353\302\262\263\370\247iEnd.doc)

(Microsoft Word - \261M\256\327\272\353\302\262\263\370\247iEnd.doc) 摘 要 長 榮 大 學 資 訊 管 理 學 系 畢 業 專 案 實 作 專 案 編 號 : 旅 遊 行 程 規 劃 - 以 台 南 市 為 例 Tour Scheduling for Tainan City CJU-IM- PRJ-096-029 執 行 期 間 : 95 年 2 月 13 日 至 96 年 1 月 20 日 陳 貽 隆 陳 繼 列 張 順 憶 練 哲 瑋 專 案 參 與 人 員 :

More information

苗 栗 三 山 國 王 信 仰 及 其 地 方 社 會 意 涵 The Influences and Implications of Local Societies to Three Mountain Kings Belief, in Taiwan Miaoli 研 究 生 : 林 永 恩 指 導

苗 栗 三 山 國 王 信 仰 及 其 地 方 社 會 意 涵 The Influences and Implications of Local Societies to Three Mountain Kings Belief, in Taiwan Miaoli 研 究 生 : 林 永 恩 指 導 國 立 交 通 大 學 客 家 文 化 學 院 客 家 社 會 與 文 化 學 程 碩 士 論 文 苗 栗 三 山 國 王 信 仰 及 其 地 方 社 會 意 涵 The Influences and Implications of Local Societies to Three Mountain Kings Belief, in Taiwan Miaoli 研 究 生 : 林 永 恩 指 導 教

More information

畢業專題結案報告書格式

畢業專題結案報告書格式 元 培 科 技 大 學 資 訊 工 程 系 專 題 期 末 報 告 使 用 Game maker 製 作 多 人 連 線 遊 戲 Making multiplayer games using game maker 姓 名 : 0981412016 周 宣 佑 0981412003 蔡 程 翔 0981412005 韋 梓 健 0981412015 沈 永 崑 0981412051 洪 仕 軒 指 導

More information

Microsoft Word - 期末結案報告20130104

Microsoft Word - 期末結案報告20130104 元 培 科 技 大 學 資 訊 工 程 系 101 學 年 度 專 題 結 案 報 告 守 塔 遊 戲 設 計 姓 名 : 李 宏 志 陳 文 鴻 何 侑 諺 張 承 恩 指 導 老 師 : 鄭 瑞 恒 教 授 中 華 民 國 101 年 12 月 守 塔 遊 戲 設 計 Tower Defense Game Design 學 生 : 李 宏 志 Student:Hong-Zhi Li 學 生 :

More information

A Study on Innovative Value Adding Model of New Building The Case Study of The Crystal House in Taichung StudentChen-Tair HUANG AdvisorDr.Chyan YANG A

A Study on Innovative Value Adding Model of New Building The Case Study of The Crystal House in Taichung StudentChen-Tair HUANG AdvisorDr.Chyan YANG A A Study on Innovative Value Adding Model of New Building The Case Study of The Crystal House in Taichung StudentChen-Tair HUANG AdvisorDr.Chyan YANG A Thesis Submitted to Master Program of Management for

More information

Public Projects A Thesis Submitted to Department of Construction Engineering National Kaohsiung First University of Science and Technology In Partial

Public Projects A Thesis Submitted to Department of Construction Engineering National Kaohsiung First University of Science and Technology In Partial Public Projects A Thesis Submitted to Department of Construction Engineering National Kaohsiung First University of Science and Technology In Partial Fulfillment of the Requirements For the Degree of Master

More information

國立交通大學客家文化學院

國立交通大學客家文化學院 國 立 交 通 大 學 客 家 文 化 學 院 客 家 社 會 與 文 化 學 程 碩 士 論 文 傳 統 民 俗 文 化 到 當 代 客 庄 節 慶 : 以 東 勢 新 丁 粄 節 為 例 From Traditional Folklore to Contemporary Hakka Festivals a Case Study of Dongshih Sih Ding Ban Festival

More information

山东省招生委员会

山东省招生委员会 附 件 2: 2012 年 度 山 东 大 学 精 品 课 程 申 报 表 课 程 名 称 课 程 负 责 人 所 属 院 系 网 站 建 设 与 设 计 连 莉 副 教 授 计 算 机 学 院 课 程 类 型 理 论 课 ( 不 含 实 践 ) 理 论 课 ( 含 实 践 ) 实 践 ( 验 ) 课 所 属 专 业 大 类 所 属 专 业 类 理 工 电 子 信 息 科 学 类 联 系 电 话 13256167020

More information

Vol. 22 No. 4 JOURNAL OF HARBIN UNIVERSITY OF SCIENCE AND TECHNOLOGY Aug GPS,,, : km, 2. 51, , ; ; ; ; DOI: 10.

Vol. 22 No. 4 JOURNAL OF HARBIN UNIVERSITY OF SCIENCE AND TECHNOLOGY Aug GPS,,, : km, 2. 51, , ; ; ; ; DOI: 10. 22 4 2017 8 Vol. 22 No. 4 JOURNAL OF HARBIN UNIVERSITY OF SCIENCE AND TECHNOLOGY Aug. 2017 150080 GPS,,, : 27. 36 km, 2. 51, 110. 43, ; ; ; ; DOI: 10. 15938 /j. jhust. 2017. 04. 015 U469. 13 A 1007-2683

More information

(Microsoft Word - 0620r\275\327\244\345.doc)

(Microsoft Word - 0620r\275\327\244\345.doc) 國 立 交 通 大 學 管 理 學 院 碩 士 在 職 專 班 經 營 管 理 組 碩 士 論 文 人 民 幣 匯 率 調 整 決 策 模 式 之 研 析 The Analysis of Decision-Making Adjustment Model for Renminbi (RMB) Exchange Rate 指 導 老 師 : 胡 均 立 教 授 學 生 : 陳 立 心 學 號 : 9674509

More information

834 Vol G = (V, E), u V = V (G), N(u) = {x x V (G), x u } N (u) = {u} N(u) u. 2.2 F, u V (G), G u N (u) F [10 11], G F -., G m F -, u V (G), G

834 Vol G = (V, E), u V = V (G), N(u) = {x x V (G), x u } N (u) = {u} N(u) u. 2.2 F, u V (G), G u N (u) F [10 11], G F -., G m F -, u V (G), G Vol. 37 ( 2017 ) No. 4 J. of Math. (PRC) 1, 1, 1, 2 (1., 400065) (2., 400067) :, Erdös Harary Klawe s.,,,. : ; ; ; MR(2010) : 05C35; 05C60; 05C75 : O157.5 : A : 0255-7797(2017)04-0833-12 1 1980, Erdös,

More information

Vol. 15 No. 1 JOURNAL OF HARBIN UNIVERSITY OF SCIENCE AND TECHNOLOGY Feb O21 A

Vol. 15 No. 1 JOURNAL OF HARBIN UNIVERSITY OF SCIENCE AND TECHNOLOGY Feb O21 A 5 200 2 Vol 5 No JOURNAL OF HARBIN UNIVERSITY OF SCIENCE AND TECHNOLOGY Feb 200 2 2 50080 2 30024 O2 A 007-2683 200 0-0087- 05 A Goodness-of-fit Test Based on Empirical Likelihood and Application ZHOU

More information

小儿疾病防治(四).doc

小儿疾病防治(四).doc ...1...3...6...10...12...13...14...15...17...20...21...22...23...23...24...25 B...28...31...32 I ...33...35...37...40...41...43 X...44...45...47...49...50...52...52...54...56...57...59...61...62...62...63...66

More information

46 2011 11 467 數位遊戲式學習系統 7 2011 11 467 47 3 DBGameSys 48 2011 11 467 正規化資料模組 如何配置並儲存電子化資料 以 便減少資料被重覆儲存的程序 DBGameSys的主要功能模組包 學習者 審核評分模組 含 正規化資料模組 審核評分 模組 高分列表模組3大區塊 系統資料庫 在正規化資料模組的執行 高分列表模組 過程中 先要求學習者瀏覽遊戲

More information

张建城毕业论文.doc

张建城毕业论文.doc Nanjing University of Aeronautics and Astronautics The Graduate School College of Civil Aviation Research and Development on Revenue Management Forecasting System A Thesis in Transportation Engineering

More information

(Microsoft Word - 1012-2\256\325\260\310\267|\304\263\254\366\277\375.doc)

(Microsoft Word - 1012-2\256\325\260\310\267|\304\263\254\366\277\375.doc) 國 立 屏 北 高 級 中 學 101 學 年 度 第 2 學 期 第 2 次 校 務 會 議 紀 錄 壹 會 議 名 稱 :101 學 年 度 第 2 學 期 第 2 次 校 務 會 議 貳 時 間 :102 年 6 月 28 日 ( 星 期 五 ) 下 午 13 時 10 分 參 地 點 : 本 校 圖 書 館 四 樓 視 聽 會 議 室 肆 出 列 席 人 員 : 詳 如 簽 到 簿 伍 主

More information

Time Estimation of Occurrence of Diabetes-Related Cardiovascular Complications by Ching-Yuan Hu A thesis submitted in partial fulfillment of the requi

Time Estimation of Occurrence of Diabetes-Related Cardiovascular Complications by Ching-Yuan Hu A thesis submitted in partial fulfillment of the requi Time Estimation of Occurrence of Diabetes-Related Cardiovascular Complications by Ching-Yuan Hu Master of Science 2011 Institute of Chinese Medical Sciences University of Macau Time Estimation of Occurrence

More information

不 同 合 作 學 習 法 在 除 法 學 習 成 效 之 提 升 - 以 國 中 七 年 級 為 例 The Learning Achievement of Different Cooperative Learning into Enhancement of Seventh Graders' Di

不 同 合 作 學 習 法 在 除 法 學 習 成 效 之 提 升 - 以 國 中 七 年 級 為 例 The Learning Achievement of Different Cooperative Learning into Enhancement of Seventh Graders' Di 國 立 交 通 大 學 理 學 院 科 技 與 數 位 學 習 學 程 碩 士 論 文 不 同 合 作 學 習 法 在 小 數 除 法 學 習 成 效 之 提 升 - 以 國 中 七 年 級 為 例 The Learning Achievement of Different Cooperative Learning into Enhancement of Seventh Graders' Decimal

More information

厨房小知识(四)

厨房小知识(四) I...1...2...3...4...4...5...6...6...7...9...10... 11...12...12...13...14...15...16...17...18...18...19...22...22 II...23...24...25...26...27...27...28...29...29...30...31...31?...32...32...33?...33...34...34...35...36...36...37...37...38...38...40

More information

妇女更年期保健.doc

妇女更年期保健.doc ...1...2...3...5...6...7 40...8... 11...13...14...16...17...19...20...21...26...29...30...32 I ...34...35...37...41...46...50...51...52...53...54...55...58...64...65 X...67...68...70...70...74...76...78...79

More information

小儿传染病防治(上)

小儿传染病防治(上) ...1...2...3...5...7...7...9... 11...13...14...15...16...32...34...34...36...37...39 I ...39...40...41...42...43...48...50...54...56...57...59...59...60...61...63...65...66...66...68...68...70...70 II

More information

<4D6963726F736F667420576F7264202D2031303430333234B875B9B5A448ADFBBADEB27AA740B77EA4E2A5555FA95EAED6A641ADD75F2E646F63>

<4D6963726F736F667420576F7264202D2031303430333234B875B9B5A448ADFBBADEB27AA740B77EA4E2A5555FA95EAED6A641ADD75F2E646F63> 聘 僱 人 員 管 理 作 業 參 考 手 冊 行 政 院 人 事 行 政 總 處 編 印 中 華 民 國 104 年 3 月 序 人 事 是 政 通 人 和 的 關 鍵 是 百 事 俱 興 的 基 礎, 也 是 追 求 卓 越 的 張 本 唯 有 人 事 健 全, 業 務 才 能 順 利 推 動, 政 府 施 政 自 然 績 效 斐 然 本 總 處 做 為 行 政 院 人 事 政 策 幕 僚 機

More information

女性青春期保健(下).doc

女性青春期保健(下).doc ...1...4...10... 11...13...14...15...17...18...19...20...21...22...23...24...26...27...30...31 I ...32...33...36...37...38...40...41...43...44...45...46...47...50...51...51...53...54...55...56...58...59

More information

避孕知识(下).doc

避孕知识(下).doc ...1...3...6...13...13...14...15...16...17...17...18...19...19...20...20...23...24...24...25 I ...25...26...26...27...28...28...29...30...30...31...32...34...35 11...36...37...38...40...42...43...44...44...46

More information

孕妇饮食调养(下).doc

孕妇饮食调养(下).doc ...1...2...5...9 7...9...14...15...16...18...22...23...24...25...27...29...31...32...34 I ...35...36...37...39...40...40...42...44...46...48...51...52...53...53...54...55...56...56...58...61...64 II ...65...66...67...68...69...70...71...72...73...74...75...76...77...80...83...85...87...88

More information

禽畜饲料配制技术(一).doc

禽畜饲料配制技术(一).doc ( ) ...1...1...4...5...6...7...8...9...10... 11...13...14...17...18...21...23...24...26 I ...28 70...30...33...35...36...37...39...40...41...49...50...52...53...54...56...58...59...60...67...68...70...71

More information

中老年保健必读(十一).doc

中老年保健必读(十一).doc ...1...2...4...6...8...9...10...12...14...15...17...18...20...22...23...25...27...29 I ...30...32...35...38...40...42...43...45...46...48...52...55...56...59...62...63...66...67...69...71...74 II ...76...78...79...81...84...86...87...88...89...90...91...93...96...99...

More information

i

i i ii iii iv v vi 1 2 3 4 5 (b) (a) (b) (c) = 100% (a) 6 7 (b) (a) (b) (c) = 100% (a) 2 456 329 13% 12 120 7.1 0.06% 8 9 10 11 12 13 14 15 16 17 18 19 20 (a) (b) (c) 21 22 23 24 25 26 27 28 29 30 31 =

More information

怎样使孩子更加聪明健康(七).doc

怎样使孩子更加聪明健康(七).doc ...1...2...2...4...5 7 8...6...7...9 1 3... 11...12...14...15...16...17...18...19...20...21...22 I II...23...24...26 1 3...27...29...31...31...33...33...35...35...37...39...41...43...44...45 3 4...47...48...49...51...52

More information

i

i i ii iii iv v vi 1 g j 2 3 4 ==== ==== ==== 5 ==== ======= 6 ==== ======= 7 ==== ==== ==== 8 [(d) = (a) (b)] [(e) = (c) (b)] 9 ===== ===== ===== ===== ===== ===== 10 11 12 13 14 15 16 17 ===== [ ] 18 19

More information

二零零六年一月二十三日會議

二零零六年一月二十三日會議 附 件 B 有 关 政 策 局 推 行 或 正 在 策 划 的 纾 缓 及 预 防 贫 穷 措 施 下 文 载 述 有 关 政 策 局 / 部 门 为 加 强 纾 缓 及 预 防 贫 穷 的 工 作, 以 及 为 配 合 委 员 会 工 作, 在 过 去 十 一 个 月 公 布 及 正 在 策 划 的 新 政 策 和 措 施 生 福 利 及 食 物 局 (i) 综 合 儿 童 发 展 服 务 2.

More information

马太亨利完整圣经注释—雅歌

马太亨利完整圣经注释—雅歌 第 1 页 目 录 雅 歌 简 介... 2 雅 歌 第 一 章... 2 雅 歌 第 二 章... 10 雅 歌 第 三 章... 16 雅 歌 第 四 章... 20 雅 歌 第 五 章... 25 雅 歌 第 六 章... 32 雅 歌 第 七 章... 36 雅 歌 第 八 章... 39 第 2 页 雅 歌 简 介 我 们 坚 信 圣 经 都 是 神 所 默 示 的 ( 提 摩 太 后 书

More information

Sep (SCI) 10. Jiann-Ming Wu, Annealing by two sets of interactive dynamics, IEEE Trans. on Systems Man and Cybernetics Part B-Cybernetics 34 (3)

Sep (SCI) 10. Jiann-Ming Wu, Annealing by two sets of interactive dynamics, IEEE Trans. on Systems Man and Cybernetics Part B-Cybernetics 34 (3) 03-863-3531 E-mail jmwu@mail.ndhu.edu.tw /(1990/06-1994/06) (1988/06-1990/06) (1984/09-1988/06) / (1997/8-) (1996/08-1997/07) () 1996 8 Wu, Jiann-Ming ( SCI EI SSCI TSSCI EconLit A&HCI ) 1. Pei-Hsun Hsu

More information

論文寫作技巧

論文寫作技巧 論 文 寫 作 注 意 事 項 (How to Write a Paper) 初 版 合 撰 者 : (2/3/2004) 中 央 大 學 資 工 系 許 健 平 教 授 長 榮 大 學 資 管 系 陳 宗 禧 教 授 淡 江 大 學 資 工 系 張 志 勇 教 授 淡 江 大 學 資 工 系 石 貴 平 教 授 中 正 大 學 資 工 系 陳 裕 賢 教 授 一 題 目 (Title) 1. 題

More information

13-4-Cover-1

13-4-Cover-1 106 13 4 301-323 302 2009 2007 2009 2007 Dewey 1960 1970 1964 1967 303 1994 2008 2007 2008 2001 2003 2006 2007 2007 7 2013 2007 2009 2009 2007 2009 2012 Kendall 1990 Jacoby 1996 Sigmon 1996 1 2 3 20062000

More information

元培科技大學 年度「傑出校友」推薦表

元培科技大學      年度「傑出校友」推薦表 101 年 度 傑 出 校 友 蕭 文 達 本 校 畢 業 年 屆 民 國 74 年 畢 業 科 系 土 木 工 程 科 五 專 部 二 專 日 間 部 進 修 部 二 技 日 間 部 進 修 部 四 技 日 間 部 進 修 部 進 修 學 院 學 經 歷 學 歷 經 歷 國 立 中 興 大 學 土 木 工 程 學 系 博 士 朝 陽 科 技 大 學 環 境 安 全 衛 生 中 心 組 長 (90.2~

More information

填 写 要 求 一 以 word 文 档 格 式 如 实 填 写 各 项 二 表 格 文 本 中 外 文 名 词 第 一 次 出 现 时, 要 写 清 全 称 和 缩 写, 再 次 出 现 时 可 以 使 用 缩 写 三 涉 密 内 容 不 填 写, 有 可 能 涉 密 和 不 宜 大 范 围 公

填 写 要 求 一 以 word 文 档 格 式 如 实 填 写 各 项 二 表 格 文 本 中 外 文 名 词 第 一 次 出 现 时, 要 写 清 全 称 和 缩 写, 再 次 出 现 时 可 以 使 用 缩 写 三 涉 密 内 容 不 填 写, 有 可 能 涉 密 和 不 宜 大 范 围 公 2013 年 度 上 海 高 校 市 级 精 品 课 程 申 报 表 ( 本 科 ) 学 校 名 称 东 华 大 学 课 程 名 称 计 算 机 系 统 与 网 络 技 术 课 程 类 型 理 论 课 ( 不 含 实 践 ) 理 论 课 ( 含 实 践 ) 实 验 ( 践 ) 课 所 属 一 级 学 科 名 称 所 属 二 级 学 科 名 称 课 程 负 责 人 申 报 日 期 工 科 计 算 机

More information

南華大學數位論文

南華大學數位論文 南華大學 碩士論文 中華民國九十五年六月十四日 Elfin Excel I II III ABSTRACT Since Ming Hwa Yuan Taiwanese Opera Company started to cooperate with the Chinese orchestra, the problem of how the participation of Chinese music

More information

Microsoft Word - ACL chapter02-5ed.docx

Microsoft Word - ACL chapter02-5ed.docx 第 2 章神奇的質數 2.1.1 什麼是質數 1 1 1 打下好基礎 - 程式設計必修的數學思維與邏輯訓練 1 1 0 10 2 3 5 7 4 6 8 9 10 4 10000 1229 1000 168 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131

More information

Practical Guide For Employment Of Foreign Domestic Helpers

Practical Guide For Employment Of Foreign Domestic Helpers 僱 用 外 籍 家 庭 傭 工 實 用 指 南 外 籍 家 庭 傭 工 及 其 僱 主 須 知 目 錄 前 言 第 1 章 開 始 僱 傭 關 係 時 須 注 意 的 事 項 第 2 章 發 還 傭 工 申 請 證 件 的 費 用 第 3 章 支 付 及 扣 除 工 資 第 4 章 休 息 日 法 定 假 日 及 有 薪 年 假 第 5 章 醫 療 和 疾 病 津 貼 第 6 章 生 育 保 障 第

More information

穨423.PDF

穨423.PDF Chinese Journal of Science Education 2002,, 423-439 2002, 10(4), 423-439 1 2 1 1 1 2 90 8 10 91 4 9 91 8 22 ) NII 1995 7 14, 1999 1997 (Cooperative Remotely Accessible Learning CORAL) 424 (Collaborative

More information

中 國 文 化 大 學 文 學 院 史 學 系 碩 士 論 文 Master of Arts Thesis Graduate School of History College of Liberal Arts Chinese Culture University 聊 齋 誌 異 研 究 從 聊 齋 誌 異 看 蒲 松 齡 的 社 會 批 判 觀 The Study of Liaozhai Zhiyi-Discussion

More information

<A448A4E5AAC0B77CBEC7B3F8B2C43132A8F7B2C434B4C15F E706466>

<A448A4E5AAC0B77CBEC7B3F8B2C43132A8F7B2C434B4C15F E706466> 105 12 4 319-340 1 2 2 3 1 2 3 6 NVDA NVDA 2015 2014 320 5 37 22 5 2014 3000 2016 3 313 2016 12% inclusive education screen reader 321 2 3 2015 self-learning semi-structured interview 2002 2011 2008 322

More information

P(x,y) P(x-1,y) P(x,y-1) P(x,y+1) P(x+1,y) 1 3.2 Sobel LaplacePrewittRoberts Sobel [2] Sobel 3.3 2 [6] 0 1 1: P(x,y) t (4-connectivity) 2: P(x,y) t 3:

P(x,y) P(x-1,y) P(x,y-1) P(x,y+1) P(x+1,y) 1 3.2 Sobel LaplacePrewittRoberts Sobel [2] Sobel 3.3 2 [6] 0 1 1: P(x,y) t (4-connectivity) 2: P(x,y) t 3: chdong@npic.edu.tw rola@mail.stu.edu.tw (ITS) (LPR) ITS 2. [1][8] [3][9][12] [9] frequency table Sobel [3][12] RGB HSB color model [11] Hough transformation Sobel [4] [10] 1. Intelligent Transportation

More information

國立台灣師範大學英語研究所

國立台灣師範大學英語研究所 中 國 文 化 大 學 文 學 院 中 國 文 學 研 究 所 碩 士 論 文 Master of Arts Thesis Graduate Institute of Chinese Literature College of Liberal Arts Chinese Culture University 李 漁 風 箏 誤 研 究 A Study on Li Yu's Kite Error 指 導

More information

1 2 3 4 5 6

1          2         3         4         5         6 80 2002 8 6 4 3 5 15 [2] 21 5 13 7 5 3 2 1 1998 GIP [3] 109 55 1 5-10 2 15 20 16 13 [1] 75 3 20 4R&D =0.0411 10 40 Nissan 2006 200-300 2003 12 2003 3 80 4 3 10%-15% [4] QC SED OLAP 1993 30 [5] [6] 20 WSGorsset(1876-1937)

More information

國立中山大學學位論文典藏.PDF

國立中山大學學位論文典藏.PDF 國立中山大學教育研究所 碩士論文 Amabile 創造力成分模式與共識評量技術之驗證 以國小五年級繪畫為例 研究生 : 賴足菁撰 指導教授 : 鄭英耀 中華民國九十五年七月 1 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 B1

More information

Business Model Analysis of Kyoto Enterprises StudentYi-Jen Chan AdvisorMuh-Cherng Wu A Thesis Submitted to Master Program of Management for Executives

Business Model Analysis of Kyoto Enterprises StudentYi-Jen Chan AdvisorMuh-Cherng Wu A Thesis Submitted to Master Program of Management for Executives Business Model Analysis of Kyoto Enterprises Business Model Analysis of Kyoto Enterprises StudentYi-Jen Chan AdvisorMuh-Cherng Wu A Thesis Submitted to Master Program of Management for Executives College

More information

國立中山大學學位論文典藏.PDF

國立中山大學學位論文典藏.PDF 93 2 () ()A Study of Virtual Project Team's Knowledge Integration and Effectiveness - A Case Study of ERP Implementation N924020024 () () ()Yu ()Yuan-Hang () ()Ho,Chin-Fu () ()Virtual Team,Knowledge Integration,Project

More information

A VALIDATION STUDY OF THE ACHIEVEMENT TEST OF TEACHING CHINESE AS THE SECOND LANGUAGE by Chen Wei A Thesis Submitted to the Graduate School and Colleg

A VALIDATION STUDY OF THE ACHIEVEMENT TEST OF TEACHING CHINESE AS THE SECOND LANGUAGE by Chen Wei A Thesis Submitted to the Graduate School and Colleg 上 海 外 国 语 大 学 SHANGHAI INTERNATIONAL STUDIES UNIVERSITY 硕 士 学 位 论 文 MASTER DISSERTATION 学 院 国 际 文 化 交 流 学 院 专 业 汉 语 国 际 教 育 硕 士 题 目 届 别 2010 届 学 生 陈 炜 导 师 张 艳 莉 副 教 授 日 期 2010 年 4 月 A VALIDATION STUDY

More information

藍牙網路在資訊家電的應用

藍牙網路在資訊家電的應用 崑 山 科 技 大 學 資 訊 工 程 系 專 題 製 作 報 告 ANDROID 3D 推 箱 子 遊 戲 ANDROID 3D - BOXGAME 學 生 : 黃 咸 嘉 陳 政 男 郭 撫 龍 指 導 老 師 : 李 宗 儒 中 華 民 國 一 百 一 年 五 月 i ANDROID 3D 推 箱 子 遊 戲 ANDROID 3D - BOXGAME 學 生 : 黃 咸 嘉 Student:

More information

Microsoft Word - A201009-646.doc

Microsoft Word - A201009-646.doc # 中 国 网 络 游 戏 外 挂 问 题 现 状 分 析 * 兰 晓, 尹 杰 ( 中 国 传 媒 大 学 信 息 工 程 学 院 ) 摘 要 : 网 络 游 戏 外 挂 的 泛 滥 严 重 阻 碍 了 中 国 网 络 游 戏 产 业 的 正 常 发 展 本 文 给 出 了 网 络 游 戏 外 挂 的 定 义, 并 对 当 前 中 国 网 络 游 戏 存 在 的 安 全 问 题 进 行 了 分 析,

More information

本 論 文 獲 行 政 院 客 家 委 員 會 99 年 客 家 研 究 優 良 博 碩 士 論 文 獎 助

本 論 文 獲 行 政 院 客 家 委 員 會 99 年 客 家 研 究 優 良 博 碩 士 論 文 獎 助 國 立 雲 林 科 技 大 學 設 計 運 算 研 究 所 碩 士 班 碩 士 論 文 人 物 類 數 位 典 藏 加 值 應 用 之 研 究 - 以 桃 園 縣 客 家 文 化 館 之 鄧 雨 賢 文 化 加 值 產 品 設 計 為 例 A Study of Value-added Applications in Digital Archiving: Deng Yu-Shian's memorabilia

More information

Microsoft Word - 专论综述1.doc

Microsoft Word - 专论综述1.doc 2016 年 第 25 卷 第 期 http://www.c-s-a.org.cn 计 算 机 系 统 应 用 1 基 于 节 点 融 合 分 层 法 的 电 网 并 行 拓 扑 分 析 王 惠 中 1,2, 赵 燕 魏 1,2, 詹 克 非 1, 朱 宏 毅 1 ( 兰 州 理 工 大 学 电 气 工 程 与 信 息 工 程 学 院, 兰 州 730050) 2 ( 甘 肃 省 工 业 过 程 先

More information

北 京 大 学

北 京 大 学 北 京 大 学 硕 士 研 究 生 培 养 方 案 ( 信 息 工 程 学 院 报 表 修 订 版 本 ) 一 级 学 科 名 称 专 业 名 称 计 算 机 科 学 与 技 术 计 算 机 应 用 技 术 专 业 代 码 081203 北 京 大 学 研 究 生 院 制 表 填 表 日 期 :2012 年 06 月 16 日 一 学 科 ( 专 业 ) 主 要 研 究 方 向 序 研 究 方 向

More information

SVM OA 1 SVM MLP Tab 1 1 Drug feature data quantization table

SVM OA 1 SVM MLP Tab 1 1 Drug feature data quantization table 38 2 2010 4 Journal of Fuzhou University Natural Science Vol 38 No 2 Apr 2010 1000-2243 2010 02-0213 - 06 MLP SVM 1 1 2 1 350108 2 350108 MIP SVM OA MLP - SVM TP391 72 A Research of dialectical classification

More information

Microsoft Word - 20130627完整版

Microsoft Word - 20130627完整版 國 立 高 雄 餐 旅 大 學 台 灣 飲 食 文 化 產 業 研 究 所 The Graduate Institute of Taiwan Food Culture National Kaohsiung University of Hospitality and Tourism 碩 士 論 文 Thesis for the Master Degree 中 國 美 容 養 生 保 健 文 化 之 研

More information

Microsoft Word - 专论综述1.doc

Microsoft Word - 专论综述1.doc 1 基 于 协 同 过 滤 的 高 考 志 愿 推 荐 系 统 徐 兰 静, 李 珊, 严 钊 ( 南 京 航 空 航 天 大 学 经 济 与 管 理 学 院, 南 京 211100) 摘 要 : 近 年 来 信 息 过 载 问 题 的 出 现 使 得 个 性 化 推 荐 技 术 应 运 而 生, 其 中 协 同 过 滤 推 荐 技 术 通 过 在 用 户 和 信 息 之 间 建 立 联 系, 被

More information

专科疾病诊治(二十)

专科疾病诊治(二十) ...1... 11...19...32...43...50...52...53...58...61...64...66...69...84...89...92...95 I ...97... 100... 103... 107... 109 AD...111... 125... 128... 131... 135... 138... 140... 143... 146... 149... 152...

More information

(Chi)_.indb

(Chi)_.indb 1,000,000 4,000,000 1,000,000 10,000,000 30,000,000 V-1 1,000,000 2,000,000 20,000,00010,000,0005,000,000 3,000,000 30 20% 35% 20%30% V-2 1) 2)3) 171 10,000,00050% 35% 171 V-3 30 V-4 50,000100,000 1) 2)

More information

14A 0.1%5% 14A 14A.52 1 2 3 30 2

14A 0.1%5% 14A 14A.52 1 2 3 30 2 2389 30 1 14A 0.1%5% 14A 14A.52 1 2 3 30 2 (a) (b) (c) (d) (e) 3 (i) (ii) (iii) (iv) (v) (vi) (vii) 4 (1) (2) (3) (4) (5) 400,000 (a) 400,000300,000 100,000 5 (b) 30% (i)(ii) 200,000 400,000 400,000 30,000,000

More information

穨_2_.PDF

穨_2_.PDF 6 7.... 9.. 11.. 12... 14.. 15.... 3 .. 17 18.. 20... 25... 27... 29 30.. 4 31 32 34-35 36-38 39 40 5 6 : 1. 2. 1. 55 (2) 2. : 2.1 2.2 2.3 3. 4. ( ) 5. 6. ( ) 7. ( ) 8. ( ) 9. ( ) 10. 7 ( ) 1. 2. 3. 4.

More information

女性减肥健身(四).doc

女性减肥健身(四).doc ...1...2...3...4...6...7...8...10... 11...14...16...17...23...25...26...28...30...30 I ...31 10...33...36...39...40...42...44...47...49...53...53 TOP10...55...58...61...64...65...66...68...69...72...73

More information

Microsoft Word - 18-p0402-c3.doc

Microsoft Word - 18-p0402-c3.doc 第 14 卷 第 3 期 中 南 大 学 学 报 ( 社 会 科 学 版 ) Vol.14 No3 2008 年 6 月 J. CENT. SOUTH UNIV. (SOCIAL SCIENCE) Jun 2008 肺 病 隐 喻 与 性 别 身 份 建 构 中 国 现 代 文 学 中 的 肺 病 意 象 分 析 王 冬 梅 ( 枣 庄 学 院 中 文 系, 山 东 枣 庄,277160) 摘 要

More information

University of Science and Technology of China A dissertation for master s degree Research of e-learning style for public servants under the context of

University of Science and Technology of China A dissertation for master s degree Research of e-learning style for public servants under the context of 中 国 科 学 技 术 大 学 硕 士 学 位 论 文 新 媒 体 环 境 下 公 务 员 在 线 培 训 模 式 研 究 作 者 姓 名 : 学 科 专 业 : 导 师 姓 名 : 完 成 时 间 : 潘 琳 数 字 媒 体 周 荣 庭 教 授 二 一 二 年 五 月 University of Science and Technology of China A dissertation for

More information

Labour Department Annual Report

Labour Department Annual Report Labour Department Annual Report 2008 1 Labour Department Annual Report 2008 2 Labour Department Annual Report 2008 3 Labour Department Annual Report 2008 4 Labour Department Annual Report 2008 5 Labour

More information

生活百科(二)

生活百科(二) ...1...2...3...5...8...9...10... 11...14...15...17...18...19...20...20...21...24...25...26... 27 I ...28...29...31...32...32...34...35...36...37...38...39...40...42...43...45...46...47...49...49...53...

More information

中 國 文 化 大 學 藝 術 研 究 所 美 術 組 碩 士 論 文 現 代 女 性 體 態 美 初 探 此 論 文 為 藝 術 學 碩 士 學 位 之 部 分 要 求 指 導 教 授 : 歐 豪 年 研 究 生 : 賴 嚴 禾 中 華 民 國 98 年 06 月

中 國 文 化 大 學 藝 術 研 究 所 美 術 組 碩 士 論 文 現 代 女 性 體 態 美 初 探 此 論 文 為 藝 術 學 碩 士 學 位 之 部 分 要 求 指 導 教 授 : 歐 豪 年 研 究 生 : 賴 嚴 禾 中 華 民 國 98 年 06 月 中 國 文 化 大 學 藝 術 研 究 所 美 術 組 碩 士 論 文 現 代 女 性 體 態 美 初 探 此 論 文 為 藝 術 學 碩 士 學 位 之 部 分 要 求 指 導 教 授 : 歐 豪 年 研 究 生 : 賴 嚴 禾 中 華 民 國 98 年 06 月 碩 士 學 位 論 文 現 代 女 性 體 態 美 初 探 研 究 生 : 賴 嚴 禾 符 合 演 奏 / 創 作 組 部 分 要 求

More information

<4D6963726F736F667420576F7264202D20D6D0C9BDBBF0BEE6D6B0D2B5BCBCCAF5D1A7D4BAB9C7B8C9D0A3BDA8C9E8CFEEC4BFD7DCBDE1B1A8B8E631302E3138>

<4D6963726F736F667420576F7264202D20D6D0C9BDBBF0BEE6D6B0D2B5BCBCCAF5D1A7D4BAB9C7B8C9D0A3BDA8C9E8CFEEC4BFD7DCBDE1B1A8B8E631302E3138> I 目 录 前 言... 1 第 一 部 分 项 目 建 设 基 本 情 况... 2 一 项 目 建 设 总 体 目 标... 2 二 项 目 建 设 任 务... 2 ( 一 ) 项 目 主 要 建 设 内 容... 2 ( 二 ) 主 要 建 设 指 标... 3 三 项 目 建 设 资 金 预 算... 6 四 项 目 建 设 组 织 与 管 理... 6 ( 一 ) 健 全 组 织 机

More information

Improved Preimage Attacks on AES-like Hash Functions: Applications to Whirlpool and Grøstl

Improved Preimage Attacks on AES-like Hash Functions: Applications to Whirlpool and Grøstl SKLOIS (Pseudo) Preimage Attack on Reduced-Round Grøstl Hash Function and Others Shuang Wu, Dengguo Feng, Wenling Wu, Jian Guo, Le Dong, Jian Zou March 20, 2012 Institute. of Software, Chinese Academy

More information

中 华 女 子 学 院 外 语 系 教 学 实 践 周 2014 级 学 生 实 践 报 告 外 语 系 二 零 一 五 年 十 一 月 北 京 女 企 业 家 协 会 会 员 单 位 : 闫 会 欣 曹 群 牟 书 函 莫 茜 涵 中 威 融 通 资 产 管 理 ( 北 京 ) 有 限 公 司 : 刘 佳 文 庄 语 琪 周 思 敏 陈 梦 王 明 珠 姚 静 然 北 京 普 惠 宝 科 技 有

More information

續論

續論 國 立 臺 北 教 育 大 學 學 報, 第 19 卷 第 1 期 (95 年 3 月 )23~50 王 士 禎 的 山 水 詩 ( 下 ): 神 韻 與 山 水 23 國 立 臺 北 教 育 大 學 王 士 禎 的 山 水 詩 ( 下 ): 神 韻 與 山 水 * 黃 雅 歆 摘 要 引 領 康 熙 詩 壇 的 王 士 禎, 匯 聚 有 清 以 來 詩 人 對 詩 歌 創 作 的 主 張, 加 以

More information

Microsoft Word - 08 单元一儿童文学理论

Microsoft Word - 08 单元一儿童文学理论 单 元 ( 一 ) 儿 童 文 学 理 论 内 容 提 要 : 本 单 元 共 分 成 三 个 小 课 目, 即 儿 童 文 学 的 基 本 理 论 儿 童 文 学 创 作 和 儿 童 文 学 的 鉴 赏 与 阅 读 指 导 儿 童 文 学 的 基 本 理 论 内 容 包 括 儿 童 文 学 的 基 本 含 义 儿 童 文 学 读 者 儿 童 文 学 与 儿 童 年 龄 特 征 和 儿 童 文 学

More information

第三章

第三章 第 三 章 :2017 年 行 政 長 官 產 生 辦 法 - 可 考 慮 的 議 題 行 政 長 官 的 憲 制 及 法 律 地 位 3.01 基 本 法 第 四 十 三 條 規 定 : 香 港 特 別 行 政 區 行 政 長 官 是 香 港 特 別 行 政 區 的 首 長, 代 表 香 港 特 別 行 政 區 香 港 特 別 行 政 區 行 政 長 官 依 照 本 法 的 規 定 對 中 央 人

More information

nb.PDF

nb.PDF 3 4 5 7 8 9..10..15..16..19..52 -3,402,247-699,783-1,611,620 1,790,627 : - - -7,493 - -1,687 2,863 1,176 2,863 - -148,617 - - 12,131 51,325 - -12,131-2,165 14-2,157 8-3,393,968-794,198-1,620,094 1,781,367

More information

bnbqw.PDF

bnbqw.PDF 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ( ( 1 2 16 1608 100004 1 ( 2003 2002 6 30 12 31 7 2,768,544 3,140,926 8 29,054,561 40,313,774 9 11,815,996 10,566,353 11 10,007,641 9,052,657 12 4,344,697

More information

1. 本文首段的主要作用是 A. 指出 異蛇 的藥用功效 說明 永之人爭奔走焉 的原因 B. 突出 異蛇 的毒性 為下文 幾死者數矣 作鋪墊 C. 交代以蛇賦稅的背景 引起下文蔣氏有關捕蛇的敘述 2. 本文首段從三方面突出蛇的 異 下列哪一項不屬其中之一 A. 顏色之異 B. 動作之異 C. 毒性之

1. 本文首段的主要作用是 A. 指出 異蛇 的藥用功效 說明 永之人爭奔走焉 的原因 B. 突出 異蛇 的毒性 為下文 幾死者數矣 作鋪墊 C. 交代以蛇賦稅的背景 引起下文蔣氏有關捕蛇的敘述 2. 本文首段從三方面突出蛇的 異 下列哪一項不屬其中之一 A. 顏色之異 B. 動作之異 C. 毒性之 1. 本文首段的主要作用是 A. 指出 異蛇 的藥用功效 說明 永之人爭奔走焉 的原因 B. 突出 異蛇 的毒性 為下文 幾死者數矣 作鋪墊 C. 交代以蛇賦稅的背景 引起下文蔣氏有關捕蛇的敘述 2. 本文首段從三方面突出蛇的 異 下列哪一項不屬其中之一 A. 顏色之異 B. 動作之異 C. 毒性之異 3. 太醫以王命聚之 中的 以 字與下列哪一項的 以 意思相同 A. 以齧人 B. 而吾以捕蛇獨存

More information

untitled

untitled 1993 79 2010 9 80 180,000 (a) (b) 81 20031,230 2009 10,610 43 2003 2009 1,200 1,000 924 1,061 800 717 600 530 440 400 333 200 123 0 2003 2004 2005 2006 2007 2008 2009 500 2003 15,238 2009 31,4532003 2009

More information

Microsoft Word - 發布版---規範_全文_.doc

Microsoft Word - 發布版---規範_全文_.doc 建 築 物 無 障 礙 設 施 設 計 規 範 內 政 部 97 年 4 年 10 日 台 內 營 字 第 0970802190 號 令 訂 定, 自 97 年 7 月 1 日 生 效 內 政 部 97 年 12 年 19 日 台 內 營 字 第 0970809360 號 令 修 正 內 政 部 101 年 11 年 16 日 台 內 營 字 第 1010810415 號 令 修 正 目 錄 第 一

More information

概 述 随 着 中 国 高 等 教 育 数 量 扩 张 目 标 的 逐 步 实 现, 提 高 教 育 质 量 的 重 要 性 日 益 凸 显 发 布 高 校 毕 业 生 就 业 质 量 年 度 报 告, 是 高 等 学 校 建 立 健 全 就 业 状 况 反 馈 机 制 引 导 高 校 优 化 招

概 述 随 着 中 国 高 等 教 育 数 量 扩 张 目 标 的 逐 步 实 现, 提 高 教 育 质 量 的 重 要 性 日 益 凸 显 发 布 高 校 毕 业 生 就 业 质 量 年 度 报 告, 是 高 等 学 校 建 立 健 全 就 业 状 况 反 馈 机 制 引 导 高 校 优 化 招 I 概 述 随 着 中 国 高 等 教 育 数 量 扩 张 目 标 的 逐 步 实 现, 提 高 教 育 质 量 的 重 要 性 日 益 凸 显 发 布 高 校 毕 业 生 就 业 质 量 年 度 报 告, 是 高 等 学 校 建 立 健 全 就 业 状 况 反 馈 机 制 引 导 高 校 优 化 招 生 和 专 业 结 构 改 进 人 才 培 养 模 式 及 时 回 应 社 会 关 切 的 一 项

More information

鱼类丰产养殖技术(二).doc

鱼类丰产养殖技术(二).doc ...1...1...4...15...18...19...24...26...31...35...39...48...57...60...62...66...68...72 I ...73...88...91...92... 100... 104... 144... 146... 146... 147... 148... 148... 148... 149... 149... 150... 151...

More information

疾病诊治实务(一)

疾病诊治实务(一) ...1...4...5...8...13...14...15...18...18...19...22...25...26...27...29...30...32...35 I ...38...42...43...45...48...51...53...56...59...60...60...61...63...65...67...69...72...74...77...80...82...84 II

More information

名人养生.doc

名人养生.doc I...1...3...4...6... 11...14...18...22...26...29...31...38...45...49...56...57...59...61...67 ...72...73...75...77...80...83...85...91...92...93...95...96...97... 103... 107... 109... 110... 112... 118...

More information

<4D6963726F736F667420576F7264202D2040B9C5B871A661B0CFABC8AE61C2A7AB55ACE3A8735FA7F5ABD8BFB3B9C5B871A661B0CFABC8AE61C2A7AB55ACE3A8732E646F63>

<4D6963726F736F667420576F7264202D2040B9C5B871A661B0CFABC8AE61C2A7AB55ACE3A8735FA7F5ABD8BFB3B9C5B871A661B0CFABC8AE61C2A7AB55ACE3A8732E646F63> 嘉 義 地 區 客 家 禮 俗 研 究 第 一 章 前 言 嘉 義 地 區 的 客 家 族 群 約 略 可 分 為 福 佬 客 詔 安 客 與 北 部 客 等 三 種 類 別, 其 分 佈 區 域 以 海 線 地 區 平 原 地 形 沿 山 地 區 為 主 有 相 當 多 的 北 部 客 家 人, 是 二 次 大 戰 末 期 和 戰 後 初 期 才 移 民 嘉 義, 是 什 麼 因 素 令 許 多

More information

05301930

05301930 國 立 中 正 大 學 法 學 系 碩 士 論 文 河 川 砂 石 法 規 範 之 探 討 - 以 採 取 土 石 及 挖 掘 河 川 認 定 基 準 為 主 指 導 教 授 : 盧 映 潔 博 士 研 究 生 : 王 瑞 德 中 華 民 國 一 百 零 一 年 五 月 目 錄 第 一 章 緒 論... 1 第 一 節 研 究 動 機... 1 第 二 節 研 究 目 的... 3 第 三 節 研

More information

中老年保健必读(十).doc

中老年保健必读(十).doc ...1...2...3...4...5...6...8...9... 11 - -...13...15...17...18...20...22...23...25...26...28 I II...30...32...34...35...38...40...42...44...46...47...48...50...52...53 X...55...56...57...58...60...61...63...65

More information

23 29 15.6% 23 29 26.2% 3 25 2 15 1 5 1,542 12,336 14,53 16,165 18,934 22,698 25,125 25 2 15 1 5 5,557 7,48 8,877 11, 13,732 17,283 22,485 23 24 25 26

23 29 15.6% 23 29 26.2% 3 25 2 15 1 5 1,542 12,336 14,53 16,165 18,934 22,698 25,125 25 2 15 1 5 5,557 7,48 8,877 11, 13,732 17,283 22,485 23 24 25 26 4, 197823 2916.3%29 335, 23 29.5% 23 29 16.3% 14 35 33,535 14 135 13 125 1,292 1,3 1,38 1,314 1,321 1,328 1,335 3 25 2 15 1 5 1. 1.1 13,582 15,988 1.4 18,322 11.6 11.9 21,192 24,953 3,67 9. 8.7 12 1 8

More information

海淀区、房山区(四)

海淀区、房山区(四) ...1...1...2...7...8...9... 11... 15... 17... 17... 18... 19... 20... 21... 23... 25... 28... 31... 32 I ... 35... 36... 37... 39... 42... 43... 48... 53... 54... 58... 63... 64... 65... 66... 68... 71...

More information

穨ecr1_c.PDF

穨ecr1_c.PDF i ii iii iv 1 2 3 4 5 5555522 6664422 77722 6 7 8 9 10 11 22266 12833 1894 12 13 14 15 16 17 18 19 20 21 22 23 24 25 8.14 2.15 2.18 26 27 28 29 30 31 2.16 2.18 5.23 32 33 34 35 36 37 38 39 40 41 42 43

More information

穨2005_-c.PDF

穨2005_-c.PDF 2005 10 1 1 1 2 2 3 5 4 6 2 7 3 11 4 1 13 2 13 3 14 4 14 5 15 6 16 7 16 8 17 9 18 10 18 2005 10 1 1. 1.1 2 1.2 / / 1.3 69(2) 70(2) 1.4 1.5 1.6 2005 10 1 2. 2.1 2.2 485 20(8) (a) (i) (ii) (iii) (iv) 571

More information

北京理工大学.doc

北京理工大学.doc ( )...1...6...8...10...20...22...24...28...30...32...40 I ...53...55...61 ( )...62...71...74 ( )...77...81...84...86...88...89...91...92...96...99... 110...111... 112 II ... 113... 114... 115... 116...

More information

尲㐵.⸮⸮⸮⸮⸮

尲㐵.⸮⸮⸮⸮⸮ I...1...2...3...4...5...6...8...9...10... 11...12...13...14...15...16...17...18...19...20...21...22...23...24...26 II...27...28...28...29...30...31...32...34...35...36...37...38...39...39...40...41...43...43...44...45...46...47...48...48...49...50

More information

东城区(下)

东城区(下) ...1...1...2...3...9...9... 12... 12... 17... 17... 18... 19... 20... 29... 31... 37... 41... 70... 73 I ... 74... 78... 78... 79... 80... 85... 86... 88... 90... 90... 90... 92... 93... 95... 95... 96...

More information

果树高产栽培技术(一).doc

果树高产栽培技术(一).doc ( ) ...1...1...3...10... 11...12...15...17...18...19...20...22...23...24...26...27...28...30...31...32 I ...36...38...40...41...42...44...45...47...48...49...50...51...52...53...55...58...59...60...61...62...66...67

More information

物质结构_二_.doc

物质结构_二_.doc I...1...3...6...8 --... 11 --...12 --...13 --...15 --...16 --...18 --...19 --...20 --...22 --...24 --...25 --...26 --...28 --...30 --...32 --...34 --...35 --...37 --...38...40 II...41...44...46...47...48...49...51...52...55...58

More information

第一節 研究動機與目的

第一節 研究動機與目的 中 國 文 化 大 學 中 國 文 學 研 究 所 碩 士 論 文 華 嚴 一 真 法 界 思 想 研 究 指 導 教 授 : 王 俊 彥 研 究 生 : 許 瑞 菁 中 華 民 國 98 年 12 月 自 序 在 佛 教 經 典 中 最 初 接 觸 的 是 佛 說 無 量 壽 經, 此 經 乃 大 方 廣 佛 華 嚴 經 的 精 華 版 綱 要 版 為 了 瞭 解 經 義, 深 知 宇 宙 運

More information