Effective Dimensions in the Theory of Computing

计算理论中的有效维度

• 批准号: 0728806
• 负责人: Jack Lutz
• 金额: --
• 依托单位: Iowa State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-15 至 2010-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0728806&HistoricalAwards=false
• 关键词: Effective; Dimensions; Theory; Computing

Effective Dimensions in the Theory of Computing AbstractThe investigator recently developed effective fractal dimensions in order to measure the density of information in large data objects.In this project, he and his group are using these dimensions toextend the theoretical foundations of high-precision scientificcomputing, to study prediction and compression of data streams that are truly massive relative to available computational resources, and to attack fundamental questions concerning the number of computation steps required to solve complex problems.The research on foundations of scientific computing is incorporating multiresolution processing of data from continuous geometric domainsin order to develop an algorithmic extension of geometric measuretheory in Euclidean spaces. Investigations of prediction and compression are focused on computation by finite-state devices andextend methods of ergodic number theory. Computational complexityresearch topics include derandomization, diagonalization, and dimension characterizations of time-bounded Kolmogorov complexity.Overall, the project is developing new analytic methods for use intheoretical computer science, working to achieve a greater unity between computational complexity and information theory, and training young researchers to cross traditional boundaries in theconduct of rigorous research.

计算理论中的有效维数 为了测量大数据对象中的信息密度，研究人员最近开发了有效的分形维数。在这个项目中，他和他的团队正在使用这些维数来扩展高精度科学计算的理论基础，研究相对于可用计算资源而言真正庞大的数据流的预测和压缩，科学计算基础的研究是对连续几何域的数据进行多分辨率处理，以发展几何域的算法扩展，欧氏空间中的测度论。 预测和压缩的研究集中在有限状态设备的计算和遍历数论的扩展方法。 计算复杂性的研究主题包括时间限制的柯尔莫哥洛夫复杂性的去随机化、对角化和维数特征。总的来说，该项目正在开发用于理论计算机科学的新分析方法，努力实现计算复杂性和信息论之间的更大统一，并培训年轻研究人员在严格的研究过程中跨越传统界限。