Проблема остановки не может быть решена в общем случае. Можно придумать определенные правила, которые ограничивают разрешенные входы, и можно ли решить проблему остановки для этого особого случая? Например, кажется вероятным, что язык, который не допускает циклы, например, будет очень легко...
Из ответов на (Когда) есть поиск в хэш-таблице O (1)? Я понимаю, что хеш-таблицы имеют O ( 1 )О(1)O(1) наихудшее поведение, по крайней мере амортизированное, когда данные удовлетворяют определенным статистическим условиям, и существуют методы, которые помогут сделать эти условия широкими. Однако, с...
Проще говоря, если бы нужно было создать квантовое вычислительное устройство с мощностью, скажем, 20 кубитов, мог бы такой компьютер быть использован для того, чтобы сделать любой современный алгоритм хеширования бесполезным? Возможно ли даже использовать мощь квантовых вычислений в традиционных...
Теория Экзистенциальная из реалов в PSPACE , но я не знаю , является ли это PSPACE-Complete . Если я считаю, что это не так, как я могу доказать это? В более общем смысле, учитывая проблему в некотором классе сложности X , как я могу показать, что это не X-Complete ? Например, X может быть NP ,...
Комбинаторика играет важную роль в информатике. Мы часто используем комбинаторные методы как в анализе, так и в алгоритмах. Например, один из методов нахождения покрытия графа вершины в графе может просто проверить все \ binom {n} {k} возможных подмножеств. В то время как биномиальные функции...
Как следует из моего предыдущего вопроса , я играл с гипотезой Римана как с рекреационной математикой. В ходе этого процесса я столкнулся с довольно интересным повторением, и мне любопытно, как оно называется, как оно сокращается, и как оно приспосабливается к разрешимости разрыва между простыми...
Разрешены ли проблемы типа «посещение вечеринки» в Прологе? Например: Лопух Малдун и Карлотта Пинкстоун сказали, что придут, если придет Альбус Дамблдор. Альбус Дамблдор и Дейзи Доддридж оба сказали, что придут, если придет Карлотта Пинкстоун. Альбус Дамблдор, Бердок Малдун и Карлотта Пинкстоун...
Как проверить, возвращают ли два алгоритма (скажем, сортировка слиянием и наивная сортировка) один и тот же результат для любого входа, когда набор всех входов бесконечен? Обновление: Спасибо, Бен, за описание того, как это невозможно сделать алгоритмически в общем случае. Ответ Дейва - это краткое...
Я начал читать все больше и больше статей по языковым исследованиям. Я нахожу это очень интересным и хорошим способом узнать больше о программировании в целом. Тем не менее, как правило , приходит раздел , где я всегда борюсь с (Возьмем, например , части третьей этой ) , так как мне не хватает...
Учебники повсюду предполагают, что проблема ограниченной почтовой корреспонденции является NP-полной (не более индексов допускается с повторениями). Тем не менее, нигде не показано простого (как, например, то, что может понять студент) полиномиального сокращения времени из другой NP-полной...
Википедия определяет это как Считается, что алгоритм имеет полиномиальное время, если его время выполнения ограничено сверху полиномиальным выражением в размере входных данных для алгоритма, т. Е. для некоторой константы k.T( n ) = O ( nК)T(N)знак равноО(NК)T(n) = O(n^k) Алгоритм работает за сильно...
В своей книге Рандомизированных алгоритмы , Motwani и Raghavan открыть введение с описанием их функции RandQS - Рандомизированная - где быстрой сортировкой стержень, используемый для разделения множества на две части, выбирается случайным образом . В течение некоторого времени я ломал свои мозги...
Учитывая регулярный язык , легко доказать, что существует постоянная N такая, что σ ∈ L , причем | σ | ≥ N существуют строки α , β и γ такие, что | α β | ≤ N и | β | ≠ & epsi ; и для всех к это & alpha ; & beta ; к & gamma ∈ LLLLNNNσ∈ Lσ∈L\sigma \in L| σ| ≥ N|σ|≥N\lvert \sigma...
Дана матрица . Пусть обратная матрица будет (то есть ). Предположим, что один элемент в изменен (скажем, до ). Цель состоит в том, чтобы найти после этого изменения. Есть ли способ найти эту цель, который более эффективен, чем пересчет обратной матрицы с нуля.n × nN×Nn \times...
В последнее время я самостоятельно изучал максимизацию ожиданий и собрал в процессе несколько простых примеров: От сюда : Есть три монеты c0c0c_0 , c1c1c_1 и c2c2c_2 с p0p0p_0 , p1p1p_1 и p2p2p_2 соответствующей вероятностью для посадки на голове , когда кинули. Бросок c0c0c_0 . Если результат -...
У вас есть массив из отдельных элементов. У вас есть доступ к компаратору (функция черного ящика, принимающая два элемента и и возвращающая true, если ) и действительно случайный источник битов (функция черного ящика, не принимающая аргументов и возвращающая независимо равномерно случайный бит)....
Если у меня возникла сложная проблема, один из стандартных подходов состоит в том, чтобы выразить его как экземпляр SAT и попробовать запустить на нем решатель SAT. Другой стандартный подход состоит в том, чтобы выразить это как проблему удовлетворения ограничений и попытаться использовать решатель...
В частности: 1) Кэш прямого отображения с 4096 блоками / строками, в котором каждый блок содержит 8 32-битных слов. Сколько бит нужно для полей тегов и индексов, предполагая 32-битный адрес? 2) Тот же вопрос, что и 1), но для полностью ассоциативного кэша ? Поправьте меня, если я ошибаюсь, не так...
Я заинтересован в небольшом варианте мозаики: головоломка: каждый край (квадратной) плитки помечен символом из , и две плитки могут быть расположены рядом друг с другом, если символ на лицевой стороне одной плитки равен а символ на лицевой стороне другой плитки равен , для некоторых . Тогда,...
Я знаком с дюжиной языков программирования, которые в некотором роде имеют исключения, но я стал свидетелем двух «патологических» тенденций. Кажется, что не существует общего шаблона или иерархии исключений. Каждый язык в основном катит свою собственную версию, и если исключения делают это...