Информатика

Моя проблема. Учитывая , я хочу , чтобы подсчитать число действительных мультимножествами . Мультисеть действительна, еслиS SnnnSSSSSS Сумма элементов является , инSSSnnn Каждое число от до может быть выражена однозначно как сумма некоторых элементов .п S111nnnSSS Пример. Например , если , то...

Извините, если у этого вопроса есть какой-то тривиальный ответ, который я пропускаю. Всякий раз, когда я изучаю какую-то проблему, которая оказалась неразрешимой, я замечаю, что доказательство основывается на сведении к другой проблеме, которая оказалась неразрешимой. Я понимаю, что это создает...

Согласно статье в Википедии о схемах аппроксимации за полиномиальное время : Все проблемы в FPTAS доступны для фиксированных параметров. Этот результат меня удивляет - эти занятия, похоже, совершенно не похожи друг на друга. FPTAS характеризует проблемы по тому, насколько легко их аппроксимировать,...

Решение проблемы Учитывая булеву формулу , имеет ли ровно одно удовлетворяющее присваивание?ϕϕ\phiϕϕ\phi можно увидеть в , -hard и -hard. Что-нибудь более известно о его...

Я работаю над алгоритмами поиска строк, которые поддерживают поиск по нескольким шаблонам. Я нашел два алгоритма, которые кажутся наиболее сильными кандидатами с точки зрения времени выполнения, а именно: Aho-Corasick и Rabin-Karp . Однако я не смог найти исчерпывающего сравнения между этими двумя...

Я читаю Sipser , и я нахожу , что это трудно понять , что этот процесс таким образом, что , если вы дадите мне K машины Тьюринга с к лентам, я могу выплюнуть эквивалентную машину Тьюринга только с одной лентой. Пример был бы хорош. На самом деле, отработанный пример , который показывает , как...

Я только начал изучать искусственный интеллект и мне интересно , почему достижимо фазовое пространство 8-головоломки . Я вижу , что число перестановок из плитокно не сразу очевидно, почему половина возможных состояний головоломки недоступна в любом данном состоянии. Кто-нибудь может...

Существует ли алгоритм / систематическая процедура для проверки правильности языка? Другими словами, учитывая язык , заданный в алгебраической форме (думаю , что - то вроде ), проверить , является ли регулярным или не язык. Представьте, что мы пишем веб-сервис, чтобы помочь студентам со всеми...

Как бы вы подошли к проблеме ранца в ситуации динамического программирования, если теперь вам нужно ограничить количество предметов в ранце константой ппp ? Это та же самая проблема (максимальный вес , каждый предмет имеет значение и вес ), но вы можете добавить только предмет (ы) в рюкзак и,...

Пусть nnn будет целым числом, и пусть ZZ\mathbb{Z} обозначает множество всех целых чисел. Обозначим через [a,b][a,b][a,b] интервал целых чисел {a,a+1,a+2,…,b}{a,a+1,a+2,…,b}\{a,a+1,a+2,\dots,b\} . Ищу структуру данных для представления отображения f:[1,n]→Zf:[1,n]→Zf:[1,n] \to \mathbb{Z} . Я хочу,...

Меня интересуют свойства класса двудольных графов где все узлы в 3-регулярны, все узлы в 2-регулярны и, Во-первых, это хорошо известный класс графиков? Во- вторых,G(X∪Y,E)G(X∪Y,E)G(X \cup Y, E)XXXYYY|X|=|2Y/3||X|=|2Y/3||X|=|2Y/3| Есть ли пример неразрешимой вычислительной задачи, ограниченной этим...

У меня есть проблема, и я думаю, что это NP-трудно, но я не могу доказать это. Вот график слоя, где слой 0 - самый высокий слой, а слой L - самый низкий. Есть некоторые направленное ребро между слоями, где ребро (А, В) указывает на то, что узел А может [крышка] узла В. И когда А может охватывать B,...

Контекстно-свободные языки не закрываются при дополнении. В лекциях нам дали тот же аргумент, что и здесь, в Википедии : для A={anbncm; m,n∈N0}andB={ambncn; m,n∈N0},A={anbncm; m,n∈ℕ0}andB={ambncn; m,n∈ℕ0},A = \{\mathtt a^n \mathtt b^n \mathtt c^m;~m, n ∈ ℕ_0\}\quad\text{and}\quad B = \{\mathtt a^m...

Учитывая два набора строк над алфавитом Σ , можем ли мы вычислить наименьший детерминированный конечный автомат (DFA) M такой, что A ⊆ L ( M ) и L ( M ) ⊆ Σ ∗ ∖ B ?А , БA,ВA,BΣΣ\SigmaMMMA ⊆ L ( M)A⊆L(M)A \subseteq L(M)Л ( М) ⊆ Σ*∖ BL(M)⊆Σ*∖ВL(M) \subseteq \Sigma^*\setminus B Другими словами,...

Я участвую в первом курсе по программированию и алгоритмам. В недавней лекции я решил представить материал, используя живое кодирование , что по сути означало, что я сижу за клавиатурой, пишу код и оцениваю его, используя emacs для облегчения процесса. Это было довольно успешно, и студенты...

Я прочитал несколько раз, что невозможно эффективно перевернуть ответ NDTM. Однако я не понимаю, почему. Например, учитывая NDTM который выполняется в , этот текст (раздел 3.3) утверждает, что неясно, как другой NDTM может определить за время, как перевернуть...

Мы были представлены в классе с алгоритмом нахождения максимума в массиве параллельно в временной сложности с компьютерами.O(1)O(1)O(1)n2n2n^2 Алгоритм был: Дан массив A длины n: Создайте массив флагов B длиной n и инициализируйте его нулями с компьютерами.nnn Сравните каждые 2 элемента и напишите...

Минимизация детерминированных конечных автоматов (DFA) является проблемой, которая была тщательно изучена в литературе, и было предложено несколько алгоритмов для решения следующей проблемы: Учитывая DFA , вычислим соответствующий минимальный DFA, принимающий тот же язык, что и . Большинство этих...

Я видел машины Тьюринга, изображенные бесконечными лентами в одном и двух направлениях. Есть ли разница в мощности таких машин Тьюринга или они в основном эквивалентны? В своей голове я думаю, что они эквивалентны, так как я предполагаю, что должен быть какой-то способ представить двустороннюю...

Сколько арифметических операций требуется, чтобы найти псевдообратную матрицу Мура – ​​Пенроуза произвольного поля? Если матрица обратима и имеет комплексное значение, то это просто обратная величина. Нахождение обратного времени занимает , где - константа умножения матриц. Это Теорема 28.2 в...