У меня проблема: Покажите, что существует действительное число, для которого не существует ни одной программы, которая работает бесконечно долго и записывает десятичные цифры этого числа. Я полагаю, что это можно решить, сведя его к проблеме остановки, но я понятия не имею, как это сделать. Буду...
В Частичном тесте для подготовки к GATE возник вопрос: f(n): if n is even: f(n) = n/2 else f(n) = f(f(n-1)) Я ответил: «Это прекратится для всех целых чисел», потому что даже для некоторых отрицательных целых чисел это прекратится как ошибка переполнения стека . Но мой друг не согласился, сказав,...
Вот контекст ( Структура и интерпретация компьютерных программ , раздел 1.1.8, под заголовком «Локальные имена»): Формальный параметр процедуры играет особую роль в определении процедуры, поскольку не имеет значения, какое имя имеет формальный параметр. Такое имя называется связанной переменной , и...
Учитывая строку значений энтропии Шеннона в логарифм приходит к 0,922 . Из того, что я понимаю, в базе 2 энтропия Шеннона, округленная в большую сторону, является минимальным числом битов в двоичном коде, чтобы представить одно из значений.AAAAAAAABCAAAAAAAABCAAAAAAAABC2220.9220.9220.922222 Взято...
Процессоры в некоторой степени разработаны с учетом программного обеспечения, которое люди будут писать для него, неявно или явно. Мне кажется, что если вы посмотрите на архитектуру набора команд, они очень «императивны» в том смысле, что каждая команда кодирует команду императивного стиля. Мне...
Имеется двухмерный лабиринт, где вы можете дать 4 команды «двигаться вверх / вниз / вправо / влево». Зная лабиринт, а не где находится человек, как найти минимальную последовательность команд, которая гарантирует выход из лабиринта? Я ищу единственную последовательность команд, которая будет...
Я немного запутался в том, что именно означает «ключ» в компьютерной науке. Я понимаю пары ключ-значение, первичные ключи и т. Д. Но я не могу найти определение того, что сам по себе термин «ключ» означает. Насколько я могу судить, это просто часть данных. В CLRS данные, связанные с узлами дерева,...
Список nnn элементов может быть проверен как отсортированный путем сравнения каждого элемента с его соседом. В моем приложении я не смогу сравнивать каждый элемент с его соседом: вместо этого сравнения иногда будут между удаленными элементами. Учитывая, что список содержит более трех элементов, а...
Я хочу создать совершенно случайную судоку . Определите сетку Судоку как сетку целых чисел от 1 до 9, где некоторые элементы могут быть опущены. Сетка - это правильная головоломка, если есть уникальный способ ее завершения, чтобы соответствовать ограничениям Судоку (каждая строка, столбец и...
Существует ли алгоритмический подход для определения того, что даты, указанные в абзаце, соотносятся с конкретными событиями (фразами) в абзаце? Пример, рассмотрим следующий абзац: В июне 1970 года великий лидер принес присягу. Но только после мая 1972 года, после смерти государственного министра,...
Простая игра, в которую обычно играют дети, в игру «Война» играют два человека, используя стандартную колоду из 52 игральных карт. Сначала колода перемешивается, и все карты раздаются двум игрокам, так что у каждой по 26 случайных карт в случайном порядке. Предположим, что игрокам разрешено...
При сообщении алгоритмической сложности алгоритма предполагается, что базовые вычисления выполняются на некоторой абстрактной машине (например, ОЗУ), которая приближается к современному ЦП. Такие модели позволяют нам сообщать о временной и пространственной сложности алгоритмов. Теперь, с...
Пусть S={Si}1≤i≤nS={Si}1≤i≤n\cal{S}=\{S_i\}_{1\leq i\leq n} - частичный (m,k)(m,k)(m,k) -дизайн, а f:{0,1}m→{0,1}f:{0,1}m→{0,1}f: \{0,1\}^m \to \{0,1\} - булева функция. Генератор Нисана-Вигдерсона Gf:{0,1}l→{0,1}nGf:{0,1}l→{0,1}nG_f: \{0,1\}^l \to \{0,1\}^n определяется следующим образом:...
Я читал статью, которая описывает переключение между пользовательским пространством и пространством ядра, которое происходит при системном вызове. В статье говорится Приложение ожидает завершения системного вызова, прежде чем возобновить выполнение в пользовательском режиме. Теперь до сих пор я...
Рассмотрим следующий протокол, предназначенный для аутентификации (Алиса) в B (Боб) и наоборот.AAABBB A→B:B→A:A→B:“I'm Alice”,RAE(RA,K)E(⟨RA+1,PA⟩,K)A→B:“I'm Alice”,RAB→A:E(RA,K)A→B:E(⟨RA+1,PA⟩,K) \begin{align*} A \to B: &\quad \text{“I'm Alice”}, R_A \\ B \to A: &\quad E(R_A, K) \\ A \to B: &\quad...
Проблема почтовой корреспонденции (PCP) неразрешима. Ограниченная версия PCP является -полной и отмеченная версией PCP (слова одного из двух списков, должны отличаться по первой букве) в P S P A C E [1].Н ПNп\mathrm{NP}P S P A C EпSпAСЕ\mathrm{PSPACE} Используются ли эти ограниченные версии, чтобы...
Проблема 3-Перегородка спрашивает , может ли набор из целых чисел может быть разделена на п наборов из трех чисел таким образом, что каждый набор сумм до некоторого заданного целого числа B . Задача сбалансированного разбиения спрашивает, можно ли разбить 2 n целых чисел на два одинаковых набора...
Я часто работаю с лексером / парсерами , в отличие от комбинатора парсеров, и вижу людей, которые никогда не посещали уроки по синтаксическому анализу, спрашивают о парсинге двоичных данных. Обычно данные не только двоичные, но и контекстно-зависимые. Это в основном приводит к тому, что токен...
Меня смущает, как выбираются метчики для регистров сдвига с линейной обратной связью. У меня есть диаграмма, которая показывает LFSR с полиномом связи . Пять ступеней обозначены: и а ответвления выходят из и .C(X)=X5+X2+1C(X)=X5+X2+1C(X) = X^5 + X^2 + 1R4,R3,R2,R1R4,R3,R2,R1R4, R3, R2,...
LLL - обычный язык над алфавитом . Левый фактор относительно - это язык Σ={a,b}Σ={a,b}\Sigma = \{a,b\}LLLw∈Σ∗w∈Σ∗w \in \Sigma^*w−1L:={v∣wv∈L}w−1L:={v∣wv∈L}w^{-1} L := \{v \mid wv \in L\} Как я могу доказать, что...