При выполнении умственного исчисления можно сделать: Дано целое число k, суммировать все цифры (в базе 10), и если результат кратен 3, то k кратен 3. Знаете ли вы о каком-либо алгоритме, работающем аналогично, но работающем с двоичными числами (битами)? Сначала я думал об использовании готовых...
Я только начал читать о теории вычислений. Если мы сравним, что является более мощным (в принятии строк), оба одинаковы. Но как насчет эффективности? DFA будет быстрым по сравнению с NFA, поскольку у него есть только один исходящий фронт, и не будет никакой двусмысленности. Но в случае NFA мы...
Я в некотором роде новичок, но очень интересуюсь областью вычислений и теории сложности, и я хочу разъяснить свое понимание того, как классифицировать проблемы и насколько сильно проблемы связаны с машиной, используемой для их решения. Мое понимание Стандартная машина Тьюринга - машина Тьюринга,...
Предположим , у меня есть граф с M ( G ) на (неизвестно) набор совершенных паросочетаний G . Предположим, что это множество не пустое, тогда как трудно выбрать равномерно случайную выборку из M ( G ) ? Что если я в порядке с распределением, близким к равномерному, но не совсем равномерным, то...
У меня есть следующий вопрос, но у меня нет ответа на этот вопрос. Буду признателен, если мой метод правильный: Q. При поиске значения ключа 60 в двоичном дереве поиска узлы, содержащие значения ключа 10, 20, 40, 50, 70, 80, 90, пересекаются, необязательно в указанном порядке. Сколько возможных...
Функция максимального сдвига занятого бобра имеет известные значения для n ≤ 4 . Есть ли какая-то основная, структурная причина, по которой немыслимо, что мы когда-нибудь найдем S ( n ) для n > 4 ? Что такого отличного в n = 4 от n = 5 ? Или n = 6 ? Где-то на этом пути должна быть какая-то...
Есть бункеров, то я й бин содержит я шары. Шары имеют п цветы, есть а я шары цвета я . Пусть m = ∑ n i = 1 a i .NNnяяiaяaяa_iNNnaяaяa_iяяiм = ∑Nя = 1aямзнак равноΣязнак равно1Naяm=\sum_{i=1}^n a_i Обмен - это взять мяч из одной корзины и поменять мяч из другой корзины. Мы хотим минимальное...
Должен ли вывод синтаксического анализатора быть деревом или это также может быть общий граф? Кроме того, существует ли какой-либо существующий или вероятный язык, который использует общее представление графов вместо деревьев для своего...
Я читал о различиях между сериализуемостью и линеаризуемостью , которые являются критериями согласованности для реплицируемых систем, таких как реплицируемые базы данных. Однако я не знаю, в каких случаях потребуется линеаризуемость, даже если она сильнее, чем сериализуемость. Не могли бы вы...
Пусть язык L ⊆ Σ ∗L⊆Σ∗\mathcal{L} \subseteq \Sigma^* регулярный. Факторизация LL\mathcal{L} - это максимальная пара ( X , Y )(X,Y)(X,Y) наборов слов с X ⋅ Y ⊆ LX⋅Y⊆LX \cdot Y \subseteq \mathcal{L} X ≠ ∅ ≠ YX≠∅≠YX \neq \emptyset \neq Y , где X ⋅ Y = { x yX⋅Y={xyX \cdot Y = \{xy | x ∈ X , y ∈ Y...
Есть ли какой-нибудь естественный или заметный способ связать или связать математические группы и формальные языки CS или какую-то другую основную концепцию CS, например машины Тьюринга? Я ищу ссылки / приложения. Однако обратите внимание, что я знаю о связи между полугруппами и языками CS (а...
Я пытаюсь понять, что подразумевается под «детерминистическим» в выражениях, таких как «детерминистическая контекстно-свободная грамматика». (Есть более детерминированные «вещи» в этой области). Я был бы признателен за пример более, чем самое сложное объяснение! Если возможно. Мой основной источник...
Используя следующий рекурсивный алгоритм Фибоначчи: def fib(n): if n==0: return 0 elif n==1 return 1 return (fib(n-1)+fib(n-2)) Если я введу число 5, чтобы найти fib (5), я знаю, что это выведет 5, но как мне проверить сложность этого алгоритма? Как рассчитать соответствующие...
Какова сложность MIN-2-XOR-СБMIN-2-XOR-SAT\text{MIN-2-XOR-SAT} и MAX-2-XOR-СБMAX-2-XOR-SAT\text{MAX-2-XOR-SAT} ? Они в П? Они NP-хард? Чтобы формализовать это более точно, пусть Φ ( x ) = ∧NяСя,Φ(x)=∧inCi,\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i, где х =( х1, … , Хм)x=(x1,…,xm)\mathbf{x}...
Я ищу эффективный алгоритм для следующей задачи или доказательства NP-твердости. Пусть Σ - множество, а A ⊆ P ( Σ ) - множество подмножеств Σ . Найдите последовательность w ∈ Σ ∗ наименьшей длины, такую, что для каждого L ∈ A найдется такое k ∈ N , что { w k + i ∣ 0 ≤ i < | L | } = Л...
Я читал статью Википедии о сложности Колмогорова ( благодаря этому вопросу ), в которой говорится: Можно показать, что колмогоровская сложность любой строки не может быть более чем на несколько байтов больше, чем длина самой строки. Зачем вам когда-либо что-то большее, чем сама строка, чтобы...
Функциональное программирование имеет очень элегантное Lambda Calculus и его варианты в качестве теории резервного копирования. Есть ли такая вещь для ООП? Что такое абстракция для объектно-ориентированной...
Я хотел бы привести пример квин в чистом лямбда-исчислении . Я был довольно удивлен, что я не мог найти один, прибегая к помощи. На странице квин есть списки квин для многих «настоящих» языков, но не для лямбда-исчисления. Конечно, это означает определение того, что я имею в виду под квинем в...
Общеизвестно, что «корреляция не равна причинности», но машинное обучение, кажется, почти полностью основано на корреляции. Я работаю над системой оценки успеваемости учащихся по вопросам, основанным на их прошлых выступлениях. В отличие от других задач, таких как поиск в Google, это не похоже на...
Я читал в Википедии и некоторых других текстах, которые Проблема остановки [...] разрешима для линейных ограниченных автоматов (LBA) [и] детерминированных машин с конечной памятью. Но ранее было написано, что проблема остановки - неразрешимая проблема, и поэтому TM не может ее решить! Так как LBA...