Пол десятилетия назад я сидел в классе структур данных, где профессор предлагал дополнительные кредиты, если кто-то мог пройти по дереву без использования рекурсии, стека, очереди и т. Д. (Или любых других подобных структур данных) и всего лишь нескольких указателей. Я придумал, как мне казалось,...
Я пытаюсь подготовиться к экзамену и понял, что запутался в том, как работают TLB и кеш данных. Я понимаю, что TLB - это, по сути, кеш самых последних использованных физических адресов. Однако я смотрел на диаграмму в своем учебнике (показанную ниже), и я не понимаю, что в ней происходит. Я думаю,...
Проблема клики - это хорошо известная неполная задача где размер требуемой клики является частью входных данных. Однако задача k-клики имеет тривиальный алгоритм полиномиального времени ( O ( n k ), когда k является постоянным). Меня интересуют самые известные верхние границы, когда k является...
Из того, что я узнал, асимптотически тесная связь означает, что она связана сверху и снизу, как в тета-записи. Но что означает асимптотически узкая верхняя граница для обозначения...
Я пытаюсь построить все неэквивалентные матрицы (или если хотите) с элементами 0 или 1. Операция, которая дает эквивалентные матрицы, - это одновременный обмен строк i и j И столбцов i и j , например. для8×88×88\times 8n×nn×nn\times n1↔21↔21\leftrightarrow2...
Я знаю, что можно доказать, что PROLOG является полным по Тьюрингу, создав программу, которая имитирует машину Тьюринга, например: turing(Tape0, Tape) :- perform(q0, [], Ls, Tape0, Rs), reverse(Ls, Ls1), append(Ls1, Rs, Tape). perform(qf, Ls, Ls, Rs, Rs) :- !. perform(Q0, Ls0, Ls, Rs0, Rs) :-...
Я пытаюсь обернуть голову вокруг доказательства полноты NP, которое, кажется, вращается вокруг SAT / 3CNF-SAT. Возможно, это поздний час, но я боюсь, что не могу придумать формулу 3CNF, которая не может быть удовлетворена (возможно, я упускаю что-то очевидное). Можете ли вы привести пример такой...
У меня есть тетраэдр и многогранник . ограничен так, что он всегда разделяет все свои вершины с . Я хочу определить, находится ли внутри .п т п т пttt ppptttpppttt ppp Я хотел бы добавить одну деталь к проблеме в случае, если она может внести вклад в решение: - тетраэдр Делоне, а грани p...
Меня смущает, почему разработчики MIPS включают 5 бит, предназначенных для сдвига, и имеют отдельные биты кода операции и функции. Поскольку MIPS является настолько RISC, я предполагаю, что в нескольких инструкциях будет выполнено только смещение, поэтому эти 5 бит кажутся бесполезными, когда их...
Некоторые процессоры имеют регистр флагов (ARM, x86, ...), другие нет (MIPS, ...). В чем преимущество наличия инструкции CMP для обновления регистра флагов, сопровождаемой инструкцией ветвления, вместо использования нулевого регистра и условных ветвей для проверки знака, переполнения и т....
Головоломка «Поток свободен» состоит из натурального числа и набора (неупорядоченных) пар различных вершин в графе сетки , так что каждая вершина находится не более чем в одной паре. Решением такой головоломки является набор неориентированных путей в графе, так что каждая вершина находится на одном...
Можно проанализировать документ, используя один проход из конечного автомата. Какая польза от двух проходов, т.е. иметь лексер для преобразования текста в токены и иметь анализатор для проверки правил производства на этих токенах? Почему бы не иметь один проход, который применяет правила...
Я читал Линейную Алгебру и ее Приложения, чтобы помочь понять материал информатики (главным образом машинное обучение), но я обеспокоен тем, что большая часть информации не полезна для CS. Например, знание того, как эффективно решать системы линейных уравнений, не кажется очень полезным, если вы не...
Прошлой осенью я отправился в тур по суперкомпьютеру Blue Waters в университете штата Иллинойс. Я спросил, использовал ли кто-нибудь весь компьютер. Мне сказали, что он всегда работал над несколькими проектами. Это заставило меня задуматься о полезности суперкомпьютеров. Возможно, «Голубые воды»...
В моем учебнике упоминается, что: где - пустой язык.∅*= { ϵ }∅*знак равно{ε}\emptyset^*=\{\epsilon\}∅∅\emptyset Однако мы знаем, что , где - любой язык.L ⋅ ∅ = ∅L⋅∅знак равно∅L \cdot \emptyset = \emptysetLLL Я не могу интуитивно понять эту концепцию, потому что операция звезды Клини указывает на...
Что означает ?журналO ( 1 )NlogO(1)n\log^{O(1)}n Я знаю нотацию big-O, но эта нотация для меня не имеет смысла. Я тоже ничего не могу найти по этому поводу, потому что поисковая система не может правильно это интерпретировать. Для некоторого контекста предложение, в котором я нашел это, гласит:...
Алгоритм псевдополиномиального времени - это алгоритм, который имеет полиномиальное время работы на входном значении (величина), но экспоненциальное время работы на входном размере (количество бит). Например, для проверки, является ли число простым или нет, требуется выполнить цикл по числам от 2...
В статье Филиппа Уодлера о теоремах для свободного он утверждает в разделе 2 о параметричности, что нет наивных теоретико-множественных моделей полиморфного лямбда-исчисления В наивной теоретико-множественной модели типы - это множества, а функции - теоретико-множественные функции, что...
Пусть . Язык Говорят , обладает свойством «анти-палиндром» , если для каждой строки , что является палиндром, . Кроме того, для каждой строки которая не является палиндромом, либо либо , но не оба (!) (Исключая или).L ⊆ Σ ∗ w w ∉ L u u ∈ L R e v e r s e ( u ) ∈ LΣ={0,1}Σ={0,1}\Sigma = \{ 0, 1...
Я очень знаком с Dijkstra, и у меня есть конкретный вопрос об алгоритме. Если у меня есть огромный граф, например, 3,5 миллиарда узлов (все данные OpenStreetMap), то я явно не смог бы иметь граф в памяти, поэтому граф хранится на диске в базе данных. Есть библиотеки, доступные для вычисления...