數(shù)據(jù)科學(xué)與工程導(dǎo)論IntroductiontoDataScienceandEngineeringGoogle的數(shù)字化開篇實例Google對書籍的處理不僅是掃描，還進(jìn)行了數(shù)字化(Digitizing)與數(shù)據(jù)化(Datafication)，龐大的書籍?dāng)?shù)據(jù)庫甚至孕育了一個新學(xué)科的成立：文化組學(xué)(Culturomics)。GoogleBooksNgramViewer開篇實例比特與數(shù)據(jù)進(jìn)制與數(shù)據(jù)表達(dá)數(shù)據(jù)的編碼與存儲123第3章

數(shù)據(jù)的模型與結(jié)構(gòu)5數(shù)據(jù)的結(jié)構(gòu)數(shù)據(jù)的模型4數(shù)據(jù)的離散化3.1比特與數(shù)據(jù)連續(xù)信號(模擬信號)離散信號(數(shù)字信號)數(shù)據(jù)的離散化3.1比特與數(shù)據(jù)僅表示正負(fù)10數(shù)據(jù)的離散化3.1比特與數(shù)據(jù)010111011001…101110100101…00110010001011011100110001011011……ADDAL,08HMOVBX,AX0011000010000100010100001000000001離散化的目的：表示數(shù)據(jù)、存儲數(shù)據(jù)、處理數(shù)據(jù)計算機(jī)中使用二進(jìn)制表示數(shù)據(jù)、存儲數(shù)據(jù)、處理數(shù)據(jù)二進(jìn)制：01二進(jìn)制與比特3.1比特與數(shù)據(jù)011000011100110110101100比特（位）bit字節(jié)Byte

信號、數(shù)據(jù)、信息和知識3.1比特與數(shù)據(jù)信號數(shù)據(jù)信息知識數(shù)據(jù)傳輸過程中以電磁波的表示形式包括電信號、光信號等分為模擬信號和數(shù)字信號信號、數(shù)據(jù)、信息和知識3.1比特與數(shù)據(jù)信號數(shù)據(jù)信息知識原始信號噪聲疊加后實際傳輸?shù)男盘柦邮斩私獯a后得到的信號數(shù)據(jù)的范疇3.1比特與數(shù)據(jù)信號數(shù)據(jù)信息知識很多人認(rèn)為，數(shù)據(jù)就是數(shù)字，或者必須是由數(shù)字構(gòu)成的，其實不然，數(shù)據(jù)的范疇比數(shù)字要大得多。互聯(lián)網(wǎng)上的任何內(nèi)容（文字、圖片和視頻）；醫(yī)院里包括醫(yī)學(xué)影像在內(nèi)的所有檔案也是數(shù)據(jù)；公司和工廠里的各種設(shè)計圖紙；出土文物上的文字、圖示，甚至它們的尺寸、材料；宇宙在形成過程中的許多數(shù)據(jù)，如宇宙基本粒子數(shù);人類活動本身。數(shù)據(jù)的范疇是隨著文明的進(jìn)程不斷變化和擴(kuò)大的。數(shù)據(jù)與噪音3.1比特與數(shù)據(jù)信號數(shù)據(jù)信息知識數(shù)據(jù)本身是人造物，因此它們可以被隨意制造，甚至可以被偽造。沒有信息的數(shù)據(jù)通常沒有太大意義。例如，優(yōu)化網(wǎng)頁搜索排名而人為制造出來的各種作弊數(shù)據(jù)數(shù)據(jù)常和毫無意義的數(shù)據(jù)和偽造的噪音混在一起；需要過濾掉沒有用的數(shù)據(jù)，從而獲取數(shù)據(jù)背后的信息。信息的含義3.1比特與數(shù)據(jù)信號數(shù)據(jù)信息知識信息是具有時效性的有一定含義的、有邏輯的、經(jīng)過加工處理的、對決策有價值的數(shù)據(jù)流。數(shù)據(jù)中隱藏的信息和知識是客觀存在的，但是只有具有相關(guān)領(lǐng)域?qū)I(yè)知識的人才能將其挖掘出來。數(shù)據(jù)和信息3.1比特與數(shù)據(jù)信號數(shù)據(jù)信息知識人們常常把數(shù)據(jù)和信息的概念混同起來。E.g.數(shù)據(jù)處理和信息處理信息是關(guān)于世界、人和事的描述，它比數(shù)據(jù)來得抽象；而數(shù)據(jù)則是信息的載體。信息既可以是人類創(chuàng)造的，也可以是天然存在的客觀事實E.g.兩個人的語音通話記錄，地球的面積和質(zhì)量信息有時藏在事物背后，需要測量和挖掘才能得宇宙大爆炸的證據(jù)、物理學(xué)定律中的參數(shù)、日月星辰運(yùn)行的周期數(shù)據(jù)和信息3.1比特與數(shù)據(jù)信號數(shù)據(jù)信息知識知識比信息更高一個層次，也更加抽象，它具有系統(tǒng)性的特征。比如通過測量星球的位置和對應(yīng)的時間，就得到數(shù)據(jù)；通過這些數(shù)據(jù)得到星球運(yùn)轉(zhuǎn)的軌跡，這就是信息；通過信息總結(jié)出開普勒三定律，就是知識。人類的進(jìn)步就是靠使用知識不斷地改變我們的生活和周圍的世界，而數(shù)據(jù)是知識的基礎(chǔ)。信號數(shù)據(jù)信息知識從現(xiàn)象到知識3.1比特與數(shù)據(jù)從現(xiàn)象、數(shù)據(jù)到信息、知識，抽象層次是越來越高的。知識的抽象層次是很高的了，而知識中抽象層次最高的，應(yīng)該就是基礎(chǔ)概念。因為這些概念是知識大廈的基石。抽象層次和處理數(shù)據(jù)的能力，也都是衡量文明發(fā)展程度的重要標(biāo)準(zhǔn)。世界是由什么構(gòu)成的3.1比特與數(shù)據(jù)比特與數(shù)據(jù)進(jìn)制與數(shù)據(jù)表達(dá)數(shù)據(jù)的編碼與存儲123第3章

數(shù)據(jù)的模型與結(jié)構(gòu)5數(shù)據(jù)的結(jié)構(gòu)數(shù)據(jù)的模型4什么是進(jìn)制3.2進(jìn)制與數(shù)據(jù)表達(dá)9+11008:5808:5909:00Year2038Problem進(jìn)位制是一種記數(shù)方式，亦稱進(jìn)位計數(shù)法或位值計數(shù)法。利用這種記數(shù)法，可以使用有限種數(shù)字符號來表示所有的數(shù)值。什么是進(jìn)制3.2進(jìn)制與數(shù)據(jù)表達(dá)二進(jìn)制八進(jìn)制十進(jìn)制十六進(jìn)制基數(shù)（底數(shù)）可使用的數(shù)字符號個數(shù)010123456701234567890123456789ABCDEF什么是進(jìn)制3.2進(jìn)制與數(shù)據(jù)表達(dá)1234.5610=1×103+2×102+3×101+4×100+5×10-1+6×10-2101102=1×24+0×23+1×22+1×21+0×203F6B16=3×163+15×162+6×161+11×160位權(quán)該位的單位值R進(jìn)制的位權(quán)是什么？嘗試對八進(jìn)制數(shù)135.27進(jìn)行分解你學(xué)會了R進(jìn)制數(shù)→十進(jìn)制數(shù)二進(jìn)制在計算機(jī)中的應(yīng)用3.2進(jìn)制與數(shù)據(jù)表達(dá)計算機(jī)為何選擇二進(jìn)制？if(x<5)True(1)False(0)易于表示實現(xiàn)簡易抗干擾二進(jìn)制在計算機(jī)中的應(yīng)用3.2進(jìn)制與數(shù)據(jù)表達(dá)從邏輯門到集成電路比特與數(shù)據(jù)進(jìn)制與數(shù)據(jù)表達(dá)數(shù)據(jù)的編碼與存儲123第3章

數(shù)據(jù)的模型與結(jié)構(gòu)5數(shù)據(jù)的結(jié)構(gòu)數(shù)據(jù)的模型4二進(jìn)制編碼的基本概念3.3數(shù)據(jù)的編碼與存儲……..0011010010110011101011010100110101110011……..0x1C250x1C29...地址數(shù)據(jù)1Byte1Byte=8bit1KB=210Byte1MB=210KB———————G–230T–240P–250E–260二進(jìn)制編碼的基本概念3.3數(shù)據(jù)的編碼與存儲100Mbit/s生產(chǎn)商：1KB=1000B計算機(jī)：1KB=1024BASCIIAmericanStandardCodeforInformationInterchange美國信息交換標(biāo)準(zhǔn)代碼基于拉丁字母的一套電腦編碼系統(tǒng)它主要用于顯示現(xiàn)代英語。ASCII碼3.3數(shù)據(jù)的編碼與存儲漢字及其他語言編碼3.3數(shù)據(jù)的編碼與存儲GBK、GB2312、GB18030（中國內(nèi)地）HKSCS（香港）Big5、CNS11643（臺灣）JIS（日本）KSX1001（韓國）KPS9566（朝鮮）Unicode對世界上大部分的文字系統(tǒng)進(jìn)行了整理、編碼，使得電腦可以用更為簡單的方式來呈現(xiàn)和處理文字。????????????包含Emoji表情數(shù)字圖像3.3數(shù)據(jù)的編碼與存儲數(shù)字音頻3.3數(shù)據(jù)的編碼與存儲SoundSampleMIDI數(shù)字視頻3.3數(shù)據(jù)的編碼與存儲FrameFramepersecond幀頻比特與數(shù)據(jù)進(jìn)制與數(shù)據(jù)表達(dá)數(shù)據(jù)的編碼與存儲123第3章

數(shù)據(jù)的模型與結(jié)構(gòu)5數(shù)據(jù)的結(jié)構(gòu)數(shù)據(jù)的模型4數(shù)據(jù)模型是一種抽象模型，用于組織數(shù)據(jù)元素并標(biāo)準(zhǔn)化它們之間的關(guān)系以及與現(xiàn)實世界實體的屬性。例如，數(shù)據(jù)模型可以指定代表汽車的數(shù)據(jù)元素由許多其他元素組成，這些元素依次表示汽車的顏色、尺寸、所有者。程序語言中的數(shù)據(jù)模型數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)系統(tǒng)軟件中的數(shù)據(jù)模型文件、目錄、進(jìn)程什么是數(shù)據(jù)模型3.4數(shù)據(jù)的模型Pythonboolcomplexdict…Cintfloatcharstruct…編程語言中的基本數(shù)據(jù)模型3.4數(shù)據(jù)的模型編程語言中的高級數(shù)據(jù)模型3.4數(shù)據(jù)的模型樹圖列表集合編程語言中的高級數(shù)據(jù)模型3.4數(shù)據(jù)的模型計算機(jī)最為重要的一項應(yīng)用就是存儲和管理數(shù)據(jù)。數(shù)據(jù)的組織方式對訪問和管理信息的容易程度有著深刻的影響。最簡單而最萬能的數(shù)據(jù)組織方式就是將其存儲在表中。關(guān)系模型是這一概念的核心：數(shù)據(jù)被組織成稱為“關(guān)系”的二維表集合。關(guān)系（Relation）數(shù)據(jù)模型關(guān)系中的每個元組都是一列，它表示每個元組中所含組分的數(shù)量。例如，表中的列都被給定了名稱，稱為屬性（attribute）。屬性分別有課程、學(xué)號和成績。編程語言中的高級數(shù)據(jù)模型3.4數(shù)據(jù)的模型模式是具有某個可識別屬性的對象組成的集合。字符串集合就是一類模式。比如C語言合法標(biāo)識符的集合，其中每個標(biāo)識符都是個字符串，由字母、數(shù)字和下劃線組成，開頭為字母或下劃線。另一個例子是由只含0和1的給定大小數(shù)組構(gòu)成的集合，讀字符的函數(shù)可以將其解釋為表示相同的符號。下圖展示了可以解釋為字母“A”的3個7×7數(shù)組。所有這樣的數(shù)組就可以構(gòu)成模式“A”。模式（Patterns）編程語言中的高級數(shù)據(jù)模型3.4數(shù)據(jù)的模型用來查找模式的程序通常有著特殊的結(jié)構(gòu)。我們可以在代碼中確定某些位置，在這些位置可以得知與程序?qū)ふ夷Ｊ綄嵗倪^程有關(guān)的特殊信息。我們將這些位置稱為狀態(tài)。而程序的整體行為可以視作程序隨著讀入輸入從一種狀態(tài)轉(zhuǎn)移到另一種狀態(tài)。表示程序狀態(tài)的圖都是有向圖，它們的弧都是用字符集標(biāo)記的，這樣的圖就被稱為有限自動機(jī)，或就叫自動機(jī)。自動機(jī)（Automata）編程語言中的高級數(shù)據(jù)模型3.4數(shù)據(jù)的模型正則表達(dá)式（RegularExpressions）自動機(jī)定義了模式，即表示自動機(jī)的圖中，作為從起始狀態(tài)到某個接受狀態(tài)的路徑標(biāo)號的字符串組成的集合。正則表達(dá)式與我們熟悉的算術(shù)表達(dá)式代數(shù)，以關(guān)系代數(shù)相似，可以用正則表達(dá)式代數(shù)表示的模式組成的集合，與可以用自動機(jī)描述的模式組成的集合相同。正則表達(dá)式是對字符串操作的一種邏輯公式，就是用事先定義好的一些特定字符、及這些特定字符的組合，組成一個“規(guī)則字符串”，這個“規(guī)則字符串”用來表達(dá)對字符串的一種過濾邏輯。編程語言中的高級數(shù)據(jù)模型3.4數(shù)據(jù)的模型正則表達(dá)式示例功能正則表達(dá)式匹配身份證號(^\d{15}$)|(^\d{17}([0-9]|X)$)匹配電子郵箱

w+([-+.]w+)@w+([-.]w+).w+([-.]w+)*

匹配手機(jī)號\d{3}-\d{8}|\d{4}-\d{7}

中國郵政編碼d{6}中國電話號碼((d{3,4})|d{3,4}-)?d{7,8}(-d{3})*

將一個URL解析為協(xié)議、域、端口及相對路徑/(\w+):\/\/([^/:]+)(:\d*)?([^#]*)/匹配HTML標(biāo)記/<\s*(\S+)(\s[^>]*)?>[\s\S]*<\s*\/\1\s*>/對程序語言設(shè)計的指導(dǎo)面向不同場景豐富內(nèi)置數(shù)據(jù)模型接近人類世界觀對算法設(shè)計的影響對傳統(tǒng)算法的改進(jìn)突破傳統(tǒng)數(shù)據(jù)模型限制對問題的構(gòu)造與求解抽象復(fù)雜問題屏蔽內(nèi)部細(xì)節(jié)數(shù)據(jù)模型的應(yīng)用3.4數(shù)據(jù)的模型數(shù)據(jù)模型的應(yīng)用3.4數(shù)據(jù)的模型數(shù)據(jù)模型的應(yīng)用3.4數(shù)據(jù)的模型比特與數(shù)據(jù)進(jìn)制與數(shù)據(jù)表達(dá)數(shù)據(jù)的編碼與存儲123第3章

數(shù)據(jù)的模型與結(jié)構(gòu)5數(shù)據(jù)的結(jié)構(gòu)數(shù)據(jù)的模型4在數(shù)據(jù)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)是計算機(jī)中存儲、組織數(shù)據(jù)的方式數(shù)據(jù)結(jié)構(gòu)意味著接口或封裝一個數(shù)據(jù)結(jié)構(gòu)可被視為兩個函數(shù)之間的接口或者是由數(shù)據(jù)類型聯(lián)合組成的存儲內(nèi)容的訪問方法封裝。數(shù)據(jù)結(jié)構(gòu)具體指同一類數(shù)據(jù)元素中，各元素之間的相互關(guān)系，包括三個組成部分?jǐn)?shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運(yùn)算結(jié)構(gòu)。什么是數(shù)據(jù)結(jié)構(gòu)3.5數(shù)據(jù)的結(jié)構(gòu)數(shù)據(jù)模型是數(shù)學(xué)抽象數(shù)據(jù)結(jié)構(gòu)是程序表達(dá)數(shù)據(jù)模型與數(shù)據(jù)結(jié)構(gòu)的關(guān)系3.5數(shù)據(jù)的結(jié)構(gòu)數(shù)據(jù)模型數(shù)據(jù)結(jié)構(gòu)代碼實現(xiàn)列表鏈表順序表數(shù)據(jù)結(jié)構(gòu)的研究對象3.5數(shù)據(jù)的結(jié)構(gòu)邏輯結(jié)構(gòu)集合線性結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)元素的機(jī)內(nèi)表示關(guān)系的機(jī)內(nèi)表示順序映像非順序映像常見的數(shù)據(jù)結(jié)構(gòu)3.5數(shù)據(jù)的結(jié)構(gòu)數(shù)組22170-57A[0]A[1]A[2]A[3]A[4]dataindex由相同類型的元素的集合所組成的數(shù)據(jù)結(jié)構(gòu)，分配一塊連續(xù)的內(nèi)存存儲。整數(shù)數(shù)組浮點(diǎn)數(shù)數(shù)組字符串……..22170-57……..4Byte0x1C250x1C2D0x1C290x1C310x1C35常見的數(shù)據(jù)結(jié)構(gòu)3.5數(shù)據(jù)的結(jié)構(gòu)鏈表data每個節(jié)點(diǎn)中存放下一節(jié)點(diǎn)的指針，無須按順序存儲。優(yōu)勢插入新節(jié)點(diǎn)時間復(fù)雜度為常數(shù)級無需預(yù)先確定數(shù)組大小劣勢查找不便……..170x1C3E……..220x1C18……..00x1D2A……..0x1C2522170-5NULLpointer0x1C180x1C3E只允許在有序的線性數(shù)據(jù)集合的一端（棧頂Top）進(jìn)行如下操作入棧（