计算机科学导论-计算思维程序实践 课件 L11 难解性问题求解-组合、随机与近似解；L12 机器网络、信息网络与互联网+

第11章难解性问题求解—组合、随机与近似解本章导图难解性问题求解—组合、随机与近似解P类问题NP类问题精确解近似解NPC类问题NPC类问题的解算法计算生物界问题求解思维：过程化理解类比与借鉴趋近于降低计算量算法复杂性计算复杂性可求解问题难求解问题概率与随机过程随机遍历/枚举-验证难解性问题求解—组合、随机与近似解一、可求解与难解性问题二、难解性问题的基本求解策略三、遗传算法的缘起-生物学中的遗传与进化四、计算学科的遗传算法五、用遗传算法求解集合覆盖问题六、遗传算法的进一步探究一个快递公司要在一个拥有8栋住宅楼的小区设立快递柜。可能的设立点有5处，每个点都有服务覆盖范围（50米）。已知每个快递柜能覆盖哪些住宅楼。问最少需要设立几个快递柜才能覆盖全部住宅楼？可求解与难解性问题快递柜选址问题-贯穿本讲的案例【最优化问题】在给定的约束条件下,求解最优的方案使得目标最大化或最小化的问题。快递柜选址问题：约束条件为“覆盖全部住宅楼”，优化目标为“用最少的快递柜数目满足约束条件”。问：生活中有哪些最优化问题和决定性问题呢？可求解与难解性问题最优化问题与决定性问题【决定性问题】回答是和否的问题。例，问题改为：能否建设k个快递柜来满足覆盖全部住宅楼的要求。解空间与最优化问题的精确解解空间是由所有可能的解组成的集合。最优化问题的精确解指的是所有可能的解中符合约束条件和优化目标的解。对解空间中所有可能的解进行遍历，计算并验证每一个解是否符合约束条件。依据优化目标选择最优的解。精确解的求解方法可求解与难解性问题解空间与精确解更一般的问题：住宅楼总数为m，快递柜建设点总数为n。可能解的总数：2n。穷举法：对2n个可能解进行验证。时间复杂度：O(2n)。可求解与难解性问题求解快递柜选址问题精确解的方法问：图中的问题解空间的大小是多少？快递柜建设地点总数n方案总数需要时间5323.2毫秒201百多万100秒501千万亿3570年可求解与难解性问题快递柜选址问题的计算复杂度注：计算机每秒运行百万次，假设验算一个方案需要执行100次基本运算，因此计算机每秒可验算1万个方案。问：试计算n为100时需要多长时间？现实世界中的问题分类计算机在有限时间内能够求解的(可求解问题)计算机在有限时间内不能求解的(难求解问题)计算机完全不能求解的(不可计算问题)指数级复杂度O(bn),O(n!)多项式复杂度O(1),O(logn),O(n),O(nlogn),O(nb)可求解与难解性问题可求解与难解性问题如何分类【可求解问题】存在多项式时间复杂度的求解算法的问题。【难解性问题】不存在多项式时间复杂度的求解算法的问题。【快递柜选址问题是难解性问题】快递柜选址问题到目前为止是不存在多项式时间复杂度算法。【P类问题】多项式问题(PolynomialProblem)，即：可以找出一个呈现O(na)复杂性算法求出精确解的问题，其中a为常数。P类问题是指计算机可以在有限时间内求出精确解的问题，【NP类问题】非确定性多项式问题(Non-deterministicPolynomial)，即：可以找出一个呈现O(na)复杂性算法来验证一个解是否正确的非确定性问题。有些问题，其答案无法直接计算得到，但可通过间接的猜算/试算来得到，这就是非确定性问题(Non-deterministic)。虽然在多项式时间内难于求解，但给定一个解却不难在多项式时间内验证其正确性的问题，即是NP类问题。可求解与难解性问题怎样以复杂性来划分问题【NP-Hard问题】不仅不能在多项式时间内求精确解，而且不一定能在多项式时间内验证一个解的正确性【NPC类问题】完全非确定性多项式问题(NP-Complete)，即：如果NP问题的所有可能解都可以在多项式时间内进行正确与否的验算，且枚举所有可能解的时间复杂性为指数级别，则为NP-Complete问题。NP-Hard问题和NP类问题的交集是NPC类问题。可求解与难解性问题怎样以复杂性来划分问题难解性问题求解—组合、随机与近似解一、可求解与难解性问题二、难解性问题的基本求解策略三、遗传算法的缘起-生物学中的遗传与进化四、计算学科的遗传算法五、用遗传算法求解集合覆盖问题六、遗传算法的进一步探究穷举法或称遍历法：对解空间中的每一个可能解进行计算并验证，直到所有的解都被验证是否正确，便能得到精确的结果---精确解可能是O(n!)或O(an)近似解求解算法---近似解应该是O(na)∆=|近似解–

精确解|满意解：∆充分小时的近似解快递柜选址问题的遍历算法快递柜选址问题的爬山法仿生学算法进化算法，遗传算法，蚁群算法，蜂群算法,…难解性问题的基本求解策略难解性问题如何求解快递柜选址问题是NPC问题难解性问题

难解性问题的基本求解策略快递柜问题的数学模型快递柜选址问题的约束矩阵（m=8，n=5）

住宅楼快递柜x5x4x3x2x1t800011t700010t611010t511000t401100t301100t200101t100001

难解性问题的基本求解策略约束矩阵的行编码行向量A1A2A3A4A5A6A7A8行编码0000100101011000110011000110100001000011快递柜选址问题的约束矩阵（m=8，n=5）

住宅楼快递柜x5x4x3x2x1t800011t700010t611010t511000t401100t301100t200101t100001【快递柜问题的解的编码】X5X4X3X2X1，Xi为1表示建设第i个快递柜，为0表示不建设。例：解01011表示建设第1、2、4个快递柜。可能解的总数：25=32难解性问题的基本求解策略可能解的编码及其验证【判断一个解X能否覆盖全部住宅楼的方法】解X与约束矩阵的行向量依次进行“位与”操作如果每一次运算结果都大于0，说明该编码解能覆盖所有住宅楼问：10101能否覆盖全部住宅楼？

行向量A1A2A3A4A5A6A7A8行编码0000100101011000110011000110100001000011难解性问题的基本求解策略关于【解】的一组概念假设一个问题的解的形式为x，则：可能解：由x的取值空间/定义域给定的任何一个x值可行解：问题通常有很多约束。满足问题所有约束的x值，才是有效的、可行的近似解：由一个算法在任何一组可行解中求出的最优解满意解：符合用户期望的近似解

精确解：所有可行解中的最优解，是问题的最优解【可能解】集合

【可行解】集合

【近似解】集合

【满意解】集合

【最优解/精确解】集合难解性问题的基本求解策略【解】的质量评价方法：目标函数

【例】X=00111编码中有3个1，第一项的结果为3；00111与各个行编码的“位与”结果分别为00001、00101、00100、00100、00000、00010、00010、00011，结果（十进制）为0的总数是1，因此目标函数的结果为：F(00111)=3+1*8=11

行向量A1A2A3A4A5A6A7A8行编码0000100101011000110011000110100001000011难解性问题的基本求解策略快递柜选址问题的所有可能解的目标函数值难解性问题的基本求解策略随机搜索策略【难解性问题难以求解的根本原因】解空间太庞大，无法在合理的时间内进行遍历。【什么是随机搜索策略】随机地在解空间中选择若干可能解构成一个子集，子集的大小以算法能在合理的时间内完成遍历为准；在子集中搜索最优的解。【随机搜索策略的本质】牺牲解的质量来换取求解问题的效率。【随机搜索策略的缺陷】最终近似解的质量完全取决于“运气”，是一种“瞎猫碰死耗子”的行为。难解性问题的基本求解策略提高随机解的质量【如何提高随机解的质量】从一个可能解出发，沿着某个路径找到质量更高的解。【例】解10100，5个二进制位的任何一位的改变，会得到另一个不同的解。【后继解】一个解的二进制编码中的某一位发生变化（0变1或1变0），结果称为后继解。难解性问题的基本求解策略导向性随机搜索策略【什么是导向性随机搜索策略】从一个随机的可能解出发，在可到达的所有后继解中，选择质量最高（目标函数值最小）的解作为下一个解，一直迭代下去，直到无法找到质量更高的解，停止迭代。也叫爬山法。【优点】随着迭代的进行，解的质量会越来越高。【缺点】不一定能导向最优解。最终解的质量受初始解的影响很大。难解性问题的基本求解策略导向性群体随机搜索策略【什么是导向性群体随机搜索策略】随机选择多个可能解作为起点，这些可能解分别使用导向性随机搜索策略搜索近似解，得到一个近似解的集合，最后将集合中目标函数值最低的解作为最终的近似解。【优点】有多条搜索路径，提高了找到满意解的概率。【缺点】不同的搜索路径是各自独立演化的，路径之间没有交流。难解性问题求解—组合、随机与近似解一、可求解与难解性问题二、难解性问题的基本求解策略三、遗传算法的缘起-生物学中的遗传与进化四、计算学科的遗传算法五、用遗传算法求解集合覆盖问题六、遗传算法的进一步探究关于生物遗传进化的基本观点(i)生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状；(ii)染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；(iii)生物的繁殖过程是由其基因的复制过程来完成的；(iv)通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。(v)对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。遗传与进化优胜劣汰遗传算法的缘起--生物学中的遗传与进化生物学中的遗传和进化繁衍后的种群种群新一代种群基因重组新个体的染色体个体A的染色体个体B的染色体染色体B的基因片段染色体A的基因片段个体对环境的适应性:优胜劣汰两个个体新个体

染色体与基因遗传算法的缘起--生物学中的遗传与进化将生物体的遗传与进化理解为【过程】种群(Population)

vs.个体(Individual)

vs.染色体(chromosome)染色体(chromosome)vs.基因(gene)基因型(Genotype)vs.表现型(Phenotype)个体的适应度(Fitness)选择(Selection)复制((Reproduction)交配/杂交(Crossover)突变(Mutation)遗传算法的缘起--生物学中的遗传与进化识别基本概念生物学中的问题求解思想生物学中的问题求解过程与步骤计算学科中的问题求解过程与步骤难解性问题难解性问题的解过程/步骤中的设计技巧具体问题遗传算法的缘起--生物学中的遗传与进化类比中创新问题求解的算法难解性问题求解—组合、随机与近似解一、可求解与难解性问题二、难解性问题的基本求解策略三、遗传算法的缘起-生物学中的遗传与进化四、计算学科的遗传算法五、用遗传算法求解集合覆盖问题六、遗传算法的进一步探究生物学中的概念计算学科中的概念解释计算学科的遗传算法将生物学中的概念映射为计算学科中的概念种群解集/种群若干可能解的集合个体解/个体一个可能解的表现型，本例中即是十进制的X染色体编码解/染色体一个可能解的基因型，本例即是X的二进制编码。X=X5X4X3X2X1，其中Xi=0或1。基因基因解编码中的若干位的Xi适应度适应度对可能解的评价方式，本例直接使用目标函数计算适应度，函数值越小，适应度越高选择选择指从种群(解集)中依据适应度按某种条件选择某些个个体(可能解)复制复制将一个解从一个解集复制到另一个解集交配/杂交交叉即交配/杂交，是新可能解的一种形成方法，即是对两个可能解的编码通过交换某些编码位而形成两个新的可能解的遗传操作突变变异也是新可能解的一种形成方法，它是通过随机地改变一个可能解的编码的某些片段(或基因)而使一个可能解变为一新的可能解的遗传操作计算学科的遗传算法【个体(可能解)的表现形式】

X=0,…,31个体(可能解)的基因形式：染色体

X=X5X4X3X2X1,其中Xi=0or1遗传算法求解快递柜选址问题【初始种群生成方式】随机生成6个0～31之间的数，构成大小为6的种群生成初始种群计算学科的遗传算法遗传算法求解快递柜选址问题【基于竞争的选择操作】以适应度为基础随机选择父本，直接用目标函数作为适应度适应度越高，被选择的概率越大问：10111为什么被选择2次？【不能每次都选适应度最高的个体】都选最高的个体，下一代全是一对夫妻的后代，种群无法进化选择个体成为父本计算学科的遗传算法遗传算法求解快递柜选址问题父本交叉产生子代【交叉操作】父本以较高概率（0.2～0.8）进行交叉交叉的父本形成新的子代（有性繁殖）未交叉的父本直接复制到子代（单性繁殖）计算学科的遗传算法遗传算法求解快递柜选址问题【变异操作】子代以较小概率发生变异，产生新基因概率通常为0.01～0.201111变异为01101子代变异产生新基因计算学科的遗传算法遗传算法求解快递柜选址问题【迭代与终止】新种群继续选择、交叉和变异，一轮轮迭代若达到终止条件，从种群中选出适应度最高的个体为问题的解最终解为：01011终止条件：找到了满意解或达到指定迭代次数新种群进行迭代或终止计算学科的遗传算法遗传算法求解快递柜选址问题【完整求解过程】生成初始种群选择个体为父本父本交叉或直接复制形成子代子代进行变异形成新种群进行迭代或终止最终解为：01011完整过程图示难解性问题求解—组合、随机与近似解一、可求解与难解性问题二、难解性问题的基本求解策略三、遗传算法的缘起-生物学中的遗传与进化四、计算学科的遗传算法五、用遗传算法求解集合覆盖问题六、遗传算法的进一步探究某机构要组织m次讲座，需要租用会议室，有n个会议室可供租用。会议室适合的讲座约束如右表所示。一个会议室可以举办多次讲座。问最少需要租用哪些会议室来完成m次讲座。用遗传算法求解集合覆盖问题会议室租用问题问：与快递柜选址问题有什么区别？会议室租用问题的约束矩阵（m=8，n=5）

讲座会议室x5x4x3x2x1t800011t700010t611010t511000t401100t301100t200101t100001【两类问题的共性】快递柜选址问题和会议室租用问题都是集合覆盖问题。用遗传算法求解集合覆盖问题什么是集合覆盖问题问：生活中还有什么集合覆盖问题？【集合覆盖问题】给定大小为m的全集U和他的一组子集组成的大小为n的集合S，找到S的一个子集X，使得X的并集V等于全集U，此时X称为一个覆盖。给定(U,S)，求所有可能的覆盖中最小的覆盖。集合覆盖问题的约束矩阵（m=8，n=5）

住宅楼/讲座快递柜/会议室x5x4x3x2x1t800011t700010t611010t511000t401100t301100t200101t100001【随机选点法】在解空间中随机选择若干可能解形成初始种群。优点：设计简单且效率较高。缺点：有可能因为解的不均匀分布而漏掉最优解区域。用遗传算法求解集合覆盖问题选择初始种群【均匀网格法】将解空间划分为j个不同区域并在各区域分别随机抽取个体。优点：避免遗漏优质区域。缺点：设计更复杂。Input:种群大小k，编码解的长度nOutput:初始种群的集合populationfunctionGEN-POPULATION(k,n)beginpopulation[1...k]←空集合fori←1tokdopopulation[i]←0～2n-1之间的均匀随机数endforreturnpopulationendbegin【适应度的用途】遗传算法在解空间中搜索满意解的驱动力。用遗传算法求解集合覆盖问题计算个体的适应度【适应度的本质】反映可能解和最优解之间的距离。1Input:编码解X，约束矩阵的行编码数组A，全集大小m，编码解长度n。2Output:编码解X的适应度。3functionFITNESS(X,A,m,n)4begin5part1←X的二进制编码中1的个数6part2←0//惩罚项7fori←1tomdo8ifX与A[i]的位与结果是0then9part2←part2+1//统计未覆盖数目10endif11endfor12returnpart1+m*part2//以m为惩罚系数13endbegin【适应度的设计方法】以优化目标和约束条件为基础设计，本例使用带惩罚项的目标函数。【随机选择的原则】个体的适应度越强，获选的机会越大用遗传算法求解集合覆盖问题选择个体作为父代【适应度选择策略】计算种群中所有个体的适应度根据适应度为每个个体设置选择概率，适应度较高的个体拥有更高的选择概率交叉前，使用两次选择算法选出两个父本用于交叉1Input:种群集合population2Output:population中的一个编码解3functionSELECT(population)4begin5fitnesses[1...n]←population中所有个体的适应度//计算所有个体的适应度并存入数组6probabilities[1...n]←所有个体的选择概率，适应度越高概率越高7i←随机产生的1～n间的数字，且probabilities[i]越大，产生i的概率越高8X←population[i]//以选择概率为基础选择个体9returnX10endbegin【交叉的策略】固定位置交叉/随机位置交叉、两段交叉/多段交叉用遗传算法求解集合覆盖问题父代交叉形成子代【交叉概率】以一定概率（交叉概率，一般0.2~0.8）进行交叉：形成交叉的是有性繁殖，否则是单性繁殖1Input:x1和x2是进行交叉的两个个体，pc为交叉概率2Output:x1与x2交叉后的两个子代的集合3functionCROSSOVER(x1,x2,pc)4begin5p←0~1之间的均匀随机数//决定是否交叉的概率6children[1...2]←空集合7ifp≤pcthen//产生交叉8pos←1~SIZE(x1)-1之间的均匀随机数//决定交叉位置的随机数9children[1]←x1左边第1~pos位拼接x2右边第pos+1~n位//产生一个新个体10children[2]←x2左边第1~pos位拼接x1右边第pos+1~n位//产生另一个新个体11else//不产生交叉12children[1]←x1//x1进行单性繁殖13children[2]←x2//x2进行单性繁殖14endif15returnchildren16endbegin【变异的策略】扰动策略：将编码解中的某个二进制位从0变为1或从1变为0互换策略：将编码解中的不同位置上的两位互换用遗传算法求解集合覆盖问题子代进行随机变异【变异概率】子代发生变异的概率，一般0.01~0.2Input:一个编码解origin，变异概率pmOutput:变异后的编码解functionMUTATE(origin,pm)begin r←0~1之间的均匀随机数 ifr>pmthen returnorigin//不发生变异 endif result←origin i←1~SIZE(origin)之间的均匀随机数 result[i]←1-result[i] returnresultendbegin【新种群】由所有子代构成的种群，新种群与原种群大小一致用遗传算法求解集合覆盖问题形成新种群并进行迭代或终止【迭代与终止】新种群循环地进行选择、交叉与变异，直到满足终止条件P(1)->P(2)->...->P(t)->终止终止条件：（1）算法迭代次数达到了设置的最高次数。（2）算法运行时间超过设置的最高值。（3）已找到符合要求的满意解。（4）适应度已达到饱和，继续进化不会获得适应度更高的解。（5）人为干预终止。（6）以上多个条件的组合。遗传算法完整过程begin//

遗传算法

t←1；//

进化的种群代数

P(t)←GEN-POPULATION(k,n)//生成初始种群P(t);

计算初始种群P(1)中每个个体的适应值；

while

不满足终止条件

do产生空的新种群P(t+1)

whileSIZE(P(t+1))<kdo//确保新种群规模一致

x1←SELECT(P(t))//选择一个父本

x2←SELECT(P(t))//选择另一个父本

child1,child2←CROSSOVER(x1,x2,pc)//交叉产生子代

child1←MUTATE(child1,pm)//子代随机变异

child2←MUTATE(child2,pm)//子代随机变异

将child1和child2加入新种群P(t+1)

endwhile

t←t+1

end

while

returnP(t)中最优个体end

begin用遗传算法求解集合覆盖问题难解性问题求解—组合、随机与近似解一、可求解与难解性问题二、难解性问题的基本求解策略三、遗传算法的缘起-生物学中的遗传与进化四、计算学科的遗传算法五、用遗传算法求解集合覆盖问题*六、遗传算法的进一步探究*难解性问题：解空间巨大，无法在有限时间内遍历整个解空间遗传算法的本质：是一种导向性群体随机搜索策略，限制了解空间搜索范围

遗传算法为什么能求解难解性问题遗传算法的进一步探究【随机性】初始种群的生成、父本的选择、交叉的策略、变异的方式都使用了随机处理机制

【导向性】在选择阶段，通过为适应度较高的个体分配更高的选择概率，将搜索路径导向适应度更佳的方向。【群体性】遗传进化不是单个个体的行为，而是一种群体搜索行为。种群的初始化：随机生成K个个体，K为种群大小种群规模：规模太小，多样性低，不利于种群的迭代演化；规模太大，需要更多的计算力基于概率的随机处理是遗传算法的核心：生成初始种群的随机处理遗传算法的进一步探究选择操作本质上是优胜劣汰，适应度高的个体被选择的概率高基于概率的随机处理方法：以适应度为基础随机选择用于交叉的父本，避免父代永远是适应度最高的2个个体选择概率：在一个群体中，个体被选择出成为父本的概率基于概率的随机处理是遗传算法的核心：选择操作中的随机处理遗传算法的进一步探究问：适应度低的个体的选择概率太低会发生什么？交叉操作本质上是一种组合，交叉组合所形成的可能解空间依然是庞大的，难以确定性的遍历每个组合基于概率的随机处理方法：每次随机选取一个或多个位置进行交叉，每对父本仅产生2个或1个后代，降低计算量

交叉概率：两个父本进行交叉的概率基于概率的随机处理是遗传算法的核心：交叉操作中的随机处理遗传算法的进一步探究010101101010010101101010交叉010101101010010101101010交叉点总计12个,取几个?种群变异操作是产生新基因的唯一途径，不同位置、不同数目的变异组合所形成的可能解空间依然是庞大的，难以确定性的遍历每个组合基于概率的随机处理方法：每次随机选取一位或多位二进制进行变异变异概率：个体进行变异的概率基于概率的随机处理是遗传算法的核心：变异操作中的随机处理遗传算法的进一步探究【选择操作的目的】让适应度较高的个体有更高的概率将基因遗传给下一代。不能每次都选择适应度最高的个体，会让下一代的所有个体都是适应度最高的两个父本的后代，造成种群的多样性不足。选择、交叉与变异操作的目的遗传算法的进一步探究【交叉操作的目的】为遗传算法提供全局搜索能力。交叉的位置可以不同，交叉点的数目也可以不同，能够产生非常多样化的新个体。【变异操作的目的】为遗传算法提供局部搜索能力、维持群体的多样性。

【编码解中什么是遗传基因】“0、1组合相同的片段〞越多是否就是遗传基因呢？例：00101011,00101001,10100101,01100100中自左而右第3和第4位都是“10”，是否是基因？

【如何在交叉时不破坏基因】自然界生物的染色体交叉重组时，不会在基因中间断开。如何在对编码解进行交叉时，确保基因不从中间断开？

染色体编码中的遗传基因遗传算法的进一步探究这些问题都是遗传算法中值得思考和解决的问题【什么是收敛速度】对于具有迭代特征的近似算法，在迭代多少次之后能够使得结果稳定，即结果不再随着进一步的迭代发生变化或发生的变化极小可以忽略不计。收敛速度与解的质量遗传算法的进一步探究【影响收敛速度与解的质量的因素】初始种群的大小：太大导致收敛很慢；太小导致收敛于局部最优解适应度函数的设计：设计合理的适应度函数是算法收敛速度和解的质量的保障选择策略：过于均匀，无法进化从而收敛很慢；过于倾向高适应度个体，会快速收敛于局部最优解变异概率：太低，很难产生新基因从而进化缓慢；太高，容易破坏已有优质基因，收敛速度震荡第12讲

机器网络、信息网络与互联网本讲目标：以信息如何发送为主线，引出两个维度交叉的知识网络，一个维度从网络硬件到网络协议再到应用，另一维度从局域网、广域网、再到物联网社交网络，形成一个知识相关，思维相连的网络知识体系。LC1机器网络：互联互通的物理基础LC2信息网络：基于互联网的内容网络LC3网络与社会思考一下：信息如何从一台计算机传递到另一台计算机？

对比人类快递网络，我们一层一层的分析LC1机器网络：互联互通的物理基础首先了解一下最底层的通讯原理参与者： 信源：发送者 信宿：接受者 信道：传送媒介

LC1机器网络：互联互通的物理基础发送过程： 编码&发送 接收&解码 存储&转发数据交换技术

1、线路交换：线路交换方式在两个网络节点进行数据交换前，必须建立起专用的通信信道。

2、报文交换：通过中间节点进行存储转发，形成间接的通讯。 3、分组交换：分组交换是把长的报文分成若干个较短的报文分组，以报文分组为单位进行交换。LC1机器网络：互联互通的物理基础网络通讯的最简单的形式是实现两台计算机之间的直接通讯，但是随着计算机的增加，当有n个计算机节点时，如果所有节点之间都建立专用的点—点通信线路，即用全连接的方式，将需要n（n-1）/2条线路。计算机网络连接

1、总线型：共用总线，实现简单，但通讯可靠性低。2、星型：连接简单，中心节点要求高。 3、环形：两两相连，可靠性高，稳定性好。LC1机器网络：互联互通的物理基础各自的优点缺点是什么性能指标：

速度、迟延、可靠性传输速率:单位时间内传递信息的数量--每秒内传送的二进制有效位数--比特/秒网络协议的概念

协议：是为两方能够正确实现信息交流而建立的一组规则、标准或约定。 分层结构：设置多层次的协议来完成一个复杂问题的解决 优势：相对独立、 接口简单LC1机器网络：互联互通的物理基础计算机网络连接

1、典型设备 网卡，常具有编码&发送、接收&解码和存储&转发等功能。 集线器：多端口的连接器，有多个端口可以将多台计算机连接起来。 2、连接关系服务器：是持久运行的集中管理网络共享资源、提供网络通信及各种网络服务的计算机系统。客户机：是网络上的个人计算机，一般称为工作站。LC1机器网络：互联互通的物理基础计算机网络连接

典型局域网：以太网 硬件——星型连接，总线结构 软件——载波监听冲突检测 物理地址：为了区分在局域网不同通讯设备之间的身份，网络中每台设备都有一个唯一的网络标识 。LC1机器网络：互联互通的物理基础如何处理冲突010010000001

0010

网际互连

局域网扩大问题 连接成本上升，通讯效率下降 网络互联优势与劣势 通讯局部性原理 通讯复杂度增加 硬件连接

路由器：专用互联硬件设备 软件协议 TCP/IP:传输控制协议和网际协议LC1机器网络：互联互通的物理基础网络与接入

广域网：是指由相距较远的计算机通过公共通信线路互联而成的网络。 公共交换电话网（PSTN） 综合业务数字网（ISDN） 无线网络：无线网络就是利用无线电波作为信息传输的媒介构成的网络。 WIFI，蜂窝网络1G-6G（3G三大标准之一TDSCDMA，4GTD-LTE，5G） 广域网接入：

以太网接入 光纤接入 无线接入

有线电视网络

电话线拨号 ADSL接入

LC1机器网络：互联互通的物理基础因特网与TCP/IP协议TCP/IP模型在物理网基础上建立的，包括：

网络接口层： 网络接口层负责将IP分组封装成适合在具体的物理网络上传输的帧结构并交付传输。

网际层（IP层）： 网络互联的核心设备路由器作用于网际层，网际层协议主要解决两个问题：IP地址与路由

传输层（TCP层）： 负责在源主机和目的主机的应用程序间提供端到端的数据传输服务。

应用层：提供不同的应用层协议，以便能够向用户提供不同类型的网络服务。LC1机器网络：互联互通的物理基础LC1机器网络：互联互通的物理基础网络号机器号A类08162432网络号机器号B类网络号机器号C类011010IP地址设置

网络标识+主机标识 IP地址分类：提供基本的网络划分 子网掩码：提供更加灵活的划分

0000000000000000000000000000000011111111111111111111111111111111子网掩码的前一部分全是1，表示IP地址中对应部分是网络标识符；后一部分全为0，表示IP地址中对应部分是主机编号。A、B、C三类网络的默认掩码为：A类，11111111000000000000000000000000,B类，11111111111111110000000000000000,C类，11111111111111111111111100000000,国际互联网身份

MAC地址：物理层地址 IP地址：网际层地址 域名：应用层地址LC1机器网络：互联互通的物理基础网络标识+主机标识33网络地址主机号为了便于书写和理解，采用点分十进制表示，两个字节中间用“.”分割。主机名.机构名.顶层域名

中国教育部IPv4：32位地址，地址数量为4.3×109IPv6：128位地址，地址数增加到4.3×1038个号称可以为全世界的每一粒沙子编上一个网址，有力地支持了物物互联网络的发展。ABCD:EF01:2345:6789:ABCD:EF01:2345:6789ICANN——CNNIC理解网络传输过程：5个关键环节

LC1机器网络：互联互通的物理基础理解网络传输过程：TCPIP协议进行网络传输过程

LC1机器网络：互联互通的物理基础LC1机器网络：互联互通的物理基础信息共享与标记语言

1、万维网的基本思想在机器互联的物理基础上，计算机之间以向下透明的方式进行应用层通讯，建立起面向内容的复杂信息网络。 发展过程： web1.0以共享为特征

特点：

门户网站集中发布

用户以浏览为主

典型应用：

新浪、百度、谷歌、雅虎

LC2信息网络：基于互联网的内容网络信息共享 1、URL与资源定位2、常见服务LC2信息网络：基于互联网的内容网络URL的组成如:/pub/index.htm12341、服务标志2、主机地址（域名）3、子目录4、文档名超文本传输：HTTP文件传输：FTP远程登录：TELNET电子邮件传输：SMTP信息共享与标记语言

信息的网络化组织——超文本

文本

媒体

超链接

网络化组织信息表达——HTML WEB页面

根据标记语言的信息呈现——浏览器 HTTP协议

LC2信息网络：基于互联网的内容网络结构标记<HEAD>格式标记<P><B>链接标记<AHREF=””>信息共享与标记语言

3、超文本

标记语言：HTML与XMLLC2信息网络：基于互联网的内容网络信息共享 分类检索：将各种概念按照学科、专业性质进行分类和系统排列 信息搜索：自动从Internet搜集信息并检索匹配用户需求返回检索结果 搜索引擎的工作过程： 1）自动搜索网页 2）建立网页索引数据库 3）分析检索条件返回结果LC2信息网络：基于互联网的内容网络倒排索引技术原理：Web2.0

web2.0以交互为特征

特点：

信息双向交互

典型应用：

微博、Facebook、Wiki

微信LC2信息网络：基于互联网的内容网络WEB2.0 1、信息交互特征 双向交互——用户分享 信息聚合——以兴趣为聚合点 开放的平台——优劣 2、推荐系统 基于内容的推荐 协同过滤推荐 基于规则推荐 组合推荐LC2信息网络：基于互联网的内容网络内容推荐： 基于内容的推荐算法的本质是对内容进行分析，建立特征LC2信息网络：基于互联网的内容网络协同过滤： 一般采用最近邻技术，利用用户的历史喜好信息计算用户之间的距离，然后利用目标用户的最近邻居用户对商品评价的加权评价值来预测目标用户对特定商品的喜好程度，系统从