算法設(shè)計(jì)與分析

前言

　　民眾多好飲酒，中外概莫能外。酒館和釀酒坊伴隨飲酒客而起，人類對(duì)酒的喜愛(ài)造就了酒文化和一個(gè)龐大的產(chǎn)業(yè)。好酒能賣好價(jià)錢，能使文人詩(shī)興大發(fā)，催生佳作，還能解人間百難。于是，釀天下名酒自然成為不少人的畢生追求?！　≡鯓硬拍茚劤龊镁颇?？國(guó)人的看法不盡相同。崇信洋酒的人主張引進(jìn)國(guó)外的生產(chǎn)工藝，學(xué)習(xí)洋人的生產(chǎn)和經(jīng)營(yíng)理念，而喜歡國(guó)酒的人則主張走自己的路，但不排除借鑒國(guó)外先進(jìn)的科學(xué)技術(shù)和管理經(jīng)驗(yàn)。這樣的爭(zhēng)論或許永遠(yuǎn)不會(huì)終結(jié)，但外國(guó)人重視科學(xué)釀酒，這一點(diǎn)是值得我們學(xué)習(xí)和借鑒的?！　∮?jì)算機(jī)科學(xué)教育，如同釀酒工業(yè)的生產(chǎn)一樣，科學(xué)辦學(xué)迄今還只是部分學(xué)者的一種理想。與國(guó)內(nèi)一樣，國(guó)外的計(jì)算機(jī)科學(xué)教育并沒(méi)有像他們的科學(xué)釀酒業(yè)一樣，實(shí)現(xiàn)科學(xué)辦學(xué)。也許科學(xué)辦學(xué)要遠(yuǎn)比科學(xué)釀酒困難得多。譬如，怎么實(shí)現(xiàn)科學(xué)辦學(xué)？甚至怎么推出一套科學(xué)的系列教材都是一篇大文章?！　∵@套教材的創(chuàng)作始于教育部面向21世紀(jì)教育與教學(xué)改革13-22項(xiàng)目的研究。2000年，在13-22項(xiàng)目研究工作即將完成之際，一些學(xué)者開(kāi)始認(rèn)識(shí)到面對(duì)計(jì)算機(jī)科學(xué)與技術(shù)的高速發(fā)展，我們亟需一套體現(xiàn)科學(xué)辦學(xué)思想、反映內(nèi)涵發(fā)展要求、服務(wù)教育與教學(xué)改革、參與構(gòu)建學(xué)科人才培養(yǎng)科學(xué)體系的系列教材。強(qiáng)調(diào)系列教材是因?yàn)槟菚r(shí)已經(jīng)意識(shí)到計(jì)算機(jī)科學(xué)教育本質(zhì)上是一項(xiàng)科學(xué)活動(dòng)，但長(zhǎng)期以來(lái)教師向?qū)W生傳授科學(xué)技術(shù)知識(shí)的方式方法科學(xué)性不強(qiáng)。由于高等教育幾百年來(lái)一直沿襲經(jīng)驗(yàn)方式而非科學(xué)方式辦學(xué)，大學(xué)教學(xué)的方式方法仍然還停留在古代作坊式的階段，只不過(guò)今天使用的教學(xué)技術(shù)手段先進(jìn)而已。在經(jīng)驗(yàn)辦學(xué)方式下，無(wú)論是研究型大學(xué)還是教學(xué)型大學(xué)，由于種種原因，教學(xué)活動(dòng)的全過(guò)程存在著太多的漏洞和質(zhì)量上的隱患?？茖W(xué)辦學(xué)是對(duì)高等教育界傳統(tǒng)的一個(gè)挑戰(zhàn)，盡管在認(rèn)識(shí)上，人們不難理解，科學(xué)辦學(xué)是經(jīng)驗(yàn)辦學(xué)的最高形式，而經(jīng)驗(yàn)辦學(xué)應(yīng)該成為科學(xué)辦學(xué)的有益補(bǔ)充。

內(nèi)容概要

本書(shū)主要取材于反映當(dāng)今計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科中算法設(shè)計(jì)及分析發(fā)展潮流方面的內(nèi)容。內(nèi)容除包括國(guó)外一些比較成熟的算法技術(shù)，例如基本的隨機(jī)算法以及近似算法，還包括一些最新的研究成果，例如基于近似和隨機(jī)思想的混合算法：隨機(jī)近似算法、在線算法、現(xiàn)代啟發(fā)式算法等。本書(shū)包括大量的問(wèn)題實(shí)例并給出了相應(yīng)的求解方法。而工業(yè)應(yīng)用領(lǐng)域的許多實(shí)際問(wèn)題和疑難問(wèn)題，都需要有效的求解算法，本書(shū)提供了大量的可供選擇的解決途徑。    本書(shū)可作為計(jì)算機(jī)科學(xué)系、數(shù)學(xué)系、管理科學(xué)等高年級(jí)本科以及研究生課程的教材，也適合科研人員學(xué)習(xí)使用。

書(shū)籍目錄

第1章　預(yù)備知識(shí)　1.1　數(shù)學(xué)基礎(chǔ)　1.2　問(wèn)題的復(fù)雜性　1.3　規(guī)劃問(wèn)題第2章　隨機(jī)算法　2.1　基本概念　2.2　數(shù)值隨機(jī)算法　2.3　Sherwood算法　2.4　Las Vegas算法　2.5　Monte Carlo算法　2.6　隨機(jī)復(fù)雜性　2.7　總結(jié)第3章　近似算法　3.1　基本概念　3.2　調(diào)度問(wèn)題　3.3　旅行商問(wèn)題　3.4　覆蓋問(wèn)題　3.5　Bin packing問(wèn)題　3.6　背包問(wèn)題　3.7　隨機(jī)近似算法　3.8　基于線性規(guī)劃的近似算法　3.9　近似的難度　3.10　在線算法　3.11　總結(jié)第4章　啟發(fā)式算法　4.1　概述　4.2　作業(yè)車間調(diào)度問(wèn)題　4.3　packing問(wèn)題　4.4　SAT問(wèn)題　4.5　總結(jié)參考文獻(xiàn)

章節(jié)摘錄

　　第1章 入門　　1.4 算法的效率　　對(duì)于給定的問(wèn)題，起初只是考慮只要找到一個(gè)算法解決該問(wèn)題就行，而不管該算法花多長(zhǎng)時(shí)間或者占用多大的存儲(chǔ)空間。隨著計(jì)算機(jī)技術(shù)的發(fā)展，人們發(fā)現(xiàn)，求解同一個(gè)問(wèn)題的不同的算法，所需要的運(yùn)行時(shí)間是不同的。例如對(duì)排序問(wèn)題，除了上面介紹過(guò)的插入排序算法，我們還將介紹選擇排序、合并排序以及快速排序算法。我們自然會(huì)問(wèn)，哪個(gè)排序算法好呢？怎么樣評(píng)價(jià)一個(gè)算法的好壞呢？這就涉及到算法的時(shí)間和空間資源的分析，即算法效率(Efficiency)的分析?！　∷惴ㄐ实姆治?，指的是算法求解一個(gè)問(wèn)題所需要的時(shí)間和空間。分析一個(gè)算法，意味著預(yù)測(cè)該算法解一個(gè)問(wèn)題時(shí)，需要花費(fèi)多少時(shí)間和空間資源?？臻g資源一般指解決一個(gè)問(wèn)題，需要多大的內(nèi)存、硬盤空間等來(lái)存儲(chǔ)輸入輸出數(shù)據(jù)等。時(shí)間資源一般指的是解決一個(gè)問(wèn)題需要多長(zhǎng)的時(shí)間。一般地，對(duì)一個(gè)問(wèn)題，存在不同的求解算法，我們可以根據(jù)算法所需要的時(shí)空資源來(lái)確定出其中有效的算法。隨著計(jì)算機(jī)硬件技術(shù)的發(fā)展，現(xiàn)在計(jì)算機(jī)的內(nèi)存和硬盤空間基本上能滿足問(wèn)題的需要，即空間資源已經(jīng)不是問(wèn)題，因此，我們分析一個(gè)算法，主要考慮算法的計(jì)算時(shí)間，今后，我們也主要從時(shí)間資源方面對(duì)算法進(jìn)行分析，即分析算法有多快?！　≡诜治鲆粋€(gè)算法前，我們需要知道如何實(shí)現(xiàn)一個(gè)算法，這就涉及到計(jì)算模型的概念。如果對(duì)一個(gè)問(wèn)題，利用計(jì)算模型能夠?qū)崿F(xiàn)一個(gè)求解算法，則該問(wèn)題是可解的，否則是不可解的。排序問(wèn)題是一個(gè)可解的問(wèn)題，因?yàn)槲覀円呀?jīng)找到了許多排序算法。對(duì)于不可解的問(wèn)題，由于無(wú)法找到其求解算法，對(duì)其進(jìn)行算法研究也就沒(méi)必要，本書(shū)探討可解問(wèn)題的算法設(shè)計(jì)與分析。

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    算法設(shè)計(jì)與分析 PDF格式下載

---