У меня есть следующая алгоритмическая проблема: Определить сложность пространства Тьюринга распознавания цепочек ДНК, которые являются палиндромами Уотсона-Крика. Палиндромы Уотсона-Крика - это строки, обратным дополнением которых является исходная строка. Дополнением определяется буква-накрест,...
Дано целое число и множество триплетов различных целых чисел найдите алгоритм, который либо находит перестановку множества такую, что или правильно определяет, что такой перестановки не существует. Менее формально мы хотим изменить порядок номеров от 1 до ; каждая тройка в указывает, что должен...
Я понимаю, что церковная цифра выглядит как λ s . λ z . s (... n раз ...) . Это означает не что иное, как «функция примененная раз к функции ».сNcnc_nλ s . λ z, sλs.λz.s\lambda s. \lambda z. ss n zsZszs\;zsssNnnZzz Возможное определение функции следующее: . Глядя на тело, я понимаю логику функции....
Во многих текстах нижняя граница для нахождения го наименьшего элемента выводится с использованием аргументов, использующих медианы. Как я могу найти один, используя аргумент противника?Кkk Википедия говорит, что алгоритм турнира работает в , и n - k + ∑ n j = n + 2 - k ⌈ lgO ( n + k logн...
Пусть A и B - языки с A ⊆ B, а B распознаваема по Тьюрингу. Может ли быть не узнаваемым по Тьюрингу? Если да, то есть ли
Моя книга утверждает это Если задача решения B находится в P, а A сводится к B, то проблема решения A находится в P. Решение задачи B является NP-полным, если B находится в NP, и для каждой задачи в A в NP, A сводится к B. Решающая задача C является NP-полной, если C находится в NP, а для некоторой...
Хорошо известно, что монотонные полигоны играют решающую роль в триангуляции полигонов . Определение: Многоугольник на плоскости называется монотонным относительно прямой , если каждая прямая, ортогональная пересекает не более двух раз.PPPLLLLLLPPP При заданной прямой и многоугольнике существует ли...
Будет ли необходимость менять определения безопасности, если у нас будут квантовые компьютеры? Какие криптографические конструкции сломаются? Знаете ли вы опрос или статью, которая объясняет, что нужно будет...
Из-за характера вопроса, я должен включить много справочной информации (потому что мой вопрос: как мне сузить это?). Тем не менее, это можно обобщить (насколько мне известно) как: Какие существуют методы поиска локальных оптимумов в чрезвычайно больших комбинаторных пространствах поиска? Фон В...
Я пытаюсь разработать задание (взятое из книги « Алгоритмы» С. Дасгупты, К. Х. Пападимитриу и У. В. Вазирани , глава 8, проблема 8.6а), и я перефразирую то, что в нем говорится: Учитывая, что 3SAT остается NP-завершенным, даже если он ограничен формулами, в которых каждый литерал появляется не...
Есть ли способ оценить, сколько данных добавляется во всемирную паутину каждую секунду? Есть ли какие-либо исследования по этому
Есть ли необходимость, чтобы был бесконечным, чтобы быть неразрешимым?L⊆Σ∗L⊆Σ∗L\subseteq \Sigma^* Я имею в виду, что если мы выберем язык как ограниченную конечную версию , то есть , ( ), с . Возможно ли, что будет неразрешимым языком? L ⊆ Σ ∗ | L ′ | ≤ N N ∈ N L ′ ⊂ L L ′L′L′L' L⊆Σ∗L⊆Σ∗L\subseteq...
Есть ли какие-то преимущества наличия более 2 скрытых слоев в нейронной сети? Я видел некоторые места, которые рекомендуют это, другие доказывают, что нет никакого преимущества. Какой из них...
Альтернативная формулировка Я придумал альтернативную формулировку нижеприведенной проблемы. Альтернативная формулировка на самом деле является частным случаем проблемы ниже и использует двудольные графы для описания проблемы. Тем не менее, я считаю, что альтернативная формулировка все еще...
Я дурачился с демоверсией Google Blocky's Maze и вспомнил старое правило, что если вы хотите решить лабиринт, просто держите левую руку на стене. Это работает для любого односвязного лабиринта и может быть реализовано конечным преобразователем. Пусть наш робот будет представлен преобразователем со...
Я получил доказательство перехода от перечислителя к машине Тьюринга (продолжайте запускать перечислитель и посмотрите, соответствует ли он вводу), но я не вижу, как работает другой способ. Согласно моим заметкам и книге (Введение в теорию вычислений - Sipser), чтобы получить перечислитель Тьюринга...
У меня проблема в голове, я думаю, что это проблема NPC, но я не знаю, как это доказать. Вот проблема: В очень большом озере k островов и n понтонов в форме вееров. Эти понтоны имеют одинаковый размер, но имеют разные начальные направления и находятся в разных первоначальных положениях в озере....
Доказано, что нейронные сети с рациональными весами обладают вычислительной мощностью универсальной машины Тьюринга, вычислимой по Тьюрингу с нейронными сетями . Из того, что я получаю, кажется, что использование вещественных весов дает еще большую вычислительную мощность, хотя я не уверен в этом....
Для данного плоского графа встроены в плоскости, определяется набором отрезков Е = { е 1 , . , , , e m } , каждый сегмент e i представлен своими конечными точками { L i , R i } . Создайте структуру данных DCEL для плоского подразделения, опишите алгоритм, докажите его правильность и покажите...
Я изучал ранговый коэффициент корреляции Спирмена ρ = ∑я( хя- х¯) ( уя- у¯)Σя( хя- х¯)2Σя( уя- у¯)2-------------------√ρзнак равноΣя(Икся-Икс¯)(Yя-Y¯)Σя(Икся-Икс¯)2Σя(Yя-Y¯)2\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2 \sum_i(y_i-\bar{y})^2}} ....