Сколько разных max-куч существует для списка из nnn целых чисел? Пример: список [1, 2, 3, 4] Макс-куча может быть 4 3 2 1: 4 / \ 3 2 / 1 или 4 2 3 1: 4 / \ 2 3 / 1
Согласно этой статье в Википедии , неограниченные грамматики эквивалентны машинам Тьюринга. В статье отмечается, что я могу преобразовать любую машину Тьюринга в неограниченную грамматику, но она показывает только, как преобразовать грамматику в машину Тьюринга. Как мне действительно это сделать и...
Во многих реализациях поиска в глубину, который я видел (например: здесь ), код различает серую вершину (обнаружена, но не все ее соседи были посещены) и черную вершину (обнаружена и все ее соседи посещены) , Какова цель этого различия? Кажется, что алгоритм DFS никогда не посещает посещенную...
Меня интересует вопрос об асимптотическом времени выполнения алгоритма Укконена , возможно, самого популярного алгоритма построения суффиксных деревьев за линейное (?) Время. Вот цитата из книги «Алгоритмы на строках, деревьях и последовательностях» Дэна Гасфилда (раздел 6.5.1): »... в...
Иногда легко определить временную сложность алгоритма, если внимательно его изучить. Алгоритмы с двумя вложенными циклами , очевидно, N 2 . Алгоритмы , которые исследуют все возможные комбинации N групп из двух значений, очевидно , 2 N .NNNN2N2N^2NNN2N2N2^N Однако я не знаю, как «определить»...
Построим две функции удовлетворяющие:f,g:R+→R+е,грамм:р+→р+ f,g: R^+ → R^+ f,gе,граммf, g непрерывны; f,gе,граммf, g монотонно возрастают; f≠O(g)е≠О(грамм)f \ne O(g) и .g≠O(f)грамм≠О(е)g \ne O(f)...
Предположим, мы получаем цифры в потоке. После получения каждого числа необходимо вычислить взвешенную сумму последних NNN чисел, где веса всегда одинаковы, но произвольны. Насколько эффективно это можно сделать, если нам разрешено сохранять структуру данных, чтобы помочь с вычислениями? Можем ли...
Как отсортировать список из 5 целых чисел, чтобы в худшем случае потребовалось 7 сравнений? Мне все равно, сколько других операций выполняется. Я не знаю ничего конкретного о целых числах. Я пробовал несколько разных подходов «разделяй и властвуй», которые сводят меня к 8 сравнениям, например,...
В статье Рамирес-Альфонсон « Сложность проблемы Фробениуса» доказана, что задача NP-полна с использованием редукций Тьюринга. Это возможно? Как именно? Я думал, что это было возможно только за полиномиальное время много одного сокращения. Есть ли какие-либо ссылки по этому поводу? Существуют ли два...
Возможно ли для среды выполнения обнаружить бесконечные циклы и впоследствии остановить связанный процесс, или реализация такой логики будет эквивалентна решению проблемы остановки? Для целей этого вопроса я определяю «бесконечный цикл», чтобы обозначить последовательность инструкций и связанных...
Ассемблер конвертирует язык ассемблера в машинный язык. Зачем компилятору конвертировать язык высокого уровня в ассемблер? Разве он не может напрямую преобразовать язык высокого уровня в машинный...
Постоянные структуры данных являются неизменными структурами данных. Операции над ними возвращают новую «копию» структуры данных, но измененную операцией; старая структура данных остается неизменной. Эффективность обычно достигается за счет совместного использования некоторых базовых данных и...
В некоторых (исторических) работах шахматы называют дрозофилой искусственного интеллекта. Хотя я полагаю, что в современных исследованиях простое применение алгоритма поиска в лучшем случае является передовой информатикой , я считаю, что есть еще области, где можно применять (и практиковать)...
Я смотрел лекцию Джима Вейриха « Приключения в функциональном программировании ». В этой лекции он вводит понятие Y-комбинаторов, которое, по существу, находит неподвижную точку для функций более высокого порядка. Один из мотивов, как он упоминает, состоит в том, чтобы иметь возможность выражать...
Я читал о динамическом программировании, когда наткнулся на следующую цитату Алгоритм динамического программирования рассмотрит все возможные пути решения проблемы и выберет лучшее решение. Таким образом, мы можем приблизительно представить динамическое программирование как интеллектуальный метод...
Алгоритм Рамер-Дуглас-Peucker для упрощения линии имеет наихудший среда выполнения. Для правильно распределенных случайных входов ожидаемая сложность времени выполнения . В 2D есть другие алгоритмы со сложностью времени выполнения худшем случае , которые вычисляют точно такой же результат, что и...
В Linux файлы /dev/randomи/dev/urandom файлы являются блокирующими и неблокирующими (соответственно) источниками псевдослучайных байтов. Их можно читать как обычные файлы: $ hexdump /dev/random 0000000 28eb d9e7 44bb 1ac9 d06f b943 f904 8ffa 0000010 5652 1f08 ccb8 9ee2 d85c 7c6b ddb2 bcbe 0000020...
Блокировки, как правило, реализуются с помощью инструкций на уровне проверки и установки и обмена на уровне машины. Есть ли другие реализации, которые не используют их? Кроме того, можем ли мы сказать, что все аппаратные решения критической секции можно разделить на три, а именно: отключение...
Я ищу примеры проблемы, которая имеет нижнюю границу ) для входа x .Ω ( | x |2Ω(|x|2\Omega(|x|^2Иксxx Проблема должна иметь следующие свойства: доказательство времени выполнения для любого алгоритма - первым приоритетом должен быть как можно более простой аргумент нижней границы.Ω (...
С приближением праздничного сезона я решил сделать несколько звезд с корицей . Это было весело (и результат вкусно), но мой внутренний ботаник съежился, когда я положил первый поднос со звездами в коробку, и они не поместились бы в один слой: Почти! Есть ли способ, которым они могли бы...