大数据计算的基础理论探究  

Investigation of Basic Theory in Big-Data Computations

作　　者：许道云[1] XU Daoyun(College of Computer Science and Technology, Key Lab of Public Big Data of Guizhou Province, Guizhou University, Guiyang 550025, Chin)

机构地区：[1]贵州大学计算机科学与技术学院,贵州省公共大数据重点实验室,贵州贵阳550025

出　　处：《贵州大学学报（自然科学版）》2016年第4期1-11,共11页Journal of Guizhou University:Natural Sciences

基　　金：国家自然科学基金项目资助(61262006)

摘　　要：在经典计算中,对前端输入数据的复杂性不做分析。在大数据计算中,前端输入数据的复杂性分析反而成为大数据计算和分析的重点。本文讨论大数据计算的基础理论问题,将大数据计算问题分为目标任务型和内容认知型。大数据计算形式上依赖于一个外部信息源,从计算的有效性,将大数据计算的讨论限制在对数空间复杂类,涵盖了并行计算复杂类。基于带Oracle的图灵计算模型,限制在对数空间内图灵可计算,并且外部信息源能够用一个对数空间可计算的递归函数枚举,引入了大数据可计算的计算模型和大数据可计算性、可判定问题等概念。In classical computations,it don＇t need to analyze the data complexity of inputs in algorithms,but analyzing data complexity of inputs in big-data computations becomes key problems. Some basic theories of big-data computations were investigated,and computations were classified into objective-task and context-recognition types. The big-data computations depend formally on some external information sources. For effectiveness of computations,restrict complexity of big-data computations was restricted to classes of computable problems in logspace,which contains the class of parallel computations. The computation model,big-data computability and decidability were introduced based on Turing machine with oracles in log-space,where the information sources as oracle is a recursive enumerable set that is computable in log-space.

关 键 词：大数据计算 对数空间可计算性 并行可计算性 带Oracle图灵机 大数据可计算性 

分 类 号：O171[理学—数学]