用数学语言说计算机科学

Question

用数学语言说计算机科学

5

我正在撰写一篇关于计算机科学主题的相当长的专著。然而，我通常发现自己需要用数学术语来表达某些计算机科学概念，这对我来说很困难。例如，假设我想编写一个for循环或void函数。大多数时候，我会去查看我的Knuth、Cormen或Sedgewick，但现在它们已经不够了。是否有一个“手册”或一些文本可以作为将计算机科学翻译成数学的示例？

编辑

让我更具体一些（谢谢，Uri）。我的意思是：例如，我有一个返回长度为n的随机字符串的void函数。这引起了我的好奇心，我甚至不知道如何在数学中表示void函数...但这只是一个例子。

- Dervin Thunk

不得不说，那三本书可能是最数学化的计算机科学书籍。如果你已经读完了它们，我想你可能需要在这个话题上成为一个先锋。 :) - J. Polfer

@sheep： :) 我希望我是...我认为我正在处理的主题比纯排列、链表之类的更加应用，而且更多地涉及概率论，这些书根本没有涉及到。 - Dervin Thunk

如果您发送给我手稿和具体问题，也许我可以在线下帮助您。在转向软件开发之前，我曾是一名数学教授。http://www.johndcook.com/contact.html - John D. Cook

对于长度为n的随机字符串，您可以简单地说“X是一个长度为n的随机字符串...”，然后明确说明您所说的“随机”的含义。例如，它是从某个字母表中所有n个字母字符串中均匀随机选择的吗？ - Seth

4个回答

2

我认为你需要更具体一些。你是在谈论翻译算法吗？还是编写伪代码？

有许多更“数学化”的形式主义，其中许多用于程序的形式验证。它们通常基于离散数学。

根据你想要做什么，霍尔逻辑（Hoare Logic）是表示算法步骤的好方法，我个人认为。

你也可以使用Z符号来正式指定某些架构和协议。

- Uri

我见过的每个构造的正式符号表示都是以某种形式的离散数学为基础的 - 通常是数理逻辑、集合论、组合数学和代数。像Z这样的形式化规范语言，严重依赖于离散数学中的构造。 - Thomas Owens

1

针对您的具体问题：在数学中，如果一个函数不需要参数并返回长度为n的随机字符串，那么它可能根本就不是一个函数！也就是说，如果f()不等于f()（例如，使用f() = rand()），那么按照定义，f()就不是一个函数。您可以根据自己的喜好以不同的方式解决这个问题：您可以传递状态参数并让它返回修改后的状态参数，或者您可以将其作为多值函数并返回所有可能的值，或者您可以使用两个函数：f(n, state)给出长度为n的下一个随机字符串，而g(n, state)给出生成f(n, state)后的新状态。

- Charles

1

你可以查看亚历山大·斯捷潘诺夫和保罗·麦克琼斯所著的《编程元素》：

本书采用演绎法将程序与抽象的数学理论联系起来，以使它们能够工作。这些理论的规范、用这些理论编写的算法以及描述其属性的定理和引理一起呈现。在实际的编程语言中实现算法是本书的核心。虽然规范应该并且必须在严谨性和适当的非正式性之间进行结合，以供人类阅读，但面向计算机的代码必须在具有一般性的同时绝对精确。

- anno

我喜欢这本书，但大部分实际算法等都用C++方言表达，而“数学”符号则保留用于定义概念和属性（即使如此，它们也经常分解成C++的片段）。我认为它不适合作为如何用数学符号表达程序的示例，因为这本书中的程序使用的是C++，甚至不是伪代码。 - Logan Capaldo

是的，这应该是一个很重要的免责声明。然而，我认为数学概念与实际编程语言结构之间的映射对于提问者可能会有帮助。 - anno

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jim Lewis · Accepted Answer

求和或乘积符号可能可以代替一些for循环。其他的可能可以表示为逻辑量词（“存在i使得a[i]具有某些属性”或“对于所有i，a[i]都具有某些属性”）。（抱歉我不知道如何在Markdown中呈现这些内容...希望你能理解。）

“无返回值函数”...嗯，也许可以使用方便的逻辑符号来说明前置条件和后置条件，因为这种函数只有它们的副作用才有用？

但我认为大多数数学家将足够熟悉算法描述，以理解任何合理的伪代码约定。只要尽量避免任何需要对某种特定编程语言具有“语言律师”技能水平的东西即可。