《算法設(shè)計(jì)與分析》教學(xué)研究*

尚軍亮 李圣君 孫燕

（曲阜師范大學(xué) 信息科學(xué)與工程學(xué)院，山東日照276826）

《算法設(shè)計(jì)與分析》教學(xué)研究*

尚軍亮 李圣君 孫燕

（曲阜師范大學(xué) 信息科學(xué)與工程學(xué)院，山東日照276826）

針對(duì)《算法設(shè)計(jì)與分析》的課程特點(diǎn)，結(jié)合教學(xué)實(shí)踐經(jīng)驗(yàn)，研究探討了本門(mén)課的教學(xué)方法和教學(xué)手段。結(jié)合經(jīng)典教學(xué)模式，引入blending learning和研究性學(xué)習(xí)等先進(jìn)有效的教學(xué)模式，對(duì)提高教學(xué)效果、完善教學(xué)模式、促進(jìn)學(xué)生綜合素質(zhì)的提高有積極的作用。

算法設(shè)計(jì)與分析；教學(xué)方法；主體地位；blending learning；研究性學(xué)習(xí)

一、概述

《算法設(shè)計(jì)與分析》是一門(mén)理論性與實(shí)踐性兼顧的課程，處于計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的核心地位?！端惴ㄔO(shè)計(jì)與分析》課程的設(shè)立，是為了適應(yīng)新世紀(jì)我國(guó)計(jì)算機(jī)科學(xué)技術(shù)及軟件工程人才培養(yǎng)的需要。在本科教學(xué)中，無(wú)論是對(duì)于應(yīng)用類(lèi)的學(xué)生還是理論類(lèi)的學(xué)生來(lái)說(shuō)，理解、掌握算法設(shè)計(jì)的基本方法以及正確進(jìn)行算法復(fù)雜性的分析都是十分必要的［1，2］。

然而，該課程知識(shí)點(diǎn)多而復(fù)雜，不易理解，學(xué)生往往因此喪失學(xué)習(xí)的興趣和熱情，或者能“深入”而不能“淺出”。因此，教師在教授這門(mén)課時(shí)，應(yīng)該以學(xué)生為主體，在傳授基本算法的同時(shí)，注意培養(yǎng)他們獨(dú)立思考解決問(wèn)題的能力。文章結(jié)合教學(xué)實(shí)踐經(jīng)驗(yàn)，將就《算法設(shè)計(jì)與分析》在本科教學(xué)中的教學(xué)方法和教學(xué)手段進(jìn)行探討研究。

二、《算法設(shè)計(jì)與分析》教學(xué)方法研究

（一）明確目標(biāo)，培養(yǎng)興趣

教學(xué)伊始，首先讓學(xué)生明確《算法設(shè)計(jì)與分析》課程的教學(xué)目標(biāo)，這樣才能有的放矢?！端惴ㄔO(shè)計(jì)與分析》的教學(xué)目標(biāo)是：通過(guò)學(xué)習(xí)本課程，學(xué)生應(yīng)該掌握計(jì)算機(jī)軟件設(shè)計(jì)中常用的算法，并可以對(duì)算法的復(fù)雜性進(jìn)行分析，能夠幫助我們?cè)趯?shí)際工作中，根據(jù)具體問(wèn)題設(shè)計(jì)和優(yōu)化算法，以最少的成本、最快的速度、最好的質(zhì)量開(kāi)發(fā)出適合各種應(yīng)用需求的軟件。

“興趣是最好的老師”，因此在學(xué)生剛剛接觸這門(mén)課的時(shí)候就要激發(fā)起學(xué)生學(xué)習(xí)的熱情。比如計(jì)算機(jī)界的大師Donald E.Knuth曾經(jīng)說(shuō)過(guò)“Computer science is the study of algorithms”。以此例讓學(xué)生體會(huì)到算法在整個(gè)計(jì)算機(jī)科學(xué)中的地位。李開(kāi)復(fù)先生曾著文《算法的力量》，從多個(gè)角度探討了算法在當(dāng)今生活中的應(yīng)用，并強(qiáng)調(diào)在計(jì)算機(jī)應(yīng)用和數(shù)據(jù)飛速增長(zhǎng)的大環(huán)境下，算法的重要性在日益加強(qiáng)。通過(guò)這些實(shí)例，讓學(xué)生領(lǐng)會(huì)到，算法與我們的生活息息相關(guān)，從而產(chǎn)生學(xué)習(xí)的興趣和動(dòng)力。

（二）循循善誘，深入淺出

教授每章內(nèi)容時(shí)，一般首先介紹算法設(shè)計(jì)策略的思想，然后從解決計(jì)算機(jī)科學(xué)與應(yīng)用中出現(xiàn)的實(shí)際問(wèn)題入手，由簡(jiǎn)到繁的描述幾個(gè)經(jīng)典的精巧算法，同時(shí)對(duì)每個(gè)算法所需要的時(shí)間和空間進(jìn)行分析。而在具體講述經(jīng)典算法時(shí)，則一般按照提出問(wèn)題、分析問(wèn)題、解決問(wèn)題的基本思路，并且注意引導(dǎo)學(xué)生思考。

比如在講解分治算法處理大整數(shù)乘法問(wèn)題時(shí)，首先提出問(wèn)題：兩個(gè)n位二進(jìn)制大整數(shù)如何相乘。學(xué)生會(huì)很容易的想到用小學(xué)所學(xué)的方法來(lái)解決。分析這種方法需要進(jìn)行O（n2）步運(yùn)算才能算出乘積，時(shí)間復(fù)雜度較高。有沒(méi)有更好的方法呢？若將兩個(gè)n位大整數(shù)各分成規(guī)模相等的兩部分，再來(lái)計(jì)算一下時(shí)間復(fù)雜度，用板書(shū)與學(xué)生一起計(jì)算得到仍然是O（n2）。因此進(jìn)一步提問(wèn)：這里我們采用了分治策略，但是算法的時(shí)間復(fù)雜性并沒(méi)有得到改進(jìn)，為什么？當(dāng)學(xué)生明白是因?yàn)榇颂幍淖訂?wèn)題不是互相獨(dú)立的。那么如何轉(zhuǎn)化呢？提示學(xué)生進(jìn)行恒等變形，引導(dǎo)學(xué)生自己嘗試轉(zhuǎn)化方法。接著與學(xué)生一起進(jìn)行轉(zhuǎn)化操作，從而使算法的時(shí)間復(fù)雜性降低。問(wèn)題解決了，這不是最終目的，我們?cè)谏钊胫笕孕铚\出。因此，這時(shí)要強(qiáng)調(diào)分治策略在大整數(shù)乘法問(wèn)題處理中的應(yīng)用，讓學(xué)生從層層的問(wèn)題中解脫出來(lái)。最后，為了引導(dǎo)學(xué)生進(jìn)一步思考，可以留下問(wèn)題：若將大整數(shù)各分成規(guī)模相等的三段、四段甚至更多段會(huì)不會(huì)再次改進(jìn)其時(shí)間復(fù)雜度呢？學(xué)生通過(guò)課后的進(jìn)一步思考，可以對(duì)分治策略和大整數(shù)乘法問(wèn)題有更深的認(rèn)識(shí)。

（三）精心提煉，深刻理解

有的內(nèi)容教材上講解比較簡(jiǎn)練，學(xué)生自己讀教材往往理解比較膚淺。因此，教師要善于從中提煉出關(guān)鍵性的有價(jià)值的問(wèn)題，讓學(xué)生展開(kāi)多維度思考，從而有助于學(xué)生對(duì)該問(wèn)題的理解。

比如，教材在講述回溯算法解決圓排列問(wèn)題時(shí)，在簡(jiǎn)單分析后直接給出了實(shí)現(xiàn)算法。而算法實(shí)現(xiàn)中有幾處實(shí)現(xiàn)比較巧妙，學(xué)生往往似懂非懂。比如center函數(shù)中圓心橫坐標(biāo)計(jì)算時(shí)為什么不用最后一個(gè)圓計(jì)算，而用for循環(huán)，有必要么？compute函數(shù)中計(jì)算當(dāng)前圓排列長(zhǎng)度為什么也用for循環(huán)？學(xué)生在深入思考這兩個(gè)問(wèn)題后，對(duì)圓排列問(wèn)題有了全面的認(rèn)識(shí)。

（四）強(qiáng)化主體，培養(yǎng)主動(dòng)

教學(xué)中，一定要保證學(xué)生的主體地位，充分調(diào)動(dòng)學(xué)生的主觀(guān)能動(dòng)性。只有學(xué)生積極主動(dòng)的參與到教學(xué)中來(lái)，才能更好地完成教學(xué)任務(wù)。

比如在講解回溯法解決裝載問(wèn)題時(shí)，學(xué)生在掌握了算法的思想和算法實(shí)現(xiàn)后，舉一個(gè)實(shí)例，稍作說(shuō)明后留給學(xué)生課下解決。下次上課時(shí)，隨機(jī)點(diǎn)一名學(xué)生上來(lái)講解，反響特別好。其他學(xué)生在之前也自己思考準(zhǔn)備過(guò)，因此聽(tīng)講的目的性更強(qiáng)，而且注意力特別集中。學(xué)生講解完，教師首先對(duì)他的認(rèn)真準(zhǔn)備和條理講解給予高度評(píng)價(jià)，然后指出其存在的不足和問(wèn)題，并啟發(fā)全班同學(xué)一起繼續(xù)思考解決。這樣，通過(guò)學(xué)生自己的頭腦加工，教師的知識(shí)或者書(shū)本的知識(shí)才能轉(zhuǎn)化為學(xué)生的知識(shí)。

（五）動(dòng)手實(shí)踐，提高能力

要想讓學(xué)生真正掌握本課程的精髓和技能，在課堂講解和學(xué)生思考之外，還需要提供實(shí)踐的環(huán)節(jié)。

在教學(xué)過(guò)程中，教師給學(xué)生布置適當(dāng)?shù)纳蠙C(jī)任務(wù)，以“任務(wù)驅(qū)動(dòng)”調(diào)動(dòng)學(xué)生的積極性。上機(jī)輔導(dǎo)時(shí)，及時(shí)解決學(xué)生出現(xiàn)的問(wèn)題，并鼓勵(lì)學(xué)生舉一反三，活學(xué)活用。上機(jī)實(shí)踐使得學(xué)生由被動(dòng)的旁聽(tīng)者變?yōu)橹鲃?dòng)的實(shí)踐者，有利于加深他們對(duì)課程的理解，培養(yǎng)他們的綜合能力。

三、《算法設(shè)計(jì)與分析》教學(xué)手段研究

（一）傳統(tǒng)板書(shū)與多媒體相結(jié)合

當(dāng)今的計(jì)算機(jī)專(zhuān)業(yè)教學(xué)，多媒體輔助教學(xué)以其直觀(guān)、形象、信息量大等優(yōu)勢(shì)占據(jù)了主要地位。算法是一門(mén)很抽象的學(xué)科，通過(guò)演示教學(xué)法把理論問(wèn)題具體化，把靜態(tài)的教學(xué)動(dòng)態(tài)化，一方面可以幫助學(xué)生的理解，另一方面可以激發(fā)學(xué)生的學(xué)習(xí)興趣。但是，完全將抽象形象化，又不利于學(xué)生抽象思維能力的培養(yǎng)，因此，在利用多媒體教學(xué)手段時(shí)應(yīng)該適度。

比如，動(dòng)態(tài)規(guī)劃算法解決0-1背包問(wèn)題，證明其具有最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，用板書(shū)形式一步一步證明，學(xué)生經(jīng)歷了板書(shū)從無(wú)到有，思路從疑惑到漸漸明白的過(guò)程。教師整個(gè)的講解過(guò)程與其說(shuō)是為了證明一個(gè)問(wèn)題，不如說(shuō)是為了展示一個(gè)思維的方法。相對(duì)于在大屏幕上演示證明過(guò)程，板書(shū)形式效果更好。

（二）適時(shí)采用blending learning模式

Blending learning是現(xiàn)在大學(xué)教學(xué)中重要的教學(xué)手段。何克抗指出，blending learning就是要把傳統(tǒng)學(xué)習(xí)的優(yōu)勢(shì)和E-learning的優(yōu)勢(shì)結(jié)合起來(lái)；教師要啟動(dòng)監(jiān)督和引導(dǎo)教學(xué)，同時(shí)學(xué)生要積極參加學(xué)習(xí)［3］。

我們?cè)凇端惴ㄔO(shè)計(jì)與分析》教學(xué)中，也充分利用現(xiàn)在便利的互聯(lián)網(wǎng)條件，將一些優(yōu)秀的網(wǎng)絡(luò)資源和課程提供給學(xué)生，讓他們以專(zhuān)題的形式在線(xiàn)學(xué)習(xí)，并且以學(xué)習(xí)小組的形式共同討論。鼓勵(lì)學(xué)生選修MOOC，爭(zhēng)取拿到MOOC證書(shū)，學(xué)生的學(xué)習(xí)積極性得到極大提高。

（三）研究性學(xué)習(xí)模式引入

結(jié)合我們?cè)谄渌n程的研究性教學(xué)經(jīng)驗(yàn)［4］，在《算法設(shè)計(jì)與分析》中，我們也不失時(shí)機(jī)的引入研究性教學(xué)模式。將教師的科研課題涉及到的算法以專(zhuān)題的形式讓學(xué)生學(xué)習(xí)探討，既讓學(xué)生對(duì)《算法設(shè)計(jì)與分析》課程的作用更加明晰，而且有些學(xué)生參與到教師的科研項(xiàng)目，科研能力和創(chuàng)新能力得到了進(jìn)一步的提高。數(shù)學(xué)建模、齊魯軟件大賽、創(chuàng)新創(chuàng)業(yè)項(xiàng)目等比賽項(xiàng)目，也成為學(xué)生們進(jìn)一步強(qiáng)化算法理解，提高分析問(wèn)題和解決問(wèn)題能力的重要平臺(tái)。

（四）課程考核評(píng)價(jià)方式研究

教學(xué)評(píng)價(jià)是對(duì)受教育者的多種要素進(jìn)行價(jià)值評(píng)估，而考試是教學(xué)評(píng)價(jià)的工具和手段，是測(cè)量應(yīng)試者知識(shí)與能力、素質(zhì)與潛力的量尺?？荚嚍榻虒W(xué)評(píng)價(jià)提供了量化資料，卻不能替代教學(xué)評(píng)價(jià)［5］。

《算法設(shè)計(jì)與分析》課程涉及內(nèi)容廣，應(yīng)用性強(qiáng)。以傳統(tǒng)的考試考核為基礎(chǔ)，我們創(chuàng)設(shè)了多元評(píng)價(jià)體系。將實(shí)驗(yàn)、期末考試和平時(shí)的作業(yè)及考勤納入評(píng)價(jià)體系，并且將學(xué)生對(duì)專(zhuān)題和MOOC學(xué)習(xí)的情況也列入評(píng)價(jià)體系。這種多元評(píng)價(jià)方式對(duì)學(xué)生學(xué)習(xí)積極性的提高，以及理論與創(chuàng)新實(shí)踐能力等綜合素質(zhì)的提高起到了很好的促進(jìn)作用。

四、結(jié)束語(yǔ)

《算法設(shè)計(jì)與分析》是計(jì)算機(jī)專(zhuān)業(yè)的核心課程。教師只有加深自身理論修養(yǎng)和實(shí)踐能力，并且注意采用適當(dāng)?shù)慕虒W(xué)方法，才能夠讓學(xué)生真正掌握算法的精髓，取得較好的教學(xué)效果。在實(shí)際教學(xué)中，我們綜合靈活的運(yùn)用各種教學(xué)方法，并結(jié)合多種教學(xué)手段，既提高了學(xué)生能力，又取得了較好的教學(xué)效果。

在今后的算法教學(xué)中，我們計(jì)劃進(jìn)一步結(jié)合優(yōu)秀的教學(xué)模式，設(shè)計(jì)更有趣更適合學(xué)生的專(zhuān)題，讓學(xué)生在掌握基本理論的基礎(chǔ)上，可以在應(yīng)用項(xiàng)目方面做出更多的創(chuàng)新和有價(jià)值的工作。

［1］王曉東.算法設(shè)計(jì)與分析（第2版）［M］.北京：清華大學(xué)出版社，2008.

［2］陳蕾，張怡婷，許建.基于創(chuàng)新能力培養(yǎng)的算法設(shè)計(jì)與分析課程教學(xué)改革［J］.計(jì)算機(jī)教育，2010（20）：27-29.

［3］何克抗.從Blended Learning看教育技術(shù)理論的新發(fā)展（上）［J］.電化教育研究，2004（3）：1-6.

［4］李圣君，尚軍亮，雷玉霞，等.人工智能實(shí)驗(yàn)研究性教學(xué)模式探索［J］.高教學(xué)刊，2016（3）：236-239.

［5］周蘇.專(zhuān)業(yè)課程教學(xué)測(cè)評(píng)的創(chuàng)新實(shí)踐［J］.計(jì)算機(jī)教育，2008（7）：88-93.

In terms of the characteristics of Algorithm Design and Analysis，this paper explores the teaching methods of the course with consideration of practical teaching experiences.This paper proposes the combination of classic teaching mode，and the introduction of advanced and effective teaching modes，such as blending learning and research-based teaching mode，can improve the teaching effect，perfect the teaching mode，and promote the improvement of the overall quality of the students.

algorithm design and analysis；teaching method；dominant role；blending learning；research-based teaching

G642

A

2096-000X（2016）21-0047-02

曲阜師范大學(xué)校級(jí)精品實(shí)驗(yàn)（實(shí)訓(xùn)）項(xiàng)目（jp2015005）；曲阜師范大學(xué)科技計(jì)劃項(xiàng)目（xkj201524）。

尚軍亮，男，副教授，研究方向?yàn)橹悄苄畔⑻幚?、大?shù)據(jù)挖掘和生物信息學(xué)。