Существуют ли NP-полные задачи, которые доказали алгоритмы субэкспоненциального времени? Я спрашиваю об общих входных данных, я не говорю о конкретных особых случаях здесь. Под субэкспоненциальным я подразумеваю порядок роста над полиномами, но менее экспоненциального, например,...
Я прочитал статью в Википедии о « Списке проблем с NP-полнотой » и обнаружил, что такие игры, как Super Mario, Pokemon, Tetris или Candy Crusha Saga, являются NP-полными. Как я могу представить np-полноту игры? Ответы не должны быть слишком точными. Я просто хочу получить общее представление о том,...
В многоядерном процессоре, что происходит с содержимым кэша ядра (скажем, L1), когда происходит переключение контекста в этом кэше? Зависит ли поведение от архитектуры или от всех производителей...
Почему в информатике любая сложность, которая в большинстве случаев является полиномиальной, считается эффективной? Для любого практического применения (a) алгоритмы со сложностью работают намного быстрее, чем алгоритмы, выполняющиеся во времени, скажем, , но первый считается неэффективным, а...
Я закончил разработку приложения для Android и собираюсь опубликовать его под лицензией GPL - я хочу, чтобы оно было с открытым исходным кодом. Однако природа приложения (игры) заключается в том, что оно задает загадки и кодирует ответы в строковом ресурсе. Я не могу опубликовать ответы! Мне...
Вы должны проверить, что ваш друг, Боб, имеет ваш правильный номер телефона, но вы не можете спросить его напрямую. Вы должны написать вопрос на карточке и передать его Еве, которая передаст карточку Бобу и вернет вам ответ. Что вы должны написать на карточке, помимо вопроса, чтобы Боб мог...
Поиск массив элементов с помощью бинарного поиска дублей, в худшем случае журнал 2 N итераций , потому что на каждом шаге мы подрезать половину нашего пространства поиска. Если бы вместо этого мы использовали «троичный поиск», мы бы вырезали две трети пространства поиска на каждой итерации, поэтому...
Все знают, что скорость вычислений резко возросла с момента их изобретения, и, похоже, она продолжится. Но меня озадачивает одно: если бы вы пропустили электрический ток через материал сегодня, он бы двигался с той же скоростью, как если бы вы делали это с тем же материалом 50 лет назад. Имея это в...
Есть много способов доказать, что язык не является регулярным , но что мне нужно сделать, чтобы доказать, что какой-то язык является регулярным? Например, если мне дано, что регулярно, как я могу доказать, что следующее регулярно?LLLL'L′L' L': = { w ∈ L : u v = w для u ∈ Σ*∖ L и v ∈...
Я читаю книгу под названием « Принципы информатики» (2008) Карла Рейнольдса и Пола Тиманна (опубликована в «Схемах Шаума»). Во второй главе представлены алгоритмы с примером последовательного поиска, который просто перебирает список имен и возвращает TRUE, если в списке найдено данное имя. Автор...
Из того, что я обнаружил, очень большое количество протоколов, которые передаются через Интернет, являются «текстовыми», а не двоичными. Рассматриваемые протоколы включают, но не ограничиваются HTTP, SMTP, FTP (я думаю, что все эти текстовые?), WHOIS, IRC. Фактически, некоторые из этих протоколов...
Заранее извиняюсь за наивность этого вопроса. Мне 50 лет, и я впервые пытаюсь правильно понять компьютеры. Так что здесь идет. Я пытался понять, как типы данных и переменные обрабатываются компилятором (в очень общем смысле, я знаю, что это много). Мне не хватает чего-то в моем понимании...
Существует множество структур данных, которые реализуют интерфейс очереди приоритетов: Вставить: вставить элемент в структуру Get-Min: вернуть самый маленький элемент в структуре Extract-Min: удалить самый маленький элемент в структуре Распространенными структурами данных, реализующими этот...
Сопоставление паттернов высокого порядка - неразрешимая проблема. Это означает, что не существует алгоритма, который, учитывая уравнение a => b, где aи bявляются открытыми слагаемыми в простом типе лямбда-исчисления, находит замену так S, что aS => bS, где =>означает «имеет такую же Bn...
Кажется, что везде, где я смотрю, структуры данных реализуются с использованием красно-черных деревьев ( std::setв C ++, SortedDictionaryв C # и т. Д.) Только что покрыв (a, b), красно-черные и AVL деревья в своем классе алгоритмов, вот что я получил (также из бесед с профессорами, просмотра...
Чтобы найти медиану несортированного массива, мы можем сделать минимальную кучу за времени для элементов, а затем мы можем извлечь один за другим элементов, чтобы получить медиану. Но этот подход занял бы времени.O(nlogn)O(nlogn)O(n\log n)nnnn/2n/2n/2O(nlogn)O(nlogn)O(n \log n) Можем ли мы...
Обсуждая некоторые темы начального уровня сегодня, в том числе использование генетических алгоритмов; Мне сказали, что исследования в этой области действительно замедлились. Причина была в том, что большинство людей сосредоточено на машинном обучении и интеллектуальном анализе данных. Обновление:...
В чем разница между алгоритмом минимального связующего дерева и алгоритмом кратчайшего пути? В моем классе структур данных мы рассмотрели два алгоритма минимального связующего дерева (Прима и Крускала) и один алгоритм кратчайшего пути (Дейкстры). Минимальное остовное дерево - это дерево в графе,...
Обсуждая, насколько многопоточной должна быть наша программа, моя команда ломала голову над тем, есть ли что-то, что абсолютно невозможно сделать на одноядерном процессоре. Я утверждал, что обработка графики требует массовой параллельной обработки, но они утверждают, что такие вещи, как DOOM, были...
Существует этот стандартный алгоритм поиска самого длинного пути в ненаправленных деревьях с использованием двух поисков в глубину: Запустите DFS из случайной вершины и найдите самую дальнюю из нее; скажи это .vvvv′v′v' Теперь запустите DFS из чтобы найти самую дальнюю вершину. Этот путь является...