我使用的数学

最近，在一个在线论坛上提出了一个问题：在一个真正的程序员的条件下，数学的需求量是多少，他使用频率是多少？它的领域是什么？ 这是我的答案。

首先，与几乎所有程序员一样，我使用布尔逻辑 ，从对条件语句和退出条件的逻辑表达式进行分析，使此类表达式符合例如de Morgan的定律 。 我们的大多数工作都以对先决条件，不变量等进行分析的形式，对一阶谓词和其他谓词逻辑进行微积分 （尽管似乎我们正在做其他任务）。

此外，我经常从事算法复杂性的分析。 这些天正在处理的数据集的规模巨大。 在2010年技术会议上， 埃里克·施密特 （ Eric Sc​​hmidt）说，今天人类在短短两天内创建的数据量就等于2003年世界上所有现有数据的量。 对我而言，重要的是能够处理这些数量很大的部分并从中受益。 从这个意义上讲，了解我们应用于数据的操作的时空复杂性是确定某些计算原则上是否可行的关键。 与更传统的O分析或theta分析类型相比，在这种规模上的常数因子具有显着影响：因子2不会改变算法的渐近时间复杂度，但是需要将处理器数量从1万增加到2万，并且消耗量也要如此资源将是有形的。 结果，计算变得更加复杂。 示例：我可以进行一些线性计算并将其简化为对数吗？ 是否可以将内存消耗减少三倍？ 依此类推。

通常，我需要计算上限的最不利变量，例如某些数据集的大小。 在许多情况下，这样的计算可能是不平凡的。 或者，您可能需要分析一些递归公式，以检查其随递归深度的增加如何变化。 为此，除其他外，我必须了解递归关系的基本定理以及如何理解数列分析的原理。 这似乎令人难以置信，但是有时这意味着我需要计算积分 （尽管大多数情况下只是黎曼积分）。 还是可以只解决递归关系并获得有限数量的解决方案 ？ 我必须求助于线性代数吗？ 这导致生成函数 ， 斯特林数 ， 矩阵计算之类的事情。 如果您对理解计算机科学所需的基本数学概念集中包含的内容感到好奇，请参阅Donald Knuth的第一本“编程的艺术”或Knut，Ronald Graham和Oren Patashnik的“具体数学”。

在汇总，合并和转换数据方面，我做了很多基本的计算，而组合学 （计算数量，发现不同维度的对称性，等等）对我有帮助。 我认为这方面的例子很明显。

我使用了大量离散数学 ，尤其是在对大型数据集进行运算时搜索代数系统。 是否可以借助同构性将这个或那个结构显示为特定的组或环 ，这对我来说会更清楚？ 是否有连接不太紧密的选项？ 我可以将组的动作应用于某个集合以创建一个推测性的转换模型来简化推理吗？ 我可以定义一些拓扑进行数据分析吗？ 如果您知道使用离散拓扑可以描述多少事物，您将感到惊讶。 三角不等式的需求将更加令人惊讶。

我在图论方面做了大量工作。 “创建网站”-不仅需要在页面上放置猫的可爱图片的能力。 此过程还涉及将节点插入到超链接的全局图中。 仅添加一页会导致图形边缘数量的潜在增加，这反过来可能会带来乍一看对性能，分析，搜索引擎排名和其他特征的影响。 了解此类更改的后果可以帮助获取有趣的信息，例如图形的增长方式。 事实证明，这种动态过程非常类似于幂律 ：万维网是无标度网络 。 此图的两个节点之间的最短路径是什么？ 如果尝试将其表示为平面图或二部图，则该网络的外观如何？ 什么时候可以遵守这些属性，如果可以的话，当然可以吗？ 但是，如果我们不将万维网视为一个图形，而是将北美，欧洲或亚洲的整个道路网络视为图表，该怎么办？

这种知识还有其他后果。 人们通常不理解现代网页不仅仅是带有链接和其他资源的HTML文档，而是在图中彼此连接的树状数据结构 。 由于用户的Web浏览器和服务器之间的交互作用（由于使用了诸如AJAX之类的技术），这些树经常被爬网，处理和动态更新。

MathJax是一个很好的例子。 或Gmail 。 了解它们的工作原理需要一定程度的符号计算知识和页面元素的语义分析 。 MathJax的作者需要编写一个程序，该程序能够遍历根据文档的对象模型生成的树，查找数学元素，“存储”它们并用新绘制的元素动态替换它们。 也许只是一些看到它如何工作的用户并不会给人留下深刻的印象，而是在幕后发生相当复杂的事情。 我通常不必做类似的事情（我不使用前端），但是一直以来我都在Lisp中做类似的事情。 请注意，Lisp最初是通过对符号信息进行数学处理来提高的：它的宏完全涵盖了处理符号表达式的问题。

我经常处理时间序列 。 交通或资源消耗如何变化？ 可以强调哪些趋势？ 这种或这种飞跃是否体现在季节性响应请求或内存消耗方面的延迟？ 当输入数据在不同维度上变化时，事物的变化率如何反应？ 与某些外部事件有关联吗？

我从事统计数据分析工作很多，不仅要确定性能特征，还要了解数据本身。 除了在上述DOM树中搜索语义元数据（例如， 微数据和微格式 ， RDF ，具有某些特定模式的其他XML数据）之外，我还尝试理解非结构化数据 。 该文字是街道地址的可能性有多大？ 还是图形坐标 ？ 他在什么情况下出现？ 是垃圾邮件吗？ 有道理吗？ 它看起来像基于马尔可夫链的文本生成器的结果吗？ 也许这是一些著名文学作品的一系列引文？ 还是文学讨论的一部分？ 还是这是有关包含文学片段的垃圾邮件的讨论？ 每当我想到垃圾邮件广告中都包装着布尔加科夫（Bulgakov）的《大师与玛格丽塔》（Master and Margarita）片段时，我仍然会笑。

范畴理论 。 计算机编程语言中的类型大致对应于类别，而monad和函子可用于严肃优雅地简化某些构造。 例如，在Haskell 功能编程语言中，monad用于I / O和状态建模。 在处理简化程序时，使其更容易工作。 谈论它们更容易，理解，更改等也更容易。 通常可以基于逻辑推理来确定类型，这会导致出现特殊情况 （也可以将其用于一般推理问题）。 想一想如果您使用结论来应用逻辑函数（如序言中使用的逻辑函数）来转换 分布式系统中的 图 ，会发生什么情况。

分布式系统使我们回到图论。 在现实世界中，系统崩溃，挖掘机撕裂纤维，地震，火山喷发和拖网渔船损坏了海洋电缆。 要了解此类事件的后果并确定应对此类事件的最佳方法，有必要了解网络图的特征。 路由算法和网络分析与诸如查找图中节点之间的最短路径之类的事情紧密相关。 Dijkstra算法将为您提供帮助。

但是，如何在世界各地的数据中心之间分配来自大型计算的负载？ 在这里，您还需要一些物理知识：在Internet规模上，光速变成了“瓶颈”。 散热 ，每单位面积的电流密度等是程序员在处理实际任务时必须考虑的示例。 我应该在冰岛托管一个数据中心吗？ 廉价的冷却和地热能源创造了诱人的条件，但是对于可能有兴趣在这样的数据中心中租用设备的用户而言，最小延迟又如何呢？ 例如，在冰岛和伦敦之间，或者在柏林和阿姆斯特丹之间，沿着大圆弧的距离是多少？ 计算所有这些非常简单，但是为此必须具有一定的数学知识。 我们可以将光纤从冰岛发送到其他中心吗？ 平均延迟时间是多少？ 在运作12个月后，北海海底电缆断裂的可能性有多大？ 还有48个月？

当然， 算法 理论，自动机理论 ， 语法分析 ， 形式语法 ， 常规语言都是程序员经常处理的知识领域。 我经常进行解析和模式匹配 。 在处理实际数据时，即使不是很大的数据集也可能包含一些元素，这些元素在使用（例如） 回溯技术时可能导致病理上不良的行为 。 使用正则表达式匹配数据时，我应该小心并确保这些表达式确实是正则表达式。

使用一台具有存储内存的机器来解析上下文无关的语法 （顺便说一下，每次您将请求发送到HTTP服务器时都会发生这种情况），我需要确保限制递归深度以避免耗尽处理器调用堆栈 ，这需要理解计算的基本原理以及它们所基于的数学。

如果我需要为某种不寻常的语法编写自己的递归下降算法 ，并且该算法不能与LALR（1）匹配（因此我不能只使用yacc或bison ），则需要格外小心或将状态堆栈与过程递归分开。 如果我遍历DOM树（或任何递归定义的数据结构），则也需要这种理解。 一些编程语言认为这是程序员工作中的困难，并通过使用分段堆栈来解决它 。 当然，如果我能够以函数的形式（从数学意义上）定义一些分析资源的集合，那就太好了。 如果归结为某种线性编程优化问题，那将会有多酷？

请注意，以上内容都不是任何深奥的知识。 所有这些都是基于任务和实际数据的经验。 当然，我并不是每天都做这些事情，但是我经常应用这些知识中的大部分，并且不时应用。 观察，经验和启发式方法可能对过程的影响比应有的要大（启发式模型通常不完整且不准确）。 我是否有足够的数学知识来计算现实和启发式模型之间的平均误差 ？

这是计算机科学的本质，也是计算机科学与编程以及现代计算现实之间相互作用的本质。 成为IT专业人员并不等同于成为计算机理论领域的专家，而且正如许多正确指出的那样，与专家数学家相比，这样的专家更接近于应用数学家。 我绝不贬低这些专业人员的重要性，因为他们很有用并且受到普遍尊重，但我只想指出计算机科学是另一回事。

（顺便说一句，我本人不是计算机科学专家。我学习的是纯数学，而且我的职业非常接近工程学。）