问题标签 [computer-science-theory]

When we write powering a number as a divide and conquer algorithm in theoretical computer science the runtime would be T(n) = 2T(n/2) + Θ(1) in my opinion, yet according to my teacher's slides it is T(n) = T(n/2) + Θ(1). Why that? I added the 2 because the algorithm gets split into 2 subproblems? Am I wrong?

我将如何继续证明这两个函数的类型正确？我对这个问题有点迷茫。

在偶然发现这个问题之后，我想到了如何定义一个纯函数。我有两条规则可以接受纯函数，这与最佳答案中引用的定义有些不同。我很想知道我的观点是否正确。我的“2条规则”是：

• 该函数不会改变程序的状态。
• 对于相同的参数或相同的本地公共程序状态，输入是恒定的。

为了澄清第二点，local public state我主要是指public班级成员。本地意味着状态与函数密切相关并且是它独有的（即不是一些全局变量）。我使用该定义的理由是，它只是术语 的更扩展视图（可能过于特定于 CS）arguments，因为我认为local public state它只是用于传递函数参数的不同接口。这个定义是可以接受的还是包含一个类上下文会破坏函数的“修剪”？

编辑：作为我的意思的示例，请考虑以下类（C++）。

考虑到实例函数调用实际上是以下调用：

这与通过结构传递公共数据（数字）有何不同？

Can anyone help with explaining how to simplify this? X and Y are two sets. Simplify the following:

(Y − X)∩X

我最近一直在研究如何在构建知识图谱时提取模糊知识，但我目前只知道使用一些模糊数学算法，但我没有头绪，所以，有什么好主意吗？

顺便问一下，知识抽取中是否包括本体构建？

我有一组同余

我想找到x，这可以通过中国剩余定理和相关算法来解决：https ://en.wikipedia.org/wiki/Chinese_remainder_theorem

一些例子：https ://rosettacode.org/wiki/Chinese_remainder_theorem

对于这个特定的例子：

我尝试过的所有算法都不起作用，因为模不是成对互质的。但是，1024360583是一个有效的解决方案：

什么算法可以找到这样的解决方案？

我还实现了密码学手册中的加纳算法：它没有解决那个例子。

假设我有多个类都具有相同的操作（在我的情况下，我正在创建一个插件框架：加载、运行、处置），并且我想使用一个接口，以便我可以创建一个 PluginFactory 来处理初始化. 问题是它们都需要完全不同的数据，因此方法相同但参数不同。是否有最佳实践或设计模式，我可以在将不同数据传递给方法时使用接口和多态？

泛型不一定能解决我的问题，因为每个插件的参数数量和类型都不同。当我实现从全局源检索参数的方法时，我正在考虑在方法中创建一个容器，因此我可以在测试时将不同的依赖项注入到该全局源中，但我不确定这是否违反了任何抽象规则。

编辑：

这是一个代码示例：

我有一个应用程序，用户登录以玩快速 1v1 游戏（持续 20 秒）。我想知道将每个用户与另一个用户配对以玩游戏并转移到下一个用户而不连续多次玩同一用户的最有效方法。

我的第一个想法是让两个队列包含每个在线用户的用户 ID。每当有新用户上线时，我都会将他们添加到最短的队列中，并且不断地从每个队列的顶部弹出一个人来互相玩。游戏结束后，我会简单地将每个用户添加到同一个队列中，以避免他们再次互相玩。这看起来不错，但我想看看是否有任何其他更有效的方法来实现这个概念，而无需在服务器上保留以前玩过的用户列表。

问：证明 L={ww|w ∈ {0,1}*} 不是上下文无关的

我的解决方案：

假设 L 是上下文无关的

设其泵送长度为 P

因此，

字符串 = 0^P 1^P 0^P 1^P

设 P=2, S= 00 11 00 11

S 可以划分为 uv^ixy^iz

抽完之后，

0^3 1^2 0^3 1^2 因此它采用ww的形式 （满足第一个条件）

|vy|=4>0（满足第二个条件）

|vxy|= 7，大于泵送长度 2（不满足第 3 个条件）

因此，与 L 是上下文无关的假设相矛盾。

因此 L 不是上下文无关的

我的证明正确吗？

我被困在一个问题的归纳案例上。

问题：

将树的高度定义为根与任何叶子之间的最大边数。我们认为一棵空树的高度为 -1，由单个节点组成的树的高度为 0。通过归纳证明每个高度为 h 的非空二叉树包含少于 2 ^(h+1)节点。

= 2 ⁽⁰⁺¹⁾ = 2 ⁽¹⁾ = 2 当高度为 0 时，树由单个节点组成，所以是的，1 个节点小于 2 个节点。归纳步长 = h 小于或大于 0 这就是我卡住的地方...我知道这句话是正确的，因为高度总是比节点数小 1，我只是不知道如何证明它代数。

提前致谢。