一点排行网
当前位置:一点排行网 > 电视 > 正文

计算机程序设计艺术(计算机程序设计艺术 pdf)

“风味人间”%title插图%num

所谓美食,不过是一次又一次的相逢。我们带您穿越山海之间,偶尔的落地生根,成就万千肴变,随即化作滚滚红尘,穿越香料歧路,几度江湖夜雨后,点亮万家灯火。《风味人间》

浮华随风去,一菜一江湖。无论置身繁华闹市,还是身居乡野陋巷,世上的滋味,就这样流转于方寸餐桌,交织在冷暖人间。我们说五味杂陈,这五味就是酸、苦、甘、辛、咸。

%title插图%num

而我们日常食物中的食材种类可谓是丰富多彩了。简单列一下日常主要食物食性分类表:一、寒凉类食物1、粮油类:小米、大麦、荞麦、绿豆、薏苡仁、麻油、猪油、豆腐、黄豆芽、绿豆芽、淡豆鼓、麦芽2、蔬菜类:芹菜、菠菜、蕹菜、苋菜、大白菜、莼菜、紫菜、甜菜、油菜、黄花菜、薇菜、生菜、丝瓜、黄瓜、冬瓜、苦瓜、竹笋、芦笋、莴苣笋、茄子、番茄、茭白、百合、荸荠、莲藕、慈姑、马兰头、马齿苋、枸杞头、白萝卜、青萝卜、菜瓜、葫芦、蘑菇、草菇、海带、葛根、鱼腥草、苤蓝3、鱼肉类:羊肝、鸭肉、鸭血、兔肉、鸭蛋、黑鱼、田螺、螺蛳、蟹、蚌、蛤蛎、牡蛎、蛏、河蚬、青蛙、牛乳、发菜4、水果类:梨、柑、柚子、罗汉果、柿子、杨桃、芒果、猕猴桃、香蕉、橙子、草莓、西瓜、甜瓜、胖大海、余甘子、栀子5、其 他:食盐、白糖、蜂蜜、酱油、酱、茶、啤酒、薄荷、菊花、淡竹叶、金银花、决明子、菊苣、菰米、鲜白茅根、鲜芦根、桑叶二、平性类食物1、粮油类:小麦、燕麦、玉米、粳米、黄豆、黑大豆、玉米油、赤小豆、白扁豆、黑芝麻、花生、花生油、豆腐浆、豆腐皮、腐乳、大豆黄卷2、蔬菜类:荠菜、花菜、卷心菜、蓬蒿菜、青菜、塌棵菜、西洋菜、清明菜、北瓜、马铃薯、芋艿、山药、胡萝卜、苜蓿、芡实、香菇、猴头姑、木耳、银耳、蒲公英、豌豆、蚕豆、四季豆、扁豆、荷兰豆、西兰花、甘薯、豇豆、金针菇3、鱼肉类:猪肉、猪心、猪肝、猪脑、猪骨、火腿、牛肚、鸡肫、鹅肉、鹌鹑肉、鸽肉、鸡蛋、鹅蛋、鹌鹑蛋、鸽蛋、青鱼、鲤鱼、鲫鱼、鲈鱼、刀鱼、鲥鱼、鲟鱼、鳗鲡、白鱼、银鱼、黄鱼、鲳鱼、鳜鱼、鳐鱼、墨鱼、鲨鱼、橡皮鱼、鳖、海蜇、人乳、乌梢蛇4、水果类:枇杷、桑椹、莲子、枣、榛子、苹果、无花果、梅子、乌梅、菠萝、甘蔗、橘仁、香榧、菱角、葵花子、西瓜子、枸杞子、枣仁、桃仁、白果、郁季仁、火麻仁、刺梨5、其 他:味精、甘草、茯苓、菜菔子、代代花、荷叶、鸡内金三、温热类食物1、粮油类:高粱、籼米、糯米、牛油、菜油、豆油2、蔬菜类:芥菜、韭菜、大头菜、南瓜、刀豆、香椿头、芫荽、辣椒、大蒜、葱、洋葱、生姜、平菇、金瓜、木瓜、魔芋3、鱼肉类:猪肚、牛肉、牛骨髓、羊肉、羊肚、羊脑、狗肉、鸡肉、麻雀肉、雉肉、草鱼、鲢鱼、鳙鱼、鳊鱼、鳟鱼、塘鳢鱼、带鱼、黄鳝、泥鳅、蚶、河虾、海参、鲍鱼、羊乳、淡菜4、水果类:桃子、李子、葡萄、龙眼、椰子、橄榄、杏子、杏仁、橘子、金橘、荔枝、柠檬、樱桃、杨梅、石榴、槟榔、香橼、佛手、山楂、栗子、松子、南瓜子、核桃、益智5、其 他:红糖、桂花、桂皮、花椒、胡椒、茴香、八角茴香、丁香、砂仁、薤白、玫瑰花、玉兰花、醋、咖啡、米酒、白酒、黄酒、葡萄酒、红花、肉豆蔻、紫苏、陈皮、五香粉、高良姜、肉桂、白芷、藿香、沙棘、黄芥子

这食材,就像是程序设计中的数据结构 Number、String、Array、List、Link、Map、Tree 、Graph 等,组合成不同的抽象数据类型(ADT),你也可以理解成数据结构、模型、类、对象等范畴。

%title插图%num

然后,这些食材怎样早就这“风味人间” (互联网软件系统、虚拟数字世界)呢?这就必须要来好好讲讲“烹饪技法”了。做菜所要的时间和调料是非常讲究的,做到位了,所做的菜的营养、色味俱全,让人吃了回味无穷,即养身体又养眼。

炒爆熘炸烹…… 让我们来看看百度百科上列出的26种烹饪技法:

1 炒2 爆3 熘4 炸5 烹6 煎7 贴8 烧9 焖10 炖11 蒸12 氽13 煮14 烩15 炝16 腌17 拌18 烤19 卤20 冻21 拔丝22 蜜汁23 熏24 卷25 滑26 焗

厨艺世界的艺术,类比到计算机程序设计领域里面就是:

风味 = 食材 + 烹饪方法程序 = 数据结构 + 算法

Tips:类比是思想之基。参考:《表象与本质》(Surfaces and Essences) , 作者: [美]侯世达 / [法]桑德尔。当一个人深深地沉浸在某个活动,或被某个极不寻常的事迷住时,这强烈的兴趣可能会使大量的类比不请自来,涌入脑中。而且,是那些绝不会在其他地方产生的类比。这一现象,就像是类比的阿喀琉斯之踵,它可能会导致我们对情境产生荒诞的理解,并最终作出十分糟糕的决定。不过,在着迷的时候容易作出不同寻常的类比,这同样也是伟大灵感的源泉。准确来讲,正着迷时,发现的相似之处大部分没什么深刻的见解,但时不时的,这种由类比引来的联系,就会成为人类思维奇迹的神来之笔。实际上,当一个人对某物着迷的时候,到处都会看到有关他所迷恋事物的类比,这发生在生活的每一个角落,日夜不停。而且,每一件很微小的事都有可能对应上所迷恋事物的一部分。所以说,尽管并不常见,但有时这种不可抗拒的冲动真的会创造出非比寻常的事。—— 引自章节:5 类比如何操纵我们

做美食,品的是风味,尝的是人间。做程序,思的是理想,考的是现实。

程序设计是一门艺术

我们不得不接受这样一个事实:

一个未知的、无序的世界,是不可能实现“程序”的。

于是,我们抽象它,建立模型——把问题转化为结构,或者对象,或者列表,或者映射表,或者树,或者网,或者某个可以用具体规则步骤描述的事物——这就是“算法”,然后,用编程语言来表达之,或为手机APP,或为PC 网页,或为图画,或为声音,或为视频,或为3D、4D虚拟现实世界。

同样的食材,不同厨师做出来的味道,自然是千差万别。那么,同样的数据结构,不同程序员设计出来的算法和写出来的代码,实现出来的系统,自然也是不同的。

风味,不是一蹴而就,需要时间与火候;画作,不是寥寥几笔,需要不断揣摩线条、色彩、构图、光线。在追求探索美味与美色的道路上,食艺家与画艺家需要达到禅的境界,在仿佛时间静止的流动中,付出全情之投入与专注。

同样的,一个美妙的系统,代码,架构——我们这些程序艺家门,也需要臻于至善之境——禅。

%title插图%num

编程是一门艺术——我们不得不承认。这里面倾注了人类高度的创造性与智慧。

程序设计艺术欣赏:KMP 算法&源代码

,时长09:59

KMP 源代码(Kotlin语言):

/**
* getNext (pattern) 函数: 计算字符串 pattern 的最大公共前后缀的长度 (max common prefix suffix length)
*/
fun getNext(pattern: String): IntArray {
val n = pattern.length
val next = IntArray(n, { -1 })
var j = 0
next[0] = j
(1 until n).forEach {
val i = it
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j – 1]
}
if (pattern[i] == pattern[j]) {
j++
}
next[i] = j
}
return next
}

/**
* kmp substring search algorithm
* @param text : the source text
* @param pattern : the search pattern
*/
fun kmp(text: String, pattern: String): Int {
val m = pattern.length
val n = text.length
if (pattern.isEmpty()) {
return 0
}
// j: the current index of pattern
var j = 0
val next = getNext(pattern)
(0..n – 1).forEach {
// i: the current index of text
val i = it
while (j > 0 && text[i] != pattern[j]) {
j = next[j – 1]
}
if (text[i] == pattern[j]) {
j++
}
if (j == m) {
return i – m + 1
}
}
return -1
}

fun main() {
var text = "addaabbcaabffffggghhddabcdaaabbbaab"
var pattern = "aabbcaab"
print("${getNext(pattern).joinToString { it.toString() }} \n")

var index = kmp(text, pattern)
println("$pattern is the substring of $text, the index is: $index")

text = "hello"
pattern = "ll"
print("${getNext(pattern).joinToString { it.toString() }} \n")

index = kmp(text, pattern)
println("$pattern is the substring of $text, the index is: $index")

text = "abbbbbbcccddddaabaacabdcddaabbbbaad"
pattern = "aabaacab"
print("${getNext(pattern).joinToString { it.toString() }} \n")

index = kmp(text, pattern)
println("$pattern is the substring of $text, the index is: $index")

}

// 输出:
//0, 1, 0, 0, 0, 1, 2, 3
//aabbcaab is the substring of addaabbcaabffffggghhddabcdaaabbbaab, the index is: 3
//0, 1
//ll is the substring of hello, the index is: 2
//0, 1, 0, 1, 2, 0, 1, 0
//aabaacab is the substring of abbbbbbcccddddaabaacabdcddaabbbbaad, the index is: 14

第一性原理

任何事物背后必有道理。

什麼是第一性原理

第一性原理(First Principle Thinking),指的是回歸事物最基本的條件,將其拆分成各要素進行解構分析,從而找到實現目標最優路徑的方法。

%title插图%num

該原理源於古希臘哲學家亞里士多德提出的一個哲學觀點:

“每個系統中存在一個最基本的命題和假设,它不能被違背或刪除。”

%title插图%num

这个“最基本的命题和假设” 就是第一性原理(大前提)!

命题:通常指表达判断的句子,即有真假的语句 。如"黄金是贵重金属"这个句子就是一个命题。假设:以已有事实材料和科学理论为依据,对未知事实或规律所提出的一种推测性说明,即假定 。假设需要以附加前提条件的命题形式表达。

欧几里得把最基本的命题或假设定义为公理和公设,以此为基础演绎出欧式平面几何体系。

公理:指在许多科学分支中所共有的一个不证自明的假设。公设:指在科学领域基础中,某些未经证明而被接受的附加假定,此类假定称为公设。

公理与公设差别:公理是许多科学分支共有的,而各个科学分支中的公设则是不同的,公设的有效性必须建立在现实世界的经验上。

第一性原理强调从最基础的公理和假设出发,演绎推理整个理论体系和模型。把它转化成公式就是:

第一性原理(公理或假设)+ 演绎推理 = 思想或学科体系。

图示如下:

%title插图%num

举例说明:

%title插图%num

%title插图%num

%title插图%num

一个思想或学科体系,是以第一性原理为基础,演绎推理出来的。

爱因斯坦说:理论家的工作可分成两步,首先是发现公理,其次是从公理出发推出结论。

所以,建立一个体系,要从第一性原理开始;而学习一个体系,更要从第一性原理开始,才能理论指导实践!

埃隆·馬斯克与第一性原理%title插图%num

“鋼鐵俠”埃隆·馬斯克(特斯拉汽車CEO)。他曾在採訪中提到自己特別推崇“第一原理”思考法:“通過第一原理,我把事情升華到最根本的真理,然後從最核心處開始推理。”

我們運用第一性原理,而不是比較思維去思考問題是非常重要的。我們在生活中總是傾向於比較,對別人已經做過或者正在做的事情我們也都去做,這樣發展的結果只能產生細小的迭代發展。

%title插图%num

第一性原理的思想方式是用物理學的角度看待世界,也就是說一層層撥開事物表象,看到裡面的本質,再從本質一層層往上走。” 這是他眼中的“第一性原理思維模型”——回溯事物的本質,重新思考怎麼做。

%title插图%num

十幾年前,傳統鋰電池組價格曾長期居高不下,這很大程度影響了特斯拉電動車的大眾化之路。於是,創始人馬斯克回歸電池組的最基本要素,思考電池組是由哪些材料組成的?這些原料的市場價格是多少?結果他發現,如果從倫敦金屬交易所購買電池組所需的碳、鎳、鋁等原材料,再由特斯拉自己建廠研發製造,而不是直接購買供應鏈產品,電池投產之後的價格可以下降30%。

馬斯克的這種思維就是運用了“第一性原理”,並且他非常推崇使用該原理解決問題,這使他在電動汽車、航空航天、清潔能源等領域都取得了一些顛覆性的創新。

如何運用第一性原理

第一,以最本質最基礎的無法改變的條件作為出發點。

如果不是從事物最基本的條件出發,那麼拆分出的要素很可能發揮不了作用。同樣是為瞭解決電動車鋰電池組成本過高的問題,如果馬斯克把作為出發點的基礎條件放在供應商身上,試圖說服供應商降價,不僅可能吃閉門羹,甚至可能讓雙方的關係緊張。更可行的思路是解決電池的原料問題,因為電池的原材料是相對固定的,這才是最基礎的出發點。

第二,推演過程需要有嚴密的邏輯關係,儘量少引入估計。

之所以說運用第一性原理會消耗更高的認知能量,正是因為整個推演分析的過程必須保證合理可靠,否則就可能失之毫釐,謬以千里。整個過程就變成了做無用功。當然,這需要豐富的知識儲備、生活經驗和思維訓練作為支撐。

第三,不可隨意參照同類方案或現有經驗,尊重客觀推演結果。

要做好“找準出發點”和“保證邏輯關係”這兩點,最重要的就是學會保持“空杯心態”,在推演分析時屏蔽現有的、已知的各種因素的干擾。沒有了參照,有時可能會產生看似天馬行空的想法。如果出發點和邏輯關係都沒有問題,那麼就應該尊重客觀推演的結果,也許這就是一個蘊含著巨大價值的天才想法。

第一性原理思考舉例

1.鍵盤滑鼠是我們的真實需求嗎?

我們使用鍵盤滑鼠的本質目的是什麼——向電腦輸入指令和信息。為啥要用鍵盤滑鼠,因為技術限制,我們只能通過這樣的方式向電腦輸入指令和信息。但是,如果我們的大腦能夠直接與電腦交互,那我們就不需要鍵盤滑鼠了。可是我們長時間以來習慣了用鍵盤和滑鼠,所以在大多數人的認知中,電腦就應該長成那樣,有屏幕,有鍵盤,有滑鼠,或者觸摸屏。大部分人固化了這個認知,但伊隆·馬斯克卻用批判性思維和懷疑的精神拷問這個認知,於是有了他的另一個項目——neuralink(腦機融合)

2.“便利的獲取內容”更重要

20世紀80年代,互聯網誕生早期,多數互聯網企業都傾力於為網民提供各種網站內容,80後應該有印象,我們一上網就登錄搜狐、新浪之類的門戶網站。

但遠比門戶時代更早的十多年前,就有兩個年輕人認為:比起內容本身,如何讓用戶“便利的獲取內容”更重要,這將產生萬億美元級的市場潛力。那個年代,網民總量少、互聯網上內容稀少、許多服務還是付費,如果這兩個年輕人對外宣揚這種想法,公眾只會嗤之以鼻,沒人會認為他們高瞻遠矚。

但歷史證明,少數人的觀點多半是對的。這兩個年輕人是布林和佩奇,Google創始人。他們對互聯網產業的核心洞察:“便利、免費”貫穿了Google從創立到強盛的整個歷程。

什么是禅?

禪,是人類鍛鍊思維生發智慧的生活方式。

禪,是一種基於「靜」的行為。

「禪」是佛教"禪那"的簡稱,梵語的音譯。意指排除雜念,靜坐。

日本的禪讀成Zen,中國的禪讀成Chan,中國的禪來源於印度,Chan(禪)為Channa(禪那)的簡稱,而Channa則譯自巴利語(Pali)或普拉克利特語(Prakrit)的Jhana,最終源於梵語的Dhyana。

《劍橋高階英漢雙解詞典》中Zen的本義解釋如下:A form of Buddhism, that emphasizes that religious knowledge is achieved through emptying the mind of thoughts and giving attention to only one thing, rather than by reading religious writings。

寂靜而審慮,靜即定,慮即慧,定慧,均等之妙體,曰"禪那"。也就是佛家一般講的參禪。虛靈寧靜,把外緣(外在事物)都摒棄掉,不受其影響;把神收回來,使精神返觀自身(非肉身)即是"禪"。

大體與現在人們講的心流、全情投入、認真專注等同義。

水往低處流,雲在天上飄,一切都自然和諧地發生,這就是平常心。擁有一顆平常心,人生如行雲流水,回歸本真,寧靜的心,質樸無瑕,這便是參透人生,心如止水,物我兩忘,波瀾不驚——便是禪。

宋代青原惟信禪師說過一段很有名的話:「老僧三十年前未參禪時,見山是山,見水是水;及至後來,親見知識,有個人處,見山不是山,見水不是水;而今得個休歇處,依前見山只是山,見水只是水。」這道出了禪宗的三種境界。  第一境界:見山是山,見水是水,是執迷於塵世外物界。  第二境界:見山不是山,見水不是水,是對世俗的否定。  第三境界:見山只是山,見水只是水,是放下一切,萬法隨緣。  對此,另外還有一個著名的說法。宋代禪宗將參禪分為三個境界,是對佛教「空」這一概念的三種不同理解。  第一境界:落葉滿空山,何處尋芳跡。不知道禪為何物,即使就在你身邊,也無從下手。  第二境界:空山無人,水流花開。初窺門路,能以平常心修行,但身邊有草葉。  第三境界:萬古長空,一朝風月。大師境界,無相,世界為「一」。  第一境是苦苦尋覓,第二境是似有所悟,第三境是頓悟永恆。

計算機程序設計藝術,參透了,便不複雜,很簡單,臻於至善至美之藝境也。

程序 = 数据结构 + 算法

“数据结构和算法是过去 50 年来最重要的发明之一,它们是软件工程师需要了解的基础工具。” 《Think Data Structures: Algorithms and Information Retrieval in Java》(Allen B.Downey)

基本数据类型

道生一,一生二,二生三,三生万物。

计算机程序设计的世界里,先有基本数据类型,复合组装成复杂对象类型,不同对象之间再进行交互操作,进而形成丰富多彩的虚拟世界。

其实,这个过程中的原理,跟现实世界是一样的。我们人类的脑子里对这个世界的认知,恐怕没有人敢说他真正懂得这个世界本来的样子。仅仅是量子物理的世界跟广义相对论的时空世界,就把这个地球上绝大部分人的脑袋弄迷糊。

我们的数字计算机的世界,是简化了的物理世界——在这个世界里,任何事物的存在,都可以用0和1来表达——清楚简单、准确无误。任何数据结构模型,都是清晰可见的。

我们这里讲的数据结构,对应的是抽象数据类型、类、模型、实体等这些的概念,是数据的逻辑模型,不是数据的物理模型。

如果不了解计算机相关的知识和思想,可能很难明白计算机的工作原理。因为,经历从各层硬件到各层软件的层层抽象后,计算机内部已经复杂得让人难以想象。

比如芯片,指甲盖儿那么大,却有几亿甚至几十亿个晶体管电子器件,每个晶体管电子器件的电流和电压,在1秒内,能变化几亿甚至几十亿次。学过排列组合的朋友,应该知道,芯片内部每时每刻的状态数量,是一个天文数字。

%title插图%num

再比如操作系统。大概有10G的源代码,一Byte一个字符,也就是说有超过100亿个字符,每行按标准80字符来算的话,超过1亿行。WinXP系统有2亿行。Android系统为例,少说点也有1亿行代码。假设一本书有500页 (正反算两页,这已经是一本很厚的书了), 书的单面印50行代码,那么一本书就能印刷25000行代码。如果把操作系统的代码都印刷在书上,那就是4000本书。

当我们拿着手机,聊微信、逛淘宝、刷抖音时,我们是否意识到发生了什么呢?

通过手机app、中间件、操作系统、驱动程序,我们在操纵着手机芯片中的电压和电流,操纵着芯片中的无数分子中的原子中的电子。

我们还利用了麦克斯韦电磁场理论,通过电磁场和电磁波的方式,远程操纵着马化腾的服务器、马云的服务器、张一鸣的服务器的芯片中的无数分子中的原子中的电子。我们用的电,来自几千公里之外的发电厂,通过一百年前特斯拉发明的交流电系统传输到我们房子里面的电路插座……真有点武侠小说的感觉,手指在手机上轻轻一滑,世界各地的计算机芯片中的电子为之一振。

是的,从微观层面讲,那些电子在杂乱无章地“乱窜”,充满着不确定性。但是,通过抽象,我们拥有了宏观层面确定的欧姆定律、基尔霍夫定律。然而,电流电压依然会存在上下轻微波动,并不准确,于是通过再次抽象,我们拥有了确定的与或非门电路;通过再次抽象,我们拥有了确定的芯片;通过再次抽象,我们拥有了确定的驱动程序、操作系统、中间件;最后,我们拥有了确定的、带功能意义的应用程序/app, 于是乎,我们滑动着手机,玩着,乐着。

计算机,从顶层的应用程序往下看,处处都有抽象,处处都是编码和转换。我们没有办法,也没有必要弄清计算机的每个细节,但只要把握住了计算机的工作原理,弄清一些核心概念,还是能在一定抽象度上搞懂计算机。

抽象,是计算机科学和技术中最重要的思想,没有之一。抽象的重要性,在操作系统中的体现尤为明显。

通过层层抽象,我们才可以轻松地聊微信、逛淘宝、刷抖音, 而最背后的最底层,不过是芯片中的电子在“乱窜”而已。

万物皆数:Number毕达哥拉斯:数是宇宙万物的本原

毕达哥拉斯(Pythagoras,约公元前580年~约前500(490)年)古希腊数学家、哲学家。

毕达哥拉斯出生在爱琴海中的萨摩斯岛(今希腊东部小岛)的贵族家庭,自幼聪明好学,曾在名师门下学习几何学、自然科学和哲学。因为向往东方的智慧,毕达哥拉斯经过万水千山,游历了当时世界上两个文化水准极高的文明古国——巴比伦和印度,以及埃及(有争议),吸收了美索不达米亚文明和印度文明的文化。后来他到意大利的南部传授数学及宣传他的哲学思想,并和他的信徒们组成了一个所谓“毕达哥拉斯学派”的政治和宗教团体。

毕达哥拉斯学派认为数是宇宙万物的本原。研究数学的目的并不在于使用而是为了探索自然的奥秘。

事物的性质是由某种数量关系决定的,万物按照一定的数量比例而构成和谐的秩序。从三个苹果等事物中抽象出了五这个数。

%title插图%num

这在今天看来很平常的事,但在当时的哲学和实用数学界,这算是一个巨大的进步。在实用数学方面,它使得算术成为可能。在哲学方面,这个发现促使人们相信数是构成实物世界的基础。

数制

1.十进制数(Decimal)

十进制数是人们十分熟悉的计数体制,它的数码是用0、1、2、3、4、5、6、7、8、9十个数字符号来表示,基数是10,进位规律是“逢十进一”。

为什么现代人普遍使用十进制?在人类发展史上,并不是所有人都选择了十进制。古巴比伦人用的是60进制,玛雅人用的是20进制。罗马人的计数系统干脆就没有进制。古埃及也有类似的情况。所以并不存在什么十进制的必然性。回头去看历史的话,十进制的计数系统在现代占据统治地位很大程度上是历史的偶然。现代的这套“阿拉伯数字”的计数系统其实是古印度人的发明。来自中亚的伊斯兰化的突厥人征服了印度,把印度纳入到了伊斯兰世界。然后阿拉伯人又在长期的征服与贸易的过程中把这套计数系统传播到了世界各地。如果当初占据亚欧交通枢纽的不是阿拉伯人,或者当时巴布尔没有打下印度,那完全有可能我们今天用的计数方式不是十进制,而是十二进制,二十进制或是六十进制之类的。至于说十进制的来源是十根手指头,这只能说是一种可能的猜测。

2.二进制数(Binary)

与十进制数类似,二进制数的数码是用0、1两个数字符号来表示,基数为2,进位规律是“逢二进一”。

数字电子电路中,逻辑门的实现直接应用了二进制。现代的计算机和依赖计算机的设备里都用到二进制。每个数字称为一个比特(Bit,Binary digit)。

3.八进制数(Octonary)

在八进制数中,它的数码是用0、1、2、3、4、5、6、7八个数字符号来表示,基数是8,进位规律是“逢八进一”。

4.十六进制数(Hexadecimal)

在十六进制数中,它的数码是用0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F十六个数字和字母符号来表示,基数是16,进位规律是逢十六进一。

二进制数、八进制数、十六进制数和十进制数之间的对应关系:

%title插图%num

关于有理数、无理数、实数、复数等概念,比如说无限不循环小数,计算机无能为力,没有办法准确表达,只能尽量逼近,近似数值计算。这也是计算机程序设计与纯粹数学理论之间的鸿沟。这就好比是,量子力学的理论多么优美,广义相对论的思想多么宏大,但是,人类就是没办法把两种理论统一放到同一个宇宙体系中。这难道是理想与现实的永恒的裂缝?

计算机世界为什么选择了二进制?

早期的机械式和继电式计算机都用具有10个稳定状态的基本元件来表示十进制数据位0,1,2,…,9。一个数据的各个数据位是按10的指数顺序排列的。例如,从0v到9v, 总共有10个电压位,由于电子线路器件的原因及其内部复杂性,如果一根电线的电压值是7.49v, 那么,请问,它表示的是数字7还是数字8呢?这就尴尬了。

但是,要求处理机的基本电子元件具有10个稳定状态比较困难,十进制运算器逻辑线路也比较复杂。从莱布尼茨到布尔,再到香农,都在苦苦探索着。最后探索出了解决之道:可以使用二进制来计算,然后用电路来实现二进制计算。

用电路来实现二进制表示和二进制计算,我们今天看起来似乎很简单,但探索出这条路,并不容易。莱布尼茨发明了二进制,但他在做自己的乘法器时,并没有意识到二进制的重要性。莱布尼茨终生未婚,在科学和哲学史上,他真可谓是百科全书式的人物。

多数元件具有两个稳定状态,二进制运算也比较简单,而且能节省设备,二进制与处理机逻辑运算能协调一致,且便于用逻辑代数简化处理机逻辑设计。二进制遂得到广泛应用。

逻辑代数%title插图%num

布尔创建了逻辑代数,也称布尔代数,在很大程度上, 为后来的电路设计及其简化,做出了很大的贡献。现在很多编程语言中都内部了布尔类型,以纪念这位先驱。

布尔代数起源于数学领域,是一个用于集合运算和逻辑运算的公式:〈B,∨,∧,¬ 〉。其中B为一个非空集合,∨,∧为定义在B上的两个二元运算,¬为定义在B上的一个一元运算。通过布尔代数进行集合运算可以获取到不同集合之间的交集、并集或补集,进行逻辑运算可以对不同集合进行与、或、非。

20世纪以来,逻辑代数一直是数字电路设计的基础,并且所有现代编程语言提供支持。几乎所有现代通用计算机都用二值布尔逻辑做运算;也就是说它们的电路是二值布尔逻辑的物理表示。几种表示方式:导线上电压的高低,磁性存储设备中磁畴的方向,打孔卡或纸带上的洞,等等。

用电路来实现二进制%title插图%num

香农,正是香农,最先洞察到了开关系统和布尔逻辑之间的关系,并发表了论文《继电器和开关电路的符号化分析》,可以说,这篇文论让人们意识到,可以用电路来实现二进制表示和二进制计算。香农活到了二十一世纪,当他看着这个世界,因为他的贡献而变得如此美好时,内心一定是很欣慰的。

%title插图%num

1938年香农在MIT获得电气工程硕士学位,硕士论文题目是《A Symbolic Analysis of Relay and Switching Circuits》(继电器与开关电路的符号分析)。当时他已经注意到电话交换电路与布尔代数之间的类似性,即把布尔代数的“真”与“假”和电路系统的“开”与“关”对应起来,并用1和0表示。于是他用布尔代数分析并优化开关电路,这就奠定了数字电路的理论基础。哈佛大学的Howard Gardner教授说,“这可能是本世纪最重要、最著名的一篇硕士论文。”

逻辑门%title插图%num

逻辑门是在集成电路上的基本组件。简单的逻辑门可由晶体管组成。这些晶体管的组合可以使代表两种信号的高低电平在通过它们之后产生高电平或者低电平的信号。高、低电平可以分别代表逻辑上的“真”与“假”或二进制当中的1和0,从而实现逻辑运算。通常组合使用实现更为复杂的逻辑运算。一些厂商通过逻辑门的组合生产一些实用、小型、集成的产品,例如可编程逻辑器件FPGA等。

二进制与字符表达

字符信息的表示

1.字符编码

目前主要用ASCII码(American Standard Code for Information Interchange),即美国标准信息交换码,已被国际标准化组织ISO(International Organization for Standardization)定为国际标准。ASCII码采用一个字节(8个二进制位)表示一个字符,ASCII码分为标准ASCII码和扩展ASCII码。

标准ASCII码的最高位为0,其范围用二进制表示为00000000 ~ 01111111,用十六进制表示为00 ~ 7F,用十进制表示为0 ~ 127,共128个编码。在128个编码中,有34个控制字符,52个英文大小写字母,10个数字(0~9),32个字符和运算符(见 书本P19 表1-5标准ASCII码表)。

2.汉字编码

为了能在计算机中处理汉字,就必须对汉字进行编码,但汉字都有自己的形状,其基本字符较多,用一个字节编码显然是不够的。目前的汉字编码方案大多都采用两个字节,例如我国制定的“中华人民共和国国家标准信息交换汉字编码”(GB2312-80),简称国标码。在GB2312-80中规定用两个字节即16位二进制代码表示一个汉字,并且每个字节的高位规定为1,这样只可以表示128 × 128=16384个汉字。

汉字输入码,又称“外部码”,简称“外码”,指用户从键盘上输入代表汉字的编码。为了能直接使用西文标准键盘进行汉字输入,必须为汉字设计相应的编码方法。

区位码是一种最通用的汉字输入码。它是根据国标GB2312-80将6763个汉字和一些常用的图形符号组成一个94×94的矩阵,即有94行和94列。每一行称为一个区,每一列称为一个位,区号与位号组合在一起称为区位码(区位号),它可准确确定某一汉字或图形符号。如汉字“啊”位于16区第01位,则“啊”字的区位码为:区号+位号,即1601。

国家标准GB2312-80中的汉字代码除了十进制形式的区位码外,还有一种十六进制形式的编码,称为国标码。国标码是不同汉字信息系统之间进行汉字交换时所使用的编码,它的编码值不同于区位码,其值是分别对区号、位号增加32(十六进制数20H)。

汉字机内码也称“机内码”,简称“内码”,指计算机内部存储、处理加工和传输汉字时所用的由0和1符号组成的代码。机内码可以通过区位码计算出来,其值是分别对区号、位号增加160(十六进制数A0H)。

3.汉字字库

对于每一个汉字,在计算机内都有对应的字形码和汉字模型(也称字模),所有字模的集合构成了字“模库”,简称“字库”。汉字在输出时,要先找到用于输出的字形码或字模,再将字模输出形成汉字。

汉字字形的构成方法有向量法(也称矢量法、轮廓字形)、点阵法。

%title插图%num

4.汉字处理流程

汉字通过输入设备将外码送入计算机,再由汉字处理系统将其转换成内码进行存储、处理、加工和传送,当需要输出时再由汉字处理系统调用字库中汉字的字形码得到输出汉字的结果

编码与映射的思想数组与链表:Array 与 List映射表:HashMap树与网络结构无穷大是什么?0 代表的概念在物理世界无穷存在吗?计算机二进制简史

1911年:6月15日,华尔街金融投资家弗林特(C.Flent)投资霍列瑞斯的制表机公司,成立了全新的CTR公司,但公司创立之初并没有涉足任何电子领域,反而生产诸如碎纸机或者土豆削皮机之类的产品。

1912年:美国青年发明家德•福雷斯特(L.De Forest)在帕洛阿托小镇首次发现了电子管的放大作用,为电子工业奠定了基础,而今日的帕洛阿托小镇也已成为硅谷的中心地带。

1913年:麻省理工学院教授万•布什(V.Bush)领导制造了模拟计算机“微分分析仪”。机器采用一系列电机驱动,利用齿轮转动的角度来模拟计算结果。

1924年:硅谷之父特曼担任斯坦福大学教授,对创建HP、成立斯坦福工业园区起到决定性作用

2月,由霍列瑞斯创办的制表机公司几经演变,最终更名为国际商用机器公司,即我们今天看到的IBM。

1935年:IBM制造了IBM601穿孔卡片式计算机,该计算机能够在一秒钟内计算出乘法运算。

1936年:阿兰.图灵发表论文《论可计算数及其在判定问题中的应用》,首次阐明了现代电脑原理,从理论上证明了现代通用计算机存在的可能性,图灵把人在计算时所做的工作分解成简单的动作,与人的计算类似,机器需要:(1)存储器,用于贮存计算结果;(2)一种语言,表示运算和数字;(3)扫描;(4)计算意向,即在计算过程中下一步打算做什么;(5)执行下一步计算。具体到一步计算,则分成:(1)改变数字可符号;(2)扫描区改变,如往左进位和往右添位等;(3)改变计算意向等。整个计算过程采用了二进位制,这就是后来人们所称的“图灵机”。

20多岁的德国工程师楚泽(K.Zuse)研制出了机械可编程计算机Z1,并采用了二进制形式,其理论基础即来源于布尔代数

1937年:11月,美国AT&T贝尔实验室研究人员斯蒂比兹(G. Stibitz)制造了电磁式数字计算机“Model-K”。

1938年:克劳德•艾尔伍德•香农(Claude Elwood Shannon)发表了著名论文《继电器和开关电路的符号分析》,首次用布尔代数对开关电路进行了相关的分析,并证明了可以通过继电器电路来实现布尔代数的逻辑运算,同时明确地给出了实现加,减,乘,除等运算的电子电路的设计方法。这篇论文成为开关电路理论的开端。

1939年:元旦,美国斯坦福大学研究生比尔•休利特(B.Hewllet)和戴维•帕卡德(D.Packard)正式签署企业合伙协议,创办了Hewllet-Packard(HP)公司,即国内通称的惠普公司。

9月,贝尔实验室研制出M-1型计算机。

10月,约翰.阿塔纳索夫(John Vincent Atanasoff(1903-1995))制造了后来举世闻名的ABC计算机的第一台样机,并提出了计算机的三条原则,(1)以二进制的逻辑基础来实现数字运算,以保证精度;(2)利用电子技术来实现控制,逻辑运算和算术运算,以保证计算速度;(3)采用把计算功能和二进制数更新存贮的功能相分离的结构。这就是著名的计算机三原则。

1940年:9月,贝尔实验室在美国达特默思大学演示M—1型机。他们用电报线把安置在校园内的M—1型机和相连,当场把一个数学问题打印出来并传输到纽约,M—1型机在达特默思大学的成功表演,首次实现了人类对计算机进行的远距离控制的梦想。

控制论之父维纳提出了计算机五原则,(1)不是模拟式,而是数字式;(2)由电子元件构成,尽量减少机械部件;(3)采用二进制,而不是十进制;(4)内部存放计算表;(5)在计算机内部存贮数据。

1941年:楚泽完成了Z3计算机的研制工作,这是第一台可编程的电子计算机。可处理7位指数、14位小数。使用了大量的真空管。每秒种能作3到4次加法运算,一次乘法需要3到5秒。

1942年:时任美国依阿华州立大学数学物理教授的阿塔纳索夫(John V. Atanasoff)与研究生贝瑞(Clifford Berry)组装了著名的ABC(Atanasoff-Berry Computer)计算机,共使用了300多个电子管,这也是世界上第一台具有现代计算机雏形的计算机。但是由于美国政府正式参加第二次世界大战,致使该计算机并没有真正投入运行。

1943年:贝尔实验室把U型继电器装入计算机设备中,制成了M—2型机,这是最早的编程计算机之一。此后的两年中,贝尔实验室相继研制成功了M-3和M-4型计算机,但都与M-2型类似,只是存储器容量更大了一些。

10月,绰号为“巨人”的用来破译德军密码的计算机在英国布雷契莱庄园制造成功,此后又制造多台,为第二次世界大战的胜利立下了汗马功劳。

1944年:8月7日,由IBM出资,美国人霍德华•艾肯(H.Aiken)负责研制的马克1号计算机在哈佛大学正式运行,它装备了15万个元件和长达800公里的电线, 每分钟能够进行200次以上运算。女数学家格雷斯•霍波(G.Hopper)为它编制了计算程序,并声明该计算机可以进行微分方程的求解。马克1号计算机的问世不但实现了巴贝奇的夙愿,而且也代表着自帕斯卡计算机问世以来机械计算机和电动计算机的最高水平。

1946年:2月14日,美国宾夕法尼亚大学摩尔学院教授莫契利(J. Mauchiy)和埃克特(J.Eckert)共同研制成功了ENIAC (Electronic Numerical Integrator And Computer):计算机。这台计算机总共安装了17468只电子管,7200个二极管,70000多电阻器,10000多 只电容器和6000只继电器,电路的焊接点多达50万个,机器被安装在一排2.75米高的金属柜里,占地面积为170平方米左右,总重量达 到30吨,其运算速度达到每秒钟5000次加法,可以在3/1000秒时间内做完两个10位数乘法。

参考资料

https://www.zhihu.com/question/282808055/answer/973929755https://baike.baidu.com/item/%E4%BA%8C%E8%BF%9B%E5%88%B6/361457https://blog.csdn.net/stpeace/article/details/103317663https://blog.csdn.net/h_kingone/article/details/108749215

物理学史计算机历史半导体物理学半导体器件物理

《禅与计算机程序设计艺术》 / 陈光剑 目录第一性原理什么是禅?什么是计算机?什么是程序设计?什么是艺术?风味人间与计算机程序设计艺术宇宙之起源物质之形成半导体材料纳米光刻二极管、三极管太极阴阳与二进制布尔代数与数字逻辑系统模拟电子电路系统信号与处理信息论图灵机模型冯诺依曼模型计算机演化史什么是编程?编程语言进化史程序 = 数据结构 + 算法模型关系思维真理与模型建筑工程、机械工程、电气工程与软件工程CPU架构设计缓存思想计算机科学中的中间层理论从01机器码到汇编指令到高级编程语言:一切皆是映射美妙的递归用计算机画一张分形图分层思想硬件驱动操作系统通信原理:TCP/IP 与 HTTP 协议、WIFI无线协议互联网简史数据的存储:从ROM、RAM到寄存器到L1/L2 Cache 再到磁盘文件索引原理:来自大自然的启示 Tree 结构人类社会数字化人工智能虚拟现实技术、艺术与禅道

// TODO …… 待续

《禅与计算机程序设计艺术》 / 陈光剑
(今完)

未经允许不得转载:一点排行网 » 计算机程序设计艺术(计算机程序设计艺术 pdf)

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址