什么是并行算法

A. 什么是并行计算什么是分布式计算

【并行计算】
并行计算（Parallel Computing）是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算。并行计算系统既可以是专门设计的、含有多个处理器的超级计算机，也可以是以某种方式互连的若干台的独立计算机构成的集群。通过并行计算集群完成数据的处理，再将处理的结果返回给用户。
并行计算可分为时间上的并行和空间上的并行。
时间上的并行：是指流水线技术，比如说工厂生产食品的时候步骤分为：
1． 清洗：将食品冲洗干净。
2． 消毒：将食品进行消毒处理。
3． 切割：将食品切成小块。
4． 包装：将食品装入包装袋。
如果不采用流水线，一个食品完成上述四个步骤后，下一个食品才进行处理，耗时且影响效率。但是采用流水线技术，就可以同时处理四个食品。这就是并行算法中的时间并行，在同一时间启动两个或两个以上的操作，大大提高计算性能。
l 空间上的并行：是指多个处理机并发的执行计算，即通过网络将两个以上的处理机连接起来，达到同时计算同一个任务的不同部分，或者单个处理机无法解决的大型问题。

【分布式计算】
所谓分布式计算是一门计算机科学，它研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分，然后把这些部分分配给许多计算机进行处理，最后把这些计算结果综合起来得到最终的结果。 最近的分布式计算项目已经被用于使用世界各地成千上万位志愿者的计算机的闲置计算能力，通过因特网，您可以分析来自外太空的电讯号，寻找隐蔽的黑洞，并探索可能存在的外星智慧生命；您可以寻找超过1000万位数字的梅森质数；您也可以寻找并发现对抗艾滋病病毒的更为有效的药物。这些项目都很庞大，需要惊人的计算量，仅仅由单个的电脑或是个人在一个能让人接受的时间内计算完成是决不可能的。
中国科学院的定义
分布式计算是一种新的计算方式。所谓分布式计算就是在两个或多个软件互相共享信息，这些软件既可以在同一台计算机上运行，也可以在通过网络连接起来的多台计算机上运行。分布式计算比起其它算法具有以下几个优点：
1、稀有资源可以共享。
2、通过分布式计算可以在多台计算机上平衡计算负载。
3、可以把程序放在最适合运行它的计算机上。
其中，共享稀有资源和平衡负载是计算机分布式计算的核心思想之一。

B. 为什么需要并行算法

并行算法可以在同时进行计算，提高运算速度，

这个视频很清楚地展示出了并行计算的优点：
http://v.youku.com/v_show/id_XMTQxNTY2Njg0.html

C. 并行算法的介绍

并行算法就是用多台处理机 联合求解问题的方法和步骤,其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问 题,然后使用多台计算机同时求解它,从而最终求得原问题的解.

D. 并行数据挖掘是指什么并行呢

并行数据挖掘技术不同于其它并行算法的地方在于它需要处理的数据的规模很大。人们知道，对于并行而言，交互之间的消耗（即内存的使用）是比执行时间（计算阶段）重要得多的因素。串行数据挖掘算法对于规模很小的数据也需要大量的运行时间，而且可用于分析的数据增长得很快，这样就需要寻找用于数据挖掘的并行算法，目前对并行数据挖掘算法已有了充分的研究

并行数据挖掘的策略
一个算法的复杂性可以表示为空间复杂性和时间复杂性两个方面。并行算法的目标是尽可能减少时间复杂性，但其代价是通过增加空间复杂性（如增加空间的维数及增加处理器的台数）来实现的。从算法树的结构来看，通常的串行算法树“深而窄”；而并行算法树的结构截然不同。为了达到把时间复杂性转化为空间复杂性的目的，并行算法树采用“浅而宽”的结构即每个时刻可容纳的计算量相应增加，使整个算法的步数尽可能减少。

并行数据挖掘策略通常是有三种：
1.朴素并行，也就是人们通常说的网络并行。网络并行，就是通过高速信息网络充分利用网上的计算机资源，实现大规模数据上的并行计算。在这种并行类型中用于计算的时间会减少但是每一个处理器都要扫描所有的数据，这样就阻碍了算法性能的提高。

2.典型并行是当前并行数据挖掘策略的典型代表（这里称为典型并行）。在算法的每一步中，一个处理器只处理 1/p 的数据，而且在步骤的最后需要交换从数据中收集到的信息。

3逻辑并行类型 的技术是适用于逻辑性较强的并行。对于这种类型的并行数据挖掘策略，初始化阶段可能要重复进行是为了给该类型技术的结构减小数据规模。然而，该结构进一步发生在进一步抽取信息的过程中。许多归纳的逻辑方法（如的处理是ProgoL） 就是这种并行类型。

E. 并行计算的定义

并行计算（Parallel Computing）是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算。并行计算系统既可以是专门设计的、含有多个处理器的超级计算机，也可以是以某种方式互连的若干台的独立计算机构成的集群。通过并行计算集群完成数据的处理，再将处理的结果返回给用户。
并行计算可分为时间上的并行和空间上的并行。
时间上的并行：是指流水线技术，比如说工厂生产食品的时候步骤分为：
1． 清洗：将食品冲洗干净。
2． 消毒：将食品进行消毒处理。
3． 切割：将食品切成小块。
4． 包装：将食品装入包装袋。
如果不采用流水线，一个食品完成上述四个步骤后，下一个食品才进行处理，耗时且影响效率。但是采用流水线技术，就可以同时处理四个食品。这就是并行算法中的时间并行，在同一时间启动两个或两个以上的操作，大大提高计算性能。
l 空间上的并行：是指多个处理机并发的执行计算，即通过网络将两个以上的处理机连接起来，达到同时计算同一个任务的不同部分，或者单个处理机无法解决的大型问题。
比如小李准备在植树节种三棵树，如果小李1个人需要6个小时才能完成任务，植树节当天他叫来了好朋友小红、小王，三个人同时开始挖坑植树，2个小时后每个人都完成了一颗植树任务，这就是并行算法中的空间并行，将一个大任务分割成多个相同的子任务，来加快问题解决速度。

F. 并行计算与串行计算有什么区别

元计算FELAC并行版和串行版要区分特别简单，串行版是只能在一台电脑进行工作，而并行版没有电脑台数工作的限制。所以大多数会选择并行版。

G. 什么是并行算法的复杂度复杂度作用可以通过哪些指标来分析

1. 时间复杂度

2. 算法的时间复杂度是指执行算法所需要的时间。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做。

4. T(n)=Ο(f(n))

6. 因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度

8. 2.空间复杂度

9. 算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

11. 3.正确性

13. 算法的正确性是评价一个算法优劣的最重要的标准。

15. 4.可读性

17. 算法的可读性是指一个算法可供人们阅读的容易程度。

18. 5.健壮性

19. 健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也成为容错性。
    

H. 串行算法和并行算法有什么区别 尽可能详细点

串行算法是单个处理器的运算并行算法，是将一个计算任务分摊到多个处理器上并同时运行的计算方法。比如双核CPU ，从外部看起来是一个CPU，但是内部有两个运算核心。

I. 请问并行计算和分布式计算的区别和联系都是什么

首先，应用的场合和解决的问题不一样。分布式计算比较倾向于在计算寻找模式的东西，穷举暴力之类的计算。分布式的计算被分解后的小任务互相之间有独立性，节点之间的结果几乎不互相影响，实时性要求不高。而并行计算则比较倾向于一些海量数据进行分析处理的场合，每个节点的每一个任务块都是必要的，计算的结果相互影响，要求每个节点的计算结果要绝对正确，并且在时间上做到同步。举例来说，像MD5破解，就比较适合使用大规模的分布式计算来穷举，但对海量日志数据进行处理来分析用户行为就比较适合并行计算处理。

其次，实现方式区别比较大。分布式计算会是一个比较松散的结构，并行计算则是各节点之间通过高速网络或其它总线之类的东西连接。因此并行计算一般在企业内部进行，而分布式计算可能会跨越局域网，或者直接部署在互联网上，节点之间几乎不互相通信。很多公益性的项目，就是的使用分布式计算的方式在互联网上实现，比如以寻找外星人为目的的SETI项目。