大数据并行与交互式计算.pdf

大数据并行与交互式计算 Parallel and Interactive Computing of Big Data 陈国良 摘要： 在计算理论中，计算复杂类主要研究P类与 NP类两大类问题。在大数据的情况下，为了提高P 类问题的求解速度，可采用并行方法，其中一个实 例就是NC类并行计算；为了改进NP类问题的求解 质量，可采用交互方法，其中一个实例就是IP类交 互计算。本报告，首先简要介绍一下预备知识，包 括计算模型与计算复杂性，问题的确定性与非确定 性求解，P类与NP类基础知识等；然后讨论一下P 类问题的并行求解与NP类问题的交互求解；最后 在结论中根据目标，研究对策和具体实施方案，概 括出大数据计算的总体框架。 2 目 录 1. 计算模型与计算复杂性 (1) 图灵机 （TM ）模型与并行随机存取（PRAM ）模型 (2) 计算复杂性 2. 问题的确定性与非确定性求解 (1) 确