Я использую вариант 5-перекрестного медианного фильтра для данных изображения в небольшой встроенной системе, т.е. x x x x x Алгоритм действительно прост: прочитайте 5 целочисленных значений без знака, получите самые высокие 2, сделайте некоторые вычисления и запишите результат целого числа без...
Это продолжение другого вопроса здесь , и я надеюсь, что он не слишком философский. Как отметил Рафаэль в комментарии к моему предыдущему вопросу, на самом деле я не получил определения «вычислимый», но согласно некоторым прочитанным мною работам определение также не совсем понятно, когда речь идет...
В настоящее время я читаю некоторые статьи о комковании цепей Маркова и не вижу разницы между цепью Маркова и простым ориентированным взвешенным графом. Например, в статье « Оптимальное сосредоточение в пространстве состояний в цепях Маркова» они дают следующее определение CTMC (непрерывной цепи...
Рассмотрим следующую проблему. Дано: Полный граф с действительными неотрицательными весами по ребрам. Задача: Найти планарный подграф максимального веса. («Максимум» среди всех возможных плоских подграфов.) Примечание: подграф максимального веса будет триангуляцией; если полный граф находится на...
Кажется, я вспоминаю из студенческого класса, что для машины Тьюринга с конечной лентой всегда будут существовать соответствующие конечные автоматы, но я не смог найти это подтверждение где-либо в Интернете. Это на самом деле так, или я неправильно...
Насколько мне известно, не существует алгоритма наихудшего случая, который решает следующую проблему:O ( n )O(n)O(n) Для заданной последовательности длины состоящей из конечных целых чисел, найдите перестановку, где каждый элемент меньше или равен своему преемнику.Nnn Но есть ли доказательство...
Я слышал несколько возможных объяснений, поэтому я хотел бы получить надежную ссылку. Обновление 05.19: Меня интересует этот вопрос, потому что один из моих студентов написал в своей диссертации, что название происходит от объяснения ниже (1). До сих пор я думал / слышал, что это происходит из...
Я думаю об унарных языках LkLkL_k , где LkLkL_k - множество всех слов, длина которых равна сумме kkk квадратов. Формально: Легко показать, что L 1 = { a n 2 ∣ n ∈ N 0 } не является регулярным (например, с леммой Пампинга). Кроме того, мы знаем, что каждое натуральное число является суммой четырех...
На странице википедии здесь довольно хорошо описан алгоритм CDCL (и, похоже, фотографии были взяты из слайдов, созданных Шарадом Маликом в Принстоне). Тем не менее, при описании того, как откатить все, что он говорит, это «до соответствующей точки». MiniSAT также использует вариант алгоритма CDCL,...
Таким образом, существует алгоритм преобразования терминов лямбда-исчисления в комбинаторную логику с использованием комбинаторов SK. Это производит вещи, которые взрываются в размере. Я хотел бы знать больше об этом взрыве в размере. Однако я не могу придумать лучшего алгоритма. Я слышал, что...
У меня есть набор из точек, которые определены в метрическом пространстве - так что я могу измерить «расстояние» между точками, но больше ничего. Я хочу найти самую центральную точку в этом наборе, которую я определяю как точку с минимальной суммой расстояний до всех остальных точек. Метрические...
Существует ли характеристика графов, множество ребер которых разлагается в несвязное объединение совершенных совпадений? Одним из тривиальных классов таких графов являются регулярные -двойственные графы. Их набор ребер разложится на непересекающихся идеальных совпадений. ( н , н ) дddd( н , н...
В алгоритме Уэлча-Берлекампа для декодирования кодов Рида-Соломона каждому дается список точек представляющих сообщение с ошибками на в неизвестных местах (и задается алгоритму). Выходными данными является полином, проходящий через все заданные точки, кроме тех, в которых произошли...
Я пытаюсь измерить много не избыточной (фактической) информации, содержащейся в моем файле. Некоторые называют это количеством энтропии. Конечно, существует стандарт p (x) log {p (x)}, но я думаю, что Шеннон рассматривал его только с точки зрения передачи по каналу. Следовательно, формула требует...
Пусть входная строка будет задана как . Затем, если NFA в настоящее время находится в состоянии (и прочитал входной алфавит ), то перед чтением следующего входного символа NFA разделяется на два NFA, один из которых находится в состоянии а другой - в , если происходит переход тип . Если существует...
Добрый вечер! На самом деле я прохожу стажировку в Национальном архиве Франции и столкнулся с ситуацией, которую хотел решить, используя графики ... I. Пыльная ситуация Мы хотим оптимизировать расположение книг моей библиотеки в соответствии с их высотой, чтобы минимизировать стоимость их архива....
Предположим, у меня есть две функции FFF и GGG и я заинтересован в определении F(x)=∫G(x)dx.F(x)=∫G(x)dx.F(x) = \int G(x)dx. Предположим, что мои функции состоят из элементарных функций (полиномов, экспонент, логарифмов и тригонометрических функций), но не, скажем, из ряда Тейлора. Эта проблема...
Отказ от ответственности: я биолог, извините за (возможно) основной вопрос, сформулированный в таких грубых выражениях. Я не уверен, стоит ли мне задавать этот вопрос здесь или на DS / SC, но CS - самый большой из трех, так что здесь. (После того, как я написал, мне пришло в голову, что...
Мы иногда слышим: «Swift не выполняет классическую (отслеживание) GC, он использует ARC». Но я не уверен, что в семантике Swift есть что-то, что требует подсчета ссылок. Кажется, что можно использовать собственный компилятор Swift и среду выполнения, чтобы использовать трассировку GC. Так что же...
Учитывая строку , я хотел бы найти самую длинную повторяющуюся (по крайней мере дважды) подпоследовательность. То есть я хотел бы найти строку которая является подпоследовательностью (не обязательно должна быть смежной) такой что . То есть - это строка, половинки которой появляются дважды подряд....