 |
| 系統識別號 |
U0002-0507201811101800 |
| 中文論文名稱
|
(0,1)數列的奇偶置換排序之研究 |
| 英文論文名稱
|
A study of odd-even transposition sort of (0,1)-sequences |
| 校院名稱 |
淡江大學 |
| 系所名稱(中) |
數學學系數學與數據科學碩士班 |
| 系所名稱(英) |
Master's Program, Department of Mathematics |
| 學年度 |
106 |
| 學期 |
2 |
| 出版年 |
107 |
| 研究生中文姓名 |
蔡沛蓁 |
| 研究生英文姓名 |
Pei-Jhen Cai |
| 學號 |
605190031 |
| 學位類別 |
碩士 |
| 語文別 |
中文 |
| 口試日期 |
2018-06-25 |
| 論文頁數 |
38頁 |
| 口試委員 |
指導教授-潘志實
委員-張飛黃
委員-郭君逸
|
| 中文關鍵字 |
(0,1)數列
奇偶置換排序
|
| 英文關鍵字 |
(0,1)-sequences
odd-even transposition sort
|
| 學科別分類 |
|
| 中文摘要 |
給定任意圖 G=(V,E)，|V(G)|=n，對圖形上每個點標註 {v_1,v_2,…,v_n }，給定一 n 個數字的排列 π=p_1,p_2,…,p_n，每個頂點 v_i 上標記一個棋子 p_j，這些棋子是可以移動的，但必須遵守下列規則：在每個步驟中，在圖 G 中取邊的不相交子集，這些邊的端點之棋子可以做交換，目標為將所有棋子 p_i 交換到對應的頂點 v_i 上。定義 rt(G,π) 為將 π 排好的最少步數，而圖 G 的傳遞數是指對任意排列 π 都能排好所需要的最少步數，記作 rt(G)=(max)┬π〖rt(G,π)〗。
給定一數列 π=p_1,p_2,…,p_n，我們看其中一個數字 p_i，在原本數列中的數字若大於等於 p_i 則改為 1，反之則改為 0，因此可以得到一(0,1)數列λ=c_1,c_2,…,c_n。已知利用(0,1)數列可以證明路徑圖傳遞數之上界，給定任意的(0,1)數列 λ=c_1,c_2,…,c_n，將其以奇偶置換方法排序的步數小於等於 n-1 步。
在本文中針對任意的(0,1)數列 λ=c_1,c_2,…,c_N ,N=∑_(k=0)^n▒a_k +∑_(k=0)^n▒b_k ，
定義 S=a_0,b_n,a_1,b_(n-1),a_2,b_(n-2),…a_(n-2),b_2,a_(n-1),b_1,a_n,b_0，
a_i,b_i≥1,i=0,1…n 分別為 0和1 之個數且 a_0 ,b_0 亦可以等於 0，
則在奇偶置換排序後，將其排好的最少步數為
N-(min)┬(i∈{0,1,…,n-1} )〖{∑_(j=0)^i▒a_j +∑_(j=0)^(n-i-1)▒b_j }〗-1
|
| 英文摘要 |
Let G=(V,E) be a connected graph with vertices {v_1,v_2,…,v_n } and π be a permutation on [n]. Initially, each vertex v_i of G is occupied by a “pebble.” Pebbles can be moved around by the following rule: At each step a disjoint collection of edges of G is selected, and the pebbles at each edge’s two endpoints are interchanged. The goal is to move/route each pebble p_i to its destination v_i.Define rt(G,π) to be the minimum number of steps to route the permutation π.Finally, define rt(G) the routine number of G by rt(G)=(max)┬π〖rt(G,π)〗.
Given a sequence, π=p_1,p_2,…,p_n, we choose the number p_i, if the number of the original sequence is greater or equal to p_i then change to “1”, otherwise change to “0”, therefore we obtain a (0,1)-sequences, λ=c_1,c_2,…,c_n. It is known that using the (0,1)-sequence can prove the upper bound of the routine number of path,then given an arbitrary (0,1)-sequence λ=c_1,c_2,…,c_n, the number when it line up by odd-even transposition sort is less than or equal to n-1.
In this paper, in connection with arbitrary (0,1)-sequences,λ=c_1,c_2,…,c_N ,N=∑_(k=0)^n▒a_k ∑_(k=0)^n▒b_k , define S=a_0,b_n,a_1,b_(n-1),a_2,b_(n-2),…a_(n-2),b_2,a_(n-1),b_1,a_n,b_0, a_i,b_i≥1,i=0,1…n are quantity of 0,1 respectively and a_0,b_0≥0, after odd-even transposition sort, the number when it line up will be
N-(min)┬(i∈{0,1,…,n-1} )〖{∑_(k=0)^i▒a_k +∑_(k=0)^(n-i-1)▒b_k }〗-1
|
| 論文目次 |
目錄
目錄..............................................I
圖表目錄..........................................II
第一章 基本定義與簡介..............................1
第二章 奇偶置換方法................................6
第三章 (0,1)數列的奇偶置換排序.....................17
第四章 結論及未來工作..............................37
參考文獻..........................................38
圖表目錄
圖1.1(圖上棋子的傳遞)..............................3
圖1.2...........................................4
圖1.3(路徑圖的奇偶置換)............................4
圖1.4(數列的奇偶置換)..............................4
圖2.1...........................................14
圖2.2...........................................15
圖3.1...........................................17
圖3.2...........................................21
|
| 參考文獻 |
[1] N. Alon, F.R.K. Chung, and R.L. Graham, Routing Permutations on graphs via matchings, SIAM J. Discrete Math., 7(1994), pp.513-530
[2] M. Baumalag and F. Annexstein, A unified framework for off-line permutation routing in parallel networks, Math. Systems Theory, 24(1991), pp.233-251.
[3] V. E. Benes, Mathematical Theory of Connecting Networks, Academic Press, New York, 1965.
[4] F.K. Chung, Spectral Graph Theory, AMS Publications, Providence, RI, 1997.
[5] Wei-Tian-Li, Linyuan Lu, and Yiting Yang, Routing Numbers of Cycles, Complete Bipartite Graphs, And Hypercubes, SIAM J. Discrete Math. Vol.24(2010), No.4, pp.1482-1494.
[6] M. Ramras, Routing permutations on a graph, Networks, 23 (1993), pp.391-398.
[7] L. Valiant, A scheme for fast parallel communication, SIAM J. Comput., 11(1982), pp.350-361.
[8] Tomas Worsch and Hidenosuke Nishio, Real-Time Sorting of Binary Numbers on One-Dimensional CA, Journees Automates Cellulaires 2010(Turku), pp.214-225.
[9] 虞凱文，對路徑圖及路徑圖上加一條邊的傳遞數之研究，淡江大學覺生紀念圖書館2015.
[10] 韓鳴展，刻劃路徑圖的傳遞數，淡江大學覺生紀念圖書館2016.
|
| 論文使用權限 |
同意紙本無償授權給館內讀者為學術之目的重製使用，於2018-07-16公開。同意授權瀏覽/列印電子全文服務，於2018-07-16起公開。 |
 |
|
 |
