Algorithms: Top to Bottom

算法：从上到下

• 批准号: RGPIN-2018-05325
• 负责人: Morin, Patrick
• 金额: $ 3.5万
• 依托单位: Carleton University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750373
• 关键词: Algorithms; Top; Bottom

I investigate classic computer science topics (algorithms, data structures, networks) with a particular focus on topics that have a geometric or graph-theoretic component. My research program, which includes both theoretical and practical research, proceeds in three fundamental directions:(1) Worst-case analysis using the classic tools of asymptotic analysis and combinatorics. Recent examples include studying the worst-case running-time of a nearest neighbour search algorithm, the highest resolution required for a particular kind of data visualization, and the fewest colours required for to colour some class of graphs that can be drawn on a surface.(2) Probabilistic analysis using the tools of probability theory. Recent examples include the expected running-time of a point-location data structure under a random query distribution, the properties of a wireless network whose nodes are distributed uniformly in some region, and the properties of a rumour-spreading network modelled as a random tree.(3) Real performance analysis through implementation and experiments. A recent example is the study of the real-time performance, on hundreds of different systems, of classic widely-used algorithms for searching in an ordered array.The research program outlined in (1) and (2) requires a detailed study of the mathematical structures underlying these topics. As such, it uses and drives the development of new fundamental results in combinatorial geometry, graph theory, and probability theory.The research program outlined in (3) requires careful implementation and experimentation. This work helps to illuminate the often surprising nuances of modern microprocessor systems, which are exceedingly complex.

我研究经典的计算机科学主题（算法，数据结构，网络），特别关注具有几何或图论组件的主题。我的研究计划，其中包括理论和实践研究，在三个基本方向进行：（1）使用渐近分析和组合学的经典工具的最坏情况分析。最近的例子包括研究最近邻搜索算法的最坏情况下的运行时间，特定类型的数据可视化所需的最高分辨率，以及为可以在表面上绘制的某些类别的图形着色所需的最少颜色。(2)使用概率论工具的概率分析。最近的例子包括随机查询分布下的点位置数据结构的预期运行时间，无线网络的节点均匀分布在某个区域的属性，以及建模为随机树的谣言传播网络的属性。(3)通过实施和实验进行真实的性能分析。最近的一个例子是在数百个不同的系统上研究在有序数组中搜索的经典广泛使用的算法的实时性能。在（1）和（2）中概述的研究计划需要详细研究这些主题背后的数学结构。因此，它使用并推动了组合几何、图论和概率论中新的基本结果的发展。（3）中概述的研究计划需要仔细实施和实验。这项工作有助于阐明现代微处理器系统中经常令人惊讶的细微差别，这些系统非常复杂。