前言:一篇好文章的誕生,需要你不斷地搜集資料、整理思路,本站小編為你收集了豐富的貪婪算法的基本原理主題范文,僅供參考,歡迎閱讀并收藏。
關(guān)鍵詞:網(wǎng)絡(luò)編碼; 構(gòu)造算法; 多項(xiàng)式時(shí)間算法; 隨機(jī)網(wǎng)絡(luò)編碼
中圖分類號(hào):TN915-34文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1004-373X(2011)19-0011-04
Research on Construction Algorithm of Network Coding
CHEN Hai-yong1, ZHU Shi-bing2, LI Chang-qing3
(1.Department of Postgraduate, Institute of Command & Technology of Equipment, Beijing 101416, China;
2. Department of Training, Institute of Command & Technology of Equipment, Beijing 101416, China;
3.Department of The Informational Equipment, Institute of Command & Technology of Equipment, Beijing 101416, China)
Abstract: Network coding is an important breakthrough of the information transmission technology in communication network, whose main idea is using the intelligentized function of router and encoding the transmit information by the intermediate node of network to improve the efficiency of network transmission. An example about "papilionaceous net" is proposed to analyze the basic theory of network coding, the basic construction algorithm, advantages and shortages of network coding are summarized, and the further development direction of this algorithm is discussed.
Keywords: network coding; construction algorithm; multinomial time algorithm; random network coding
收稿日期:2011-04-11
0 引 言
在傳統(tǒng)的通信網(wǎng)絡(luò)及信息傳輸過程中,中間節(jié)點(diǎn)都只是完成簡(jiǎn)單的存儲(chǔ)轉(zhuǎn)發(fā)功能。2000年,R Ahlswede等人在IEEE Transactions on Information Theory上發(fā)表了論文《Network Information Flow》,第一次提出了“網(wǎng)絡(luò)編碼”這一概念,論文證明了在單信源組播網(wǎng)絡(luò)中,使用網(wǎng)絡(luò)編碼可以達(dá)到信息傳輸?shù)淖畲罅鹘?,并通過蝴蝶網(wǎng)絡(luò)的例子說明傳統(tǒng)路由無法實(shí)現(xiàn)最高的傳輸效率[1]。這篇文章是網(wǎng)絡(luò)編碼理論發(fā)展的開端。
網(wǎng)絡(luò)編碼是一種基于網(wǎng)絡(luò)層的編碼技術(shù),核心思想就是盡量利用路由器的智能化功能,將傳統(tǒng)的路由器中對(duì)數(shù)據(jù)包先接收再轉(zhuǎn)發(fā)的處理模式提升到允許對(duì)接收到的數(shù)據(jù)包進(jìn)行組合、編碼等一系列的智能化處理,然后再轉(zhuǎn)發(fā)出去[2]。
1 網(wǎng)絡(luò)編碼的基本原理
在研究網(wǎng)絡(luò)編碼的過程中,為了能夠給大家一個(gè)直觀的印象,能夠更深入地了解網(wǎng)絡(luò)編碼的概念,下面將通過著名的“蝶形網(wǎng)絡(luò)”進(jìn)行分析。假定有一個(gè)(如圖1所示)通信網(wǎng)絡(luò),它擁有單個(gè)信源和2個(gè)接收節(jié)點(diǎn),假設(shè)每條鏈路都無時(shí)延和無差錯(cuò),且信道容量為1,即單位時(shí)間內(nèi)可以傳輸一個(gè)單位信息量(例如1 b)。圖中,S是信源節(jié)點(diǎn);Y和Z是信宿節(jié)點(diǎn);T,U,W,X是中間節(jié)點(diǎn)。源節(jié)點(diǎn)S要同時(shí)向兩個(gè)信宿節(jié)點(diǎn)Y和Z發(fā)送組播信息。根據(jù)圖論的“最大流最小割”定理,該多播的最大理論傳輸容量為2,即理論上信宿Y和Z能夠同時(shí)收到信源S發(fā)出的2個(gè)單位的信息,也就是說能同時(shí)收到b1和b2。
圖1 “單信源二信宿”蝴蝶網(wǎng)絡(luò)如果是傳統(tǒng)的信息傳輸方式,如圖1(a)所示,鏈路STTY和STTWWXXZ傳送b1,鏈路SUUZ,和SUUWWXXY傳送b2,信道容量為1的要求約束了鏈路WX,使得鏈路WX無法同時(shí)傳輸b1和b2。b1和b2傳輸?shù)焦?jié)點(diǎn)W時(shí),若WX傳輸b1,則b2需要等待b1傳輸完畢才能傳輸,所以在單位時(shí)間內(nèi),信宿Y獲得兩個(gè)b1,信宿Z獲得b1和b2,該方式不能夠?qū)崿F(xiàn)最大傳輸容量。如果應(yīng)用網(wǎng)絡(luò)編碼的思想,則如圖1(b)所示,令節(jié)點(diǎn)W為編碼節(jié)點(diǎn),b1和b2傳輸?shù)焦?jié)點(diǎn)W時(shí),W對(duì)接收到的b1和b2進(jìn)行編碼,壓縮傳輸信息流,從而,使得鏈路STTY和SUUZ分別給信宿Y和Z傳輸b1和b2,鏈路WXXY和WXXZ給信宿Y和Z傳輸b1b2,Y收到b1和b1b2后,通過譯碼操作b1(b1b2)就能解出b2,因此,信宿Y同時(shí)收到了b1和b2。同理,信宿Z也同時(shí)收到b1(通過譯碼操作b2(b1b2))和b2,由此,基于網(wǎng)絡(luò)編碼思想的傳輸方式能夠?qū)崿F(xiàn)理論上的最大傳輸容量。
在無環(huán)有向網(wǎng)絡(luò)中,只要存在鏈路瓶頸,就可以利用網(wǎng)絡(luò)編碼來提高其信息傳輸吞吐量。因此,在利用網(wǎng)絡(luò)編碼思想時(shí),應(yīng)該尋找鏈路瓶頸,選擇適宜的網(wǎng)絡(luò)編碼節(jié)點(diǎn),應(yīng)用相關(guān)的網(wǎng)絡(luò)編碼構(gòu)造算法,從而實(shí)現(xiàn)理論上網(wǎng)絡(luò)組播的最大傳輸容量。
2 網(wǎng)絡(luò)編碼構(gòu)造算法
為了便于理解,在介紹網(wǎng)絡(luò)編碼構(gòu)造算法之前,先給出以下兩個(gè)定義:
定義1:全局編碼向量
如圖2所示,設(shè)X=[x1,x2…,xn]為信源S輸出的n維信息流向量;Zj為第j條鏈路上傳輸?shù)男畔⒘飨蛄?Zj為第j條鏈路上傳輸信息流中關(guān)于信源輸出信息流向量的系數(shù),則Zj=ξjXT,則ξTj稱為第j條鏈路的全局編碼向量。
定義2:系統(tǒng)轉(zhuǎn)移矩陣
關(guān)鍵詞:overlap 模擬退火算法 自動(dòng)布局規(guī)劃
中圖分類號(hào):TP391 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1007-9416(2013)12-0129-03
1 引言
隨著半導(dǎo)體工藝的迅速發(fā)展,目前絕大部分芯片已經(jīng)采用32nm及以下工藝進(jìn)行設(shè)計(jì)。因此集成電路的集成度也越來越高,集成電路已經(jīng)進(jìn)入超大規(guī)模集成電路(Very Large Scale Integrated circuits)時(shí)代。 超大規(guī)模集成電路20世紀(jì)70年代后期出現(xiàn),其主要用于制造存儲(chǔ)器和微處理機(jī)。超大規(guī)模集成電路及其相關(guān)技術(shù)是現(xiàn)代電子信息技術(shù)迅猛發(fā)展的關(guān)鍵因素和核心技術(shù)。超大規(guī)模集成電路的研究水平已經(jīng)成為衡量一個(gè)國(guó)家技術(shù)和工業(yè)發(fā)展水平高低的重要標(biāo)志,也是世界工業(yè)國(guó)家競(jìng)爭(zhēng)最激烈的一個(gè)領(lǐng)域。在VLSI中其集成度一直遵循著“摩爾定律”,即以每18個(gè)月翻一番的速度急劇增加,目前一個(gè)芯片上集成的電路元件數(shù)早已遠(yuǎn)超數(shù)億個(gè)。如此迅速的發(fā)展,除了半導(dǎo)體工藝技術(shù)、設(shè)備、原材料等方面的不斷改進(jìn)之外,設(shè)計(jì)技術(shù)的革新也是重要原因之一。這一革新技術(shù)主要表現(xiàn)在全面采用了電子設(shè)計(jì)自動(dòng)化(Electronic Design Automation, EDA)技術(shù)。因?yàn)榧呻娐钒l(fā)展到現(xiàn)在已經(jīng)十分復(fù)雜,要在幾十平方毫米上硅片上完成線條只有零點(diǎn)幾微米的數(shù)以億計(jì)門器件的整個(gè)電子系統(tǒng)設(shè)計(jì),依靠手工設(shè)計(jì)是完全不可能的,必須借助電子設(shè)計(jì)自動(dòng)化技術(shù)和工具集成電路的發(fā)展對(duì)EDA技術(shù)不斷提出新的要求,以滿足日益提高的設(shè)計(jì)需求;相應(yīng)地,EDA技術(shù)的發(fā)展又使得集成電路設(shè)計(jì)向著更廣(產(chǎn)品種類越來越多)、更快(設(shè)計(jì)周期越來越短)、更準(zhǔn)(一次成功率越來越高)、更精(設(shè)計(jì)尺寸越來越?。?、更強(qiáng)(工藝適應(yīng)性和設(shè)計(jì)自動(dòng)化程度越來越強(qiáng))的方向發(fā)展一個(gè)典型的集成電路設(shè)計(jì)流程,幾乎在其中的每個(gè)設(shè)計(jì)環(huán)節(jié)和整個(gè)設(shè)計(jì)過程都普遍用到CAD技術(shù)和工具。其中,版圖規(guī)劃是一個(gè)極其重要的設(shè)計(jì)環(huán)節(jié),也是最費(fèi)時(shí)的,并且版圖的優(yōu)劣決定了最終芯片的性能。該階段的設(shè)計(jì)任務(wù)是根據(jù)邏輯和電路功能要求以及工藝制造的約束條件(如線寬、線寬距等),完成電路中單元的擺放和互連,最終形成設(shè)計(jì)的掩膜圖。在版圖規(guī)劃中布圖設(shè)置是很重要的一環(huán)。布圖規(guī)劃算法完成的任務(wù)是在滿足各項(xiàng)電學(xué)和工藝要求的條件下,在給定區(qū)域內(nèi)(或盡可能小的區(qū)域內(nèi))互不重疊地安置電路中的所有單元,并且盡可能好地滿足單元互連的要求。超大規(guī)模集成電路的布局規(guī)劃作為物理設(shè)計(jì)階段的重要組成部分近年來受到了廣泛關(guān)注,其質(zhì)量直接影響后續(xù)布線工作的順利完成,乃至最終影響到電路的性能,隨著布局設(shè)計(jì)過程中各種新問題的不斷引入,布局規(guī)劃問題較原先更加復(fù)雜,也越來越難以解決。
2 目前現(xiàn)狀
2.1 布局算法的提出
自動(dòng)化版圖設(shè)計(jì)實(shí)際是在有限的區(qū)域內(nèi),尋找出一個(gè)最優(yōu)的擺放結(jié)果,不僅能夠把所有的單元全部放入其中,并且為后續(xù)的布局布線提供最優(yōu)的結(jié)果,使最終的芯片得到最好的性能。其對(duì)應(yīng)的數(shù)學(xué)問題為對(duì)合法構(gòu)形空間的搜索問題。VLSI物理設(shè)計(jì)中的布局、布線等問題是高度復(fù)雜的,且其中很多問題已被證明為NP-Hard問題。NP就是Non-deterministic Polynomial的問題,也即是多項(xiàng)式復(fù)雜程度的非確定性問題。而如果任何一個(gè)NP問題都能通過一個(gè)多項(xiàng)式時(shí)間算法轉(zhuǎn)換為某個(gè)NP問題,那么這個(gè)NP問題就稱為NP完全問題(Non-deterministic Polynomial complete problem)。經(jīng)過前人的研究,布圖規(guī)劃已經(jīng)被證明為是NP完全問題的數(shù)學(xué)模型。所以,布圖規(guī)劃是一個(gè)值得深入的課題。隨著VLSI向深亞微米納米不斷推進(jìn),系統(tǒng)規(guī)模不斷擴(kuò)大,系統(tǒng)目標(biāo)的多樣化,問題空間維數(shù)隨之劇增。傳統(tǒng)的優(yōu)化算法要么面臨計(jì)算量爆炸(如窮舉法、線性規(guī)劃等),要么易陷入局部極值,無法接近全局最優(yōu)解(如貪心算法等)。因此對(duì)各種新的智能優(yōu)化方法的研究應(yīng)運(yùn)而起,先后提出了遺傳算法、模擬退火法[11]等算法。各種方法各有千秋,但到目前為止,還沒有任何一種方法可以有效地應(yīng)用于解決VLSI物理設(shè)計(jì)中的所有問題。
對(duì)于布局規(guī)劃中,特別是自動(dòng)布局規(guī)劃(master plan),通過對(duì)比相關(guān)算法,采用模擬退火算法。使用模擬退火算法我們可以較快的得出全局最優(yōu)解。在用模擬退火算法反復(fù)迭代找出最優(yōu)解時(shí),會(huì)出現(xiàn)一些不可避免的重疊(overlap),這個(gè)時(shí)候我們要盡可能的消除它們,同時(shí)還要考慮模塊間的距離(wirelength)以及通過的總線長(zhǎng)(timing path)。模塊間中心距離是我們布局最主要的約束條件,理論上我們要使它盡可能的小。因?yàn)樵谝粔K小小的集成電路板塊中可能會(huì)有千萬個(gè)單元(stand cell),它們組成了各個(gè)模塊(module),為此,布局開始階段模塊在起始的溫度下自由排列,隨著溫度的下降,當(dāng)找到不錯(cuò)的排列組合時(shí)存檔,繼續(xù)尋找,直到達(dá)到最優(yōu)解。模擬退火算法的基本原理是:跳出局部最優(yōu),亦稱爬山解((up-hill)當(dāng)滿足一定的條件時(shí)以收斂到全局最優(yōu)。算法可以看成是隨機(jī)和貪婪算法的結(jié)合。當(dāng)然模擬退火有著堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ),其對(duì)新解的接受概率是min{1,e-C/T},其中C為代價(jià)函數(shù)的差,T為當(dāng)前溫度。開始當(dāng)溫度較高時(shí),接受壞解的概率近似等于1,無論解的質(zhì)量是好是壞,一律接受,可以看成是隨機(jī)搜索。當(dāng)溫度足夠低時(shí),接受壞解的概率近似等于0,只接受好的解,可以近似的認(rèn)為是貪婪搜索。在溫度變化的過程中是一個(gè)從隨機(jī)到貪婪的漸變過程[12](圖1)。
3 算法的改進(jìn)
3.1 功能模塊設(shè)計(jì)
4 運(yùn)行結(jié)果與分析
對(duì)于以上改進(jìn)算法的實(shí)現(xiàn)進(jìn)行代碼編寫,并且在Linux操作系統(tǒng)開發(fā)環(huán)境下運(yùn)行encounter軟件,采用一組case進(jìn)行實(shí)現(xiàn),得到的結(jié)果如(圖3、4)。
通過對(duì)實(shí)驗(yàn)結(jié)果的分析可以看出,改進(jìn)后的算法是有效的,跟傳統(tǒng)的布局規(guī)劃相比布局線路wirelength優(yōu)化了17.5%,overlap降低了12.1%,達(dá)到了實(shí)驗(yàn)預(yù)期的效果。
5 結(jié)語
本文主要通過對(duì)自動(dòng)布局規(guī)劃設(shè)計(jì)分析,提出了改進(jìn)的模擬退火算法,并消除布局中不應(yīng)產(chǎn)生的overlap。該算法中采用了自頂向下的結(jié)群策略,實(shí)驗(yàn)表明,該算法比較穩(wěn)定,得出的結(jié)果好,適用性強(qiáng)。
參考文獻(xiàn)
[1]L.Jin,D.Kim,L.Mu,D.-S.Kim,and S.-M. Hu,“A sweepline algorithm for Euclidean Voronoi diagram of circules,”IEEE put.-Aided Des.,vol.38,no.3,pp. 260-272,Mar.2006.
[2]Y.Feng,D.P.Mehta,and H.Yang,“Constrained modern floorplanning,”in Proc.ISPD,2003,pp.128-135.
[3]J.-M.Lin and Y.-W.Chang,“TCG:A transitive closure graph base representation for general floorplans,”IEEE Trans.Very Large Scale Integr.,vol. 13, no. 4, pp. 288–292,Apr.2005.
[4]X.Hong,G. Huang,Y.Cai, J. Gu,S. Dong, C.-K. Cheng,and J. Gu,“Corner block list: An effective and efficient topological representation of non-slicing floorplan,” in Proc.ICCAD,2000,pp.8-12.
[5]S.Nakatake, M. Furuya, and Y. Kajitani, “Module placement on BSGstructure with pre-placed modules and rectilinear modules,” in Proc.ASP-DAC, 1998, pp. 571–576.
[6] Richard Auletta,Expert System Perimeter Block Placement Floorplanning,” date, p. 30140, Design,Automation and Test in Europe Conference and Exhibition Designers Forum (DATE’04),2004.
[7]Y.Zhan,Y. Feng, and S.Sapatnekar,“A fixed-die floorplanning algorithm using an analytical approach,”in Proc.ASP-DAC,2006, pp.771-776.
[8]Alupoaei,S.; Katkoori,S.Ant colony system application to macrocell overlap removal,Very Large Scale Integration (VLSI) Systems, IEEE Transactions,Vol.12, Iss.10,pp.1118- 1123,Oct.2004.
[9]S.N.Adya,I.L. Markov, Fixed-outline Floorplanning: Enabling Hierarchical Design, to appear in IEEE Trans.On VLSI,2003.
[10]W.Choi and K.Bazargan Hierarchical Global Floorplacement Using Simulated Annealing and Network Flow Area Migration,DATE 2003.
[11]楊依忠,解光軍.基于遺傳模擬退火算法的門陣列布局方法.計(jì)算機(jī)工程,2010,1.
[12]蔣中華.超大規(guī)模集成電路布圖布局算法及熱模型研究.2008.3.21.
[13]劉懷亮.模擬退火算法及其改進(jìn).廣州大學(xué)學(xué)報(bào)(自然科學(xué)版).2005,4(6):503-506.
目前國(guó)內(nèi)大多數(shù)研究集中在績(jī)效考核體系和指標(biāo)的確定,各類方法的綜合運(yùn)用(如KPI,模糊綜合評(píng)價(jià)法等),較少關(guān)注這些績(jī)效考核的實(shí)際可操作性和結(jié)果的運(yùn)用。由于績(jī)效考核本身就是一項(xiàng)非常復(fù)雜的工程,其數(shù)據(jù)涉及到公司諸多系統(tǒng),如人事系統(tǒng)、財(cái)務(wù)系統(tǒng)、生產(chǎn)指揮系統(tǒng),其考核所需數(shù)據(jù)也會(huì)來自不同系統(tǒng),以提高相關(guān)數(shù)據(jù)的準(zhǔn)確性,提升績(jī)效考核的公平公正,減輕績(jī)效考核人員的工作量。因此,如何在現(xiàn)有績(jī)效管理模式下,結(jié)合績(jī)效考核全過程,利用網(wǎng)絡(luò)技術(shù)構(gòu)建一個(gè)通用的、靈活的考核系統(tǒng)顯得非常重要,系統(tǒng)需整合公司各類數(shù)據(jù),完成績(jī)效考核全過程的網(wǎng)絡(luò)化管理和數(shù)據(jù)共享,使之成為企業(yè)管理的強(qiáng)有力手段之一,從而實(shí)現(xiàn)個(gè)人業(yè)績(jī)與企業(yè)整體戰(zhàn)略目標(biāo)的有效結(jié)合。
2績(jī)效考核總體設(shè)計(jì)
2.1績(jī)效考核流程
績(jī)效考核一般從發(fā)出績(jī)效考核通知(有些為周期性考核,雖無明確考核通知,但仍有固定開始時(shí)間和考核起止時(shí)間節(jié)點(diǎn))開始,再由各部門、各人員開始錄入相應(yīng)業(yè)績(jī)數(shù)據(jù),完成自評(píng)、他評(píng)等工作,在部門對(duì)原始錄入數(shù)據(jù)審核后,再由考核小組對(duì)數(shù)據(jù)進(jìn)行核實(shí),并公布績(jī)效考核結(jié)果。詳細(xì)流程見圖1所示。
2.2系統(tǒng)技術(shù)構(gòu)架
隨著油田信息化的發(fā)展,油田生產(chǎn)指揮系統(tǒng)、財(cái)務(wù)系統(tǒng)、人事系統(tǒng)等都已建立,如何將這些信息共享,提取以便績(jī)效考核系統(tǒng)實(shí)現(xiàn)數(shù)據(jù)共享是員工績(jī)效考核系統(tǒng)設(shè)計(jì)之初首先需要考慮到的。績(jī)效考核系統(tǒng)采用多層體系設(shè)計(jì)、利用B/S模式開發(fā),基于技術(shù),以SQLServer為數(shù)據(jù)庫(kù)支撐,面向服務(wù)構(gòu)架(SOA)等來進(jìn)行綜合平臺(tái)的構(gòu)架和數(shù)據(jù)集成。在數(shù)據(jù)引入和共享時(shí),提供WebServices技術(shù)對(duì)核心業(yè)務(wù)封裝成可對(duì)外開放、遠(yuǎn)程訪問的服務(wù),實(shí)現(xiàn)不同系統(tǒng)間數(shù)據(jù)交換與共享???jī)效考核系統(tǒng)主要分為應(yīng)用層、資源層、基礎(chǔ)平臺(tái)層,其技術(shù)構(gòu)架圖。
1)應(yīng)用層
承擔(dān)不同部門和用戶與考核系統(tǒng)的交互操作,為用戶提供業(yè)務(wù)處理和信息交互的操作界面。為提高用戶體驗(yàn),構(gòu)建可拓展的服務(wù)平臺(tái),前臺(tái)頁面采用Ajax技術(shù)開發(fā),在考核數(shù)據(jù)錄入、校驗(yàn)時(shí),實(shí)行局部數(shù)據(jù)交換,無需頻繁刷新頁面,確保系統(tǒng)簡(jiǎn)潔易用。
2)資源層
基于數(shù)據(jù)倉(cāng)庫(kù)和數(shù)據(jù)挖掘技術(shù),在用戶操作后,系統(tǒng)自動(dòng)發(fā)出指令,獲取相關(guān)系統(tǒng)數(shù)據(jù)資源,如生產(chǎn)指揮系統(tǒng)中生產(chǎn)數(shù)據(jù),人事系統(tǒng)中部門、人員信息,并在生成考核數(shù)據(jù)后自動(dòng)將數(shù)據(jù)提供給財(cái)務(wù)系統(tǒng),以便為績(jī)效獎(jiǎng)勵(lì)的發(fā)放提供決策數(shù)據(jù)。績(jī)效考核中數(shù)據(jù)的交換和處理依賴資源層,以支撐績(jī)效考核系統(tǒng)的正常運(yùn)作。3)基礎(chǔ)平臺(tái)層:由于石油企業(yè)特點(diǎn),很多員工常年在外,為確???jī)效考核工作的順利有序進(jìn)行,系統(tǒng)提供了互聯(lián)網(wǎng)、無線網(wǎng)、短信等多方式的服務(wù),用戶可充分利用現(xiàn)有各種終端(計(jì)算機(jī)、平板、手機(jī))隨時(shí)隨地訪問系統(tǒng)。同時(shí),系統(tǒng)還會(huì)依據(jù)考核進(jìn)度在重要時(shí)間節(jié)點(diǎn)發(fā)送短信提醒用戶。
3系統(tǒng)分析與設(shè)計(jì)
系統(tǒng)采用模塊化開發(fā)思路,根據(jù)績(jī)效考核實(shí)際情況,將系統(tǒng)功能分為系統(tǒng)配置、用戶管理、指標(biāo)庫(kù)、要約配置、在線考核、統(tǒng)計(jì)分析等六大模塊。
1)系統(tǒng)配置
主要包括對(duì)考核系統(tǒng)周期、起止時(shí)間的設(shè)定,可以批量設(shè)置,如固定每月5號(hào)開始考核。非考核時(shí)間段,用戶只能錄入日常工作基礎(chǔ)數(shù)據(jù),以便考核時(shí)自動(dòng)匯總,防止遺忘;對(duì)考核歷史數(shù)據(jù)的歸檔以及共享設(shè)置。
2)用戶管理
主要提供公司二級(jí)單位、直屬單位的管理;公司員工個(gè)人信息,如賬號(hào)、密碼、聯(lián)系方式等維護(hù);用戶角色權(quán)限的管理與維護(hù),不同用戶訪問系統(tǒng)時(shí)只提供與其權(quán)限相關(guān)的界面和交互操作功能。
3)指標(biāo)庫(kù)
按照井下作業(yè)公司的特點(diǎn),針對(duì)不同類型的員工考核項(xiàng)目、考核內(nèi)容均有不同。這些指標(biāo)需要統(tǒng)一維護(hù)和管理,特別是涉及到量化指標(biāo)的配置。這類指標(biāo)按照考核項(xiàng)目進(jìn)行分類儲(chǔ)存和查閱,并提供模糊查詢功能。
4)要約配置
要約即每個(gè)考核周期內(nèi),針對(duì)被考核人選取的指標(biāo)和其設(shè)置的權(quán)重。為保持考核的延續(xù)性和可操作性,要約一般在年底或年前統(tǒng)一設(shè)定,考核期內(nèi)不會(huì)隨意修改。一般一類崗位一套要約,也可以根據(jù)不同人員選擇指標(biāo),設(shè)置不同的指標(biāo)組合,配以權(quán)重后,形成不同要約。在要約配置界面,如果某個(gè)人單項(xiàng)指標(biāo)需要多人考核,可以在后臺(tái)設(shè)置指定考核人,考核人可以是一人,也可以是多人。當(dāng)考核人是多人時(shí),需要配置這些考核人的權(quán)重,即單指標(biāo)下的考核人權(quán)重。
5)在線考核
在線考核是由多用戶對(duì)某人的要約進(jìn)行在線的定性和定量的考評(píng),根據(jù)要約的設(shè)定,某一位員工可能由一人(一般是主管領(lǐng)導(dǎo)),也可以由多人進(jìn)行考核。多人考核時(shí),所有考核人數(shù)據(jù)錄入后,由系統(tǒng)根據(jù)各自權(quán)重自動(dòng)計(jì)算最后得分。
6)統(tǒng)計(jì)分析
關(guān)鍵詞 計(jì)算生物學(xué);教學(xué)現(xiàn)狀;體會(huì)
AbstractThe status of undergraduate course about computational biology was introduced. The teaching experience was summarized from different teaching steps in computational biology education.Besides,the beneficial exploration was carried out to improve teachers’ performance and train interdisciplinary talents for bioinformatics to promote the teaching reform of compulational biology.
Key wordscomputational biology;teaching status;experience
計(jì)算生物學(xué)是指開發(fā)和應(yīng)用數(shù)據(jù)分析及理論的方法、數(shù)學(xué)建模和計(jì)算機(jī)仿真技術(shù),用于生物學(xué)研究的一門學(xué)科。計(jì)算生物學(xué)正在成為現(xiàn)代生物學(xué)研究的核心方法之一,它們的重要性和復(fù)雜性在當(dāng)前生物學(xué)數(shù)據(jù)量的不斷增長(zhǎng)中日益彰顯,要回答的問題越復(fù)雜就越顯得突出,使得計(jì)算生物學(xué)成為當(dāng)今生命科學(xué)最具活力的新興前沿學(xué)科之一。計(jì)算生物學(xué)是一門概念性學(xué)科,以生物信息學(xué)為基礎(chǔ),以計(jì)算為工具,解決生物學(xué)問題。與生物信息學(xué)的定義類似,只是側(cè)重點(diǎn)有所不同。計(jì)算生物學(xué)側(cè)重于計(jì)算,通過計(jì)算來解決問題,并使用計(jì)算技術(shù)對(duì)生物學(xué)問題進(jìn)行研究。生物信息學(xué)主要側(cè)重于對(duì)生物學(xué)中所得信息的采集、存貯、分析處理與可視化方面[1-2]。
運(yùn)用計(jì)算生物學(xué),科學(xué)家有望直接破譯在核酸序列中的遺傳語言規(guī)律,模擬生命體內(nèi)的信息流過程,從而認(rèn)識(shí)代謝、發(fā)育、進(jìn)化等一系列規(guī)律,最終為人類造福。目前,計(jì)算生物學(xué)在國(guó)內(nèi)外受到高度重視。在國(guó)內(nèi),我國(guó)國(guó)家自然科學(xué)基金委員會(huì)將計(jì)算生物學(xué)作為重點(diǎn)資助的研究方向之一。許多科學(xué)家敏銳地意識(shí)到生物信息學(xué)必將會(huì)在生物學(xué)中發(fā)揮重要的作用,而計(jì)算生物學(xué)作為生物信息學(xué)專業(yè)的主干課目前處于創(chuàng)立階段。
自從湖南農(nóng)業(yè)大學(xué)2005年開設(shè)生物信息專業(yè)以來,計(jì)算生物學(xué)一直是該專業(yè)學(xué)生的專業(yè)主干課程,經(jīng)過3年的理論與實(shí)踐教學(xué),筆者將發(fā)現(xiàn)的問題及獲得的經(jīng)驗(yàn)進(jìn)行初步總結(jié),以供商榷。
1教學(xué)現(xiàn)狀
(1)缺乏合格的生物信息學(xué)師資。教師隊(duì)伍的整體數(shù)量和質(zhì)量與我國(guó)生物信息學(xué)教育快速發(fā)展的規(guī)模極不相稱。湖南農(nóng)業(yè)大學(xué)由生物安全與科學(xué)技術(shù)學(xué)院的生物信息系專業(yè)開設(shè)了計(jì)算生物學(xué)這門課程,盡管從開設(shè)這門課程至今,一直由生物信息學(xué)教研室教學(xué)經(jīng)驗(yàn)最豐富、學(xué)術(shù)造詣高的教師主講,但目前教研組中只有一位生物信息學(xué)專業(yè)畢業(yè)的博士,大部分教師為理學(xué)或農(nóng)學(xué)專業(yè)的碩士或博士,不具備計(jì)算機(jī)及算法的良好基礎(chǔ)知識(shí),使該專業(yè)仍缺乏良好的學(xué)緣結(jié)構(gòu)。
(2)計(jì)算生物學(xué)教育與其他專業(yè)的合作還有待加強(qiáng)。盡管計(jì)算生物學(xué)是一門新興學(xué)科,但與其他專業(yè)之間存在不少聯(lián)系?,F(xiàn)階段的問題是不同專業(yè)學(xué)科的教師之間缺乏交流與合作,難以滿足計(jì)算生物學(xué)教學(xué)的需求。據(jù)不完全統(tǒng)計(jì),我國(guó)超過30個(gè)高校或科研機(jī)構(gòu)開設(shè)生物信息學(xué)專業(yè)課程。不同學(xué)校根據(jù)自身的情況,在開設(shè)計(jì)算生物學(xué)這門課時(shí),側(cè)重點(diǎn)都不一樣。如果由醫(yī)學(xué)院的教師授課,則側(cè)重點(diǎn)可能在致病基因的研究方面,計(jì)算機(jī)專業(yè)教師授課則可能側(cè)重于數(shù)據(jù)庫(kù)的構(gòu)建、查詢等方面,理學(xué)院的教師授課則可能側(cè)重于生物信息學(xué)中的數(shù)學(xué)問題。計(jì)算生物學(xué)側(cè)重于算法,從而利用計(jì)算技術(shù)對(duì)生物學(xué)問題進(jìn)行研究。因此,各相關(guān)專業(yè)的教師需要加強(qiáng)這方面交流與學(xué)習(xí)[3]。
(3)在教學(xué)方法上,重視系統(tǒng)知識(shí)的傳授和授課計(jì)劃的完成,忽視學(xué)生能力和素質(zhì)的培養(yǎng)。此外,缺乏理論教學(xué)與實(shí)驗(yàn)教學(xué)的有機(jī)整合,實(shí)驗(yàn)教學(xué)只是以驗(yàn)證理論為目的,內(nèi)容單一,無創(chuàng)新點(diǎn),忽視對(duì)學(xué)生實(shí)際操作能力的培養(yǎng)。
(4)教學(xué)中還缺乏適合的理論和實(shí)驗(yàn)教材。授權(quán)影印國(guó)外原版教科和翻譯書籍仍占主導(dǎo)地位,而國(guó)人自編的教材寥寥無幾。此外,系統(tǒng)性不強(qiáng)也是目前計(jì)算生物學(xué)教材中普遍存在的一個(gè)問題。
2教學(xué)經(jīng)驗(yàn)及心得體會(huì)
(1)規(guī)范計(jì)算生物學(xué)教學(xué)大綱和計(jì)劃是開好本課程的前提。根據(jù)前2年的實(shí)驗(yàn)開展情況和該專業(yè)人才培養(yǎng)定位,制定了詳細(xì)的理論和實(shí)驗(yàn)大綱,組織老師編寫實(shí)驗(yàn)計(jì)劃和教材。緊跟專業(yè)發(fā)展前沿,改革教學(xué)內(nèi)容,大綱中概括了理論課每個(gè)章節(jié)的基本內(nèi)容、教學(xué)基本要求、教學(xué)重點(diǎn)難點(diǎn)以及教學(xué)建議。實(shí)驗(yàn)教材中明確了實(shí)驗(yàn)名稱、實(shí)驗(yàn)時(shí)間、實(shí)驗(yàn)學(xué)時(shí)、分組人數(shù)、實(shí)驗(yàn)?zāi)康暮鸵蟆?shí)驗(yàn)原理、實(shí)驗(yàn)方法與步驟、結(jié)果記錄及分析、思考題等內(nèi)容。實(shí)驗(yàn)計(jì)劃和教學(xué)大綱的制定把握以下幾個(gè)原則:減少重復(fù)性,體現(xiàn)連貫性,實(shí)現(xiàn)整體性。
(2)針對(duì)不同的教學(xué)內(nèi)容和教學(xué)需要,采取不同的教學(xué)方法。計(jì)算生物學(xué)是一門多學(xué)科交叉的科學(xué),涉及的知識(shí)面既深又廣,學(xué)生難以獨(dú)立自學(xué)。尤其是計(jì)算生物學(xué)涉及到的數(shù)學(xué)知識(shí),諸如窮舉搜索、貪婪算法、動(dòng)態(tài)規(guī)劃算法、分而治之算法、圖算法、組合模式匹配、聚類和樹、隱馬氏模型、隨機(jī)化算法等。
對(duì)于理論課,在教學(xué)過程中主要采用教師主導(dǎo)的傳統(tǒng)講授方法。課堂上,運(yùn)用多媒體授課并結(jié)合當(dāng)前科學(xué)研究中的最新進(jìn)展。利用多媒體課件以彌補(bǔ)書本教材呆板、抽象的缺點(diǎn)。在計(jì)算生物學(xué)教學(xué)課件中可以利用大量圖片生動(dòng)地展示當(dāng)前計(jì)算生物學(xué)研究領(lǐng)域的最新進(jìn)展。收集或制作動(dòng)畫、視頻教程在課堂上進(jìn)行演示。由于理學(xué)學(xué)科的學(xué)生,未系統(tǒng)且詳細(xì)地學(xué)習(xí)代數(shù)、概率論等數(shù)學(xué)知識(shí),要很好地理解計(jì)算生物學(xué)中的各種算法存在一定的困難,因此,每堂課要采取以簡(jiǎn)單有趣的故事或數(shù)學(xué)游戲?yàn)殚_端,引導(dǎo)學(xué)生理解每種算法的基本原理,再結(jié)合生物學(xué)問題,將算法與生物學(xué)問題結(jié)合起來,探討如何利用不同的算法解決生物學(xué)問題,深入淺出地闡明各章節(jié)的重點(diǎn)難點(diǎn)。最后,定期布置一定的思考題,引導(dǎo)學(xué)生在課堂外積極探索問題,鼓勵(lì)學(xué)生通過各種途徑自覺的關(guān)注學(xué)科發(fā)展動(dòng)態(tài),拓寬知識(shí)面,培養(yǎng)學(xué)生的自學(xué)能力和創(chuàng)新意識(shí)。采用這種授課方法,一方面大大提高了學(xué)生的積極性,另一方面使學(xué)生脫離了枯燥的數(shù)學(xué)公式學(xué)習(xí),加強(qiáng)了對(duì)算法和生物學(xué)問題的理解,從而達(dá)到使學(xué)生學(xué)有所獲、學(xué)有所用的目的。
(3)優(yōu)化計(jì)算生物學(xué)實(shí)驗(yàn)教學(xué)內(nèi)容,發(fā)揮網(wǎng)絡(luò)教學(xué)優(yōu)勢(shì)。計(jì)算生物學(xué)實(shí)驗(yàn)是生物信息學(xué)專業(yè)一門重要的實(shí)驗(yàn)技能課,通過實(shí)驗(yàn)課程的學(xué)習(xí),使學(xué)生計(jì)算生物學(xué)的研究方法,能夠運(yùn)用相關(guān)軟件如Perl、Matlab等進(jìn)行簡(jiǎn)單的編程,解讀包含在生物信息序列的信息,推測(cè)基因的功能,具體包括EST序列聚類、構(gòu)建進(jìn)化樹、識(shí)別轉(zhuǎn)錄銀子結(jié)合位點(diǎn)、RNA二級(jí)結(jié)構(gòu)預(yù)測(cè)、蛋白質(zhì)二級(jí)結(jié)構(gòu)預(yù)測(cè)等[3]。該系研究室以適應(yīng)學(xué)科發(fā)展要求與培養(yǎng)創(chuàng)新性復(fù)合型新世紀(jì)人才為目標(biāo),建設(shè)優(yōu)質(zhì)的計(jì)算生物學(xué)本科教學(xué)和計(jì)算生物學(xué)網(wǎng)絡(luò)課程。在充分調(diào)研的基礎(chǔ)上進(jìn)行詳細(xì)規(guī)劃,課堂教學(xué)精益求精,實(shí)驗(yàn)教學(xué)突出學(xué)生的創(chuàng)新能力培養(yǎng),促進(jìn)教學(xué)質(zhì)量更上一個(gè)臺(tái)階。該系現(xiàn)已建立了良好的實(shí)驗(yàn)平臺(tái),所有實(shí)驗(yàn)課程可實(shí)現(xiàn)網(wǎng)絡(luò)教學(xué)資源共享。計(jì)算生物學(xué)實(shí)驗(yàn)教學(xué)以互聯(lián)網(wǎng)為媒介、計(jì)算機(jī)為工具,全部在計(jì)算機(jī)網(wǎng)絡(luò)實(shí)驗(yàn)室內(nèi)完成。在教學(xué)中,充分利用網(wǎng)絡(luò)的交互特點(diǎn)實(shí)現(xiàn)信息技術(shù)與課程的結(jié)合[4]。教師將實(shí)驗(yàn)教學(xué)內(nèi)容、實(shí)驗(yàn)序列、工具等上傳到服務(wù)器,再由學(xué)生將資料下載到本地機(jī)進(jìn)行學(xué)習(xí)、實(shí)驗(yàn)。學(xué)生同樣通過上傳服務(wù)器,將實(shí)驗(yàn)報(bào)告、作業(yè)、問題和意見等反饋給教師,教師在網(wǎng)上批改實(shí)驗(yàn)報(bào)告后將成績(jī)和評(píng)語發(fā)送給學(xué)生,讓學(xué)生及時(shí)了解自己的學(xué)習(xí)情況。
總之,計(jì)算生物學(xué)教學(xué)是網(wǎng)絡(luò)環(huán)境下生物教學(xué)的全新內(nèi)容。通過上述教學(xué)措施,提高了學(xué)生的學(xué)習(xí)積極性、實(shí)踐操作能力、解決實(shí)際問題的綜合應(yīng)用能力及創(chuàng)新能力,收到了良好的教學(xué)效果,受到學(xué)生的普遍歡迎,具有較強(qiáng)的可操作性和實(shí)踐性。在今后的教學(xué)實(shí)踐中,隨著教師自身素質(zhì)的提高和進(jìn)一步的教學(xué)改革,將會(huì)不斷完善計(jì)算生物學(xué)教學(xué),培養(yǎng)具有跨越生命科學(xué)、信息科學(xué)、數(shù)理科學(xué)等不同領(lǐng)域的“大科學(xué)”素質(zhì)和意識(shí)的生物信息學(xué)人才。
3參考文獻(xiàn)
[1] 程妍,劉仲林.計(jì)算生物學(xué)——一門充滿活力的新興交叉學(xué)科[J].科學(xué)學(xué)與科學(xué)技術(shù)管理,2006(3):11-15.
[2] 高亞梅,韓毅強(qiáng).《生物信息學(xué)》本科教學(xué)初探[J].生物信息學(xué),2007,(1):46-48.