計(jì)算機(jī)是一種現(xiàn)代化的信息處理工具，它對(duì)信息進(jìn)行處理并提供所需結(jié)果，其結(jié)果取決于所接受的信息及相應(yīng)的處理算法。算法是以計(jì)算機(jī)能夠理解的語(yǔ)言描述的解題過(guò)程。當(dāng)算法作用于所求解問(wèn)題的給定輸入集或作用于問(wèn)題自身的描述上，將產(chǎn)生唯一確定的有限動(dòng)作序列。此序列或終止于給定問(wèn)題的解，或終止于對(duì)此輸入信息無(wú)解。對(duì)于給定的問(wèn)題，基于對(duì)其的深刻理解，可設(shè)計(jì)出解答該問(wèn)題的一個(gè)算法。在這個(gè)意義上，設(shè)計(jì)算法是將有關(guān)問(wèn)題的知識(shí)，轉(zhuǎn)化為解決問(wèn)題的智慧。知識(shí)誠(chéng)可貴，智慧價(jià)更高。設(shè)計(jì)算法就是揭示所研究問(wèn)題的基本特征，以尋求其解答策略的過(guò)程，這是一項(xiàng)艱苦的創(chuàng)造性工作。
　　對(duì)于給定的問(wèn)題，有可能設(shè)計(jì)出多個(gè)算法，但不同的算法質(zhì)量會(huì)不一樣。衡量算法質(zhì)量的主要因素是算法執(zhí)行所耗費(fèi)的時(shí)間和所需存儲(chǔ)空間，以及算法適用范圍等。對(duì)算法質(zhì)量的分析研究稱為算法分析。算法設(shè)計(jì)和算法分析是計(jì)算機(jī)科學(xué)的核心基礎(chǔ)。國(guó)內(nèi)外大學(xué)的計(jì)算機(jī)專業(yè)中，都將“算法設(shè)計(jì)與分析”作為專業(yè)基礎(chǔ)課。
　　近半個(gè)世紀(jì)以來(lái)，算法研究始終是計(jì)算機(jī)科學(xué)的一個(gè)研究熱點(diǎn)。以E.W.Dijkstra、S.A.Cook、R.M.Karp、J.H.Hopcroft及R.E.Tarjan等為代表的一批計(jì)算機(jī)科學(xué)家，以創(chuàng)造性工作推動(dòng)著算法研究不斷深入發(fā)展。在研究過(guò)程中，算法理論研究與軟件技術(shù)研究之間產(chǎn)生了鴻溝，使得算法研究缺乏足夠的實(shí)驗(yàn)支持，而實(shí)驗(yàn)工作又沒(méi)有充分的理論分析。這種現(xiàn)狀引起了人們的憂慮。在1996年的ACM計(jì)算理論學(xué)術(shù)年會(huì)（STOC‘96）上，一些計(jì)算機(jī)科學(xué)家提出“算法工程”的概念，強(qiáng)調(diào)研究算法實(shí)現(xiàn)技術(shù)的重要性，呼吁算法研究者應(yīng)重視理論與實(shí)踐的結(jié)合，將算法設(shè)計(jì)、分析、實(shí)現(xiàn)、測(cè)試及改進(jìn)等過(guò)程一體化、工程化。這種研究思路越來(lái)越受到人們的關(guān)注，促使算法研究健康發(fā)展。
　　本書(shū)原稿寫(xiě)于20世紀(jì)80年代中期、筆者在山東大學(xué)為計(jì)算機(jī)專業(yè)研究生講授“算法設(shè)計(jì)與分析”課程期間，先后幾經(jīng)修改，于1992年定稿并由山東大學(xué)出版社正式出版。此后一直使用本書(shū)作為計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的學(xué)位課教材，由筆者和朱大銘教授共同為研究生講授，效果尚好。經(jīng)過(guò)20多年的研究沉淀，算法設(shè)計(jì)與分析雖然沒(méi)有太多變遷，但其研究?jī)?nèi)容更加豐富和成熟。這期間我們始終堅(jiān)持在這個(gè)研究方向上從事教學(xué)和科研工作，連續(xù)主持了10多項(xiàng)國(guó)家自然科學(xué)基金課題，培養(yǎng)了一批博士、碩士研究生。為適應(yīng)培養(yǎng)創(chuàng)新型人才的需要，經(jīng)過(guò)反復(fù)醞釀，決定由朱大銘教授執(zhí)筆，重新修改編著這本書(shū)，增加近10年來(lái)的研究成果，使之能反映21世紀(jì)以來(lái)算法設(shè)計(jì)與分析的研究現(xiàn)狀�？梢哉f(shuō)，本書(shū)是山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院兩代人堅(jiān)持不懈、刻苦努力完成的。在本書(shū)寫(xiě)作過(guò)程中，得到朱洪教授的指導(dǎo)和幫助，在此表示感謝。
　　本書(shū)主要面向計(jì)算機(jī)相關(guān)專業(yè)的高年級(jí)本科生和研究生。全書(shū)共分8章，其中：第1、2章討論算法分析技術(shù)和算法設(shè)計(jì)技術(shù)；第3、4、5、6章論述NP-完全性理論，特別強(qiáng)調(diào)多項(xiàng)式變換和多項(xiàng)式圖靈歸約的方法及應(yīng)用；第7章論述NP-難解問(wèn)題近似算法的基本概念和設(shè)計(jì)NP-難解問(wèn)題近似算法的基本方法；第8章討論近似算法設(shè)計(jì)的基本理論與技術(shù)。
　　算法研究是一項(xiàng)富有挑戰(zhàn)性的工作，對(duì)提高計(jì)算機(jī)學(xué)科的研究水平極為重要，希望能有更多的有識(shí)之士投身這項(xiàng)工作。由于我們學(xué)術(shù)水平有限，本書(shū)內(nèi)容必有疏漏、欠妥、謬誤之處，敬請(qǐng)讀者指正。