系統識別號 | U0002-0507201811101800 |
---|---|
DOI | 10.6846/TKU.2018.00163 |
論文名稱(中文) | (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. |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信