У меня есть эти вопросы из старого экзамена, который я пытаюсь решить. Для каждой задачи, вход является кодирование некоторой машины Тьюринга MMM . Для целого числа c>1c>1c>1 и следующих трех задач: Правда ли, что для каждого входа xxx M не передает |x|+c|x|+c|x|+c позиции при работе на xxx ?...
Классическое приложение «разделяй и властвуй» заключается в решении следующей проблемы: Учитывая массив различных сопоставимых элементов, подсчитайте количество пар инверсии в массиве: пар ( i , j ), таких что a [ i ] > a [ j ] и i < j .a[1…n]a[1…n]a[1\dots...
В этом вопросе о подсчете инверсий я нашел статью, в которой доказывается нижняя оценка сложности пространства для всех (точных) потоковых алгоритмов . Я утверждал, что эта граница распространяется на все линейные алгоритмы времени. Это немного жирным шрифтом, так как в целом, алгоритм линейного...
Я пытаюсь научить себя использованию зубров. На странице man bison (1) говорится о зубре: Создайте детерминированный LR или обобщенный анализатор LR (GLR) с использованием таблиц LALR (1), IELR (1) или канонических LR (1). Что такое IELR-парсер? Все соответствующие статьи, которые я нашел во...
Мне 16 лет, и мой друг недавно подарил мне большую энциклопедию по информатике. Я обычно не очень интересуюсь компьютерами и технологиями, но компьютерные науки начали очаровывать меня. Однако я собираюсь изучать физику и / или математику, а не CS, поэтому мой вопрос: было бы полезно провести...
Я понимаю, что быстрее, чем и медленнее, чем . Мне трудно понять, как на самом деле сравнить и с где .Θ ( n log n ) Θ ( n / log n ) Θ ( n log n ) Θ ( n / log n ) Θ ( n f ) 0 < f < 1Θ(n)Θ(n)\Theta(n)Θ(nlogn)Θ(nlogn)\Theta(n\log n)Θ(n/logn)Θ(n/logn)\Theta(n/\log n)Θ(nlogn)Θ(nlogn)\Theta(n...
У меня есть ряд связанных вопросов по этим двум темам. Во- первых, большинство текстов сложности только замазывать класс NCNC\mathbb{NC} . Есть ли хороший ресурс, который более подробно освещает исследования? Например, то, что обсуждает все мои вопросы ниже. Кроме того, я предполагаю, что...
Планар 3SAT является NP-полным. Планарный экземпляр 3SAT - это экземпляр 3SAT, для которого график, построенный с использованием следующих правил, является плоским: добавить вершину для каждого и ¯ х яxixix_ixi¯xi¯\bar{x_i} добавить вершину для каждого предложения CjCjC_j добавить ребро для каждого...
Из Википедии о рандомизированных алгоритмах Нужно различать алгоритмы, которые используют случайный ввод для уменьшения ожидаемого времени работы или использования памяти, но всегда заканчивают с правильным результатом в ограниченное время, и вероятностные алгоритмы , которые, в зависимости от...
Предположим, что у нас есть множество DDD и каждый член DDD является парой данных и ключей. Нам нужна структура данных, которая бы поддерживала следующие операции: Вставьте (d,k)(d,k)(d,k) в DDD , Удалить член eee (не нужно искать, чтобы найти eee , например, eee указывает на члена в DDD ),...
У меня есть группа из n наборов, для которых мне нужно вычислить значение типа «уникальность» или «сходство». Я остановился на индексе Жакара как на подходящей метрике. К сожалению, индекс Жакара работает только с двумя наборами одновременно. Для того чтобы вычислить сходство между всеми...
Если действительно равен , как это улучшит наши алгоритмы, чтобы быстрее вычислять целые числа? Другими словами, какое понимание даст нам этот факт для лучшего понимания целочисленной факторизации?PP{\sf P}NPNP{\sf...
Я хотел бы знать, существует ли функция fff от n-битных чисел до n-битных чисел, которая имеет следующие характеристики: fff должно быть биективным Оба fff и f−1f−1f^{-1} должны быть вычислены довольно быстро fff должен вернуть число, которое не имеет существенной корреляции с его вводом....
Алгоритм Беллмана-Форда определяет кратчайший путь от источника до всех других вершин. Первоначально расстояние между и всеми остальными вершинами установлено в . Затем вычисляется кратчайший путь от до каждой вершины; это продолжается для итераций. Мои вопросы:ssssss∞∞\inftysss|V|−1|V|−1|V|-1...
Я пытаюсь решить проблему с графиком (это не для домашней работы, просто для тренировки моих навыков). Дана DAG , где V - множество вершин, а E - ребра. Граф представлен в виде списка смежности, поэтому A v - это множество, содержащее все соединения v . Моя задача состоит в том, чтобы найти , какие...
Я не выпускник CS, и моя область исследований не связана с CS. Тем не менее, в рамках более крупного плана стать специалистом по информатике, я хочу получить солидный опыт в теоретической информатике и математике применительно к CS. Я провел много исследований и выбрал следующие лучшие /...
Аппликативный порядок: всегда полностью оценивайте аргументы функции перед оценкой самой функции, например: (λx.x2(λx.(x+1) 2)))→(λx.x2(2+1))→ (λx.x2(3))→ 32 → 9(λx.x2(λx.(x+1) 2)))→(λx.x2(2+1))→ (λx.x2(3))→ 32 → 9(\lambda x. x^2(\lambda x.(x+1) \ \ 2))) \rightarrow (\lambda x....
Дана трубка с пронумерованными шариками (случайно). Трубка имеет отверстия для удаления шарика. Рассмотрим следующие шаги для одной операции: Вы можете выбрать один или несколько шариков из отверстий и запомнить порядок, в котором вы выбрали шарики. Вам нужно наклонить трубу влево, чтобы оставшиеся...
Я наткнулся на странный опыт программирования на Си. Рассмотрим этот код: int main(){ int array1[6] = {0, 1, 2, 3, 4, 5}; int array2[6] = {6, 7, 8, 9, 10, 11}; printf("%d\n", array1[-1]); return 0; } Когда я компилирую и запускаю это, я не получаю никаких ошибок или предупреждений. Как сказал мой...
Я хочу знать, разрешима ли следующая проблема: Экземпляр: NFA A с n государствами Вопрос: существует ли некоторое простое число p такое, что A принимает некоторую строку длины p. Я считаю, что эта проблема неразрешима, но я не могу доказать это. Решающий орган может легко иметь алгоритм для...