Я заметил, что существует два различных типа состояний в предсказании ветвлений. В суперскалярном выполнении, где прогноз ветвления очень важен, и он в основном в задержке выполнения, а не в задержке выборки. В конвейере команд, где выборка является более проблемной, поскольку инструкции на самом...
Какое из следующих утверждений является правильным? достаточные и необходимые условия о регулярности языка существуют, но еще не обнаружены. Там нет достаточного и необходимого условия о регулярности языка. Насосная лемма является необходимым условием нерегулярности языка. Насосная лемма является...
Рассмотрим файловую систему, нацеленную на некоторые встроенные устройства, которая делает чуть больше, чем хранит файлы в иерархической структуре каталогов. В этой файловой системе отсутствуют многие операции, которые вы можете использовать в таких системах, как Unix и Windows (например, ее права...
Как можно решить, имеет ли некоторую последовательность цифр? ππ\piвдохновил меня на вопрос, можно ли вычислить следующую невинную версию: е( n ) = { 10если н¯ происходит в десятичном представлении πв противном случаеf(n)={1if n¯ occurs in the decimal representation of π0otherwisef(n) =...
Переписывание системы представляет собой набор правил в виде . Если мы применим это правило к строке мы заменим любую подстроку в подстрокой и наоборот.A ↔ BA↔ВA \leftrightarrow BвесвесwAAAвесвесwВВB Учитывая начальную строку мы можем получить в системе по следующим правилам:A A A B BAAAВВAAABBB A...
Диспенсер для напитков требует, чтобы пользователь вставил монету ( ), а затем нажмите одну из трех кнопок: запрашивает чашку чая , то же самое для кофе , и запрашивает возврат (т. е. автомат возвращает монету: ). Этот дозатор может быть смоделирован следующим процессом CCS :c¯c¯\bar...
Алгоритм машины Тьюринга за полиномиальное время считается эффективным, если его время выполнения, в худшем случае, ограничено полиномиальной функцией входного размера. Мне известен сильный тезис Черча-Тьюринга: Любая разумная модель вычислений может быть эффективно смоделирована на машинах...
Это может граничить с вычислительной когнитивной наукой, но мне любопытно, как процесс, сопровождаемый общими алгоритмами поиска пути (такими как A * ), сравнивается с процессом, который люди используют в различных ситуациях поиска пути (учитывая ту же информацию). Эти процессы...
У меня есть следующий язык { 0я1J2К∣ 0 ≤ i ≤ j ≤ k }{0i1j2k∣0≤i≤j≤k}\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\} Я пытаюсь определить, к какому классу языка Хомского он подходит. Я могу видеть, как это можно сделать, используя контекстно-зависимую грамматику, поэтому я знаю, что это, по...
В настоящее время я изучаю лямбда-исчисление, и мне было интересно узнать о двух разных видах написания лямбда-термина. λxy.xyλxy.xy\lambda xy.xy λx.λy.xyλx.λy.xy\lambda x.\lambda y.xy Есть ли разница в значении или способе применения бета-сокращения, или это просто два способа выразить одно и то...
Если я правильно понимаю, NFA обладают той же выразительной силой, что и регулярные выражения. Зачастую считывание эквивалентных регулярных выражений из NFA легко: вы переводите циклы в звезды, соединения в качестве альтернатив и так далее. Но что делать в этом случае: [ источник ] Перекрывающиеся...
Симплексный алгоритм жадно идет по углам многогранника, чтобы найти оптимальное решение задачи линейного программирования. В результате, ответ всегда угол многогранника. Методы внутренней точки проходят внутри многогранника. В результате, когда целая плоскость многогранника является оптимальной...
Это предшественник моего другого, более продвинутого вопроса об инспекции стека. Проверка стека - это механизм безопасности, введенный в JVM для работы с кодом, исходящим из местоположений, имеющих разные уровни доверия. Этот вопрос направлен на поиск простого описания его функциональности. Так:...
У меня есть домашнее задание, от которого я некоторое время ломал голову, и я буду благодарен за любые подсказки. Речь идет о выборе известной проблемы, NP-полнота которой доказана, и построении перехода от этой проблемы к следующей проблеме, которую я назову DGD (диагностика направленного графа)....
Fibonnaci кучного поддерживает следующие операции: insert(key, data) : добавляет новый элемент в структуру данных find-min() : возвращает указатель на элемент с минимальным ключом delete-min() : удаляет элемент с минимальным ключом delete(node) : удаляет элемент, на который указывает node...
Это домашнее задание из книги Уди Манбера. Любой намек был бы хорош :) Я должен показать, что: n(log3(n))5=O(n1.2)n(log3(n))5=O(n1.2)n(\log_3(n))^5 = O(n^{1.2}) Я попытался использовать теорему 3.1 книги: c > 0 a > 1f(n)c=O(af(n))f(n)c=O(af(n))f(n)^c = O(a^{f(n)}) (для , )c>0c>0c >...
Основная идея к-ближайших соседей учитывает ближайших точек и определяет классификацию данных большинством голосов. Если это так, то он не должен иметь проблемы в более высоких размерности данных , поскольку такие методы , как н.п. чувствительное хеширование могут эффективно находить ближайшие...
Я работаю над языком выражения, основанным на генеалогии ML, поэтому, естественно, требуется вывод типа> :) Теперь я пытаюсь расширить решение на основе ограничений для определения типов, основанное на простой реализации в EOPL (Фридман и Ванд), но они элегантно обходят алгебраические типы...
Предположим, мне дан конечный набор точек на плоскости, и меня просят нарисовать дважды дифференцируемую кривую через , чтобы ее периметр был как можно меньше. Предполагая, что и , я могу формализовать эту проблему следующим образом: С ( Р ) р я р я = ( х я , у я ) х I < х я +...
Мой вопрос к тем, кто занимается алгоритмикой вычислительной биологии. Этой осенью я собираюсь пройти курс биоинформатики; проблема, однако, в том, что у меня слишком мало знаний в области биологии и химии, чтобы чувствовать себя подготовленным к этому циклу лекций (я был довольно слаб в этих...