第一篇：2013年年報告-離散數(shù)學-福州大學

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

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

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

一、實驗室現(xiàn)有三個研究方向：圖論與組合數(shù)學、大規(guī)模集成電路設計中的數(shù)學方法、優(yōu)化理論與算法。

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

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

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

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

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

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

四、年度科研成果

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

（1）VLSI中的圖論與優(yōu)化算法研究工作

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

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

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

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

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

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

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

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

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

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

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

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

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

五、學術(shù)交流

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

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

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

第二篇：2012年報告-離散數(shù)學-福州大學

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

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

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

一、實驗室現(xiàn)有三個研究方向：圖論與組合數(shù)學、大規(guī)模集成電路設計中的數(shù)學方法、優(yōu)化理論與算法。

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

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

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

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

2.無線傳感器網(wǎng)絡中任務調(diào)度的并行聯(lián)盟生成與博弈分配策略（61103175），郭文忠

3.圖的拉普拉斯譜及相關(guān)拓撲指標（11101087），劉劍萍 4.不含某些子式的擬陣結(jié)構(gòu)（11201076），陳容

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

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

四、科研成果

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

（1）VLSI中的圖論與優(yōu)化算法研究工作

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

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

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

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

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

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

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

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

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

五、學術(shù)交流

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

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

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

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

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

第三篇：2011年報告-離散數(shù)學-福州大學

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

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

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

一、實驗室現(xiàn)有三個研究方向：圖論與組合數(shù)學、大規(guī)模集成電路設計中的數(shù)學方法、優(yōu)化理論與算法。

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

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

新增教育部重點項目1項：動態(tài)拓撲下WSN任務調(diào)度中多目標優(yōu)化問題的算法研究，郭文忠。

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

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

四、科研成果

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

（1）VLSI中的圖論與優(yōu)化算法研究工作

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

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

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

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

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

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

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

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

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

五、學術(shù)交流

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

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

離散數(shù)學及其應用教育部重點實驗室工作總結(jié)報告

（2011年3月18日）

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

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

一、實驗室現(xiàn)有三個研究方向：圖論與組合數(shù)學、大規(guī)模集成電路設計中的數(shù)學方法、優(yōu)化理論與算法。

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

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

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

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

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

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

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

四、科研成果

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

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

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

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

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

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

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

（3）優(yōu)化理論與算法

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

五、學術(shù)交流

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

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

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

第五篇：離散數(shù)學

離散數(shù)學課件作業(yè)

第一部分 集合論

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

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(xiàn) = { 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+；

第二章二元關(guān)系

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

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

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

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

DomR={R中所有有序?qū)Φ膞}={2,1,1}={2,1};

RanR={R中所有有序?qū)Φ膟}={3,2,3}={3,2}；

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

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

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

答：根據(jù)方程式有：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 的函數(shù)；并對其中的 f：A→B 指出他的性質(zhì)，即

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

（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 的函數(shù)，是滿射而不是單射；

（2）是雙射；

（3）是雙射；

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

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

2-4 設 A ={1，2，3，4}，A 上的二元關(guān)系

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 都是從實數(shù)集合Ｒ到Ｒ的函數(shù)，則ｆ。ｇ＝[C]

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

第三章 結(jié)構(gòu)代數(shù)(群論初步)

3-1 給出集合及二元運算，闡述是否代數(shù)系統(tǒng)，何種代數(shù)系統(tǒng) ？

（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，*＂不能構(gòu)成代數(shù)系統(tǒng)。

（2）由二元運算的定義不難知道。在 S2 內(nèi)是封閉的，所以，〈S2?！禈?gòu)成代數(shù)

系統(tǒng)；然后看該代數(shù)系統(tǒng)的類型：該代數(shù)系統(tǒng)只是半群。

（3）很明顯，〈{0，1}，*〉構(gòu)成代數(shù)系統(tǒng)；滿足結(jié)合律，為半群；1是幺元，為獨異

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

3-2 在自然數(shù)集合上，下列那種運算是可結(jié)合的［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 為整數(shù)集合，在 Z 上定義二元運算。，對于所有 x，y ∈Z都有

x。y=x + y，試問〈Z?！的芊駱?gòu)成群，為什麼 ？

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

第二部分圖論方法

第四章 圖

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

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

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

第五章樹

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

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

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

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

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

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

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

5-4以下給出的符號串集合中，那些是前綴碼？將結(jié)果填入[]內(nèi).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(是非判斷題)二元正則樹有奇數(shù)個頂點。[是]

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

1、最優(yōu)二元樹 T；2.每個字母的碼字；

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

出現(xiàn)次數(shù)即為權(quán)，如右下圖).。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）離散數(shù)學很重要。[真命題]

（3）離散數(shù)學難學嗎 ？[真命題]

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

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

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

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

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

（3）明天考試英語或考數(shù)學。（兼容或）

（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)為選擇題,將正確者填入[]內(nèi).6-4 令 p：經(jīng)一塹；q：長一智。命題’’只有經(jīng)一塹，才能長一智’’符號化為[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證明題:用不同方法(必須有構(gòu)造證明法)判斷推理結(jié)果是否正確。

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

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

結(jié)論：﹃q；

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

（2）p前提引入

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

（4）﹃q

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

第七章謂詞邏輯

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

（1）這臺機器不能用。

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

答：（1）﹃F（a）。

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

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

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

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

（2）人固有一死。

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

（2）與（1）相仿，要注意量詞、聯(lián)結(jié)詞間的搭配：

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

《附錄》習題符號集

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

2010年8月12號。