Я читал Введение в алгоритмы от Cormen et al. и я читаю формулировку основной теоремы, начиная со страницы 73 . В случае 3 также существует условие регулярности, которое необходимо выполнить, чтобы использовать теорему: ... 3. Если f(n)=Ω(nlogba+ε)е(N)знак равноΩ(Nжурналбa+ε)\qquad \displaystyle...
Эта проблема для меня выглядит очень интересной. Он собирался найти простой цикл (то есть цикл, где нет повторяющихся узлов) в ориентированном графе. Мое решение идет следующим образом, то есть этот график является проблемой случая: Я знаю, что в графике есть цикл, когда вы можете найти «задние...
Текущие шахматные алгоритмы проходят примерно на 1 или 2 уровня вниз по дереву возможных путей в зависимости от хода игрока и ходов противника. Допустим, у нас есть вычислительные возможности для разработки алгоритма, который предсказывает все возможные движения противника в шахматной игре....
Очевидно, что если , все языки в кроме и , будут -полными.P = N P P ∅ Σ ∗ N PP=NP{\sf P}={\sf NP}P{\sf P}∅\emptysetΣ*\Sigma^*Н П{\sf NP} Почему именно эти два языка? Разве мы не можем свести к ним какой-либо другой язык в Pп{\sf P} , выводя их при принятии или не...
Счетные машины с двумя или более счетчиками обычно показаны эквивалентными машинам Тьюринга в курсах по теории вычислений. Однако я не видел формального анализа того, какие языки можно распознать с помощью машины с одним счетчиком. Являются ли эти языки эквивалентными языкам, не зависящим от...
Недавнее сообщение в блоге о поиске трех равномерно распределенных приводит меня к вопросу о стековом потоке с главным ответом, который утверждает, что сделал это за O (n lg n) время. Интересная часть состоит в том, что решение включает возведение в квадрат полинома, ссылаясь на статью, которая...
После того, как я узнал, как построить массив суффиксов в сложности O(N)O(N)O(N) , я заинтересовался открытием приложений массивов суффиксов. Одним из них является нахождение самой длинной общей подстроки между двумя строками за O(N)O(N)O(N) времени. Я нашел в интернете следующий алгоритм:...
Хидоку - это сетка с некоторыми предварительно заполненными целыми числами от 1 до . Цель состоит в том, чтобы найти путь последовательных целых чисел (от 1 до ) в сетке. Более конкретно, каждая ячейка сетки должна содержать различное целое число от 1 до и каждая ячейка со значением должна иметь...
Таким образом, в основном L удовлетворяет условиям леммы накачки для КЛЛ, но не является КЛЛ (это возможно в соответствии с определением
Я пытаюсь найти эффективный метод определения, имеет ли данный граф G два разных минимальных остовных дерева. Я также пытаюсь найти метод, чтобы проверить, есть ли у него 3 различных минимальных остовных дерева. Наивное решение, о котором я думаю, - запустить алгоритм Крускала один раз и найти...
В оригинальной статье о распределенных системах Парламент с частичной занятостью (протокол Paxos) Лесли Лэмпорт называет выдуманных законодателей, которые участвуют в протоколе парламента Paxon. Согласно этому письму , он отмечает, что: Я дал греческим законодателям имена компьютерных ученых,...
Википедия говорит : Полные решетки появляются во многих приложениях в математике и информатике Это просто ссылка на тот факт, что стандартная булева алгебра, используемая в вычислениях, является полной решеткой? Есть ли что-то, что мы приобретаем, работая на абстрактном уровне решеток, а не...
Скорее всего, этот вопрос задавался раньше. Это из CLRS (2-е изд) проблема 6.5-8 - Задайте алгоритм времени для объединения k отсортированных списков в один отсортированный список, где n - общее количество элементов во всех входных списках. (Подсказка: используйте минимальную кучу для слияния k-...
Каковы некоторые примеры сложных проблем решения, которые могут быть решены за полиномиальное время? Я ищу проблемы, для которых оптимальный алгоритм является «медленным», или проблемы, для которых самый быстрый известный алгоритм является «медленным». Вот два примера: Распознавание совершенных...
Недавно был задан интересный вопрос, который впоследствии был удален. Для обычного языка его сложность DFA - это размер минимального DFA, принимающего его, а сложность NFA - это размер минимального NFA, принимающего его. Хорошо известно, что между двумя сложностями существует экспоненциальное...
Я хочу начать с того, что это НЕ домашний вопрос. Я читаю Введение в алгоритмы - известный текст CLRS, чтобы стать лучшим программистом. Я пытаюсь решить проблемы и упражнения, приведенные в книге, самостоятельно. Я пытаюсь решить Excercise 10.1-2 из главы 10 «Элементарные структуры данных» из...
Есть ли разница между ними? Согласно книге Уллмана , компиляторы конвертируют один язык в другой (обычно низкоуровневый), как и ассемблер. Чем они отличаются?...
library(ggplot2) compress <- function(str) { length(memCompress(paste(rep("a", str), collapse=""), type="bzip2")) / nchar(paste(rep("a", str), collapse="")) } cr <- data.frame(i = 1:10000, r = sapply(1:10000, compress)) ggplot(cr[cr$i>=5000 & cr$i<=10000,], aes(x=i, y=r)) +...
Я делал упражнения по динамическому программированию и нашел алгоритм Флойда-Варшалла. По-видимому, он находит кратчайшие пути из всех пар для графа, который может иметь отрицательные весовые ребра, но без отрицательных циклов. Итак, мне интересно, каково в действительности значение отрицательных...
У нас есть DAG. У нас есть функция на узлах (грубо говоря, мы нумеруем узлы). Мы хотели бы создать новый ориентированный граф с этими правилами:F: V→ NF:V→NF\colon V\to \mathbb N Только узлы с одинаковым номером могут быть заключены в один и тот же новый узел. . (Однако .)x ′ ≠ y ′ ⇏ F ( x ) ≠ F (...