Я читал об алгоритме типизации Хиндли-Милнере при написании реализации, и видят , что, до тех пор , как каждый переменная связана, вы всегда будете получать либо атомарные тип или типов , где аргументы будут определять окончательный тип, например, t1 -> t1или (t1 -> t2) -> (t1 -> t2)где...
Предположим, у меня есть автономное надводное судно на солнечной энергии где-то во фьордах Норвегии, снабженное довольно недавним набором карт, приемником GPS и никакими средствами для передачи подробных команд от меня. Это судно должно достичь, скажем, острова Хайнань в кратчайшие возможные сроки....
Учитывая алфавит , сколько существует различных регулярных языков, которые могут быть приняты недетерминированным конечным автоматом с n состояниями?Σ={a,b}Σ={a,b}\Sigma = \{ a,b \}nnn В качестве примера рассмотрим . Затем у нас есть 2 18 различных конфигураций перехода и 2 3 различных конфигурации...
Меня интересует связь между вычислительной сложностью и иерархией Хомского в целом. В частности, если я знаю, что какая-то проблема является NP-полной, следует ли из этого, что язык этой проблемы не является контекстно-свободным? Например, проблема клики является NP-полной. Следует ли из этого, что...
Я взял класс алгоритмов на Coursera. Профессор в видео о хеш-таблицах сказал, что Что действительно верно, так это то, что для непатологических данных вы будете получать операции с постоянным временем в правильно реализованной хэш-таблице. Что означает «непатологические данные»? Можете привести...
Я читаю книгу HoTT, и у меня есть (возможно, очень наивный) вопрос о материалах в первой главе. В этой главе вводится тип функции f:A→Bf:A→B f:A\to B а затем обобщается ее зависимость от и это называется типом зависимой функции .BBBx:Ax:Ax:A B:A→U,g:∏x:AB(x)B:A→U,g:∏x:AB(x)B:A\to\mathcal{U},\qquad...
Предположим, нам даны два числа и и мы хотим найти для .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Наивный алгоритм просто проверяет все возможные пары; например, в ruby у нас будет: def max_xor(l, r) max = 0 (l..r).each do |i| (i..r).each do |j| if (i ^ j > max) max...
Один студент недавно попросил меня проверить доказательство твердости NP для них. Они выполнили сокращение в соответствии с: Я уменьшаю эту проблему P′п'P' которая, как известно, является NP-полной, к моей проблеме (с многократным уменьшением многократного числа), поэтому является NP-трудной.PпPPпP...
Предположим, я хочу построить операционную систему на основе очень маленького собственного нижнего ядра, которое действует как интерпретатор / среда выполнения управляемого кода, и большего верхнего ядра, скомпилированного с неродным машинным языком (байт-код Java, CIL и т. Д.). Примерами подобных...
Микроядро реализует все драйверы как программы пользовательского пространства и реализует основные функции, такие как IPC, в самом ядре. Однако монолитное ядро реализует драйверы как часть ядра (например, работает в режиме ядра). Я читал некоторые утверждения, что микроядра работают медленнее,...
Такие языки, как являются сокращением много-один. Нетрудно видеть, что имеет полные проблемы. С. Шмитц [1] рассматривает некоторые классы между и . Они представляют полные проблемы для этих классов при специально созданных...
например, ?xy+x+y=x+y(x+1)xy+x+y=x+y(x+1)xy+x+y=x+y(x+1) Выражения взяты из обычной школьной алгебры, но ограничены арифметическим сложением и умножением (например, ), без инверсий, вычитания или деления. Буквы являются переменными.2+2=4;2.3=62+2=4;2.3=62+2=4; 2.3=6 Если это поможет, мы можем...
Я интересно, что это лучший известный алгоритм, в терминах big- нотации, для решения целочисленных линейного программирования?OOO Я знаю, что проблема в полном, поэтому я не ожидаю ничего полиномиального. И я знаю, что есть много эвристик и тому подобного, которые используются в практических...
Я пытаюсь понять доказательство теоремы Карпа-Липтона, изложенное в книге «Вычислительная сложность: современный подход» (2009). В частности, в этой книге говорится следующее: Теорема Карпа-Липтона Если NP P ∖ p o l y , то PH = Σ p 2 .⊆⊆\subseteq P∖polyP∖polyP_{\backslash poly} =Σp2=Σ2p= \Sigma^p_2...
Для измерения сложности алгоритма это сложность времени или вычислительная сложность? В чем разница между ними? Я использовал для расчета максимального (наихудшего) количества основных (наиболее затратных) операций в...
Я уверен, что кто-то думал об этом раньше или сразу же отклонил это, но почему теория дихотомии Шефера наряду с теоремой Махани о разреженных множествах не подразумевает P = NP? Вот мои рассуждения: создайте язык который равен SAT, пересекаемому бесконечным разрешимым разреженным множеством. Тогда...
Здесь я прочитал это: У Haskell определенно нет самой продвинутой системы типов (даже близко, если считать языки исследований), но из всех языков, которые фактически используются в производстве, Haskell, вероятно, находится на вершине. Поэтому я прошу две вещи: какие языки исследований имеют более...
Поэтому обычно судоку составляет , но этот вопрос распространяется и на головоломок с . Существует много правил вычета полиномиального времени, которые могут помочь в поиске решения головоломки Судоку. Но тогда иногда требуется угадывание значений и последующие цепочки выводов, чтобы исключить...
Я знаю, что это очень распространенный вопрос. Но у меня в голове другой взгляд. Я просто попытаюсь сформулировать это здесь. Из того, что я знаю, каждая инструкция, которую выполняет ЦП, написана на машинном языке, и все, что ЦП может сделать, это выполнить некоторые арифметические операции...
Я знаю, что шлюзы NAND можно использовать для создания схем, реализующих каждую таблицу истинности, а современные компьютеры состоят из вентилей NAND. Какова теоретическая связь между воротами NAND и полнотой Тьюринга? Мне кажется, что схемы затворов NAND ближе к конечным автоматам, чем машины...