Учитывая два символа и , давайте определим строку Фибоначчи следующим образом:б кaa\text{a}бb\text{b}Кkk F( к ) = ⎧⎩⎨бaF( k - 1 ) ⋆ F( к - 2 )если к=0если к=1ещеF(k)={bif k=0aif k=1F(k−1)⋆F(k−2)else F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\ \text{a} &\mbox{if } k = 1 \\ F(k-1) \star...
В проблеме остановки нас интересует, существует ли машина Тьюринга которая может определить, останавливается ли данная машина Тьюринга на заданном входе i . Обычно доказательство начинает предполагать, что такой T существует. Затем мы рассмотрим случай , когда мы ограничиваем I к М самим, а затем...
Существует классическая игра-головоломка, очень похожая на кроссворд, за исключением того, что дается список слов, а затем дается квадратная доска составленная из единичных квадратов, с некоторыми квадратами, затемненными как кроссворд , и на некоторых квадратах уже написано письмо. Цель состоит в...
Я работаю с алгоритмом сопоставления с образцом, который генерирует ациклический конечный автомат, который принимает заданную текстовую строку и все ее подстроки. Алгоритм FSA выполняется на символическом представлении музыкального потока (например, данных MIDI). Музыкальный поток был...
Я читал в разных местах, как это , что Hyper-Threading приводит к снижению производительности. Я не могу понять, почему или как гиперпоточность приводит к деградации. Почему это так, что даже когда Hyper-Threading позволяет ОС использовать свободные ресурсы, происходит деградация. Хотя тесты...
Один из способов рассмотрения регулярных выражений - это конструктивное доказательство следующего факта: можно создавать регулярные языки, начиная с небольшого набора языков и комбинируя их с помощью небольшого фиксированного набора свойств замыкания. В частности, если мы начнем с пустого языка,...
У вас есть палочек произвольной длины, не обязательно интегральных.nnn Отрезая несколько палочек (один разрез режет одну палку, но мы можем резать так часто, как мы хотим), вы хотите получить палочек, которые...
Доказано, что проблема определения, является ли вход палиндромом или нет, требует пространства на машине Тьюринга. Однако даже для сохранения входных данных требуется пространство n , не значит ли это, что всем машинам Тьюринга требуется пространство Ω ( n ) ?Ω ( журналн )Ω(журналN)\Omega(\log...
Я учусь в наихудший случае время выполнения сортировки при условии , что она никогда не будет делать очень несбалансированный раздел для различных определений очень . Чтобы сделать это, я задаю себе вопрос, каким будет время выполнения , если быстрая сортировка всегда происходила с разбиением на...
Может кто-то просветить меня, почему парсер рекурсивного спуска с возвратом, который пробует продукцию и (в этом порядке), не распознает язык, образованный грамматикой .S→aSaS→aSaS \rightarrow aSaS→aaS→aaS \rightarrow aaS→aSa | aaS→aSa | aaS \rightarrow aSa\ |\ aa Похоже, он разбирает только слова...
Я пытаюсь понять, как двоичные индексированные деревья (деревья Фенвика) могут быть изменены для обработки как запросов диапазона, так и обновлений диапазона. Я нашел следующие источники: http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/...
Я искал здесь , и я заметил, что лучшее время выполнения для умножения двух битных чисел - это , но я легко могу заметить алгоритм, который работает в .O ( n ⋅ log n ⋅ 2 O ( log ∗ n ) O ( n ⋅ log n )nnnO(n⋅logn⋅2O(log∗n)O(n⋅logn⋅2O(log∗n)O(n\cdot \log n \cdot 2^{O(\log^*...
Мне интересно, существует ли метод автоматического анализа времени выполнения, который работает, по крайней мере, на соответствующем подмножестве алгоритмов (алгоритмы, которые можно анализировать)? Я прогуглил «Автоматический анализ алгоритма», который дал мне это, но это слишком математично. Я...
Используется ли алгоритм Дейкстры в современных системах поиска маршрутов, таких как карты Google или спутниковая навигация в вашем автомобиле? Если нет, то...
Когда я читал статью с описанием различий в ОО и функциональном программировании, я наткнулся на указатели функций. Прошло много времени с тех пор, как я получил степень в области компьютерных наук (2003), и поэтому я искал указатели, чтобы освежить свою память. Указатели - это переменные,...
Я понимаю , что сегментные дерева могут быть использованы , чтобы найти сумму юга массива . И что это может быть сделано за O ( log n ) в соответствии с руководством здесь .AAAO(logn)O(logn)\mathcal{O}(\log n) Однако я не могу доказать, что время запроса действительно равно . Эта ссылка (и многие...
Проблема заключается в следующем: У нас есть двумерный массив / сетка чисел, каждое из которых представляет некоторую «выгоду» или «прибыль». У нас также есть два фиксированных целых числа и h (для «ширины» и «высоты».) И фиксированного целого числа n .wwwhhhnnn Теперь мы хотим наложить...
Пусть - довольно приятная функция (например, непрерывная, дифференцируемая, не слишком много локальных максимумов, может быть вогнутая и т. Д.). Я хочу найти максимумы : значение которое делает максимально большим.f:Rd→Rf:Rd→Rf:\mathbb{R}^d \to \mathbb{R}fffx∈Rdx∈Rdx \in \mathbb{R}^df(x)f(x)f(x)...
Пытаясь улучшить производительность моего класса обнаружения столкновений, я обнаружил, что ~ 80% времени, проведенного в графическом процессоре, тратится на условия if / else, просто пытающиеся определить границы для сегментов, через которые он должен проходить. Точнее: каждый поток получает...
Натуральные числа определяются индуктивно как (используя синтаксис Coq в качестве примера) Inductive nat: Set := | O: nat | S: nat -> nat. Существует ли стандартный способ конструктивного определения целых чисел (и, возможно, других множеств, таких как рациональные и...