Что мы знаем, так это то, что π бесконечно и вполне вероятно, что оно содержит все возможные конечные цепочки цифр ( дизъюнктивная последовательность ). Недавно я видел некоторый прототип πfs, который предполагает, что каждый файл, который вы создали (или кто-либо еще) или вы создадите, он уже там,...
Есть ли способ вычислить размер максимального соответствия в невзвешенном двудольном графе более эффективно (например, быстрее), чем вычисление максимального соответствия? Это длинный путь, но часто это интересная проблема, чтобы избежать одноразовых вычислений, подобных этим. мотивация Проблема ,...
Закрыто . Этот вопрос основан на мнении . В настоящее время он не принимает ответы. Хотите улучшить этот вопрос? Обновите вопрос, чтобы ответить на него фактами и цитатами, отредактировав этот пост . Закрыто 4 года назад . Я увлекаюсь математической элегантностью и строгостью, и сейчас ищу такую...
В основном проблема заключается в следующем: для набора положительных чисел найти минимальное число , которое не является делителем ни одного элемента из , т. .SSSdddSSS∀x∈S, d∤x∀x∈S, d∤x\forall x \in S,\ d \nmid x Обозначим n=|S|n=|S|n = |S|и C=max(S)C=max(S)C = \max(S) . Рассмотрим функцию...
Учитывая подмножество декартового произведения из двух конечных множеств, я хочу найти его минимальное покрытие множествами, которые сами являются декартовыми произведениями.я× Jя×JI \times J Например, учитывая произведение между и , я могу наблюдать подмножество и постарайтесь покрыть это...
Алгоритм Шора часто используется в качестве аргумента. Он может решить проблему факторизации быстрее, чем любой известный алгоритм для классических компьютеров. Тем не менее, у нас нет доказательств того, что классические компьютеры также не могут эффективно вычислять целые числа. Есть ли...
В качестве забавного проекта я работал над реализацией C # Ричарда Корфа - Поиск оптимальных решений для кубика Рубика с использованием шаблонных баз данных. https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf У меня действительно это работает, я просто пытаюсь улучшить...
Требуется найти степень (целое положительное число) матрицы действительных чисел. Существует множество эффективных алгоритмов умножения матриц (например, некоторые параллельные алгоритмы - Кэннона, DNS ), но существуют ли алгоритмы, предназначенные именно для определения мощности матрицы и более...
У меня есть два набора точек в 2-мерной плоскости. Я хочу найти ближайшую пару точек такую, чтобы , , а евклидово расстояние между как можно меньше. Насколько эффективно это можно сделать? Можно ли это сделать за , где?s , t s ∈ S t ∈ T s , t O ( n log n ) n = | S | + | T |S,TS,TS,Ts,ts,Ts,ts∈Ss∈Ss...
Википедия перечисляет временную сложность сложения как , где - количество битов.нNNnNNn Это жесткая теоретическая нижняя граница? Или это просто сложность самого быстрого известного алгоритма. Я хочу знать, потому что сложность сложения подчеркивает все другие арифметические операции и все...
Предположим , что мы читаем последовательность чисел, один за другим. Как найти к «й наименьший элемент только с помощью O ( K ) клеток памяти и в линейном времени ( O ( п ) ). Я думаю , что мы должны сохранить первые K члены последовательности и когда получим K + 1 «й член, удалить термин ,...
Учитывая симметричную вещественную матрицу , существует ли алгоритм, который вычисляет сумму по всем 1 \ leq i <j <k \ leq n со сложностью по времени лучше, чем O (n ^ 3) ?n×nn×nn \times...
Мне дали следующую проблему во время интервью: Дает строку, которая содержит некоторую смесь символов (без скобок или фигурных скобок - только символы) с другими буквенно-цифровыми символами, идентифицирует все символы без соответствующих имен. Например, в строке ") (ab))" индексы 0 и 5 содержат...
Мне нужно создать рекурсивный алгоритм, чтобы увидеть, является ли двоичное дерево бинарным деревом поиска, а также подсчитать, сколько там полных ветвей (родительский узел с левым и правым дочерними узлами) с предполагаемой глобальной переменной подсчета. Это назначение для моего класса структур...
Первоначально по математике. Но там без ответа. Рассмотрим следующий алгоритм. u := 0 v := n+1; while ( (u + 1) is not equal to v) do x := (u + v) / 2; if ( x * x <= n) u := x; else v := x; end_if end_while где u, v и n - целые числа, а операция деления - целочисленное деление. Объясните, что...
Пусть множество терминального и N множества нетерминальных символов некоторой контекстно-свободная грамматика G .ΣΣ\SigmaNNNGGG Скажем , у меня есть строка такое , что х у ∈ S ( G ) , где х , у ∈ ( Е ∪ N ) * и S ( G ) являются сентенциальные формы G .a ∈(Σ∪N)+a∈(Σ∪N)+a \in (\Sigma \cup N)^+х аy∈ S(...
Я пытаюсь понять, что не так со следующим доказательством следующего повторения T(n)=2T(⌊n2⌋)+nT(n)=2T(⌊n2⌋)+n T(n) = 2\,T\!\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n T(n)≤2(c⌊n2⌋)+n≤cn+n=n(c+1)=O(n)T(n)≤2(c⌊n2⌋)+n≤cn+n=n(c+1)=O(n) T(n) \leq...
Рассмотрим модель CSP, где изменение значения конкретной переменной стоит дорого. Есть ли работа, в которой целевая функция также учитывает количество изменений в значении переменной в процессе поиска? Пример: переменная, дорогая к изменению, может находиться под контролем какого-либо другого...
У меня есть следующая алгоритмическая проблема: Определить сложность пространства Тьюринга распознавания цепочек ДНК, которые являются палиндромами Уотсона-Крика. Палиндромы Уотсона-Крика - это строки, обратным дополнением которых является исходная строка. Дополнением определяется буква-накрест,...
Дано целое число и множество триплетов различных целых чисел найдите алгоритм, который либо находит перестановку множества такую, что или правильно определяет, что такой перестановки не существует. Менее формально мы хотим изменить порядок номеров от 1 до ; каждая тройка в указывает, что должен...