Я ищу формальное определение файла, который включает не только хранилище, но и абстракции, такие как procfs или / dev / null (или любой файл на основе предохранителей), которые не относятся к хранилищу. До сих пор я знаю, что все файлы являются абстракциями, которые можно определить могут иметь...
Чтобы решить эту проблему, я сначала заметил, что ϕ(pe11 pe22⋯ pekk)=(e1+1)(e2+1)⋯(ek+1)ϕ(p1e1 p2e2⋯ pkek)=(e1+1)(e2+1)⋯(ek+1)\phi(p_1^{e_1} \space p_2^{e_2} \cdots \space p_k^{e_k}) = (e_1 + 1)(e_2 + 1)\cdots(e_k +1) Где ϕ(m)ϕ(m)\phi(m) - число (не обязательно простых) делителей числа mmm . Если...
Я читаю эту известную статью о вселенных в теории типов . Сначала я ожидал чего-то подобного Setωв Агде, но оказалось, что это даже что-то более общее. Кажется, это обобщает построение вселенной от простого индуктивно-рекурсивного типа до связующего (аналогично и ). Главный вопрос, который я хочу...
Существует теорема, которая гласит: Дан конечный автомат, имеющий nnn указывает, существует ли строка www длина которого удовлетворяет n≤|w|≤2n−1n≤|w|≤2n−1n \leq |w| \leq 2n-1 тогда язык, принятый автоматом, бесконечен. Я понимаю ограничение |w|≥n|w|≥n|w| \geq n, но я не понимаю, почему ограничение...
Следующая контекстно-свободная грамматика представляет неоднозначность типа «висящее другое» (представьте, что обозначает, а обозначает, а обозначает какой-то другой вид инструкции или блока): Например, может быть проанализирован как или как (это самое простое / самое короткое неоднозначное слово...
В Шпаннера, TrueTime и ПСП теорема , Эрик Брюэр пишет: Одна из тонких особенностей Spanner заключается в том, что он получает сериализуемость от блокировок, но он получает внешнюю согласованность (аналогично линеаризуемости ) от TrueTime [ выделение добавлено ]. Что такое определение внешней...
Учитывая это: Язык с очень выразительными системами типов (например, Idris ) также может иметь механизмы выхода, такие как интерфейсы сторонних функций / unsafePerformIO. Существуют помощники по проверке, которые можно использовать для доказательства некоторых свойств программы, написанной на...
В « Доказательствах и типах» Жирара мы можем прочитать: С алгоритмической точки зрения, секвенциальное исчисление не имеет изоморфизма Карри-Ховарда из-за множества способов написания одного и того же доказательства. Это мешает нам использовать его в качестве типизированного исчисления, хотя мы...
Учитывая булеву матрицу X , пусть 0 записей представляют море, а 1 запись представляет землю. Определите остров как вертикально или горизонтально (но не по диагонали) смежные 1 записи.н × мN×мn \times mИксИкс\mathrm X000111111 Первоначальный вопрос заключался в подсчете количества островков в...
Многие классы сложности имеют «полные» проблемы. Существуют ли полные задачи для класса сложности задач, которые можно решить за времени?O(1)O(1)O(1) Сложность состоит в том, что этот класс зависит от модели вычислений; проблема может быть решена за раз в одной разумной модели вычислений, но не в...
Одно из утверждений о теореме Райса приведено на странице 35 «Вычислительная сложность: современный подход» (Арора-Барак): Частичная функция от до - это функция, которая не обязательно определяется на всех ее входах. Мы говорим, что TM вычисляет частичную функцию если для каждого для которого...
Я работаю над проблемой, связанной с латинскими квадратами, и я хочу метод, который сводится к решению проблемы: Входные данные : конечный простой граф G. Выходные данные : YESесли G имеет нетривиальный автоморфизм, в NOпротивном случае. Следовательно ... Вопрос : существует ли эффективный алгоритм...
Я вижу много алгоритмических проблем, которые всегда сводятся к чему-то длинному: У вас есть целочисленный массив , вам нужно найти такое, что максимизирует за времени.h[1..n]≥0h[1..n]≥0h[1..n]\geq 0i,ji,ji,j(h[j]−h[i])(j−i)(h[j]−h[i])(j−i)(h[j]-h[i])(j-i)O(n)O(n)O(n) Очевидно, что временное...
Задача состоит в том, чтобы доказать или опровергнуть существование , st, ; ; d (c_i, c_j) \ geq2,1 \ leq i <j \ leq32 . ( d обозначает расстояние Хэмминга)ССC|с | = 6 , ∀ c ∈ C|с|знак равно6,∀с∈С|c| = 6,\forall c\in C| С|= 32|С|знак равно32|C| = 32d( ся, сJ) ≥ 2 , 1 ≤ i < j ≤...
Я столкнулся с этой проблемой и изо всех сил пытаюсь найти способ приблизиться к ней. Любые мысли будут с благодарностью! Предположим, нам дана матрица { - 1 , 0 , 1 }н × к {−1,0,1}n × k\{-1, 0, 1\}^{n\ \times\ k} , например, ⎡⎣⎢⎢⎢⎢⎢⎢1- 10- 11001- 101010000010- 11- 11-...
Есть несколько примечаний, таких как или и так далее. Мне было интересно, есть ли варианты таких в реальности, как или , или они математически неверны.OOOO(n)O(n)O(n)O(n2)O(n2)O(n^2)O(2n2)O(2n2)O(2n^2)O(logn2)O(logn2)O(\log n^2) Или было бы правильно сказать, что можно улучшить до ? Я не могу и не...
Я работаю через Sipser Book (2-е издание) и наткнулся на этот пример, который я не понимаю. В книге говорится, что этот NFA принимает пустую строку εε\epsilon . Может ли кто-нибудь объяснить мне, почему это так? Насколько я понимаю, εε\epsilon перейдет к Q3Q3q_3 который не является состоянием...
Часто утверждается (например, в Википедии ), что время выполнения поиска в ширину (BFS) на графе G=(V,E)G=(V,E)G=(V,E) равно O(|V|+|E|)O(|V|+|E|)O(|V|+|E|) . Тем не менее, любой связный граф имеет |V|≤|E|+1|V|≤|E|+1|V|\leq |E|+1 , и даже в несвязном графе, BFS никогда не будет смотреть на вершинах...
Coq включает в себя выражения let на своем основном языке. Мы можем переводить выражения let в приложения, подобные этому: let x : t = v in b ~> (\(x:t). b) v я понимаю, что это не всегда работает, потому что значение vне будет доступно при проверке типов b. Однако это можно легко исправить с...