淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 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起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2486 或 來信