Вопрос в упражнении 1.9 из книги Арора-Барака « Вычислительная сложность - современный подход» : Определите машину Тьюринга в ОЗУ как машину Тьюринга с оперативной памятью. Мы формализуем это следующим образом: У машины есть бесконечный массив A, который инициализируется для всех пробелов. Он...
Является ли с оракулом доступ к N P больше, чем просто N P ? Как я понимаю, N P N P - это просто машина Тьюринга, которая может выполнять запросы к другой машине N P, если таковая, кроме N P, может имитировать N P N P ? Что-то не так с этим аргументом?NпNпNPNпNпNPNпNпNPNпNпNпNпNP^...
Адреса IPv6 в форме 862A:7373:3386:BF1F:8D77:D3D2:220F:D7E0гораздо сложнее запомнить или даже расшифровать, чем 4 октета IPv4. Там уже была попытка смягчить это, делая IPv6 - адрес как - то более запоминающимся. Существует ли намеренно слабая хеш-функция, которую можно было бы обратить вспять,...
Есть ли формальное определение средней высоты бинарного дерева? У меня есть вопрос по нахождению средней высоты двоичного дерева с помощью следующих двух методов: Естественным решением может быть определение средней длины всех возможных путей от корня до листа, то есть AVH1( Т) = 1# листья в Т⋅ ∑V...
Я не уверен, принадлежит ли этот вопрос здесь, и я прошу прощения, если нет. Что я хочу сделать, так это разработать программный способ, с помощью которого я могу вероятностно определить, принадлежит ли данная строка «сумке строк». Например, если у меня есть сумка из 10 000 названий городов США, а...
Я задал (начальный) вопрос о суммах терминов Ландау прежде , пытаясь измерить опасность злоупотребления асимптотическими обозначениями в арифметике, но с переменным успехом. Теперь, здесь наш рецидивы гуру JeffE делает в основном это: ∑i=1nΘ(1i)=Θ(Hn)∑i=1nΘ(1i)=Θ(Hn)\qquad \displaystyle...
Предположим, что - обычный язык над упорядоченным алфавитом. Создан ли язык, беря каждое слово в и сортируя его всегда как обычный
\newcommand\ldotd{\mathinner{..}} Учитывая, что A[1..n]A[1..n]A[1\ldotd n] являются целыми числами, такими, что 0≤A[k]≤m0≤A[k]≤m0\le A[k]\le m для всех 1≤k≤n1≤k≤n1\le k\le n , и вхождением каждого число, кроме определенного числа в A[1..n]A[1..n]A[1\ldotd n] является нечетным числом. Попробуйте...
Какова сложность вычисления ?nn2,n∈Nnn2,n∈Nn^{n^2},\;n \in
В Википедии дается реализация восходящей схемы динамического программирования для расстояния редактирования. Это не следует определению полностью; внутренние ячейки вычисляются следующим образом: if s[i] = t[j] then d[i, j] := d[i-1, j-1] // no operation required else d[i, j] := minimum ( d[i-1, j]...
Ради интереса я пытаюсь сделать каркасный просмотрщик для DCPU-16 . Я понимаю, как сделать все, кроме как скрыть линии, которые скрыты в каркас. Все вопросы здесь, касающиеся SO, предполагают, что у вас есть доступ к OpenGL, к сожалению, у меня нет доступа ни к чему подобному для DCPU-16 (или к...
Как я могу построить пример DFA, который имеет состояний, где эквивалентный NFA имеет состояний. Очевидно, набор состояний DFA должен содержать все подмножества набора состояний NFA, но я не знаю, с чего начать. Любые предложения, чтобы поставить меня на правильный...
При доказательстве теоремы разрешения обычно предполагается, что переменные в разных разделах различны. Это не то, что происходит автоматически; это требует значительного дополнительного кода и вычислений для реализации. Учитывая это, я ищу тестовый пример для него. Проблема в том, что во всех...
Я ищу специальность в теоретической информатике; в частности, меня интересуют теория сложности и теория вероятностных автоматов. Когда я заканчиваю учебу в течение одного года, какие продвинутые курсы по математике (например, теория Галуа или гармонический анализ), по вашему мнению, было бы полезно...
Означает ли принятие, что ТМ будет читать и распознавать символ из ячейки, с которой он в данный момент читает? И это тот случай, когда ТМ останавливается, если вход...
Я читал в Википедии, что объединение - это процесс решения проблемы выполнимости. В то же время я знаю, что такие решатели называются «решателями SAT» или «решателями SMT». Так это разные имена для одного и того же? Если вы говорите, что они разные, пожалуйста, укажите на недостатки в моем лечении....
Я ищу быстрый алгоритм сопоставления строк k-несоответствие. Учитывая строку шаблона P длины m и текстовую строку T длины n, мне нужен быстрый (линейное время) алгоритм, чтобы найти все позиции, где P соответствует подстроке T с не более чем k несоответствиями. Это отличается от проблемы k-отличий...
Я запутался, решая следующую проблему (вопросы 1–3). Вопрос Д -ичные куч, как двоичные кучи, но (с одним возможным исключением) узлы без листьев имеют d детей вместо 2 -х детей. Как бы вы представили d -ary кучу в массиве? Какова высота d- дневной кучи из n элементов в терминах n и d ? Дайте...
У меня есть проблема, которая может быть сведена к проблеме назначения. (В предыдущем вопросе я узнал, как это сделать.) Это означает, что у нас есть набор агентов и набор задач а также функция стоимости . Нам нужно найти назначение, чтобы общая стоимость была минимальной.AAAc ( i , j...
В моем классе Java мы изучаем сложность различных типов коллекций. Вскоре мы будем обсуждать бинарные деревья, о которых я читал. Книга утверждает, что минимальная высота бинарного дерева составляет , но не дает дополнительных объяснений.log2(n+1)−1log2(n+1)−1\log_2(n+1) - 1 Может кто-нибудь...