本書以通俗易懂的語言向讀者描述了各類常用算法。全書包括四個部分，涉及排序與搜索、算術(shù)與密碼、規(guī)劃、協(xié)同與設(shè)計、優(yōu)化四個領(lǐng)域，每個部分都給出該領(lǐng)域中常用的算法，每一個算法都從一個實際的生活場景引入。通過作者深入淺出的介紹，讀者可以輕松了解計算機(jī)科學(xué)中常用的算法的原理，具備初步的計算思維能力。本書適合作為高校計算機(jī)科學(xué)入門課程的教材，也適合作為計算機(jī)科學(xué)的科普書籍。
本書是在一系列給中學(xué)生普及算法和計算思維的講座基礎(chǔ)上整理編寫的，選擇了計算機(jī)科學(xué)中一些有重要應(yīng)用價值的典型問題，用通俗易懂的語言介紹著名的算法思想。盡管本書的初衷是讓高中生領(lǐng)會算法和計算機(jī)科學(xué)的奇妙與魅力，但它同樣適合已經(jīng)進(jìn)入大學(xué)計算機(jī)類專業(yè)學(xué)習(xí)的學(xué)生閱讀，目的是使學(xué)生欣賞計算機(jī)科學(xué)有趣的一面，也能對“我們?nèi)绾谓忸}”有更深入的理解。對于從事計算機(jī)教學(xué)尤其是基礎(chǔ)教育的廣大教師，也可以從本書中得到啟發(fā)與收獲。
前 言最近幾十年來許多技術(shù)創(chuàng)新和成果都依賴于算法思想，這些成果廣泛應(yīng)用于科學(xué)、醫(yī)藥、生產(chǎn)、物流、交通、通信、娛樂等領(lǐng)域。高效的算法使得你的個人計算機(jī)得以運(yùn)行新一代的游戲，這些復(fù)雜的游戲在幾年前可能都難以想象。更重要的是，這些算法為一些重大科學(xué)突破提供了基礎(chǔ)。例如，人類基因組圖譜解碼得以實現(xiàn)與新算法的發(fā)明是分不開的，這些算法能將計算速度提高幾個數(shù)量級。算法告訴計算機(jī)如何處理信息，如何執(zhí)行任務(wù)。算法組織數(shù)據(jù)，使得我們能有效地搜索。如果沒有聰明的算法，我們一定會迷失在互聯(lián)網(wǎng)這個巨大的數(shù)據(jù)叢林中。同樣，如果沒有天才的編碼和加密算法，我們也不可能在網(wǎng)絡(luò)上安全地通信。天氣預(yù)報與氣候變化分析也依靠高效模擬算法。工廠生產(chǎn)線和物流系統(tǒng)有大量復(fù)雜的優(yōu)化問題，只有奇巧的算法能幫助我們解決這類問題。甚至當(dāng)你利用GPS尋找附近的餐廳或咖啡館時，也要靠有效的最短路徑計算才能獲得滿意的結(jié)果。并非像很多人認(rèn)為的，只有計算機(jī)中才需要算法。在工業(yè)機(jī)器人、汽車、飛機(jī)以及幾乎所有家用電器中都包含許多微處理器，它們也都依賴算法才能發(fā)揮作用。例如，你的音樂播放器中使用聰明的壓縮算法，否則小小的播放器會因為存儲量不足而無法使用。現(xiàn)在的汽車和飛機(jī)中有成百上千的微處理器，算法能幫助控制引擎，減少能耗，降低污染。它們還能控制制動器和方向盤，提高穩(wěn)定性與安全性。不久的將來，微處理器可能完全替代人，實現(xiàn)汽車的全自動駕駛。目前的飛機(jī)已經(jīng)能做到在從起飛到降落的全過程中不需要人工干預(yù)。算法領(lǐng)域最大的進(jìn)步都來自美好的思想，它指引我們更有效地解決計算問題。我們面對的問題絕不局限于狹義的算術(shù)計算，還有很多表面上不是那么“數(shù)學(xué)化”的問題。例如：● 如何走出迷宮？● 如何分割一張藏寶圖讓不同的人分別保存，但只有重新拼合才可能找到寶藏？● 如何規(guī)劃路徑，用最小的成本訪問多個地方？這些問題極具挑戰(zhàn)，需要邏輯推理、幾何與組合想象力，還需要創(chuàng)造力才能解決。這些就是設(shè)計算法所需要的主要能力。本書包括不同作者撰寫的41篇文章，用非技術(shù)化的語言介紹了一些最著名的算法思想。多數(shù)文章源自德國大學(xué)中發(fā)起的科普活動，初衷是讓高中生領(lǐng)會算法和計算機(jī)科學(xué)的奇妙與魅力。閱讀本書不需要任何關(guān)于算法和計算的預(yù)備知識。我們希望不僅學(xué)生能從本書中得到啟發(fā)和樂趣，那些希望了解迷人的算法世界的成年人也能有所收獲。
本書共有66位作者，主要來自德國、瑞士。由貝特霍爾德·弗金（Berthold V?cking）、赫爾穆特·阿爾特（Helmut Alt）、馬丁·迪茨費(fèi)爾賓格（Martin Dietzfelbinger）、呂迪格·賴舒科（Rüdiger Reischuk）、克里斯蒂安·沙伊德勒（Christian Scheideler）、黑里貝特·沃爾默（Heribert Vollmer）、多蘿西婭·瓦格納（Dorothea Wagner）領(lǐng)銜編著。
目 錄譯者序前言第一部分 搜索與排序第1章 二分搜索 3第2章 插入排序 8第3章 快速排序 11第4章 并行排序—追求速度 18第5章 拓?fù)渑判颉侠戆才湃蝿?wù)執(zhí)行次序 26第6章 快速搜索文本—Boyer-Moore-Horspool算法 32第7章 深度優(yōu)先搜索 39第8章 Pledge算法—如何從黑暗的迷宮中逃脫 48第9章 圖中的回路 52第10章 PageRank—搜索萬維網(wǎng) 60第二部分 算術(shù)與密碼第11章 大整數(shù)相乘—比長乘更快 69第12章 歐幾里得算法 76第13章 埃拉托色尼篩法—計算素數(shù)表能有多快 81第14章 單向函數(shù)的陷阱—掉下去就出不來了 91第15章 一次性加密算法—最簡單、最安全的保密方式 98第16章 公鑰密碼 103第17章 如何共享機(jī)密 112第18章 通過電子郵件玩撲克 119第19章 指紋 128第20章 哈希方法 138第21章 編碼—防止數(shù)據(jù)出錯或丟失 143第三部分 規(guī)劃、協(xié)同與模擬第22章 廣播—如何迅速發(fā)布信息 155第23章 將數(shù)字轉(zhuǎn)換為英語單詞 161第24章 確定多數(shù)—誰當(dāng)選為班級代表 166第25章 隨機(jī)數(shù)—如何在計算機(jī)中創(chuàng)造隨機(jī) 172第26章 火柴游戲的取勝策略 179第27章 體育聯(lián)賽日程編排 184第28章 歐拉回路 190第29章 快速畫圓 195第30章 計算物理問題的高斯–賽德爾迭代 202第31章 動態(tài)規(guī)劃—計算進(jìn)化距離 208第四部分 優(yōu) 化第32章 最短路徑 215第33章 最小生成樹—有時貪心也有回報 221第34章 最大流—在高峰時刻去體育場 226第35章 婚姻介紹人 235第36章 圓閉包 243第37章 在線算法 246第38章 裝箱問題 251第39章 背包問題 257第40章 旅行推銷商問題 263第41章 模擬退火 270
書單推薦
