5

我有一些小算法,我想写在一篇论文中。它们相对较短,简洁。但是,我不想用伪代码(à la Cormen 甚至 Knuth)编写它们,而是编写它们的代数表示(更线性和更好的 LaTeX 渲染)。但是,如果有任何东西,我找不到关于最佳符号的资源:例如,我如何表示一个循环?如果?将元组添加到列表中?

你们有没有人遇到过这个问题,并以某种方式解决了它?

谢谢。

编辑:谢谢,人们。我认为我在表达这个问题方面做得很差。再说一遍,希望我说得更清楚:在数学符号中谈论循环和 if-then 子句的常用符号是什么?例如,我可以$acc \leftarrow acc \cup \langle i,i+1 \rangle$用来表示列表的“添加”方法。

4

8 回答 8

8

不要这样做。当人们阅读有关算法的论文时,您会偏离人们期望看到的内容。您应该遵循预期的做法;你的想法更有可能得到应有的关注。在罗马做到入乡随俗。

在 LaTeXed 论文中格式化代码(或可能是伪代码)非常容易。例如,请参阅Formatting code in LaTeX

于 2010-01-28T20:03:37.143 回答
7

我经常看到数学符号中的 if 表达式。循环通常是递归关系,或者等效地,递归定义的函数。

以下是 Wikipedia 上定义Ackermann 函数的方式,例如:

如果 m=0,则 A(m, n) = n+1; A(m-1, 1) 如果 m>0 且 n=0; 如果 m>0 且 n>0,则为 A(m-1, A(m, n-1))。

这张图片很好,因为它给人以数学的感觉,但你可以清楚地输入几乎完全一样的文字并有一个实现。并非总是可以实现这一目标。

与循环相对应的其他数学符号包括求和的 ∑-notationset-builder notation

我希望这回答了你的问题!但是,如果您的目标是描述某事是如何完成的并让某人理解,那么我认为假设数学家更愿意看到方程式可能是错误的。我不认为它们是可互换的工具(尽管图灵等效)。如果您的算法涉及可变数据结构,则程序代码可能比解释它的方程式更好。

于 2010-01-28T23:21:16.720 回答
2

我会复制高德纳。在计算机科学领域,很少有人比他更懂得如何沟通。

于 2010-01-28T20:00:35.267 回答
2

一般循环的符号不存在;通常你会使用求和运算符。“如果”使用蕴涵来表示,而要“将元组添加到列表中”,您将使用union

然而,一般来说,有点冗长并不一定是坏事——有时,特别是对于复杂的算法,最好用简单的英语,用例子和图表把它拼出来。对于非编码人员来说,这是双重事实。

想一想:当您阅读有关 GCD 的欧几里得算法或埃拉托色尼筛法的数学教科书时,它是如何编写的?通常,算法本身是散文,而算法的证明是数学符号所在的地方。

于 2010-01-29T01:00:56.140 回答
1

你可以看看 Haskell。Haskell 在 Latex 中的格式很好,有很好的代数语法,你甚至可以用 Haskell 编译一个 Latex 文件,只要代码用\begin{code}\end{code}. 见这里:http ://www.haskell.org/haskellwiki/Literate_programming 。可能有其他语言的识字编程工具。

于 2010-01-28T19:59:20.653 回答
1

Lisp 最初是作为计算模型的数学符号,以便讲师拥有比图灵机更好的工具。偶然地,事实证明它可以用汇编来实现——因此,lisp,编程语言诞生了。

但我认为这并不是您真正想要的,因为 lisp 描述的计算模型没有循环:而是使用递归。语法源自代数,其中大括号表示评估此结果并替换结果。事实上,lisp 的计算模型基本上是替换——代数本质上就是这样。

事实上,像 Lisp、Haskell 和 Erlang 这样的大多数函数式语言都源自数学。Haskell 实际上是证明 lambda 演算可用于实现类型系统的结果。所以 Haskell 就像 Lisp 一样是从纯数学中诞生的。但同样,语法不是您可能习惯的。

您当然可以向数学家解释 Lisp 和 Haskell 语法,他们会将其视为“游戏”。循环、递归和条件等语言结构可以在游戏规则之外被证明,而不是像其他语言那样盲目地实现。这将带您进入组合电子学领域,这是数学的另一个分支。事实上,在组合电子学中,即使是数字的概念也可以从游戏规则中构建出来,而不是作为语言的原生部分(谷歌教堂数字)。

如果你愿意,可以看看 Lisp/Scheme、Erlang 和 Haskell。Erlang 特别具有与您想要的语法接近的语法:

add(a,b) -> a + b

但我的建议是用类似 C 的伪代码编写。它是编程语言中最小的公分母。具有相当容易理解和清洁的语法。函数语法甚至来源于数学中的函数。还记得f(x)吗?

另外,数学家习惯于编写 C,统计学家习惯于编写 C(尽管他们通常更喜欢 R),物理学家习惯于编写 C,程序员至少习惯于看 C(我认识一些从未触摸 C)。

实际上,擦掉它。您提到您的目标受众是统计学家。写在R

于 2010-01-28T20:47:04.660 回答
0

像这个网站描述的东西?

于 2010-01-28T19:57:35.007 回答
-1

APL ? 唯一的问题是很少有人能读懂它。

于 2010-01-28T20:00:36.880 回答