第一篇：2012年報告-離散數學-福州大學

離散數學及其應用教育部重點實驗室工作總結報告（2013年2月20日）

實驗室名稱： 離散數學及其應用教育部重點實驗室 主管部門： 福建省教育廳 依托單位： 福州大學

實驗室概況: 在迅速發展的計算機科學技術及信息技術等領域，離散數學是重要的基礎學科和支撐學科，它的發展和應用是影響一個國家科學技術發展水平的重要因素。以福州大學“離散數學與理論計算機科學研究中心”為依托的離散數學及其應用教育部重點實驗室于2007年7月獲教育部批準立項建設。目前，實驗室共有固定研究人員27人，其中教授16人，副教授4人。實驗室由馬志明院士擔任學術委員會主任，范更華教授擔任實驗室主任。實驗室位于福州大學銅盤校區。2007年11月完成了實驗室裝修一期工程；2009年3月完成了二期裝修工程，達到 “環境優美、設備一流”。按國際研究所標準建設基礎設施，為每位研究人員及來訪學者提供40平米寬敞辦公室及一流科研設備。為每位研究生提供一個工作位及臺式電腦。已建成無線網覆蓋實驗室3000平米的科研、辦公場所。重視網絡建設，保證網絡高速暢通。訂購相關專業的國外數據庫及原版圖書，已基本建成一流的專業圖書資料室。

一、實驗室現有三個研究方向：圖論與組合數學、大規模集成電路設計中的數學方法、優化理論與算法。

二、本年度實驗室在研科研項目國家973計劃課題1項，國家自然科學基金7項，其中重點項目1項，面上項目2項，青年項目4項。教育部重點項目1項，高等學校博士學科點專項科研基金1項。新增國家自然科學基金7項，其中面上項目3項，分別是：

1.超大規模集成電路布局的ell-1模優化模型及其算法研究（61170308），朱文興。2.有色噪聲下基于噪聲約束最小均方估計的語音增強算法（61179037），夏又生。

3.非曼哈頓結構下帶粒子群優化的VLSI總體布線算法研究（11141005），陳國龍。青年項目4項，分別為：

1.基于視覺注意力機制的機器人認知視覺感知系統（61105102），于元隆

2.無線傳感器網絡中任務調度的并行聯盟生成與博弈分配策略（61103175），郭文忠

3.圖的拉普拉斯譜及相關拓撲指標（11101087），劉劍萍 4.不含某些子式的擬陣結構（11201076），陳容

實驗室成員劉劍萍主持的“圖譜理論及其相關問題”獲福建省自然科學二等獎。

三、實驗室不僅是高水平科學研究中心，也是高層次人才培養基地。實驗室以應用數學、計算機應用技術省級重點學科，國家集成電路人才培養基地，離散數學“211工程”建設重點學科，應用數學博士點以及兩個一級學科碩士點（數學、計算機科學與技術）為支撐，形成具有一定規模的離散數學高層次人才培養體系。實驗室將充分利用自身的條件，圍繞主攻方向，提升開放層次，促進學術交流與合作，使實驗室整體研究水平達到國內領先水平，某些研究方向達到國際先進水平，為國家及福建地方建設做出突出貢獻。本年度培養博士研究生3名，碩士研究生25名。

四、年度科研成果

實驗室在各個研究問題方面開展了深入地研究工作，在課題研究中取得了一些很好的研究結果。本年度課題組研究成員在國內外重要專業刊物上發表SCI收錄論文32篇，EI收錄5篇，主要研究成果如下：

（1）VLSI中的圖論與優化算法研究工作

在大規模集成電路設計理論研究方面，課題組在開展擬定研究工 作的同時, 進一步加強與集成電路設計研發機構的合作，先后派出課題組成員和博士研究生共計9人次到北京華大九天軟件有限公司，了解我國目前唯一的集成電路設計工具“九天”EDA的研發進展，并針對該項研發所提出的多項實際研究問題，從理論和實際兩個方面都提出了解決方案。

1）北京華大九天軟件有限公司正在著力開發的自動化對稱布線軟件中，由于當前國內外對對稱布線的系統研究非常少, 在實際布線過程中存在線網需要對稱布線的問題。該問題目前都是采用手工布線,只能解決布線層和已布線網數比較少的情況, 還經常出現找不到問題的解的情況。課題組研究了該問題，證明了H-V模型下對稱布線問題等價于在有效連通圖中找所有引腳對應點的一棵斯坦納樹問題，并提出一個解決對稱布線問題的算法。該算法適合無網格且水平和垂直布線層交替出現的模型，經過修改還得到在一層中既可以水平布線又可以垂直布線的模型下的對稱布線問題的方法。這項研究為自動化對稱布線軟件的開發提供了一個方法和理論保障。

2）研究了超大規模集成電路標準單元的布局問題。布局是超大規模集成電路物理設計的關鍵步驟，影響了芯片的可布線性、性能和功耗。我們研發了一個標準單元布局器，其中包含了全局布局和詳細布局兩個階段。在全局布局階段，我們用非線性規劃方法和最優聚類技術對電路聚類，在解聚類階段用迭代改進技術確定每個單元的位置，同時縮短線長。在詳細布局階段，我們構造一個快速合法化算法把全局布局的解合法化，并用單元序消除策略改進合法化后的解。用IBM standard cell benchmark circuits和Peko standard cell benchmark suite2對所構造的布局工具做測試，實驗表明該布局工具可以在合理的時間內得到高質量的布局結果。

3）研究了與集成電路設計相關的若干理論問題。在與電路劃分問題密切相關的圖劃分問題研究中，研究了最小平衡劃分問題，在一般圖類上給出了一個緊的上界，將這一結果應用于平面圖類上，得到了平面圖最小平衡劃分很好的上界。

4）構造了圖的max-cut問題和max-k-cut問題的動態凸化算法，計算實驗表明了算法的性能是這兩個問題當前性能最好的算法之一。利用B*-tree表示法，構造了矩形裝箱問題的啟發式裝箱策略，構造了改進該策略的一個局部搜索算法。實驗表明算法可以有效地求解矩形裝箱。研究了帶一個連續變量的0-1背包問題，構造了快速分支定界算法；構造了非凸混合非線性整數規劃問題的動態凸化算法。實驗驗證了算法的有效性。（2）圖論與組合研究工作

課題組開展了關于圖的平衡劃分，圖與超圖的譜理論擬陣分解，Ramsey理論，圖染色的研究工作，取得了多項有意義的結果。

1）在離散數學中，一個常見的現象是對連通度較低的結構很適合用數學歸納法但卻沒有很多有用的性質，而那些連通度較高的結構雖然有很多好的性質卻不能用數學歸納法。因此，如何找到一個二者的最佳結合點便成為了一個大家關注的問題。1連通擬陣很顯然可以分解成2連通擬陣。Cunningham和Edmonds證明了通過運算“2-sum”任意2連通擬陣可以像樹一樣地分解成一系列的3連通擬陣。在這篇論文中，我們證明了任何元素個數大于等于9的3連通可表示擬陣，通過運算“reducing”可以像樹一樣地分解成一系列的序列4連通擬陣和三類特殊的擬陣。序列4連通是一個介于3連通和4連通之間的連通度，它彌補了對4連通擬陣不能用數學歸納法的缺憾，也具備了3連通擬陣不具備的好的性質。該論文發表在組合頂級雜志“J.Combin.Theory Ser.B”上，審稿人稱該文“of high quality”, “of interesting and will be useful to other researchers.Moreover, the methods used are good”。

2）圖的線性蔭度是指將圖分解成線性森林的最小數目，在1984年，Akiyama提出了注明的線性蔭度猜想，在2008年,Wu等人證明了平面圖滿足線性蔭度猜想，我們對平面圖上的線性染色進行了考慮，猜測如果平面圖的最大度至少是6，則其線性蔭度可以完全確定，并且證明了如果平面圖的最大度至少是8，其線性蔭度可以完全確定，從而猜想只剩下最大度等于6或者7的情形，同時，我們給出了該類圖的一個線性染色，其時間復雜性是O(nlogn)。

3）圖的無圈邊染色問題是著名數學家Alon提出的，在2001年，Alon等人利用概率方法給出了無圈邊色數的上界。在其證明過程中，因為小圈會以很大的概率出現兩種顏色，因此其上界較難改進，我們利用類似的思路考慮的圍長較大的圖的無圈染色問題，從而改進其上界，同時，我們利用組合方法考慮的不含三角形的系列平行圖的無圈染色問題，確定了該類圖的無圈邊色數。在2001年，Alon等人給出了無圈邊染色猜想，我們驗證了不含短圈的平面圖上的情形。4）Remasy理論的研究是一直是圖論研究的熱門問題，我們研究了非對角Remasy，證明了存在一個正整數C，使得下面成立：如果N

五、學術交流

2012年11月2日--6日，由中國系統工程學會模糊數學與模糊系統專業委員會（國際模糊系統協會中國分會）主辦，由福州大學承辦的第十六屆全國模糊數學與模糊系統學術會議在福州大學學術交流中心--怡山大廈隆重舉行。

本次會議由中國模糊數學與模糊系統專業委員會名譽主任委員、中國科學院院士劉應明教授擔任大會主席，由專業委員會主任委員、四川大學羅懋康教授擔任程序委員會主任，由實驗室主任范更華教授擔任組織委員會主任，由專業委員會秘書長、四川大學張德學教授和福州大學校長助理、科技處處長陳國龍教授擔任組織委員會副主任。參加大會的代表有來自全國高等院校、研究院所等60多個單位的專家學者和研究生200多人。本次會議得到了全國模糊數學和模糊系統領域的專家和學者的大力支持，共收到學術論文110余篇，經專家評審，其中42篇論文發表在專業委員會雜志《模糊系統與數學》2012年第4期和第5期上，18篇論文發表在雜志《數學的實踐與認識》2012年第19期上。在本次會議期間，代表們進行了廣泛的學術交流。9位專家分別作了精彩的大會報告，24位代表在分組會上進行了學術交流，內容涉及模糊數學的理論研究及應用等領域。本次學術會議學 術氛圍濃厚，交流廣泛，達到了國內模糊數學界相互交流最新研究成果的目的。

2012年12月7日至11日，實驗室主辦“2012年離散數學國際研討會”，40多位國內外離散數學專家應邀參加了會議，在本次會議期間，代表們進行了廣泛的學術交流。20位專家分別作了精彩的學術報告，內容涉及離散數學的理論研究及應用等領域。本次學術會議學術氛圍濃厚，交流廣泛，達到了國內離散數學界相互交流最新研究成果的目的。

2012年12月14日至16日，實驗室主辦了“International Workshop on Image Processing and Inverse Problems”國際學術會議，共有70多位國內外學者參會。

在本年度，共有10余位國內外知名學者到校訪問，并作報告和進行合作研究，其中包含美國喬治亞理工大學教授郁星星，復旦大學教授朱洪，南開大學教授向開南等。

第二篇：2011年報告-離散數學-福州大學

離散數學及其應用教育部重點實驗室工作總結報告（2012年2月10日）

實驗室名稱： 離散數學及其應用教育部重點實驗室 主管部門： 福建省教育廳 依托單位： 福州大學

實驗室概況: 在迅速發展的計算機科學技術及信息技術等領域，離散數學是重要的基礎學科和支撐學科，它的發展和應用是影響一個國家科學技術發展水平的重要因素。以福州大學“離散數學與理論計算機科學研究中心”為依托的離散數學及其應用教育部重點實驗室于2007年7月獲教育部批準立項建設。目前，實驗室共有固定研究人員27人，其中教授16人，副教授4人。實驗室由馬志明院士擔任學術委員會主任，范更華教授擔任實驗室主任。實驗室位于福州大學銅盤校區。2007年11月完成了實驗室裝修一期工程；2009年3月完成了二期裝修工程，達到 “環境優美、設備一流”。按國際研究所標準建設基礎設施，為每位研究人員及來訪學者提供40平米寬敞辦公室及一流科研設備。為每位研究生提供一個工作位及臺式電腦。已建成無線網覆蓋實驗室3000平米的科研、辦公場所。重視網絡建設，保證網絡高速暢通。訂購相關專業的國外數據庫及原版圖書，已基本建成一流的專業圖書資料室。

一、實驗室現有三個研究方向：圖論與組合數學、大規模集成電路設計中的數學方法、優化理論與算法。

二、在本，實驗室在研科研項目國家973計劃課題1項，國家自然科學基金8項，其中重點項目1項，面上項目6項，青年項目1項。國家科技部產學研項目1項，教育部高校博士點專項科研基金聯合資助課題1項，新增國家自然科學基金3項，均為青年項目，分別是：

1.矩陣定性分析中Ray非異及復符號非異矩陣的特征刻畫（11101088），劉月。2.圖的Ramsey理論中的隨機方法（11101086），林啟忠。3.Volterra 方程與高維分數階擴散方程的理論與數值研究（11201077），李嫻娟。

新增教育部重點項目1項：動態拓撲下WSN任務調度中多目標優化問題的算法研究，郭文忠。

實驗室成員侯建鋒博士獲福建省自然科學基金杰青項目資助。

三、實驗室不僅是高水平科學研究中心，也是高層次人才培養基地。實驗室以應用數學、計算機應用技術省級重點學科，國家集成電路人才培養基地，離散數學“211工程”建設重點學科，應用數學博士點以及兩個一級學科碩士點（數學、計算機科學與技術）為支撐，形成具有一定規模的離散數學高層次人才培養體系。實驗室將充分利用自身的條件，圍繞主攻方向，提升開放層次，促進學術交流與合作，使實驗室整體研究水平達到國內領先水平，某些研究方向達到國際先進水平，為國家及福建地方建設做出突出貢獻。本碩士研究生26名。

四、科研成果

實驗室在各個研究問題方面開展了深入地研究工作，在課題研究中取得了一些很好的研究結果。本課題組研究成員在國內外重要專業刊物上發表研究SCI收錄論文28篇，EI收錄論文7篇。主要科研成果如下：

（1）VLSI中的圖論與優化算法研究工作

1）在大規模集成電路設計理論研究方面，課題組在開展擬定研究工作的同時, 進一步加強與集成電路設計研發和研究機構的合作，先后派出課題組成員和博士研究生共計9人次到北京華大電子了解我國目前唯一的集成電路設計工具“九天”EDA的研發進展，并針對該項研發所提出的多項實際研究問題，從理論和實際兩個方面都提出了解決方案。在北京華大九天公司正在著力開發的自動化對稱布線軟件研發中，由于當前國內外對對稱布線的系統研究非常少, 在實際布線過程中如果存在線網需要對稱布線都是采用手工布線, 而且手工布線也只能解決布線層和已布線 網比較少的情況, 還經常出現找不到問題的解的情況。課題組得到了H-V模型下對稱布線問題等價于在有效連通圖中找所有引腳對應的點的一棵斯坦納樹并提出一個解決對稱布線算法。本方法適合無網格且水平和垂直布線層交替出現的模型。此方法經過修改還得到一層既可以水平布線又可以垂直布線的模型下關于對稱布線問題的方法。這項研究為自動化對稱布線軟件的開發提供了一個方法和理論保障；布線在超大規模集成電路布局面積中是一個關鍵性問題。Szymanski證明找一個通道布線的最小寬度是NP-困難的。課題組研究證明了通道對應的圖CCG的一個最少平行團覆蓋等價于一個垂直限制無圈且不添加新的空列和狗腿到網格上的二層曼哈頓模型通道布線的一個最優解。根據這個結論我們還給出了一個解決二層曼哈頓模型通道布線的一個啟發式算法。為華大九天公司開發的自動化布線軟件中自動化通道布線軟件的開發提供了一個可行的解決方案；我們使用圖論的方法對David Szeszler的2層具有Manhattan模型的通道布線的算法進行改進，并給了一個新的算法，這個算法比以前的算法所用層數更少，該項研究可用在華大九天公司正在開發的布線工具通道寬度的估計。

2）研究并設計出器件匹配問題的一種自動匹配方法（MatchingLiu算法），該算法已用C程序實現。通過華大九天公司的評估，認為該算法快速、有效，可以幫助彌補公司新一代IC設計平臺Aether的自動匹配工具的空白。

3）研究了超大規模集成電路標準單元的布局問題。布局是超大規模集成電路物理設計的關鍵步驟，影響了芯片的可布線性、性能和功耗。我們研發了一個標準單元布局器，其中包含了多層全局布局和詳細布局兩個階段。在全局布局階段，我們用非線性規劃方法和最優聚類技術對電路聚類，在解聚類階段用迭代改進技術定每個單元的位置，同時縮短線長。在詳細布局階段，我們構造一個快速合法化算法把全局布局的解合法化，并用單元序消除策略改進合法化后的解。用IBM standard cell benchmark circuits和 Peko standard cell benchmark suite2對所構造的布局工具做測試，實驗表明該布局工具可以在合理的時間內得到高質量的布局結果。

4）研究了超大規模集成電路標準單元的布圖規劃問題。布圖規劃是超大規模集成電路物理設計的第一階段，是NP難問題。我們構造了不可二分布圖規劃問題的混合模擬退火算法，該算法先用一個貪心策略生成初始的B*-tree，通過B*-tree搜索解空間，并用一個新的經驗性策略平衡全局搜索和局部搜索。用MCNC benchmarks的實例對算法作測試，實驗表面算法能快速找到最優解或近優解。

5）電路劃分是VLSI 物理設計自動化中的一個關鍵階段，也影響了后續的電路設計，電路劃分問題是NP 困難的組合優化問題。我們把該問題轉化為帶約束的非線性整數規劃問題，同時構造了該問題的動態凸化算法。算法用改進的Fiduccia-Mattheyses(FM)算法作為非線性整數規劃問題的局部搜索算法。理論分析和實驗表面，通過增加一個參數的值，算法能跳出局部極小解找到更好的的解。我們用ACM/SIGDA and ISPD98 benchmarks的測試實例對算法作測試，結果表明我們的算法產生的解的質量大大優于原始的FM算法。進一步，我們把所構造的算法集成到多層劃分工具MLPart中，實驗表明，所得到的解的質量比MLpart提高了3-7%。此外，我們把FM 算法結合到分散搜索算法框架中，提出一種電路劃分的分散搜索算法。算法利用FM 算法進行局部搜索，利用分散搜索的策略進行全局搜索。為滿足分散搜索方法對初始解的質量和多樣性的要求，提出采用GRASP 和聚類相結合的方法來產生初始解。實驗結果表明，該算法可以求解較大規模的電路劃分實例，且與基于多級框架的劃分算法hMetis 相比，劃分的質量有了明顯的提高。

6）研究了從集成電路中提取的max-k-cut問題，構造了該問題的一個動態凸化算法；研究了帶一個連續變量的0-1背包問題，構造了快速分支定界算法；構造了非凸混合非線性整數規劃問題的動 態凸化算法。實驗驗證了算法的有效性。（2）圖論與組合研究工作

在圖全染色方面，證明了圖的全色數等于d+1的幾個充分條件，其中d表示圖的最大度，其結果推廣了發表在《Discrete Applied Mathematics》上的堵丁柱教授的結果。

在圖無圈邊染色方面，考慮了不含短圈的平面圖的無圈邊染色，給出了無圈邊色數等于圖的最大度的兩個充分條件，并且給出了不含三角形或者不含四圈的平面圖的無圈邊色數的上界，其上界大大改進了已有結果。

在圖的譜理論研究中，主要開展了關于圖的代數連通度、與圖與超圖的劃分問題相關的譜方法等問題的研究工作。得到了圖的最大割新的有關無符號Laplace譜的較好上下界、具有完美匹配圖的代數連通度序等多項結果。

五、學術交流

本來校訪問并作合作研究的國內外著名學者10余人次，其中包括中科院院士、北京大學教授田剛，香港浸會大學教授朱力行，澳大利亞Newcastle大學林宇清等。

第三篇：2013年年報告-離散數學-福州大學

離散數學及其應用教育部重點實驗室工作總結報告（2014年1月28日）

實驗室名稱： 離散數學及其應用教育部重點實驗室 主管部門： 福建省教育廳 依托單位： 福州大學

實驗室概況: 在迅速發展的計算機科學技術及信息技術等領域，離散數學是重要的基礎學科和支撐學科，它的發展和應用是影響一個國家科學技術發展水平的重要因素。以福州大學“離散數學與理論計算機科學研究中心”為依托的離散數學及其應用教育部重點實驗室于2007年7月獲教育部批準立項建設。目前，實驗室共有固定研究人員27人，其中教授16人，副教授4人。實驗室由馬志明院士擔任學術委員會主任，范更華教授擔任實驗室主任。實驗室位于福州大學銅盤校區。2007年11月完成了實驗室裝修一期工程；2009年3月完成了二期裝修工程，達到 “環境優美、設備一流”。按國際研究所標準建設基礎設施，為每位研究人員及來訪學者提供40平米寬敞辦公室及一流科研設備。為每位研究生提供一個工作位及臺式電腦。已建成無線網覆蓋實驗室3000平米的科研、辦公場所。重視網絡建設，保證網絡高速暢通。訂購相關專業的國外數據庫及原版圖書，已基本建成一流的專業圖書資料室。

一、實驗室現有三個研究方向：圖論與組合數學、大規模集成電路設計中的數學方法、優化理論與算法。

二、本實驗室在研科研項目國家973計劃課題1項，國家自然科學基金13項，其中重點項目1項，面上項目4項，青年項目8項。教育部重點項目1項，高等學校博士學科點專項科研基金1項。新增國家自然科學基金4項，均為青年項目，分別是： 1.圖的完美匹配計數及其相關問題的研究（11301085），林峰根。2.變密度粘性流體動力學中非線性瑞利-泰勒不穩定性的數學理論研究（11301083），江飛。3.保持全局形狀和視覺舒適度的2D和3D媒體適應方法（61300102），牛玉貞。

4.不相交QoS路徑與斯坦納網絡的近似算法研究（61300025），郭龍坤。

實驗室成員于元隆博士獲福建省“閩江學者獎勵計劃”項目資助，郭文忠博士獲福建省自然科學基金杰青項目資助。

實驗室成員陳國龍教授和郭文忠博士主持的“內網安全監控平臺研制及其產業化”獲福建省科技進步二等獎，該項研究針對日益嚴重的內網安全問題，深入分析內網所面臨的各種安全威脅，從身份認證、網絡接入控制、數據保護、移動存儲設備監控以及網絡訪問監控等關鍵問題入手開展內網安全關鍵技術的創新開發，具體如下：(1)研發了基于USB 安全鎖、手掌靜脈識別、用戶名與密碼的統一身份認證平臺，采用多因子身份認證方式，解決內網用戶身份的合法性和真實性驗證問題。(2)研發了一種高安全性的內網安全綜合管理的網絡接入控制方案，通過內網安全綜合管理系統、統一身份認證平臺、802.1x 交換機和Radius 服務器之間的聯動實現對網絡接入終端的身份驗證和接入安全控制。(3)研發了一種基于微過濾器模型及內嵌加密標識的數據動態加解密技術的數據保護技術。(4)研發了基于新一代WFP 模型的網絡數據包監控和過濾引擎，設計了一種融合防病毒和入侵檢測功能的多功能綜合網關。

實驗室成員朱文興教授主持的“連續全局優化和非線性整數規劃的算法研究”獲福建省自然科學獎三等獎。

三、實驗室不僅是高水平科學研究中心，也是高層次人才培養基地。實驗室以應用數學、計算機應用技術省級重點學科，國家集成電路人才培養基地，離散數學“211工程”建設重點學科，應用數學博士點以及兩個一級學科碩士點（數學、計算機科學與技術）為支撐，形成具有一定規模的離散數學高層次人才培養體系。實驗室將充分利用自身的條件，圍繞主攻方向，提升開放層次，促進學術交流與合作，使實驗室整體研究水平達到國 內領先水平，某些研究方向達到國際先進水平，為國家及福建地方建設做出突出貢獻。本培養博士研究生3名，碩士研究生23名。

四、科研成果

實驗室在各個研究問題方面開展了深入地研究工作，在課題研究中取得了一些很好的研究結果。本課題組研究成員在國內外重要專業刊物上發表SCI收錄論文36篇，EI收錄4篇，主要研究成果如下：

（1）VLSI中的圖論與優化算法研究工作

1、設計并實現了超大規模集成電路混合單元布局問題的一個新的布局流程，主要思想是用版圖規劃算法指導電路單元的布局。該布局流程包含4個步驟：1）在多級框架下，利用遞歸劃分技術對電路單元聚類；2）對每層的模塊用版圖規劃算法布局；3）用局部移動技術確定宏單元的精確位置；4）當宏單元的位置確定后，用標準單元布局算法確定標準單元的具體位置。與當前最好的混合單元布局器相比，對IBM mixed-size benchmark circuits和modern mixed-size(MMS)placement benchmarks，我們的布局器在合理的計算時間內能得到最好的平均半周長線長。經過分析發現，我們的布局器的劃分和模塊形成階段（即聚類階段）占用了總的計算時間的2/5，所以劃分和模塊形成階段是我們的布局器的主要瓶頸，需要進一步研究。

2、由于圖劃分問題在布局問題中有直接的應用，我們研究賦權圖的最大二等分問題，該問題是NP困難問題。我們構造了該問題的一個memetic算法，其中包括一個快速的局部搜索過程，一個的交叉算子和種群修改策略。這些策略能在全局搜索和局部搜索之間取得平衡。利用文獻中的大量有800-10000個頂點的標準測試實例對我們所構造的算法進行測試，我們的算法能取得所測試例子的比當前最好結果更好的解。與著名的circut算法相比，我們的算法在割值方面的提高幅度在0.02% 到4.15%之間。從而實驗表明了我們的memetic算法可以在可接受的計算時間內獲得高質量的解。

3、研究了超大規模集成電路劃分問題的動態凸化算法。利用輔助函數，把集成電路劃分問題等價變換為有約束非線性整數規劃問題，并構造了動態凸化算法這一全局搜索算法。我們修改了集成電路劃分的FM算法，使適合我們的整數規劃問題。理論分析和實際計算表明，我們的算法可以成功跳出離散局部極小解。在ACM/SIGDA和ISPD98的測試實例集上的測試表明，我們的局部搜索算法得到的結果比FM算法優58%以上。為解決大規模集成電路劃分問題，我們把所構造的算法集成到多級劃分框架MLPart中，在同一測試實例集上的測試表明，算法所得到的結果比MLPart優3-7%。

4、劃分與超大規模集成電路緊密相關，我們研究了圖的max-k-cut問題，把該問題轉化為非線性整數規劃問題。改進了集成電路劃分的FM算法，構造了該問題的一個局部搜索算法。為跳出局部極大解，我們構造了一個輔助函數，理論分析和實驗表明，對該函數的局部搜索，可以找到更好的局部極大解。對k=2的情況，用大量的標準實例計算實驗表明，算法不僅可以求到當今其它基于局部搜索的算法不能找到的解，而且效率較優。對k≧2的情況，算法也是穩定的，且可以與國際上最新的算法比較。

5、研究了從超大規模集成電路全局布局中提取的非線性規劃問題，其目標函數是對半周長線長的基于L1范數的近似，是兩個凸函數的和，約束是密度函數約束，是一系列Lipschitz連續非凸函數構成的不等式。該問題對交替方向法來說是新問題，我們構造了基于臨近點的交替方向法，在適當條件下證明了算法收斂于問題的KKT點。在實現的時候，我們對臨近點參數采用自適應策略。把所構造的算法嵌入到NTUplacer中，用IBM的標準測試實例測試，對18個例子所獲得的半周長線長均比NTUplacer3的短，其中例子IBM01的要短3.21%，IBM08的要短6.97%。與其他的最新的布局工具相比，我們的算法在18個例子中多數占優勢。該算法的優點是計算效果好，但是算法的計算時間太長，需要在以后的研究中加以克服。

6、研究了超大規模集成電路標準單元布局問題的ell-1模優化模型。我們把半周長線長目標函數用ell-1模近似，把單元重疊函數用非光滑函數近似，然后用非光滑共軛次梯度法求解所得到的非光滑優化模型，進而構造了一個標準單元布局的多級框架。該框架包含聚類階段和解聚類階段。在聚類階段中，我們改進了best-choice電路聚 類算法，以實現電路的全局視圖。在解聚類階段中，用我們所構造的非光滑優化技術對全局布局問題逐級求解，其中對目標線長和密度約束需要做仔細的平衡。我們用IBM standard cell benchmark circuits 和 Peko suites的測試例子測試所構造的布局工具，初步實驗表明該工具能在合理的時間內獲得高質量的布局效果，而且在時間和解的質量上與當前主流的布局工具相比，有很大的優越性。

7、總體布線是超大規模集成電路物理設計中極為重要的一個環節。針對此問題，我們在研究中引入了非曼哈頓結構，繼而在非曼哈頓結構的基礎上開展了總體布線中布線樹的相關構造工作，包括：1）超大規模集成電路中繞障X結構Steiner樹問題已經被證明是一個NP完全問題，而且對于超大規模集成電路中的非曼哈頓結構布線問題有著非常重要的意義。本課題提出了一種有效的繞障X結構Steiner樹算法。研究成果發表在國際會議《IEEE ICNC2013》。本課題在繞障X結構Steiner樹的基礎上進一步考慮多層結構，基于粒子群優化方法提出了多層繞障X結構Steiner最小樹算法；2）超大規模集成電路中性能驅動非曼頓結構Steiner樹是VLSI布線中非常重要的布線樹模型。本課題設計一個基于多目標離散粒子群優化算法的性能驅動Steiner樹構造算法。

（2）圖論與組合研究工作

課題組開展了關于超圖的張量譜理論的研究工作，并對于圖與超圖的劃分問題相關的譜與張量譜方法等問題進行了系統研究，取得了多項有意義的結果。

1.著名的Erd?s–Sós猜想是說如果圖G的平均度大于k-1，則G存在k條邊的任意樹，對于該猜想的成果較少，研究方法較單一，我們對該猜想進行了深入研究，利用新的思路證明了如果圖G的平均度大于k-1，則G存在k條邊的任意蜘蛛，其中k≥(n+5)/2，其結果為研究Erd?s–Sós猜想提供了新的思路。

2.圖的無符號Laplace矩陣的研究是圖譜理論研究的重點問題，我們將圖的無符號Laplace矩陣推廣到無符號，從而研究一致超圖譜的性質，給出了超圖的無符號Laplace張量譜理論的一些基本性質，特別是，偶一致超圖無符號Laplace張量的最小和最大的 Z-特征值的研究，并研究了與這兩個Z-特征值有關的超圖的邊割和邊連通性。

3.給出了偶一致超圖無符號Laplace張量的H-特征值，并證明了H-特征值的一些基本性質，對取到最小和最大無符號Laplace張量的H-特征值的偶一致超圖進行了刻畫，同時，研究了H-特征值與一致超圖的割，最小度，最大度的關系。同時，利用最小和最大無符號Laplace張量的H-特征值給出了一致超圖邊割和邊連通度的上下界。

4.研究了平面圖的無圈邊染色問題，給出了平面圖無圈邊色數的上界，該上界改進了《SIAM J.Discrete Math.》上的結果。同時考慮了圍長為5的平面圖的無圈邊染色，給出了這類圖無圈邊色數的緊的上界，同時證明了，如果該類圖的最大度至少是4，則其無圈邊色數等于最大度，該結果改進了原有一系列結果。

五、學術交流

2013年5月，實驗室和福州大學數學與計算機學院，主辦了“圖與超圖譜理論國際研討會議”，本次國際學術會議是首次在國內召開的有關圖與超圖譜理論的專題研討會，會議主席為香港理工大學祁力群教授和廈門大學張福基教授，執行主席為福州大學常安教授。共有來自美國、荷蘭、澳大利亞、南非、中國香港地區和國內北京大學、清華大學、上海交通大學高校的60多位學者和博、碩士研究生參加了此次研討會議，其中包括北京大學張恭慶院士、美國威斯康辛大學Richard Brualdi教授（University of Wisconsin-Madison）、賓夕法尼亞州立大學Winnie Li教授（Pennsylvania State University）、荷蘭Tilburg 大學Willem Haemers教授（Tilburg University）、同濟大學邵嘉裕教授等多位國內外知名學者。福州大學副校長、離散數學及其應用教育部重點實驗室主任范更華教授在會議開幕式上代表福州大學致辭歡迎并介紹了福州大學概況。

在為期4天的研討會期間，共有31位與會國內外學者做了圖與超圖譜理論研究領域最新研究成果的學術報告，包括20個40分鐘會 6 議邀請報告：11個20分鐘會議報告。這些報告內容涉及圖的譜理論、張量譜理論、超圖的張量表示及其譜理論，以及與圖與超圖譜理論相關的應用問題研究等。另外，會議在5月30日下午專門安排了半天的3個專題報告，由香港理工大學祁力群教授等系統介紹了關于張量特征值理論和超圖張量特征值問題的基礎知識和研究進展情況。本次會議為圖與超圖譜理論研究領域的國內外專家學者開展學術交流和合作研究提供了一次難得機會，與會者一致認為這是一次高水平的學術研討會，會議報告和講座體現和代表了國內外相關研究的先進水平和本領域國內外研究現狀和趨勢，將對于國內相關研究領域的科學研究和發展起到積極的促進作用，并有助于開拓與會研究生的視野和研究水平的提高，促進青年研究人才的培養。本次會議得到了教育部高校數學中心資助！

2013年12月，實驗室主辦了“2013 International Conference on Cloud Computing and Big Data(CloudCom-Asia)”國際學術研討會，共有100多位學者和博、碩士研究生參加了此次研討會議。2013年3月，實驗室聯合國家自然科學基金委，召開了數學天元基金“問題驅動的應用數學研究”研討會，5月，在實驗室召開了973計劃項目“信息及相關領域重大需求的應用數學研究”交流會。在本，共有10余位國內外知名學者到校訪問，并作報告和進行合作研究，其中包含美國伊利諾伊大學教授Douglas West，美國喬治亞理工大學教授郁星星，美國喬治亞州立大學教授陳冠濤，山東大學教授吳建良等。

第四篇：離散數學及其應用教育部重點試驗室工作總結報告-福州大學

離散數學及其應用教育部重點實驗室工作總結報告

（2011年3月18日）

實驗室名稱： 離散數學及其應用教育部重點實驗室 主管部門： 福建省教育廳 依托單位： 福州大學

實驗室概況: 在迅速發展的計算機科學技術及信息技術等領域，離散數學是重要的基礎學科和支撐學科，它的發展和應用是影響一個國家科學技術發展水平的重要因素。以福州大學“離散數學與理論計算機科學研究中心”為依托的離散數學及其應用教育部重點實驗室于2007年7月獲教育部批準立項建設。目前，實驗室共有固定研究人員27人，其中教授16人，副教授4人。實驗室由馬志明院士擔任學術委員會主任，范更華教授擔任實驗室主任。實驗室位于福州大學銅盤校區。2007年11月完成了實驗室裝修一期工程；2009年3月完成了二期裝修工程，達到 “環境優美、設備一流”。按國際研究所標準建設基礎設施，為每位研究人員及來訪學者提供40平米寬敞辦公室及一流科研設備。為每位研究生提供一個工作位及臺式電腦。已建成無線網覆蓋實驗室3000平米的科研、辦公場所。重視網絡建設，保證網絡高速暢通。訂購相關專業的國外數據庫及原版圖書，已基本建成一流的專業圖書資料室。

一、實驗室現有三個研究方向：圖論與組合數學、大規模集成電路設計中的數學方法、優化理論與算法。

二、在本，實驗室主任范更華教授獲全國優秀科技工作者。實驗室在研科研項目國家973計劃課題1項，國家自然科學基金7項，其中重點項目1項，面上項目6項，新增國家973計劃課題1項，為

1.大規模集成電路物理設計中關鍵應用數學理論和方法（2011CB808003），范更華 新增國家自然科學基金3項，其中面上項目2項，青年項目1項，分別是：

1.超大規模集成電路多目標劃分的算法研究（61070020），朱文興，國家基金面上項目。

2.近景攝影測量中的自動圖像分割技術（11071270），王美清，國家基金面上項目。

3.幾類圖染色問題的研究（11001055），侯建鋒，國家基金青年項目。

實驗室在2010年8月順利完成了國家重點基礎研究發展計劃（973計劃）課題“大規模集成電路設計中的圖論與代數方法（2006CB805904）”。課題實施期間，課題組共發表研究論文133篇，其中被SCI收錄104篇；由于出色完成了該課題，我們將繼續承擔新一輪的973課題：大規模集成電路物理設計中關鍵應用數學理論和方法（2011年1月至2015年12月）。

三、實驗室不僅是高水平科學研究中心，也是高層次人才培養基地。實驗室以應用數學、計算機應用技術省級重點學科，國家集成電路人才培養基地，離散數學“211工程”建設重點學科，應用數學博士點以及兩個一級學科碩士點（數學、計算機科學與技術）為支撐，形成具有一定規模的離散數學高層次人才培養體系。實驗室將充分利用自身的條件，圍繞主攻方向，提升開放層次，促進學術交流與合作，使實驗室整體研究水平達到國內領先水平，某些研究方向達到國際先進水平，為國家及福建地方建設做出突出貢獻。本培養博士研究生2名，碩士研究生21名。

四、科研成果

實驗室在各個研究問題方面開展了深入地研究工作，在課題研究中取得了一些很好的研究結果。本課題組研究成員在國內外重要專業刊物上發表SCI收錄論文27篇，EI收錄論文6篇，具體研究成果如下：

（1）圖論與組合研究工作 關于連通圖支撐樹的計數問題，給出了連通圖支撐樹個數的緊的上界，并且考慮的連通度為k的圖的支撐樹的個數，同時給出了連通圖支撐樹的個數和圖色數之間的關系，其結果發表在《Applied Mathematics Letters》上。

一個圖的Laplacian譜半徑是指該圖Laplacian矩陣的最大特征值，對于圖n個頂點，最大度為△，直徑為D的非正則圖，Shi給出了該圖的Laplacian譜半徑的上界，我們改進了該上界，并且證明了該上界給出了在某些情況是緊的，同時，給出了不含三角形圖的Laplacian譜半徑的上界。對于連通二部圖，給出了Laplacian譜半徑緊的上界和下界，從而改進了Shi的結果。

在圖染色領域，考慮了圖的列表染色問題，給出了考慮圖列表染色的新的思路，并且用該思路證明了某些形式的完全k部圖是(2, 2)-total weight choosable，并證明了除了一條邊外的所有完全二部圖都是(1, 2)-total weight choosable。研究了稀疏圖和平面圖的列表全染色問題，證明了如果平面圖的最大度不超過8，則其列表全色數不超過11；如果平面圖最大度至少是8，且不含5-圈，則其列表全色數等于最大度加一；如果圖的最大度是4，并且最大平均度不超過3，則其列表全色數是5，該項成果發表在《Information Processing Letters》上。考慮了有向圖博弈染色，給出了有向圖博弈色數以及弱的博弈色數的定義，證明每個定向平面圖的博弈色數不超過9，每個定向外平面圖的博弈色數不超過4，同時研究了有向圖強博弈染色，證明了每個定向平面圖的強博弈色數不超過16。考慮的外平面圖的無圈邊染色問題，完全確定了外平面圖無圈邊色數的上界，其結果發表在《Journal of Graph Theory》上。在化學圖論方面，一個圖的能量是指該圖所有特征值絕對值的和，一個圖的能量小于圖的頂點數，稱該圖是hypoenergetic，我們研究了圖的能量，構造了頂點數為4n+2的樹T，使得T是hypoenergetic，從而驗證了Gutman等人在2008年提出的猜想，該文發表在《Applied Mathematics Letters》上。同時考慮的圖的能量和Estrada指標之間的關系，給出了圖Estrada指標緊的上界。（2）VLSI中的圖論與優化算法研究工作

為了開展大規模集成電路設計領域的研究工作，實驗室于2010年建立了一個150m2的大規模集成電路設計EDA實驗室，擁有16個研究工作位，裝備國產熊貓EDA系統軟件16臺套，對所有實驗室研究成員和研究生開放使用。

布局是大規模集成電路電路設計重要環節，決定了超大規模集成電路芯片的性能，尺寸，產量和可靠性，我們給出了基于粒子群優化算法新的智能決策，利用該決策可以超大規模集成電路較快的獲得一個可行的電路物理布局。同時在遺傳算法的變異和交叉的原則中引入了粒子群優化算法，可以使得該算法脫離局部最優和實現更好的多樣性。實驗通過采用MCNC和GSRC基準測試表明，該算法是有效的。同時該算法可以避免局部最小，并有很好的收斂性。實驗結果表明所提出的方法可以大大幫助集成電路設計中的布局決策，其結果發表在《Soft Comput.》上。

從計算的角度來看，超大規模集成電路布局規劃是一個NP-困難問題。我們給出了非分層和模塊VLSI布圖規劃問題的一個混合演化算法（HGA），該算法使用一個有效的遺傳搜索方法來探索搜索空間和一種有效的局部搜索方法，利用信息在搜索區域。MCNC基準的實驗結果表明該算法是有效的。同時，借助于進化算法和模擬退火算法的概念，給出了另外一種混合演化算法，實驗表明該算法也是有效的。

（3）優化理論與算法

我們提出了一個高效求解三維裝箱問題（Three Dimensional Container Loading Problem 3D-CLP）的混合模擬退火算法；研究了極大可滿足性問題的局部搜索算法，提出了用單純形法產生“初始概率”(每個變量取1的概率)，用“初始概率”對局部搜索算法中變量的初始隨機指派進行適當的約束；研究了箱約束非線性整數規劃問題，提出了該問題的離散動態凸化算法，同時還證明了算法的收斂性；對非線性約束連續全局優化問題，我們構造一個結合罰函數的輔助函數，構造了解非線性約束連續全局優化的一個動態凸化算法，該算法避免了傳統罰函數法中罰參數選取困難的問題。

五、學術交流

為推動福建省數學教育和研究活動開展，在范更華教授的大力倡導下，協同福建省數學會，于2010年10月16日至17日召開福建省首屆數學大會，1100多名來自全省各地高校和中學的數學教師參會。為了使基層農村學校數學教師有機會參加會議，在省政府、省教育廳等部門的大力支持下，會議為300名工作在鄉鎮學校的教師提供了交通、住宿等經費支持。會議期間，“院士與中學教師互動座談會”和“專家講座”等專項活動交流和討論熱烈，這種面對面的交流讓來自中小學的數學教師受益匪淺、耳目一新，為廣大基層學校特別是農村學校教師提供了良好的學習機會，有效地調動了全省中學教師參與數學研究的積極性，對提升福建省數學教育水平起到了積極的推動作用。

2010年5月，實驗室協同中國運籌學會，召開中國運籌學會第八屆三次常務理事會。

在本，共有10余位國內外知名學者到校訪問，并作報告和進行合作研究，其中包含千人計劃入選者，浙江師范大學教授朱緒鼎，香港浸會大學數學系主任朱力行，加拿大Simon Fraser大學教授Pavol Hell等。

第五篇：離散數學

離散數學課件作業

第一部分 集合論

第一章集合的基本概念和運算

1-1 設集合 A ={1，{2}，a，4，3}，下面命題為真是[ B ]

A．2 ∈A；B．1 ∈ A；C．5 ∈A；D．{2} ? A。

1-2 A,B,C 為任意集合，則他們的共同子集是[ D ]

A．C；B．A；C．B；D．?。

1-3 設 S = {N，Z，Q，R}，判斷下列命題是否成立 ？

（1）N ? Q，Q ∈S，則 N ? S［不成立］

（2）-1 ∈Z，Z ∈S，則-1 ∈S［不成立］

1-4 設集合 A ={3，4}，B = {4，3} ∩ ?，C = {4，3} ∩{ ? }，D ={ 3，4，? }，2E = {x│x ∈R 并且 x-7x + 12 = 0}，F = { 4，?，3，3}，試問哪兩個集合之間可用等號表示 ？

答：A = E；B = C；D = F

1-5 用列元法表示下列集合（1）A = { x│x ∈N 且 x2 ≤ 9 }

（2）A = { x│x ∈N 且 3－x 〈 3 }

答：（1）A = { 0，1，2，3 }；

（2）A = { 1，2，3，4，……} = Z+；

第二章二元關系

2-1 給定 X =（3, 2，1），R 是 X 上的二元關系，其表達式如下：

R = {〈x，y〉x，y ∈X 且 x≤ y }

求：(1)domR =?;(2)ranR =?;(3)R 的性質。

答：R = {<2，3>，<1,2>，<1,3>}；

DomR={R中所有有序對的x}={2,1,1}={2,1};

RanR={R中所有有序對的y}={3,2,3}={3,2}；

R 的性質:反自反,反對稱,傳遞性質.2-2 設 R 是正整數集合上的關系，由方程 x + 3y = 12 決定，即

R = {〈x，y〉│x，y∈Z+ 且 x + 3y= 12}，試求：

（1）R 的列元表達式；（2）給出 dom（R。R）。

答：根據方程式有：y=4-x/3，x 只能取 3，6,9。

（1）R = {〈3，3〉,〈6，2〉,〈9，1〉}；

至于(2),望大家認真完成合成運算 R。R={<3,3>}.然后,給出 R。R 的定義域,即

（2）dom（R。R）= {3}。

2-3 判斷下列映射 f 是否是 A 到 B 的函數；并對其中的 f：A→B 指出他的性質，即

是否單射、滿射和雙射，并說明為什么。

（1）A = {1，2，3}，B = {4，5}，f = {〈1，4〉〈2，4〉〈3，5〉}。

（2）A = {1，2，3} = B，f = {〈1，1〉〈2，2〉〈3，3〉}。

（3）A = B = R，f=x。

（4）A = B = N，f=x2。

（5）A = B = N，f = x + 1。

答：（1）是 A 到 B 的函數，是滿射而不是單射；

（2）是雙射；

（3）是雙射；

（4）是單射，而不是滿射；

（5）是單射而不是滿射。

2-4 設 A ={1，2，3，4}，A 上的二元關系

R ={〈x，y〉︱（x-y）能被3整除}，則自然映射 g：A→A/R使 g(1)=[C]

A．｛1,2｝；B．｛1,3｝；C．｛1,4｝；D．｛1｝。

2-5 設 A ={1，2，3}，則商集A/IA =[D]

A．｛3｝；B．｛2｝；C．｛1｝；D．｛｛1｝，｛2｝，｛3｝｝。

2-6．設ｆ(x)＝x+1，ｇ(x)＝x-1 都是從實數集合Ｒ到Ｒ的函數，則ｆ。ｇ＝[C]

A．x+1；B．x-1；C．x；D．x2。

第三章 結構代數(群論初步)

3-1 給出集合及二元運算，闡述是否代數系統，何種代數系統 ？

（1）S1 = {1，1/4,1/3,1/2,2，3，4}，二元運算 *是普通乘法。

（2）S2 = {a1，a2，……，an}，ai ∈R，i = 1，2，……，n ；

二元運算。定義如下：對于所有 ai，aj ∈S2，都有 ai。aj = ai。

（3）S3 = {0，1}，二元運算 * 是普通乘法。

答：（1）二元運算*在S1上不封閉．所以，＂S1，*＂不能構成代數系統。

（2）由二元運算的定義不難知道。在 S2 內是封閉的，所以，〈S2。〉構成代數

系統；然后看該代數系統的類型：該代數系統只是半群。

（3）很明顯，〈{0，1}，*〉構成代數系統；滿足結合律，為半群；1是幺元，為獨異

點；而 0 為零元；結論：僅為獨異點，而不是群。

3-2 在自然數集合上，下列那種運算是可結合的［A］

A．x*y = max(x,y)；B．x*y = 2x+y ；

C．x*y = x2+y2 ；D．x*y =︱x-y︱..3-3 設 Z 為整數集合，在 Z 上定義二元運算。，對于所有 x，y ∈Z都有

x。y=x + y，試問〈Z。〉能否構成群，為什麼 ？

答：由題已知，集合Z滿足封閉性；二元運算滿足結合律，依此集合Z為半群；有幺元為 －5，為獨異點.假設代數系統的幺元是集合中的元素 e,則一個方程來自于二元運算定義, 即e。x= e + x，一個方程來自該特殊元素的定義的性質,即e。x = x.由此而來的兩個方程聯立結果就有: e+x=x 成立.削去 x,e=0 的結果不是就有了嗎!；每個元素都有逆.求每個元素的逆元素,也要解聯方程,如同求幺元一樣的道理；結論是：代數系統〈 Z。〉構成群。

第二部分圖論方法

第四章 圖

4-1 10 個頂點的簡單圖 G 中有 4 個奇度頂點，問 G 的補圖中有幾個偶數度頂點 ？ 答：因為10階完全圖的每個頂點的度數都是n-1=9――為奇數。這樣一來，一個無向簡單圖 G 的某頂點的度數是奇數，其補圖的相應頂點必偶數，因為一個偶數與一個奇數之和才是奇數．所以，Ｇ的補圖中應有 10-4＝6 個奇數度頂點。

4-2 是非判斷：無向圖G中有10條邊,4個3度頂點,其余頂點度數全是2,共有 8 個頂點.[是]

4-3 填空補缺：1條邊的圖 G 中，所有頂點的度數之和為[2]

第五章樹

5-1握手定理的應用（指無向樹）

（1）在一棵樹中有 7 片樹葉，3 個 3 度頂點，其余都是 4 度頂點，問有(有1個4度頂點)個？

（2）一棵樹有兩個 4 度頂點，3 個 3 度頂點，其余都是樹葉，問有(9個1度頂點)片？

5-2 一棵樹中有 i 個頂點的度數為 i（i=2，…k），其余頂點都是樹葉(即一度頂點)，問樹葉多少片？設有x片,則 x=

答：假設有 x 片樹葉，根據握手定理和樹的頂點與邊數的關系，有關于樹葉的方程，解方程得到樹葉數 x = Σi（i—2）i + 2，（i = 2，3，……k）。

5-3 求最優 2 元樹：用 Huffman 算法求帶權為 1，2，3，5，7，8 的最優 2 元樹 T。試問：（1）T 的權 W（T）？（2）樹高幾層 ？

答：用 Huffman 算法，以 1，2，3，5，7，8 為權，最優 2 元樹 T ；然后，計算并回答所求問題：（1）T 的權 W（T）= 61；（2）樹高幾層：4 層樹高。

5-4以下給出的符號串集合中，那些是前綴碼？將結果填入[]內.B1 = {0，10，110，1111}[是]B2 = {1，01，001，000}[是]B3 = {a，b，c，aa，ac，aba，abb，abc}[非]B4 = {1，11，101，001，0011}[非]

5-5(是非判斷題)11階無向連通圖G中17條邊，其任一棵生成樹 T 中必有6條樹枝 [非]

5-6(是非判斷題)二元正則樹有奇數個頂點。[是]

5-7 在某次通信中 a，b，c，d，e 出現的頻率分別為 5%;10%;20%;30%;35%.求傳輸他們的最佳前綴碼。

1、最優二元樹 T；2.每個字母的碼字；

答：每個字母出現頻率分別為：G、D、B、E、Y：14%，O：28%；(也可以不歸一,某符號

出現次數即為權，如右下圖).。100（近似）7.。563..4。282..2..2。..1..14141414111

1所以，得到編碼如下：G（000），D（001），B（100），E（101），Y（01），O（11）。

第三部分邏輯推理理論

第六章 命題邏輯

6-1 判斷下列語句是否命題，簡單命題或復合命題。

（1）2月 17 號新學期開始。[真命題]

（2）離散數學很重要。[真命題]

（3）離散數學難學嗎 ？[真命題]

（4）C 語言具有高級語言的簡潔性和匯編語言的靈活性。[復合命題]

（5）x + 5 大于 2。[真命題]

（6）今天沒有下雨，也沒有太陽，是陰天。[復合命題]

6-2 將下列命題符號化.（1）2 是偶素數。

（2）小李不是不聰明，而是不好學。

（3）明天考試英語或考數學。（兼容或）

（4）你明天不去上海，就去北京。（排斥或）

答：（1）符號化為： p ∧ q。

（2）符號化為：p ∧ ﹃q。

（3）符號化為：p ∨ q。

（4）符號化為：（﹃p ∧ q）∨（p ∧ ﹃q）。

6-3分別用等值演算法,真值表法,主析取范式法,判斷下列命題公式的類型.（1）﹃（p→q）∧ q；（2）（（p→q）∧ p）→q；（3）（p→q）∧ q。答：（1）0；

（2）Σ（0，1，2，3）；

（3）Σ（1，3）。

以下兩題(6-4;6-5)為選擇題,將正確者填入[]內.6-4 令 p：經一塹；q：長一智。命題’’只有經一塹，才能長一智’’符號化為[B]

A． p→q；B．q→p；C．p∧q；D．﹁q→﹁p

6-5 p：天氣好；q：我去游玩．命題 ”如果天氣好，則我去游玩” 符號化為［B］

A． p→q；B．q→p；C．p∧q；D．﹁q→p

6-6證明題:用不同方法(必須有構造證明法)判斷推理結果是否正確。

如果今天下雨，則明天不上體育課。今天下雨了。所以，明天沒有上體育課。答：將公式分成前提及結論。

前提：（p→﹃q），p；

結論：﹃q；

證明：（1）（p→﹃q）前提引入

（2）p前提引入

（3）（p→﹃q）∧p（1）（2）假言推理

（4）﹃q

要證明的結論與證明結果一致，所以推理正確。

第七章謂詞邏輯

7-1 在謂詞邏輯中用 0 元謂詞將下列命題符號化

（1）這臺機器不能用。

（2）如果 2 ＞ 3，則 2 ＞ 5。

答：（1）﹃F（a）。

（2）L（a，b）→ H（a，z）。

7-2 填空補缺題：設域為整數集合Ｚ，命題?x?y彐z（x-y=z）的真值為（0）

7-3在謂詞邏輯中將下列命題符號化

（1）有的馬比所有的牛跑得慢。

（2）人固有一死。

答：（1）符號化為：彐x（F（x）∧ 彐y（G（y）∧ H（x，y）））。

（2）與（1）相仿，要注意量詞、聯結詞間的搭配：

x（F（x）→y（G（y）→ H（x，y）））。

《附錄》習題符號集

? 空集, ∪ 并, ∩ 交,⊕ 對稱差,～ 絕對補,∑ 累加或主析取范式表達式縮寫 , － 普通減法, ÷ 普通除法, ㏑ 自然對數, ㏒ 對數，﹃ 非，?量詞 ”所有”，”每個”，∨ 析取聯結詞，∧ 合取聯結詞，彐 量詞”存在”，”有的”。

2010年8月12號。