Я хочу знать, насколько полезна система типов в языке программирования. Например, я знаю, что на языке программирования с зависимой типизацией мы можем создать Vectorкласс, включающий размер вектора в сигнатуру типа. Это как фактический пример. Мы также можем написать функцию, appendиспользуя эти...
Я изучаю деревья точек обзора, и я познакомился с этим, читая статью Структуры данных и алгоритмы поиска ближайших соседей в общих метрических пространствах Питера Йанилоса ( Материалы SODA 1993 , SIAM, стр. 311–321; PDF ). Следующий псевдокод появляется в алгоритме 1. функция Make_vp_tree...
Чтобы доказать, что 3-раскраска разрешима, достаточно сказать: Каждый узел на графике имеет 3 возможных цвета Поэтому мы можем перечислить все возможностей и затем проверить, что никакие два ребра не соединяют узлы одного цвета3N3N3^n Означает ли это, что 3-раскраска разрешима? Или мне нужно...
Мы можем сформировать DFA, принимающий двоичные числа, делимые на nnn . Например, DFA, принимающий двоичные числа, делимые на 2, может быть сформирован следующим образом: Аналогично, DFA, принимающий двоичные числа, делимые на 3, может быть сформирован следующим образом: Мы можем следовать четко...
DFA, NFA и epsilon NFA - все три позволяют нам представлять определенный регулярный язык. С любым из этих представлений мы можем прийти к одному и тому же регулярному выражению, тогда зачем нам нужно изучать все три формы представления конечных автоматов? Может быть какое-то объяснение того, что...
Рандомизированные связываемые кучи имеют операцию «соединение», которую мы затем используем для определения всех других операций, включая вставку. Вопрос в том, какова ожидаемая высота этого дерева с узлами?nnn Теорема 1 Гамбина и Малинковского « Рандомизированные смешиваемые приоритетные очереди»...
Сегодня за ланчем я поднял эту проблему со своими коллегами, и, к моему удивлению, аргумент Джеффа Э., что проблема разрешима, не убедил их ( вот тесно связанный пост о mathoverflow). Постановка проблемы, которую легче объяснить («это P = NP?»), Также разрешима: да или нет, и поэтому один из двух...
Мне пришло в голову этот вопрос о проблеме остановки, и я не смог найти хорошего ответа в Интернете, задаваясь вопросом, может ли кто-нибудь помочь. Возможно ли, что проблема остановки разрешима для любого ТМ на любом входе, если он не сам ТМ? В принципе: Halts(TM, I) IF TM == I: Undecidable,...
Я изучаю методы реализации языков программирования и недавно натолкнулся на стеки спагетти, которые предположительно хорошо подходят для модели стиля передачи продолжения (учитывая их использование, например, в Scheme и SML / NJ ). Для упрощения, давайте рассмотрим только однопоточные процессы для...
На этом сайте есть много вариантов вопроса о том, могут ли ТМ решить проблему остановки, будь то для всех других ТМ или определенных подмножеств. Этот вопрос несколько другой. Он спрашивает, может ли тот факт, что проблема остановки относится ко всем ТМ, может быть решен ТМ. Я верю, что ответ...
Я хочу создать кратчайшего пути ( k будет меньше 10) между всеми парами в графе. График (на самом деле карта метро):kkkkkk положительно взвешенный ненаправленный редкий около 100 узлов Мой текущий план - применить kkk каждой паре маршрутизацию по кратчайшему пути ; Сейчас я ищу более эффективную...
Учитывая триангуляцию (без точек Штейнера) простого многоугольника , можно рассмотреть дуал этой триангуляции, который определяется следующим образом. Мы создаем вершину для каждого треугольника в нашей триангуляции и соединяем две вершины, если соответствующие треугольники имеют общее ребро....
Существует известное и элегантное сокращение от проблемы максимального согласования по двум частям до проблемы максимального потока: мы создаем сеть с исходным узлом , терминальным узлом и одним узлом для каждого сопоставляемого элемента, затем добавляем соответствующие ребра.sssttt Конечно, есть...
Обычно я вижу, что в представлении структурной операционной семантики для цикла while состояние программы не изменяется: (whileBdoS,σ)→(ifBthenS;(whileBdoS)elseSKIP,σ)(whileBdoS,σ)→(ifBthenS;(whileBdoS)elseSKIP,σ)(while \> B \> do \>S, \sigma) \rightarrow (if \>B \> then \>S; (while \> B \> do \>S)...
Ответы на этот вопрос о Crypto Stack Exchange в основном говорят о том, что для измерения сложности проблемы логарифма мы должны принять во внимание длину числа, представляющего размер группы. Это кажется произвольным, почему мы не выбрали размер группы в качестве аргумента? Есть ли критерий, чтобы...
Двудольный граф плоский, если в нем нет или миноров. К 5K3,3K3,3K_{3, 3}K5K5K_5 Я ищу необходимые или / и достаточные условия, чтобы плоские чертежи без ребер "обходили" наборы вершин. Это рисунки, удовлетворяющие: Все вершины одной части нарисованы на одной вертикальной линии. Вершины другой части...
Я разместил это на MathUnderflow, но не получил ответов, поэтому решил попробовать здесь, Я читаю старую статью Рабина и Фишера [опубликует ссылку, когда это возможно], где, помимо прочего, доказана двоякая экспоненциальная сложность арифметики Пресбургера. Доказательство основывается на...
Недавно я задавался вопросом, что произойдет, если мы позволим грамматикам без контекста иметь бесконечное количество правил. Ясно, что если бы мы допустили произвольные такие бесконечные наборы правил, каждый язык над некоторым алфавитом мог бы быть описан с помощью CFG с . Но что, если мы...
В работе Криса Окасаки « Сглаживание комбинаторов: выживание без скобок » он показывает, что двух комбинаторов достаточно и необходимо в качестве основы для кодирования выражений по Тьюрингу без необходимости использования оператора приложения или скобок. По сравнению с кодировками комбинаторной...
Я пытаюсь придумать доказательство для следующего: Для любого языка AAA , существует язык BBB такие , что A≤TBA≤TBA \le_{\mathrm{T}} B , но B ≰TA≰TA\nleq_{\mathrm{T}} A . Я думал о том, чтобы позволить BBB быть ATMATMA_{\mathrm{TM}} , но я понимаю, что не все языки Тьюринга сводимы к...