一、 问答题

1、[矩阵转置]．请参照图6.3.3给出行方向条带状划分时矩阵转置的算法分析和性能评价。



2、[矩阵乘积的运算次序问题]．所谓矩阵乘积的运算次序问题，是指多个矩阵的乘积 按照怎样的运算次序（即怎样加括号）使得运算速度最快的问题。根据矩阵运算的结合性，不论按照怎样的次序运算，其结果都是一样的，但运算速度有所不同，现举例来说明。比如要计算乘积 ，假设三个矩阵的大小分别为5×10、10×20和20×40。按照 的运算次序所花的操作步数是5×10×20＋5×20×40＝5000；而按照 的运算次序所花的操作步数是10×20×40＋5×10×40＝10000。后者所花的时间是前者的两倍。看来寻找一个合适的运算次序是很有必要的。
     最简单的方法是穷举法，把所有可能的情况一一列举出来，计算其时间开销，从中选出耗时最少的运算次序。设有n个矩阵参与相乘，需要进行n-1次乘法运算，这些运算之间的次序共有(n-1)!种，这是指数增长的，扩展性很差。
     请用动态规划法分析和解决上述问题，并给出并行化的算法分析与性能评价。



3、[Dijkstra算法]．本题讨论对于图论中一点到其它所有点的最短路问题，即对于一个赋权图G=(V, E, w)和图G任意一点v，寻找v到图G中其它各点的最短路，最终结果是一个向量。Dijkstra算法是解决一点到其它各点最短路的常用方法，算法如下：
1.     procedure DIKDTRA_SINGLE-SOURCF-SP(V:E:w:s:)
2     . begin
3.         V_T:={s};
4.         for all v∈（V- V_T）do
5.              if(s:v) exitst set l[v]=w(s,v);
6.              elst set l[v]=∝;
7.         while V_T ≠V do
8.         begin
9.              find a vertex u such that l[u]=min{l[v]|v∈(V- V_T)};
10.              V_T := V_T∪{u};
11.              for all v∈(V- V_T) do
12.                   l[v]=min{l[v],l[v]+w(u,v)};
13.         endwhile
14.     end DIJKSTRA_SINGLE_SOURCE_SP
     请给出求解一点到其它各点最短路的并行算法并分析其性能。