Закрыто . Этот вопрос основан на мнении . В настоящее время он не принимает ответы. Хотите улучшить этот вопрос? Обновите вопрос, чтобы ответить на него фактами и цитатами, отредактировав этот пост . Закрыто 4 года назад . Я увлекаюсь математической элегантностью и строгостью, и сейчас ищу такую...
Мой вопрос к тем, кто занимается алгоритмикой вычислительной биологии. Этой осенью я собираюсь пройти курс биоинформатики; проблема, однако, в том, что у меня слишком мало знаний в области биологии и химии, чтобы чувствовать себя подготовленным к этому циклу лекций (я был довольно слаб в этих...
Есть ли способ вычислить размер максимального соответствия в невзвешенном двудольном графе более эффективно (например, быстрее), чем вычисление максимального соответствия? Это длинный путь, но часто это интересная проблема, чтобы избежать одноразовых вычислений, подобных этим. мотивация Проблема ,...
Для массива натуральных чисел ≤ k , где k - константа, я хочу ответить на O ( 1 ) запросов вида: «сколько раз m появляется в массиве между индексами i и j "?a1,…,ana1,…,ana_1,\ldots,a_n≤k≤k\leq kkkkO(1)O(1)O(1)mmmiiijjj Массив должен быть предварительно обработан за линейное время. В частности, я...
Нам дан генератор случайных чисел, RandNum50который генерирует случайное целое число равномерно в диапазоне 1–50. Мы можем использовать только этот генератор случайных чисел для генерации и печати всех целых чисел от 1 до 100 в случайном порядке. Каждое число должно приходить ровно один раз, и...
Я хотел бы кое-что узнать об этой задаче оптимизации: для заданных неотрицательных целых чисел aя , J , Kai,j,ka_{i,j,k} найдите функцию еff минимизирующую выражение МаксимумКΣяaя , ж( я ) , кmaxk∑iai,f(i),k\max_k \sum_i a_{i,f(i),k} Пример, использующий другую формулировку, может прояснить...
Существует хорошо известный в худшем случае алгоритм выбора , чтобы найти K «й наибольший элемент в массиве целых чисел. Он использует медиану из-медианы подойти , чтобы найти достаточно хороший стержень, разбивает входной массив на месте , а затем рекурсивно продолжается в его поисках к «го по...
На работе мне было поручено вывести некоторую информацию о типах динамического языка. Я переписываю последовательности операторов во вложенные letвыражения, например так: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then {...
Я начинающий студент CS и я алгоритмы обучения. Я слышал , что даже с квантовыми компьютерами, что общие алгоритмы сортировки никогда не могут быть лучше , чем время. Тем не менее, я также знаю , что алгоритмы факторинговых бы намного быстрее. В общих чертах, какие алгоритмы станут существенно...
Что мы знаем, так это то, что π бесконечно и вполне вероятно, что оно содержит все возможные конечные цепочки цифр ( дизъюнктивная последовательность ). Недавно я видел некоторый прототип πfs, который предполагает, что каждый файл, который вы создали (или кто-либо еще) или вы создадите, он уже там,...
Учитывая два вектора целых чисел, возможно, неравной длины, как я могу определить максимально возможный результат от накопления выбора максимума между соответствующими парами чисел между двумя векторами с дополнительными нулями, вставленными в более короткий вектор, чтобы компенсировать разницу в...
Как бы вы алгоритмически определяли для каждой фотографии, светило ли солнце, когда она была сделана? Примеры Пример с этой веб-камеры на вершине горы: Ясно, что солнце светит. В этом другом примере это гораздо менее очевидно: Вероятно, довольно легко определить, туманно ли это, если попытаться...
Обычное изложение проблемы справедливой резки тортов предполагает, что все игроков получают свою долю одновременно. Однако во многих случаях игроки прибывают постепенно. Например, мы можем разделить торт по n игрокам, но затем приходит новый игрок и хочет получить долю.nnnnnn Как правило,...
В глубине первого дерева есть ребра, определяющие дерево (то есть ребра, которые использовались при обходе). Есть некоторые оставшиеся ребра, соединяющие некоторые другие узлы. В чем разница между поперечной кромкой и передней кромкой? Из википедии: Основываясь на этом остовном дереве, ребра...
Учитывая тот факт , что - путь перечисления является # Р-полной задачи, может ли быть эффективные методы , которые вычисляют (или , по меньшей мере , приблизительно) средняя длина - пути без перечисления их? Что если пути разрешены для пересмотра вершин?т с тsssTTtsssTTt Соответствующие результаты...
У меня есть два набора точек в 2-мерной плоскости. Я хочу найти ближайшую пару точек такую, чтобы , , а евклидово расстояние между как можно меньше. Насколько эффективно это можно сделать? Можно ли это сделать за , где?s , t s ∈ S t ∈ T s , t O ( n log n ) n = | S | + | T |S,TS,TS,Ts,ts,Ts,ts∈Ss∈Ss...
Недавно я столкнулся с этой проблемой , разновидностью Ханойских башен . Постановка задачи: Рассмотрим следующую вариацию хорошо известной проблемы «Ханойские башни»: Нам дано башен и m дисков размером сложены на несколько башен. Ваша задача - перенести все диски в башню минимальное количество...
Имеется ли два произвольных регулярных выражения, существует ли «эффективный» алгоритм для определения того, соответствуют ли они одному и тому же набору строк? В более общем смысле, можем ли мы вычислить размер пересечения двух наборов совпадений? Какие алгоритмы существуют для этого и в каком...
Моя проблема. Учитывая , я хочу , чтобы подсчитать число действительных мультимножествами . Мультисеть действительна, еслиS SnnnSSSSSS Сумма элементов является , инSSSnnn Каждое число от до может быть выражена однозначно как сумма некоторых элементов .п S111nnnSSS Пример. Например , если , то...
Я работаю над алгоритмами поиска строк, которые поддерживают поиск по нескольким шаблонам. Я нашел два алгоритма, которые кажутся наиболее сильными кандидатами с точки зрения времени выполнения, а именно: Aho-Corasick и Rabin-Karp . Однако я не смог найти исчерпывающего сравнения между этими двумя...