計算機科學概論（Python版）

目 錄
第　1章 引言　1
1．1　什么是計算機科學　1
1．1．1　數(shù)據(jù)　2
1．1．2　算法　2
1．1．3　編程　4
1．1．4　抽象　5
1．1．5　解決問題和創(chuàng)造力　5
1．2　Picobot　5
1．2．1　Roomba問題　6
1．2．2　環(huán)境　6
1．2．3　狀態(tài)　8
1．2．4　局部思考，全局行動　9
1．2．5　不管怎樣　11
1．2．6　算法和規(guī)則　12
1．2．7　Picobot的挑戰(zhàn)　13
1．2．8　一個迷宮，朋友們　13
1．2．9　不可計算的環(huán)境　15
關(guān)鍵術(shù)語　15
練習　15
判斷題　15
討論題　15
編程題　16
第　2章 函數(shù)式編程（第 一部分）　17
2．1　人類、黑猩猩和拼寫檢查程序　17
2．2　Python入門　18
2．2．1　命名事物　19
2．2．2　名稱中有什么　20
2．3　更多數(shù)據(jù)：從數(shù)字到字符串　20
2．3．1　關(guān)于長度的簡短說明　21
2．3．2　索引　21
2．3．3　切片　21
2．3．4　字符串算術(shù)　22
2．4　列表　23
一些好消息　23
2．5　在Python中使用函數(shù)　24
2．5．1　關(guān)于文檔字符串的簡短
說明　25
2．5．2　關(guān)于注釋的同樣簡短的
說明　26
2．5．3　函數(shù)可以有多行　26
2．5．4　函數(shù)可以有多個參數(shù)　26
2．5．5　為什么要編寫函數(shù)　27
2．6　做出決策　27
2．6．1　第二個函數(shù)示例　29
2．6．2　縮進　31
2．6．3　多重條件　32
2．7　遞歸　33
2．7．1　第 一個遞歸示例：
階乘　34
2．7．2　回到編輯距離函數(shù)　36
2．8　遞歸揭秘　37
2．8．1　調(diào)用函數(shù)的函數(shù)　37
2．8．2　遞歸，真正的揭秘　39
2．9　我們來使用遞歸吧　44
2．9．1　遞歸設計　44
2．9．2　基本情況　44
2．9．3　使用遞歸進行設計　44
2．9．4　遞歸模式　47
2．9．5　可視化工具　47
2．10　取之棄之　48
2．11　編輯距離　52
2．11．1　distance的基本情況　52
2．11．2　distance的遞歸情況　53
2．12　結(jié)論　54
關(guān)鍵術(shù)語　55
練習　56
判斷題　56
填空題　57
討論題　57
編程題　58
第3章　函數(shù)式編程（第二部分）　59
3．1　密碼學和素數(shù)　59
3．2　一等函數(shù)　61
3．3　生成素數(shù)　61
3．4　過濾　65
3．5　lambda　67
3．6　將Google放在map上　69
3．6．1　map　70
3．6．2　reduce　73
3．6．3　組合與mapReduce　74
3．7　函數(shù)作為結(jié)果　75
3．7．1　用Python做微積分　76
3．7．2　高階導數(shù)　77
3．8　再談RSA密碼學　78
3．9　結(jié)論　82
關(guān)鍵術(shù)語　82
練習　83
判斷題　83
填空題　83
討論題　84
編程題　84
第4章　計算機組織　86
4．1　計算機組織概論　86
4．2　表示信息　87
4．2．1　整數(shù)　87
4．2．2　算術(shù)　88
4．2．3　負數(shù)思維　89
4．2．4　分數(shù)：拼接在一起　90
4．2．5　字母和字符串　90
4．2．6　結(jié)構(gòu)化信息　91
4．3　邏輯電路　92
4．3．1　布爾代數(shù)　92
4．3．2　產(chǎn)生其他布爾函數(shù)　93
4．3．3　使用電路的邏輯　95
4．3．4　邏輯計算　97
4．3．5　內(nèi)存　99
4．4　構(gòu)建完整的計算機　100
馮　諾依曼架構(gòu)　102
4．5　Hmmm　104
4．5．1　一個簡單的Hmmm
程序　105
4．5．2　試用　106
4．5．3　循環(huán)　107
4．5．4　函數(shù)　109
4．5．5　使用棧來遞歸　111
4．5．6　保存“珍貴財產(chǎn)”　113
4．5．7　完整的Hmmm指令集　115
4．5．8　最后幾句話　116
4．6　結(jié)論　117
關(guān)鍵術(shù)語　117
練習　118
判斷題　118
選擇題和簡答題　119
討論題　120
邏輯設計與編程題　120
第5章　命令式編程　122
5．1　計算機了解你（比你更了解你
自己）　122
我們的目標：音樂推薦系統(tǒng)　124
5．2　從用戶那里獲取輸入　125
類型轉(zhuǎn)換　125
5．3　重復任務：循環(huán)　126
5．3．1　底層的遞歸與迭代　127
5．3．2　有限迭代：for循環(huán)　128
5．3．3　如何使用循環(huán)控制
變量　129
5．3．4　累積答案　130
5．3．5　處理非預期的輸入　134
5．3．6　不確定迭代：while
循環(huán)　134
5．3．7　for循環(huán)與while循環(huán)　135
5．3．8　故意創(chuàng)建無限循環(huán)　137
5．3．9　迭代是高效的　137
5．4　引用以及可變和不可變數(shù)據(jù)　138
5．4．1　按引用賦值　138
5．4．2　可變數(shù)據(jù)類型能用其他
名稱更改　142
5．5　可變數(shù)據(jù)+迭代：挑選藝人　143
5．5．1　為什么要排序？因為運行
時間很重要　143
5．5．2　一種簡單的排序算法：selectionSort　146
5．5．3　為什么selectionSort
有效　148
5．5．4　一種不同排序的swap　149
5．5．5　二維數(shù)組和嵌套循環(huán)　151
5．5．6　字典　153
5．6　讀寫文件　155
5．7　整合在一起：程序設計　156
5．8　結(jié)論　161
關(guān)鍵術(shù)語　161
練習　162
判斷題　162
選擇題和簡答題　163
討論題　164
編程題　165
第6章　面向?qū)ο蟮某绦颉?67
6．1　簡介　167
6．2　對象式思考　167
6．3　有理數(shù)解決方案　169
6．4　重載　173
6．5　打印一個對象　175
6．6　關(guān)于對象主題的更多討論　176
6．7　用OOP實現(xiàn)圖形　178
6．8　最后，機器人大戰(zhàn)僵尸　181
6．9　結(jié)論　187
關(guān)鍵術(shù)語　188
練習　188
判斷題　188
填空題　189
討論題　189
編程題　190
第7章　問題有多難　192
7．1　永不結(jié)束的程序　192
7．2　3種問題：容易、困難和
不可能　193
7．2．1　容易的問題　193
7．2．2　困難的問題　194
7．2．3　不可能的問題　198
7．3　停機問題：不可計算的問題　205
7．4　結(jié)論　208
關(guān)鍵術(shù)語　208
練習　209
判斷題　209
填空題　209
簡答題和討論題　210