English  |  正體中文  |  简体中文  |  全文筆數/總筆數 : 78728/78728 (100%)
造訪人次 : 33351983      線上人數 : 448
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
搜尋範圍 查詢小技巧:
  • 您可在西文檢索詞彙前後加上"雙引號",以獲取較精準的檢索結果
  • 若欲以作者姓名搜尋,建議至進階搜尋限定作者欄位,可獲得較完整資料
  • 進階搜尋


    請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/57119


    題名: 設計有效率的平行演算法去辦識序列平行圖;Design Efficient Parallel Algorithms for Recognizing Series-Parallel Graphs
    作者: 何錦文
    貢獻者: 中央大學資訊工程學系
    關鍵詞: 資訊工程--硬體工程;平行演算法;序列平行圖;平行隨機存取機器模式;開放式耳朵分解;分解樹;Parallel algorithm;Series-parallel graphs;Parallel random access machine;Open ear decomposition;Decomposition tree
    日期: 1995-09-01
    上傳時間: 2012-10-01 15:14:32 (UTC+8)
    出版者: 行政院國家科學委員會
    摘要: 本計畫是為期一年的計畫.在此計畫中,我們 將研究如何在平行隨機存取機器模式下設計一 個有效率的平行演算法來辨識序列平行圖( Series parallel graphs),並為序列平行圖建構一個分 解樹(Decomposition tree).序列平行圖是一種可由單 一邊開始,不斷地運用序列合成(Series composition) 和平行合成(Parallel composition)所產生的一種圖 形.這種圖形在電子電路、排程問題和系統的 可靠性等相關領域上提供了重要的應用.而分 解樹可用來表示序列平行圖的結構,樹中的每 個內點(Internal vertice)代表一種合成運算( Composition operator),而每個樹葉(Leaf)則代表序列 平行圖的邊(Edge).假若給定一個序列平行圖的 分解樹,那麼在序列平行圖所探討的一些最佳 化子圖問題(Optimal subgraph problems)像最大獨立子 集(Maximum independent set),最多配對(Maximum matching) 和最大終結子集(Maximum dominatingset)...等可在不 可同時讀寫的平行隨機存取機器(EREW PRAM)下以 最佳花費(Cost optimal)的演算法求解;也就是說這 類問題可以在O(logn)的時間內用O(n/logn)個處理 器來完成.由此可見有效率的建構出分解樹可 直接改進上述問題的時間複雜度.而目前用來 識別序列平行圖並建構出分解樹的演算法尚須 使用O(n)個處理器在O(log/sup 2/n)時間內在EREW中 完成.此處的n是輸入圖形的大小.所以,若我們 能將辨識序列平行圖的演算法加以改進,那麼 許多用來解決有關於序列平行圖的圖論問題的花費和時間都將大大的節省下來. ; 研究期間 8308 ~ 8407
    關聯: 財團法人國家實驗研究院科技政策研究與資訊中心
    顯示於類別:[資訊工程學系] 研究計畫

    文件中的檔案:

    檔案 描述 大小格式瀏覽次數
    index.html0KbHTML379檢視/開啟


    在NCUIR中所有的資料項目都受到原著作權保護.

    社群 sharing

    ::: Copyright National Central University. | 國立中央大學圖書館版權所有 | 收藏本站 | 設為首頁 | 最佳瀏覽畫面: 1024*768 | 建站日期:8-24-2009 :::
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - 隱私權政策聲明