Информатика

20
Изменение переменных в рекуррентных отношениях

В настоящее время я изучаю введение в алгоритмы (CLRS) и есть один конкретный метод, который они описывают в книге для решения рекуррентных отношений. Следующий метод может быть проиллюстрирован на этом примере. Предположим, у нас есть рецидив T( n ) = 2 Тл( н--√) + журналNT(n)=2T(n)+log⁡nT(n) =...

20
Проблемы, для которых алгоритмы, основанные на уточнении разделов, работают быстрее, чем за логлиническое время

Уточнение разделов - это техника, в которой вы начинаете с конечного набора объектов и постепенно разбиваете набор. Некоторые проблемы, такие как минимизация DFA, могут быть достаточно эффективно решены с помощью уточнения разделов. Я не знаю никаких других проблем, которые обычно решаются с...

20
Как мне написать доказательство, используя индукцию по длине входной строки?

В моем курсе теории вычислений многие наши проблемы связаны с использованием индукции по длине входной строки для доказательства утверждений о конечных автоматах. Я понимаю математическую индукцию, однако, когда вступают в игру струны, меня сильно сбивают с толку. Я был бы очень признателен, если...

20
Почему представление с плавающей запятой использует знаковый бит вместо дополнения 2 для обозначения отрицательных чисел

Рассмотрим представление с фиксированной точкой, которое можно рассматривать как вырожденный случай с плавающей точкой. Вполне возможно использовать дополнение 2 для отрицательных чисел. Но почему знаковый бит необходим для чисел с плавающей запятой, разве биты мантиссы не должны использовать...

20
Как доказать, что ДФА от НФА могут иметь экспоненциальное число штатов?

Все недетерминированные конечные автоматы можно превратить в эквивалентные детерминированные конечные автоматы. Однако детерминированные конечные автоматы допускают только одну стрелку на символ, указывающую из состояния. Следовательно, его штаты должны входить в состав множества штатов НФА....

20
Как я могу уменьшить сумму подмножества до раздела?

Может быть, это довольно просто, но у меня есть некоторые проблемы, чтобы получить это сокращение. Я хочу уменьшить Subset Sum до Partition, но в настоящее время я не вижу связи! Можно ли уменьшить эту проблему с помощью редукции Левина? Если не понимаешь, пиши для...

20
Как упаковать полигоны внутри другого полигона?

Я заказал несколько кожаных листов, из которых я хотел бы собрать шары для жонглирования, сшивая края вместе. Я использую платоновские тела для формы шаров. Я могу отсканировать кожаные листы и создать многоугольник, который приблизительно соответствует форме кожаного листа (как вы знаете, это кожа...

20
Получение отрицательного цикла с помощью Bellman Ford

Я должен найти отрицательный цикл в ориентированном взвешенном графе. Я знаю, как работает алгоритм Беллмана Форда, и что он говорит мне, существует ли достижимый отрицательный цикл. Но это явно не называет это. Как я могу получить фактический путь цикла?v 1 , v 2 , … v k , v 1v1,v2,…vk,v1v1, v2,...

20
Означает ли

Возможно ли, что и мощность совпадает с мощностью ? Или означает, что и должны иметь разные мощности?P≠NPP≠NP\mathsf{P} \not = \mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}P≠NPP≠NP\mathsf{P} \not =

20
Используются ли когда-либо деревья с вырезанными ссылками на практике, для вычисления максимального потока или других приложений?

Многие алгоритмы максимального потока, которые я обычно вижу реализованными, алгоритм Dinic, push relbel и другие, могут улучшить свои асимптотические временные затраты за счет использования динамических деревьев (также известных как деревья среза ссылок). Push-релабель запускается в или или...

20
Строгое доказательство справедливости предположения при использовании основной теоремы

Основная теорема является прекрасным инструментом для решения определенных видов повторений . Тем не менее, мы часто замазываем неотъемлемую часть при его применении. Например, во время анализа Mergesort мы с радостью T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)\qquad T(n) =...

20
Обоснование пренебрежения постоянными факторами в Big O

Много раз, если сложности имеют константы, такие как 3n, мы пренебрегаем этой константой и говорим O (n), а не O (3n). Я не могу понять, как мы можем пренебречь такими трехкратными изменениями? Некоторые вещи меняются в 3 раза быстрее, чем другие! Почему мы пренебрегаем этим фактом?...

20
Почему плохая рекурсия?

В дизайне компилятора, почему левая рекурсия должна быть исключена в грамматике? Я читаю, что это потому, что это может вызвать бесконечную рекурсию, но разве это не так и для правильной рекурсивной...

20
Решение вопросов «разделяй и властвуй», если коэффициент разделения зависит от

Существует ли общий метод решения повторения формы: T(n)=T(n−nc)+T(nc)+f(n)T(n)=T(n−nc)+T(nc)+f(n)T(n) = T(n-n^c) + T(n^c) + f(n) для или в более общем случаеc<1c<1c < 1 T(n)=T(n−g(n))+T(r(n))+f(n)T(n)=T(n−g(n))+T(r(n))+f(n)T(n) = T(n-g(n)) + T(r(n)) + f(n) где - некоторые сублинейные функции...

20
Трудно ли определить «двойные» арифметические прогрессии 3SUM?

Это вдохновлено вопросом интервью . Нам дан массив целых чисел и мы должны определить, существуют ли различные i < j < k такие, чтоa1, ... ,Na1,…,ana_1, \dots, a_nя < J < Ki<j<ki \lt j \lt k aК- аJ= аJ- аяak−aj=aj−aia_k - a_j = a_j - a_i k - j = j - ik−j=j−ik - j = j - i т.е....

20
Сумма подмножества: уменьшите специальный к общему случаю

Википедия формулирует проблему суммы подмножеств как поиск подмножества данного мультимножества целых чисел, сумма которого равна нулю. Далее говорится, что это эквивалентно нахождению подмножества с суммой sss для любого заданного sss . Поэтому я считаю, что, поскольку они эквивалентны, должно...

20
Являются ли контекстно-свободные языки в

Языки без контекста не закрыты в дополнении, мы это знаем. Насколько я понимаю, контекстно-свободные языки, которые являются подмножеством a*б*a∗b∗a^*b^* для некоторых букв а , бa,ba,b , закрыты в дополнении (!?) Вот мой аргумент. Каждый CF язык LLL имеет полулинейный образ Париха π( L ) = { ( m ,...

20
Практическое применение Radix Sort

Radix sort теоретически очень быстр, когда вы знаете, что ключи находятся в определенном ограниченном диапазоне, скажем, например, значений в диапазоне . Если вы просто конвертируете значения в базу что занимает время , выполните сортировку по основанию и затем преобразуйте обратно в исходную базу...