问题标签 [computation-theory]

我遇到了有趣的理论问题：

假设我们通过一些 IPC（如 tcp 套接字或命名管道）连接了程序 A 和程序 B。程序 A 向程序 B 发送一些数据，并根据数据传递的成功，A 和 B 执行一些操作。但是，只有在确定 A 已收到交货确认时，B 才应进行操作。所以我们想出了3个连接：A -> B [数据传输] B -> A [交货确认] A -> B [收到交货确认的确认]

它可能看起来很奇怪，但目标是在双方都知道数据已传输之前，既不对 A 也不对 B 执行任何操作。

这就是问题所在，因为第二次连接是为了确认第一次连接成功。第三个是确认第二个，但实际上并不能保证连接 2 和 3 不会失败，在这种情况下，我们会陷入确认的无限循环。是否有一些 CS 理论可以解决这个问题？

我正在尝试确定两个元素之间的传递关系。我正在用 c 编码。

例如：a->b 由第 1 行第 2 列的邻接矩阵中的“1”表示。

所以如果 a->b 和 b-> c 和 c->d

我想确定是否 a->d。无需更新邻接矩阵。

我采用的方法：检查与 a 对应的行中的所有 1。假设第二列中有一个 1，即 b。[(a->b)] ，现在检查 b->d 是否继续检查 B 行中的所有 1 并继续到第 26 行。

我并不真正关心复杂性。我只是希望实现这一点。

我需要帮助为以下语言构建左线性和右线性语法？

对于a）我有以下内容：

这个对吗？我需要 b & c 方面的帮助。

我有这个语法

我想知道如何从这个语法中消除左递归，因为这S+S真的很令人困惑......

我正在尝试理解上下文相关的语法，并且我理解为什么语言喜欢

1. {ww | w 是一个字符串}
2. {一个ⁿ b ⁿ c ⁿ | a,b,c 是符号}

不是上下文无关的，但我想知道类似于无类型 lambda 演算的语言是否对上下文敏感。我想看一个简单但非玩具的示例（我考虑上面的玩具示例），上下文相关语法的示例，对于某些生产规则，例如，判断是否有一些符号字符串当前在范围内（例如，在生成函数体时）。上下文相关的语法是否足够强大，可以使未定义/未声明/未绑定的变量成为语法（而不是语义）错误？

这是我画的DFA-

这是正确的吗？
我很困惑，因为q4状态2对于违反规则的相同输入符号有不同的转换DFA，但我想不出任何其他解决方案。

我读了很多关于图灵机的东西并了解它是如何工作的，但是我无法掌握（而且似乎没有一本书试图教的）是我应该如何解决我要解决的问题？我的意思是：例如，检查一个单词是否是回文，由我正在学习的书中的 11 个状态组成。就我目前的知识水平而言，至少可以说，仅仅坐在一张空纸上并想出所有这些状态似乎几乎是不可能的。当我尝试做这样的事情时，我立即卡住了，因为我不知道我应该怎么做才能让这些状态以某种方式“一起”工作。我在编程时没有这样的问题，但是在这里，我只是不知道应该如何处理由一些 n-teen 状态组成的东西。你能给我一些学习的方向吗？

我正在为明天的考试而学习，我已经检查了许多教程，告诉我如何将 NFA 转换为正则表达式，但我似乎无法确认我的答案。按照教程，我解决了 NFA

我的解决方案是：

阿坝_

我对么？

假设我有一个N节点网络，每个节点都有一个唯一的身份（例如公钥），与无中央服务器的协议（例如 DHT、Kad）进行通信。每个节点存储一个变量V。以电子投票为例，该变量可以是候选人的姓名。

V现在我想对网络中所有可用的变量执行“聚合”函数。参考电子投票示例，我想计算选票。

我的问题完全是理论上的（我必须证明一个陈述，问题末尾的细节），所以请不要专注于电子投票及其所有安全方面。我必须再说一遍吗？不要回答我说“一个节点可以通过生成更多的密钥来拥有任意数量的身份”、“IP 可以追溯”等，因为那是另一回事。

让我们只从隐私来看分布式聚合的角度来看分布式聚合。

问题

有没有可能，一般情况下计算存储在其他节点上的变量的函数，而不会将它们的值与节点的身份相关联？研究人员是否设计了这种具有隐私意识的分布式算法？

我只处理隐私方面，而不是一般安全！

目前的想法

我目前的回答是否定的，所以我说中央服务器获取所有Vs 并在不存储的情况下处理它们是必要的，并且有比技术手段更合法的方法来确保中央服务器不会存储或重新传输任何单个节点的数据。我要求证明我之前的陈述是错误的:)

在电子投票的例子中，我认为不可能统计有多少人投票，Alice而Bob不是一一询问所有节点，“嘿，你投票给谁？”

真实案例

我正在研究个人数据存储领域。假设您将通话记录存储在 PDS 中，并且有人想要找到有关电话通话的统计值（即平均持续时间、每天通话次数、方差、标准差），而不会透露有关个人的汇总或准时数据（即是，没有人必须知道我给谁打电话，也不知道我自己的平均通话时间）。

如果存在受信任的代理，并且每个人都信任它，那么该节点可以公开一个API，该 API 首先在网络中的每个 PDS 上double getMeanCallDuration()调用，然后对所有行进行统计。CallRecord[] getCalls()如果没有中央可信代理，每个暴露的 PDSdouble getMyMeanCallDuration()在统计上都是不可用的（平均值不应该是所有的平均值……），最重要的是揭示单个用户的身份。

cip(int[] v, int n)(a)根据数组的维数v和值计算方法的计算成本n。

(b) 将上一步计算的成本表示为输入大小的函数。

这是我的教授在课堂上给的一个练习，但我有很多疑问。通常必须按照输入大小的函数来计算算法的计算成本？我设置了输入？还是我从提供给我的方法中获得输入？“计算成本”是指“时间成本”还是“空间和时间成本”？