将计算机算法转换为数学符号的实践

计算科学 算法 教育
2021-12-03 12:51:32

首先,一个例子:例如,
给定一个图像(2D 数组)来写下像素化函数的数学符号。

像素化
图 0:给定二维数组(左)的像素化版本(右)

上述简单函数的数学符号是什么?

第二部分:
如果人们想用数学符号写下来,有多少日常计算算法可以应用于任意维度的数据呢?作为一名计算机科学家,您将如何开始、进行和完成?考虑一下您的工作将由纯数学家检查的情况!


谁可以请添加一个新的标签数学符号

1个回答

要回答您问题的第一部分:可能有许多函数可以实现相同的目标,因此“上述简单函数的数学符号是什么”将有很多答案。例如,可以通过将每个维度的分辨率降低一半来粗化图像,以便粗图像中的每个像素对应于原始图像中的四个像素,并且可以通过平均来确定像素颜色,在这种情况下,您可以使用带索引的代数公式。我们在这里得到的几个信号处理问题使用了滤波器的特殊符号;我不熟悉信号处理,所以我不能很好地描述它,或者它意味着什么。

关于算法和数学符号之间对应关系的问题的第二部分很广泛。为了简要概述,Church-Turing 论文指出,任何“在算法上可计算”的函数当且仅当它可以由图灵机计算。所以一个简单的答案是,“任何算法都可以用数学符号表示为图灵机。” 很少有人以这种方式描述算法。你会在计算理论课上看到它,但你不会在算法课的本科介绍中看到它。算法描述似乎更常见的是伪代码。没有到处使用的标准伪代码,但可以在 Cormen、Leiserson、Rivest 和 Stein 的算法教科书中找到一种常见的变体。您还可以在 SIAM 期刊的几篇应用数学论文中找到伪代码;更多的数学算法倾向于涉及具有标准符号的方程,这些方程增加了某种伪代码,例如 Cormen 等人中的伪代码。书。其他人只是用长句来描述他们的算法,并根据需要再次使用数学符号。如果它足够短,有些人会在他们的论文中包含 MATLAB 代码(或类似类型的代码)。如果用于实现算法的程序很长,通常会给出某种描述;该程序可能会或可能不会被读者访问。根据需要再次使用数学符号。如果它足够短,有些人会在他们的论文中包含 MATLAB 代码(或类似类型的代码)。如果用于实现算法的程序很长,通常会给出某种描述;该程序可能会或可能不会被读者访问。根据需要再次使用数学符号。如果它足够短,有些人会在他们的论文中包含 MATLAB 代码(或类似类型的代码)。如果用于实现算法的程序很长,通常会给出某种描述;该程序可能会或可能不会被读者访问。

至于您对纯数学家的评论,这也取决于听众。在更正式的环境中(计算机科学课程、某些研究环境,如某些数学期刊),可能需要证明所提出的算法实现了其既定目标。在不太正式的环境中,算法可以简单地陈述而无需证明;没有证据的阐述在数学上不太严谨的期刊中更为常见,例如一些面向应用的工程期刊。

所以你的两个问题都有很多答案,后者当然可以解释和偏好。