分布式算法作业
2.1 分析在同步和异步模型下，convergecast算法的时间复杂性。
解：
（1）在同步模型中
最坏情况下，算法执行的每一轮中只有一个msg传递，而此时生成树汇聚最大
值的算法最多执行n-1轮（即生成树中除了末端节点每一个节点只有一个子节
点），也就是说同步情况下时间复杂度为O(n-1)
（2）在异步模中
在异步模型的汇集算法的每个容许执行中，树中每个距离p r为t的处理器至多
在时刻t接收消息M，因此对于每个节点而言，它到它所有子节点中t最大的
路径决定了它本身时间花费。因此在最坏情况下，仍应该是同步模型下的最坏
情况，即生成树中除了末端节点每一个节点只有一个子节点，此时时间复杂度
仍为O(n-1)
2.2 G里一结点从pr可达当且仅当它曾设置过自己的parent变量。
证明：
（1）证：一结点从pr可达，则它曾设置过自己的parent变量。
因为图G是由parent和children确定的静态图，任一节点在收到M后才会加入到图中。即可达节点收到过M，执行了算法2.2的第五行。由于是容许执行的，所以第7行（parent:=j）也会执行。
（2）证：一节点设置过自己的parent变量，则其从pr可达。
若算法2.2的第7行执行过了，因为是容许执行，则必然有第5行也执行过了。即节点收到过M。而M又是从pr发出的，所以该节点是从pr可达的。
2.3 证明Alg2.3构造一棵以Pr为根的DFS树。
证明：
（1）算法2.3构造的图G必然是连通的。否则，设G存在邻居节点Pj和Pi。Pj从Pr可达，但Pi从Pr是不可达的。
则：
1）Pi的parent为空；
2）Pi不为Pj的child.
因为：
G里一结点从pr可达当且仅当它曾设置过自己的parent变量。
所以：
1）Pj的parent必然设置过了；
2）Pi的parent为nill；
3）Pi属于Pj的unexplored集合。
而算法的第11和14行决定了Pj会向Pi发送M,使得Pi的parent成为Pj,Pi成为Pj 的child。
这与假设的结果矛盾。故Pi必然也是从Pr可达的。
（2）算法2.3构造的图G必然是无环的。否则设G中有一个环，P1,P2,….,Pi,P1。令P1是该环中最早接收到M的节点。则Pi是从P1可达的，且P1的parent是Pi，P1是Pi 的child。
而Pi在收到M后，向P1发送M。因为P1的parent已经不为空，所以P1收到来自Pi的M时，根据第16行代码，P1会向Pi放回一个
故G是无环的。
（3）图G是一棵DFS树。只需证明在有子结点与兄弟结点未访问时，子结点总是先加入树中。
设有节点P1，P2和P3。P2和P3是P1的直接相邻节点。P1在第12~14行中先选择向P2发送M，则P1当且仅当P2向其返回一个
而P2仅在其向所有的相邻节点发送过M后才会向P1返回
所以P2的子节点是永远先于P3加入树中的，即G是DFS树。
2.4 证明Alg2.3的时间复杂性为O(m)。
证明：
（1）：同步模型：每一轮中，根据算法，有且只有一个消息(M or Parent or Reject)在传输，从算法的第6 、14、16、20、25行发送消息的语句中可以发现：消息只发往一个处理器结点，除根结点外，所有的处理器都是收到消息后才被激活，所以，不存在多个处理器在同一轮发送消息的情况，所以时间复杂度与消息复杂度一致。
（2）异步模型：在一个时刻内至多有一个消息在传输，因此，时间复杂度也与消息复杂度一致。消息复杂度：对任一边，可能传输的消息最多有4个，即2 个M ，2 个相应M 的消息（Parent or Reject），所以消息复杂度为O(m)
综上，该算法的时间复杂度为O(m)
2.5 修改Alg2.3获得一新算法，使构造DFS树的时间复杂性为O(n)。
解：
两种考虑方式：
（1）在每个处理器中维护一本地变量，同时添加一消息类型，在处理器Pi转发M时，发送消息N通知其余的为访问过的邻居，这样其邻居在转发M时便不会向Pi转发。（2）在消息M和
两种方式都是避免向已转发过M的处理器发送消息M，这样DFS树外的边不再耗时，时间。
复杂度也降为O(n)
3.1 证明同步环系统中不存在匿名的、一致性的领导者选举算法。
证明：
在匿名系统中，每个处理器在系统中具有相同的状态机。由Lemma3.1可知，设算法A 是使环上某个处理器为leader 的算法。因为环是同步的，且只有一种初始配置。在每轮里，各处理器均发出同样的message ，所以在各轮里各个处理器接收到相同的message ，则状态改变也相同。所以所有处理要么同为leader ，要么同时不为leader 。
故同步环系统中匿名的、一致性的领导者选举算法的算法是不存在的。
3.2 证明异步环系统中不存在匿名的领导者选举算法。
证明：
每个处理器的初始状态和状态机相同，除了接收消息的时间可能不同外，接收到的消息序列也相同。
所以最终处理器的状态也是一致的。由于处理器处理一条消息至多需要1单位时间，若某时刻某个处理器宣布自己是leader ，则在有限时间内，其它处理器也会宣布自己是leader 。 故异步环系统中匿名的领导者选举算法是不存在的。
3.9 若将环R rev 划分为长度为j(j 是2的方幂)的连续片段，则所有这些片段是次序等价的。 证明：
对一个整数P(0≤P ≤n ?1),可以表示为：
P =∑a i .2i?1m
i=1
其中m=lg n
则有rev (P )=∑a i .2
m?1m i=1。 设P 、Q 在同一个片段上，P1、Q1在同一片段上，且设这两个片段时相邻的，由模运算的加法可得：
P1=P+l
Q1=Q+l
式中l 表示片段的长度，l=2k 。
又
P =∑a i .2i?1m
i=1
Q =∑b i .2i?1m
i=1
且P 、Q 在同一个片段上，有
|P-Q| 所以存在r(0≤r ≤k ),满足a r ≠b r 。否则，|P ?Q|≥l 。这与P 、Q 在同一个片段上矛盾。 设s =min?{r},则根据rev(P),rev(Q)的表示方法可得： sign(rev(P) - rev(Q)) = sign (a s - b s ) 而 m P1=P+l=∑a i.2i?1 +2k i=1 m Q1=Q+l=∑b i.2i?1 +2k i=1 显然，P与P1的前k位相同，Q与Q1的前k位相同。由0≤s≤k得 sign(rev(P1) - rev(Q1)) = sign (a s - b s) 这两个相邻片段是序等价的，根据等价的传递关系，可得所有的片段都是次序等价的。 算法设计与分析实验报告 学院信息科学与技术学院 专业班级软件工程3班 学号 20122668 姓名王建君 指导教师尹治本 2014年10月 实验四 矩阵相乘次序 一、问题提出 用动态规划算法解矩阵连乘问题。给定n 个矩阵{A 1,A 2,…,A n }，其中A i 与A i+1是可乘的，i=1,2,…,n-1。要算出这n 个矩阵的连乘积A 1A 2…A n 。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为： （1）单个矩阵是完全加括号的； （2）矩阵连乘积A 是完全加括号的，则A 可表示为2个完全加括号的矩阵连乘积B 和C 的乘积并加括号，即A=(BC)。 例如，矩阵连乘积A 1A 2A 3A 4有5种不同的完全加括号的方式：（A 1（A 2（A 3A 4））），（A 1（（A 2A 3）A 4）），（（A 1A 2）（A 3A 4）），（（A 1（A 2A 3））A 4），（（（A 1A 2）A 3）A 4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A 是一个p ×q 矩阵，B 是一个q ×r 矩阵，则计算其乘积C=AB 的标准算法中，需要进行pqr 次数乘。 （3）为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A 1,A 2,A 3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A 1A 2）A 3），（A 1（A 2A 3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n 个矩阵{A 1,A 2,…,A n }（其中矩阵Ai 的维数为p i-1×p i ，i ＝1,2,…,n ），如何确定计算矩阵连乘积A 1A 2…A n 的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。 二、求解思路 本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。本实验的算法思路是： 1)计算最优值算法MatrixChain()：建立两张表（即程序中的**m 和**s ，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵…、直到n 个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n 个矩阵相乘的最小运算量；另一张表存储最优断开位置。 2)输出矩阵结合方式算法Traceback()：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程Traceback()完成。分三种情况： （1）只有一个矩阵，则只需打印出A1； （2）有两个矩阵，则需打印出（A1A2）； （3）对于矩阵数目大于2，则应该调用递归过程Traceback()两次，构造出最优加括号方式。 三、算法复杂度 该算法时间复杂度最高为）（n 3 O 。 四、实验源代码 第三章部分习题答案 1、高级调度与低级调度的主要任务是什么？为什么要引入中级调度？ 答：高级调度主要任务是根据某种算法，把外存上处于后备队列中的那些作业调入内存，也就是说高级调度的调度对象是作业。 低级调度主要任务是：决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。 中级调度的任务：使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件且内存又稍有空闲时，由中级调度来决定把外存上的那些又具备运行条件的就绪进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。 2、何谓作业、作业步和作业流？ 答：作业（Job）：作业是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。 作业步(Job Step)。通常，在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，我们把其 中的每一个加工步骤称为一个作业步，各作业步之间存在着相互联系，往往是把上一个作业步的输出作为下一个作业步的输入。 作业流：若干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流。 5、试说明低级调度的主要功能。 答：(1) 保存处理机的现场信息。 (2) 按某种算法选取进程。 (3) 把处理器分配给进程。 6、在抢占调度方式中，抢占的原则是什么？ 答：(1) 优先权原则。 (2) 短作业(进程)优先原则。 (3) 时间片原则。 7、在选择调度方式和调度算法时，应遵循的准则是什么？ 答：面向用户应遵循的准则是：(1) 周转时间短。(2) 响应时间快。 (3) 截止时间的保证。(4) 优先权准则。 面向系统应遵循的准则是：(1) 系统吞吐量高。(2) 处理机利用率好。(3) 各类资源的平衡利用。 《数据库系统基础》课后练习题 数据库系统基础 课后练习题 哈尔滨工业大学计算机科学与技术学院 《数据库系统基础》课后练习题关系代数、关系元组演算、SQL语言 1.分别用关系代数、元组演算、SQL语句完成CAP数据库的查询。 CAP数据库有四个关系(表)： Customers(cid, cname, city, discnt), 客户定义表，描述了客户的唯一标识 cid，客户名称cname，客户所在的城市city，以及该客户购买产品时所可能给予的折扣discnt Agents(aid, aname, city, percent), 代理商定义表，描述了代理商的唯一标识aid, 代理商名称aname, 代理商所在的城市city，以及该代理商销售产品时所可能给予的佣金/提成percent(以百分比形式表达) 哈尔滨工业大学计算机科学与技术学院 《数据库系统基础》课后练习题关系代数、关系元组演算、SQL语言 (1) 找出订单总价大于或者等于$1000的(ordno, pid)对 哈尔滨工业大学计算机科学与技术学院 《数据库系统基础》课后练习题关系代数、关系元组演算、SQL语言 (2) 找出所有价格在$0.50和$1.00之间的商品名字，包括边界价格 哈尔滨工业大学计算机科学与技术学院 《数据库系统基础》课后练习题关系代数、关系元组演算、SQL语言 (3) 找出订单价格低于$500的(ordno, cname)对，使用一次连接 哈尔滨工业大学计算机科学与技术学院 《数据库系统基础》课后练习题关系代数、关系元组演算、SQL语言 (4) 找出所有三月份接受的订单的(ordno, aname)对，使用一次连接 哈尔滨工业大学计算机科学与技术学院 《算法分析与设计》作业( 一) 本课程作业由两部分组成。第一部分为”客观题部分”, 由 15个选择题组成, 每题1分, 共15分。第二部分为”主观题部分”, 由简答题和论述题组成, 共15分。作业总分30分, 将作为平时成 绩记入课程总成绩。 客观题部分: 一、选择题( 每题1分, 共15题) 1、递归算法: ( C ) A、直接调用自身 B、间接调用自身 C、直接或间接 调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模 较小的字问题, 这些子问题: ( D ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是: ( C ) A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的: ( A ) A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是: ( A ) A、最优子结构 B、重叠子问题 C、贪心选择 D、 形函数 6、哈夫曼编码是: ( B) A、定长编码 B、变长编码 C、随机编码 D、定 长或变长编码 7、多机调度的贪心策略是: ( A) A、最长处理时间作业优先 B、最短处理时间作业优 先 C、随机调度 D、最优调度 8、程序能够不满足如下性质: ( D ) A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是: ( A ) A、递归算法 B、动态规划算法 C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题: ( C ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是: ( A ) A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策 有可能导致算法: ( C ) A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到: ( C ) A、全局最优解 B、 0-1背包问题的解 C、背包问题的 解 D、无解 14、能求解单源最短路径问题的算法是: ( A ) A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是: 哈尔滨工业大学 <<数据库系统>> 实验报告之一 (2014年度春季学期) 实验一交互式SQL语言 一、实验目的 ●掌握SQL语句的语法 ●着重熟悉掌握利用SQL编写Select查询的方法 ●熟悉SQLite的用法 二、实验内容 ●1) 双击打开sqlite3.exe，该程序为SQLite数据库管理系统 ●2) 利用.help查看SQLite支持的控制台系统命令。注意系统命令结尾处 没有结束符“;” ●3) 阅读.help中对.databases 命令的说明，并查看输出结果 ●4) 阅读.help中对.open命令的说明，并使用该命令创建一个数据库（名 字任意）后缀名统一为“.db3”（可以没有后缀名，但不推荐） ●5) 再次运行.databases 命令，与步骤3的输出结果对比 ●6) 阅读.help中对.tables命令的说明，并使用该命令查看当前数据库的所 有表 ●7) 创建满足要求的关系表（使用create table） ●表一 ●表名：College（存储大学的信息） ●属性：cName（字符串存储的大学名字），state（字符串格式的大学所在 州），enrollment（整数形式的大学入学学费） ●表二 ●表名：Student（存储学生的信息） ●属性：sID（整数形式的学号），sName（字符串形式的学生名字），GPA （小数形式的成绩），sizeHS（整数形式的所在高中规模） ●表三 ●表名：Apply（存储学生申请学校的信息） ●属性：sID（整数形式的学号），cName（字符串形式的大学名字），major （字符串形式的专业名字），decision（字符串形式的申请结果） ●8）利用.tables查看当前数据库中的表，对比步骤6中的运行结果 ●9) 利用如下命令，将存储在txt文件中的元组导入数据库的关系中●.separator "," ●.import dbcollege.txt College ●.import dbstudent.txt Student ●.import dbapply.txt Apply 第1章分布式计算概述 一、选择题 1，CD 2，ABC 3，ABCD 4，ACD 二、简答题 1，参考1.1.1和节 2，参考1.1.2节 3，分布式计算的核心技术是进程间通信，参考1.3.2节 4，单播和组播 5，超时和多线程 三、实验题 1.进程A在进程B发送receive前发起send操作 进程A进程B 发出非阻塞send操 作，进程A继续运行 发出阻塞receive操 作，进程B被阻塞进程B在进程A发起send前发出receive操作 发出非阻塞send 操作，进程A 继续运行 发出阻塞receive 操作，进程B 被阻塞 收到进程A 发送的数据，进程B 被唤醒 2. 进程A 在进程B 发送receive 前发起send 操作 进程A 进程B 发出阻塞send 操作， 进程A 被阻塞 发出阻塞receive 操作，进程B 被阻塞 进程B 在进程A 发起send 前发出receive 操作 发出阻塞send操作，进程A被阻塞 发出阻塞receive操作，进程B 被阻塞 收到进程A发送的数据，进程B 被唤醒 收到进程B返回的数 据，进程A被唤醒 3.1).在提供阻塞send操作和阻塞receive操作的通信系统中在提供非阻塞send操作和阻塞receive操作的通信系统中2)．P1，P2，P3进程间通信的顺序状态图 m1 m1 m2 m2 第2章分布式计算范型概述 1.消息传递，客户-服务器，P2P，分布式对象，网络服务，移动代理等 2.分布式应用最广泛最流行的范型是客户-服务器范型，参考节 3.分布式应用最基本的范型是消息传递模型，参考节 4.参考节，P2P应用有很多，例如Napster，迅雷，PPS网络电视等 5.参考节 6.参考节 7.略 8.消息传递模式是最基本的分布式计算范型，适用于大多数应用；客户-服务器范型是最 流行的分布式计算范型，应用最为广泛；P2P范型又称为对等结构范型，使得网络以最有效率的方式运行，适用于各参与者地位平等的网络；分布式对象范型，是抽象化的远程调用，适用于复杂的分布式计算应用等。 9.略 10.中间件又称为代理，中间件为参与对象提供内容抽象，隐藏对象引用，起到中介作用。 11.略 第3章 Socket编程与客户服务器应用开发 一、填空题 1.数据包socket，流式socket 2.无连接方式，面向连接方式 3.数据层，业务层，应用层 4.迭代服务器和并发服务器 5.有状态服务器和无状态服务器 二、简答题 1.API：Application Programming Interface,应用程序编程接口，是一些预先定义 的函数，目的是提供应用程序与开发人员基于某软件或硬件得以访问一组例程的能 力，而又无需访问源码，或理解内部工作机制的细节 Socket API：套接字应用程序编程接口，适用于进程间通信的套接字应用程序编程 接口 《算法分析与设计》作业（一） 本课程作业由两部分组成。第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。第二部分为“主观题部分”，由简答题和论述题组成，共15分。作业总分30分，将作为平时成绩记入课程总成绩。 客观题部分： 一、选择题（每题1分，共15题） 1、递归算法：（C ） A、直接调用自身 B、间接调用自身 C、直接或间接调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：（D ） A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是：（C ） A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的：（A ） A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是：（ A ） A、最优子结构 B、重叠子问题 C、贪心选择 D、形函数 6、哈夫曼编码是：（B） A、定长编码 B、变长编码 C、随机编码 D、定长或变长编码 7、多机调度的贪心策略是：（A） A、最长处理时间作业优先 B、最短处理时间作业优先 C、随机调度 D、最优调度 8、程序可以不满足如下性质：（D ） A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是：（A ） A、递归算法 B、动态规划算法 C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题：（ C ） A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是：（A ） A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法：（ C ） A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到：（C ） A、全局最优解 B、0-1背包问题的解 C、背包问题的解 D、无解 14、能求解单源最短路径问题的算法是：（A ） A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是：（ A ） A、舍伍德算法 B、蒙特卡罗算法 C、拉斯维加斯算法 D、数值随机化算法 主观题部分： 二、写出下列程序的答案（每题2.5分，共2题） 1、请写出批处理作业调度的回溯算法。 #include 1.1算法：是对特定问题求解步骤的一种描述，是指令的有限序列。 程序：当一个算法用某种程序设计语言来描述时，得到的就是程序，也就是说,程序是用某种程序设计语言对算法的具体实现. 算法有输入、输出、确定性、能行性和有限性等特征，当不具备有穷性时，只能叫做计算过程，而不能称之为算法，算法可以终止，而程序没有此限制。 1.2程序证明和程序测试的目的各是什么？ 程序证明是确认一个算法能正确无误的工作. 程序测试的目的是发现错误 1-9解: n!的递归定义： 1 1 )! 1 (* { != ≥ - =n n n n n 求解n!的递归函数 long Factorial (long n) { if(n<0) { cout<<”error!”; exit(0); } if(n==0) return 1; else return n *Factorial (n-1); } 1-10使用归纳法，证明上题所设计的计算n！的递归函数的正确性 证明(归纳法证明)： (1)首先，如果n=0，那么程序执行 if(n==0) return 1; 返回1,算法显然正确; (2)假定函数Factorial对n 分布计算环境作业 一．通过生成进程来构建并发服务器与使用多线程来构建并发服务器相比有优点也有缺点，请分析这两种方式的优缺点。你认为基于CORBA实现的并发服务器是基于生成进程的方法，还是基于多线程的方法？为什么？ 并发服务器需要同时处理多个请求。 采用多进程： 优点：1）处理各个请求的进程之间隔离性好。 缺点：1）创建/撤销处理各个请求的进程的代价大；2）分发器（主进程……）将请求发送到另一个进程的代价大（如果能说明为什么代价大更好）；3）如果各个子进程间需要通信，代价大。 采用线程： 优点：1）创建/撤销处理各个请求的线程的代价小；2）分发器（主线程……）将请求发送到另一个线程的代价小（如果能够说明为什么代价小更好）；3）如果各个线程间需要通信，代价小。 缺点：1）一个线程出问题，可能会影响其他线程。 CORBA：使用多线程技术实现并发服务器。因为如果采用多进程实现，有以下问题：1）服务器端要同时维护多个可被用户访问的CORBA对象，这些对象的数量常常会比较大，为每个服务对象起一个进程，进程数会比较大，系统开销过大；2）对于远程方法调用来说，请求的参数比较复杂，主进程将请求再发送给子进程，开销比较大；3）主进程、子进程都需要ORB的Runtime，进程启动/撤销的代价大；所以如果采用多进程的话实现并发CORBA服务器很困难。 主要问题： (一)针对性不够： a)直接罗列进程和线程的优缺点 (二)理由不够充分： a)为支持高并发及高可用，所以多线程或多进程 b)为支持稳定性和健壮性，所以多线程或多进程 c)ORB拿到请求后要决定哪一个对象实例完成这个请求，送过去，这种工作过程类似于线程 《算法分析与设计》作业参考答案 作业一 一、名词解释： 1.递归算法：直接或间接地调用自身的算法称为递归算法。 2.程序：程序是算法用某种程序设计语言的具体实现。 二、简答题： 1.算法需要满足哪些性质？简述之。 答：算法是若干指令的有穷序列，满足性质： （1）输入：有零个或多个外部量作为算法的输入。（2）输出：算法产生至少一个量作为输出。 （3）确定性：组成算法的每条指令清晰、无歧义。 （4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 2.简要分析分治法能解决的问题具有的特征。 答：分析分治法能解决的问题主要具有如下特征： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 答：将递归算法转化为非递归算法的方法主要有： （1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归， 只不过人工做了本来由编译器做的事情，优化效果不明显。（2）用递推来实现递归函数。 （3）通过Cooper 变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。 三、算法编写及算法应用分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 do for j ←1 to n-i do if a[j] 《算法分析与设计》 学习中心： 专业： 学号： 姓名： 作业练习二 一、名词解释 1、MST性质 2、子问题的重叠性质 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质。 二、简答题 1、简述动态规划算法求解的基本要素。 答：动态规划算法求解的基本要素包括： 1)最优子结构是问题能用动态规划算法求解的前提； 2)动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。 2、备忘录方法和动态规划算法相比有何异同简述之。 答：备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。 3、贪心算法求解的问题主要具有哪些性质简述之。 答：贪心算法求解的问题一般具有二个重要的性质： 一是贪心选择性质，这是贪心算法可行的第一个基本要素； 另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。 三、算法编写及算法应用分析题 1、设计求解如下最大子段和问题的动态规划算法。只需给出其递推计算公式即可。 最大子段和问题：给定由n 个整数（可能为负整数）组成的序列a1a2 … an，求该序列形如Σi≤k≤j ak的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义，所求的最优值为max{0, max1≤i≤j≤n Σi≤k≤j ak }。 分布式系统复习题库及答案 1、计算机系统的硬件异构性、软件异构性主要表现在哪几方面？ 参考答案： 计算机系统的硬件异构性主要有三个方面的表现，即： ①计算机的指令系统不同。这意味着一种机器上的程序模块不能在另一种不兼容的机器上执行，很显然，一种机器上的可执行代码程序不能在另一种不兼容的机器上执行。 ②数据表示方法不同。例如不同类型的计算机虽然都是按字节编址的，但是高字节和低字节的规定可能恰好相反。浮点数的表示方法也常常不一样。 ③机器的配置不同。尽管机器的类型可能相同，其硬件配置也可以互不兼容。 计算机系统的软件异构性包括操作系统异构性和程序设计语言异构性。 操作系统异构性的三个主要表现方面为： ①操作系统所提供的功能可能大不相同。例如，不同的操作系统至少提供了不同的命令集。 ②操作系统所提供的系统调用在语法、语义和功能方面也不相同。 ③文件系统不同。 程序设计语言的异构性表现在不同的程序设计语言用不同方法在文件中存储数据。 2、由于分布计算系统包含多个（可能是不同种类的）分散的、自治的处理资源，要想把它们组织成一个整体，最有效地完成一个共同的任务，做到这一点比起传统的集中式的单机系统要困难得多，需要解决很多新问题。这些问题主要表现在哪些方面？ 参考答案： ①资源的多重性带来的问题。由于处理资源的多重性，分布计算系统可能产生的差错类型和次数都比集中式单机系统多。最明显的一个例子是部分失效问题：系统中某一个处理资源出现故障而其他计算机尚不知道，但单机系统任何一部分出现故障时将停止整个计算。另一个例子是多副本信息一致性问题。可见，资源多重性使得差错处理和恢复问题变得很复杂。资源多重性还给系统资源管理带来新的困难。 ②资源的分散性带来的问题。在分布计算系统中，系统资源在地理上是分散的。由于进程之间的通信采用的是报文传递的方式进行的，通信将产生不可预测的、有时是巨大的延迟，特别是在远程网络所组成的分布计算系统中更是这样。例如使用卫星通信会产生270毫秒的延迟。在分布计算系统中，系统的状态信息分布在各个分散的节点上。分布式的状态信息和不可预知的报文延迟使得系统的控制和同步问题变得很复杂，要想及时地、完整地搜集到系统各方面的信息是很困难的，从而使处理机进行最佳调度相当困难。 ③系统的异构性带来的问题。在异构性分布计算系统中，由于各种不同资源（特别是计算机和网络）的数据表示和编码、控制方式等均不相同，这样一来就产生了翻译、命名、保护和共享等新问题。 由于上述原因，分布计算系统的研制，特别是软件的验证、调试、测量和维护问题变得很复杂。这些正是分布计算系统研制者要解决的主要问题。 3、分布式计算系统具有透明性时，系统有什么主要优点？ 参考答案： 系统具有透明性时有以下一些优点： ①使软件的研制变得容易，因为访问资源的方法只有一种，软件的功能与其位置无关。 ②系统的某些资源变动时不影响或较少影响应用软件。 《算法分析与设计》实验指导. 实验一锦标赛问题 [实验目的] 1.基本掌握分治算法的原理. 2.能用程序设计语言求解锦标赛等问题的算法; [预习要求] 1.认真阅读数据结构教材和算法设计教材,了解分治算法原理; 2.设计用分治算法求解背包问题的数据结构与程序代码. [实验题] 【问题描述】设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能参赛一次； （3）循环赛在n-1天内结束。 请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n，1≤j≤n-1。 [实验提示] 我们可以按分治策略将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。 1 2 3 4 5 6 7 1 （1）（2）（3） 图1 2个、4个和8个选手的比赛日程表 图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这 样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。 [实验步骤] 1.设计并实现算法并准备测试用例,修改并调试程序,直至正确为止; 2.应用设计的算法和程序求锦标赛问题; 3.去掉测试程序,将你的程序整理成功能模块存盘备用. [实验报告要求] 1.阐述实验目的和实验内容; 2.阐述分治算法原理; 3.提交实验程序的功能模块; 4.记录最终测试数据和测试结果。 [思考与练习] 【金块问题】老板有一袋金块(共n块，n是2的幂（n>=2）），将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，请用最少的比较次数找出最重和最轻的金块。 第二章 1. 选择题 12345678910 D A B C C E C A B B 1112131415161718 B B B C A D A A 2. 程序/方法与进程/线程有什么不同？（53页第四段） 答：一个程序/方法是由程序员写的一段代码，它是静态的。进程/线程是由执行的程序/方法、当前值、状态信息和用于支持它执行的资源构成，资源是它执行时的动态因素。换言之，一个进程/线程是一个动态实体，只有当程序或函数执行时才会存在。 3. 比较多进程（多任务）操作系统和多线程编程环境。（53页5、 6、7段） 答：为了真正并行执行多个进程/线程，必须存在多个处理器。如果系统中只有一个处理器，表面上多个进程/线程执行，实际上实在分时模式下顺序执行。 从同一代码块可以创建多个进程/线程。默认情况下，包含在不同进程/线程中的代码和数据是分离的，每一个都有它自己执行代码的副本、局部变量的栈、对象数据区以及其他数据元素。 通常情况下，一个分布式操作系统可以由不同电脑上的多个实例或副本构成，每一个实例或副本都可以管理多个进程。同样，每个进程可以是由多个线程组成的一个多线程程序。 4. 什么是临界操作？用什么方法可以来保护临界操作？（54页第1 段） 答：对共享资源的访问称为临界操作。虽然一个简单的锁定可以防止共享资源被访问，但是也消除了并行处理的可能性。更理想的方法是不锁定并行读操作，而锁定并行读-写和写-写组合。 5. 什么是死锁？哪些策略可以用来解决死锁问题？（55页） 答：死锁的情况是两个或多个竞争操作等待对方完成，导致都不能完成。 解决方法： （1） 死锁预防：使用一种算法可以保证不会发生死锁。 （2） 死锁避免：使用一种算法，能够遇见死锁的发生从而拒绝资源请求、 《算法分析与设计》作业（三） 本课程作业由两部分组成。第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。第二部分为“主观题部分”，由简答题和论述题组成，共15分。作业总分30分，将作为平时成绩记入课程总成绩。 客观题部分： 一、选择题（每题1分，共15题） 1、贪心算法解各个子问题的方法是：（） A、自底向上 B、自顶向下 C、随机选择 D、自底向上或自顶向下 2、用回溯法解旅行售货员问题时生成的树是：（） A、子集树 B、排列树 C、二叉树 D、多叉树 3、在n后问题中任意两个皇后能放在：（） A、同一行 B、同一列 C、同一斜线 D、以上都不行 4、用回溯法解0-1背包问题时生成的解空间树是：（） A、子集树 B、排列树 C、二叉树 D、多叉树 5、用贪心算法解单源最短路径问题时采用的算法是：（） A、Dijkstra算法 B、Prime算法 C、Kruskal算法 D、蒙特卡罗算法 6、在用动态规划解流水作业调度时的最优调度法则是：（） A、最优子结构 B、重叠子问题 C、Johnson法则 D、最长处理时间作业优先 7、算法与程序的区别在于：（） A、输入 B、输出 C、指令的确定性 D、指令的有限性 8、从分治法的一般设计模式可以看出，用它设计的程序一般是：（） A、顺序 B、选择 C、循环 D、递归 9、回溯法的解空间是在搜索过程中：（） A、动态产生 B、静态产生 C、无解空间 D、动态或者静态产生 10、在用贪心法解多机调度时的贪心选择策略是：（） A、最优子结构 B、重叠子问题 C、Johnson法则 D、最长处理时间作业优先 11、合并排序和快速排序采用的共同策略是：（） A、分治法 B、蒙特卡罗法 C、拉斯维加斯法 D、单纯形法 12、用回溯法解最大团问题时生成的解空间树是：（） 作业一 学号：______ 姓名：________ P135 2. a.为一个分治算法编写伪代码，该算法同时求出一个元素数组的最大元素和 最小元素的值。 解：算法：EXTREMUM(A[],EXTREMUM_MAX, EXTREMUM_MIN) //递归调用EXTREMUM函数来找出数组A[]的最大元素和 最小元素。 //输入：数值数组A[] //输出：最大值EXTREMUM_MAX和最小值EXTREMUM_MIN if() //只有一个元素 EXTREMUM_MAX A[]; EXTREMUM_MIN A[]; else if //有两个元素 if EXTREMUM_MAX; EXTREMUM_MIN; else EXTREMUM_MAX; EXTREMUM_MIN; else EXTREMUM(,EXTREMUM_MAX_01, EXTREMUM_MIN_01); EXTREMUM(,EXTREMUM_MAX_02, EXTREMUM_MIN_02); if EXTREMUM_MAX_01 EXTREMUM_MAX_02 EXTREMUM_MAX = EXTREMUM_MAX_02; If EXTREMUM_MIN_02 EXTREMUM_MIN_01 EXTREMUM_MIN = EXTREMUM_MIN_02; b. 假设,为该算法的键值比较次数建立递推关系式并求解。 解： c.将该算法与解决同样问题的蛮力法做一个比较 蛮力法时间时间复杂度为2n-2，分治算法的为3n/2-2,虽然都属于Θ(n)级别，但是分治算法速度要比蛮力算法快。 5.1.3 a.为一个分治算法编写伪代码，该算法用来计算指数函数a n的值，其中a>0, n 是一个正整数。 //该算法使用分治法来计算a n Pow(a,n) If n = 1 return a else p←pow(a,n/2); If n mod 2 = 1 return p*p*a; else return p*p; b.建立该算法执行的乘法次数的递推关系式并求解 c.将该算法与解决同样问题的蛮力法做一个比较 蛮力法时间复杂度为n，分治法为,分治法速度明显要 高于蛮力法。 试卷一（哈尔滨工业大学） 一、选择题（每题1分，共20分） 1.在数据管理技术的发展过程中，数据独立性最高的是（）阶段。 A. 数据库系统 B. 文件系统 C. 人工管理 D. 数据项管理 2. （）是存储在计算机内的有结构的数据集合。 A. 网络系统 B. 数据库系统 C. 操作系统 D. 数据库 3. 在数据库的三级模式结构中，描述数据库中全体数据的全局逻辑结构和特征的是（）。 A. 外模式 B. 内模式 C. 存储模式 D. 模式 4. 作为关系数据系统，最小应具备的关系运算是（）。 A. 排序、索引、统计 B. 选择、投影、连接 C. 关联、更新、排序 D. 显示、打印、制表 5. 在select语句中使用group by Sno时，Sno 必须出现在（）子句中。 A. where B. from C. select D. having 6. 在where语句的条件表达式中，与零个或多个字符匹配的通配符是（）。 A. * B. ? C. % D. _ 7. 对关系模式进行分解时，要求保持函数依赖，最高可以达到（）。 A. 2NF B. 3NF C. BCNF D. 4NF 8. 在关系模式R（U，F）中，Y∈XF+是X→Y是否成立的（）。 A. 充分必要条件 B. 必要条件 C. 充分条件 D. 既不充分也不必要条件 9. 在关系数据库设计阶段中，完成关系模式设计的阶段是（）。 A. 需求分析阶段 B. 概念设计阶段 C. 逻辑设计阶段 D. 物理设计阶段 10. 基本E-R图就是数据库的（）。 A. 外模式 B. 逻辑模式 C. 内模式 D. 概念模式 11. 从数据流图构造E-R图时，选择实体一般应先考虑数据流图中的（）。 A. 数据项 B. 数据流 C. 数据处理 D. 数据存储 12. 以下（）不是当前常用的存取方法。 A. 索引方法 B. 聚簇方法 C. HASH方法 D. 链表方法 13. 事务一旦提交，对数据库的改变是永久的，这是事务的（）。 A. 原子性 B. 一致性 C. 隔离性 D. 持久性 14. 并发控制要解决的根本问题是保持数据库状态的（）。 A. 安全性 B. 完整性 C. 可靠性 D. 一致性 15. 在数据库系统中，对存取权限的定义称为（）。 A. 授权 B. 定义 C. 约束 D. 审计 16. 视图建立后，在数据字典中存放的是（）。 A. 查询语句 B. 视图的定义 C. 组成视图的表内容 D. 产生视图的表定义 17. 由全码组成的关系模式，最高可以达到的模式为（）。 A. 4NF B. 2NF C. 3NF D. BCNF 18. 下列叙述中，正确的是（）。 A. 对于关系数据模型，规范化程度越高越好 B. 如果F是最小函数依赖集，则R∈2NF C. 如果R∈BCNF，则F是最小函数依赖集 华南理工大学分布式计算期末考试卷题整理 第一章：分布式 1）并行计算与分布式计算区别？ （1）所谓分布式计算是一门计算机科学，它研究如何把一个需要非常巨大的计算能力才能 解决的问题分成许多小的部分，然后把这些部分分配给许多计算机进行处理，最后把这些计算结果综合起来得到最终的结果。 与并行计算不同的是，并行计算是使用多个处理器并行执行单个计算。 2）分布式计算的核心技术是？ 进程间通信IPC！！！ 3）解决进程间通信死锁的两种方法？ 超时和多线程 4）分布式系统的CAP理论是什么？ 一致性，可用性，分区容忍性 第二章：范型 1)网络应用中使用的最多的分布式计算范型是？ 客户-服务器范型（简称CS范型） 2)消息传递范型与消息中间件范型异同？ ●消息传递：一个进程发送代表请求的消息，该消息被传送到接受者；接受者处理该请求， 并发送一条应答消息。随后，该应答可能触发下一个请求，并导致下一个应答消息。如此不断反复传递消息，实现两个进程间的数据交换. 基于该范型的开发工具有Socket应用程序接口（Socket API）和信息传递接口（Message Passing Interface，MPI）等 ◆消息系统模型可以进一步划分为两种子类型：点对点消息模型 （Point-to-point message model）和发布订阅消息模型 （Public/Subscribe message model）。 ◆在这种模型中，消息系统将来自发送者的一条消息转发到接收者的消息队 列中。与基本的消息传递模型不同的是，这种中间件模型提供了消息暂存 的功能，从而可以将消息的发送和接受分离。与基本的消息传递模型相比，点对点消息模型为实现异步消息操作提供了额外的一层抽象。如果要在基 本的消息传递模型中达到同样的结果，就必须借助于线程或者子进程技术。 3)一个分布式应用能否使用多个分布式计算范型？ 可以，部分。 4)抽象层次最低的分布式计算范型是？ (单选题)1: 图中有关路径的定义是（）。 A: 由顶点和相邻顶点序偶构成的边所形成的序列 B: 由不同顶点所形成的序列 C: 由不同边所形成的序列 D: 上述定义都不是 正确答案: (单选题)2: ()是一个基本完整的开发工具集，它包括了整个软件生命周期中所需要的大部分工具，如UML工具、代码管控工具、集成开发环境等等。 A: VS B: VM C: Dev-C++ D: IDE 正确答案: (单选题)3: 下列数据结构中，属于非线性结构的是（）。 A: 循环队列 B: 带链队列 C: 二叉树 D: 带链栈 正确答案: (单选题)4: 下列叙述中正确的是（）。 A: 顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的 B: 顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 C: 顺序存储结构能存储有序表，链式存储结构不能存储有序表 D: 链式存储结构比顺序存储结构节省存储空间 正确答案: (单选题)5: 十六进制中最大的数码是（）。 A: 16 B: 15 C: F D: E 正确答案: (单选题)6: 二进制，就表示某一位置上的数运算时是逢（）进一位。 A: 2 B: 8 C: 9 D: 10 正确答案: (单选题)7: 在程序代码编辑框外（一般都是程序代码的最左侧）双击，就成功设置了一个断 点，设置成功后会在该行的最前面显示一个圆点，这样的过程称作()。 A: 设置断点 B: 单步调试 C: 程序编译 D: 程序调试 正确答案: (单选题)8: 递归结束条件，又称为()。 A: 递归判定 B: 递归策略 C: 递归出口 D: 递归返回 正确答案: (单选题)9: 下列叙述中正确的是（）。 A: 一个逻辑数据结构只能有一种存储结构 B: 数据的逻辑结构属于线性结构，存储结构属于非线性结构 C: 一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D: 一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 正确答案: (单选题)10: 下列说法正确的是()。 A: 关键字是数据元素（或记录）中某个数据项的值，可以标识一个记录，称为主关键字。B: 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。 C: 对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为log2n。 D: 折半查找的先决条件：表中结点按关键字有序，且顺序（一维数组）存储。 正确答案: (单选题)11: 下列排序方法中，哪一个是稳定的排序方法？() A: 直接选择排序 B: 二分法插入排序 C: 希尔排序 D: 快速排序 正确答案: (单选题)12: isalnum（）函数用来（）。 A: 判断字符串 B: 判断大写 C: 判断数字或字母 D: 判断小写 正确答案: (单选题)13: 深度优先搜索的搜索策略是()。 A: 尽可能“深”地搜索图算法设计与分析(作业三)
第三章部分习题答案
数据库系统基础课后题
算法分析与设计作业及参考答案样本
HIT软件学院数据库实验1
《分布式计算、云计算与大数据》习题参考解答
最新算法分析与设计作业(一)及参考答案讲课讲稿
算法部分作业答案要点
北邮分布式计算环境课堂作业答案及点评
《算法分析与设计》作业参考答案
算法分析与设计(线下作业二)
分布式系统试题及答案
《算法设计与分析》实验指导
第二章多线程分布式计算课后答案
算法分析与设计作业(三)
《算法设计与分析基础(第3版)》部分习题答案
(完整版)哈尔滨工业大学数据库试题(含答案)
华南理工大学分布式计算期末考试卷题整理
东师《算法分析与设计》19春在线作业2
相关主题
文本预览