Я знаю, что это может звучать немного нестандартно, на самом деле я всегда думал внутри коробки, но в последнее время я думал, возможно, потому, что информатика предоставляет высокую степень свободы, о способах разработки других программ, кроме те, которые преподавали в университете. Рассмотрим...
Учитывая распределение степеней, как быстро мы можем построить график, который следует заданному распределению степеней? Ссылка или эскиз алгоритма были бы хорошими. Алгоритм должен сообщать «нет», если граф не может быть построен, и любой один пример, если можно построить несколько...
Рассмотрим граф G(V,E)G(V,E)G(V,E) . Каждое ребро имеет два веса и . Найдите остовное дерево, которое минимизирует произведение . Алгоритм должен работать за полиномиальное время относительно,A e B e ( ∑ e ∈ T A e ) ( ∑ e ∈ T B e ) | V | , | E...
Задача линейного программирования: найти сильно полиномиальный алгоритм времени, который для заданной матрицы A ∈ Rm × n и b ∈ Rm решает, существует ли x ∈ Rn с Ax ≥ b. Я знаю, что в списке Стива Смейла перечислены некоторые нерешенные проблемы математики. Но такая проблема линейного...
Расстояние редактирования Левенштейна-расстояния между списками является хорошо изученной проблемой. Но я не могу найти много о возможных улучшениях, если известно, что ни один элемент не встречается более одного раза в каждом списке . Также предположим, что элементы сопоставимы / сортируемы (но...
Что это значит, когда мы говорим, что алгоритм XXX асимптотически более эффективен, чем ?YYY XXX будет лучшим выбором для всех входов. XXX будет лучшим выбором для всех входов, кроме небольших. XXX будет лучшим выбором для всех входов, кроме больших. YYY будет лучшим выбором для небольших входов....
Учитывая и ,a,b,c,d∈Na,b,c,d∈Na,b,c,d \in \mathbb Nb,d∉{0}b,d∉{0}b,d \notin \{0\} ab<cd⟺ad<cbab<cd⟺ad<cb \begin{eqnarray*} \frac a b < \frac c d &\iff& ad < cb \end{eqnarray*} Мои вопросы: Учитываяa,b,c,da,b,c,da,b,c,d Предполагая, что мы можем решить в , есть ли способ решить без...
Мне дали следующую проблему в интервью (которую я уже не смог решить, не пытаясь обмануть мой путь мимо): Игра начинается с положительного целого числа . (Например , 0 = 1234 ) . Это число преобразуется в двоичное представление, и N представляет собой количество битов в 1 . (Например, A 0 = b 100...
Я слышал, что этот вопрос задавался много раз, и я надеялся получить какое-то мнение о том, какие могут быть хорошие ответы: у вас большой файл размером более 10 ГБ, и вы хотите выяснить, какой элемент встречается чаще всего, какой способ лучше сделать это? Итерация и отслеживание на карте,...
Рассмотрим последовательность из nnn бросков несмещенной монеты. Пусть HiHiH_i обозначает абсолютное значение превышения количества голов над хвостами, которые были замечены в первом iii броске. Определить H=maxiHiH=maxiHiH=\text{max}_i H_i . Покажите, что E[Hi]=Θ(i√)E[Hi]=Θ(i)E[H_i]=\Theta (...
Итак, я знаю, что проверка того, является ли обычный язык рRR подмножеством обычного языка SSS , разрешима, поскольку мы можем преобразовать их оба в DFA, вычислить R ∩ S¯R∩S¯R \cap \bar{S} , а затем проверить, является ли этот язык пустым. Однако, поскольку это требует преобразования в DFA,...
У меня есть неориентированное дерево, вершины которого я хочу пометить. Узлы листа должны быть помечены как один. Затем предположим, что листья были удалены. На дереве, которое остается, листья должны быть помечены двумя. Этот процесс продолжается очевидным образом, пока все вершины не имеют метки....
В настоящее время я читаю введение в алгоритмы и пришел по алгоритму Джонсона, который зависит от того, чтобы убедиться, что все пути положительны. алгоритм зависит от нахождения новой весовой функции (w '), которая является положительной для всех ребер и сохраняет правильность соотношений...
Для заданного ортогонального многоугольника (многоугольник, стороны которого параллельны осям), я хочу найти наименьший набор внутренних непересекающихся квадратов, объединение которых равно многоугольнику. Я нашел несколько ссылок на слегка отличающиеся проблемы, такие как: Покрытие ортогонального...
У Алисы, студентки, есть много домашней работы в течение следующих недель. Каждый предмет домашнего задания занимает у нее ровно один день. Каждый элемент также имеет крайний срок и отрицательно влияет на ее оценки (допустим реальное число, бонусные баллы только при условии сопоставимости), если...
Я пытаюсь решить проблему SAT переменных 25k пунктов 5k переменных. Так как он работал в течение часа (precosat), и я хотел бы потом решить более крупные, я ищу многоядерный SAT-Solver. Кажется, что есть много SAT-Solvers, я совершенно потерян. Кто-нибудь может указать мне лучший вариант для моего...
Один из самых популярных вопросов о структурах данных и алгоритме, который чаще всего задают при телефонном
С точки зрения асимптотического времени выполнения в наихудшем случае, какая NP-полная задача имеет самый известный (точный) алгоритм и что это за алгоритм? Известно ли что-то, что быстрее, чем...
Учитывая этот псевдокод пузырьковой сортировки: FOR i := 0 TO arraylength(list) STEP 1 switched := false FOR j := 0 TO arraylength(list)-(i+1) STEP 1 IF list[j] > list[j + 1] THEN switch(list,j,j+1) switched := true ENDIF NEXT IF switched = false THEN break ENDIF NEXT Какие основные идеи я...
Я работаю над алгоритмами поиска строк, которые поддерживают поиск по нескольким шаблонам. Я нашел два алгоритма, которые кажутся наиболее сильными кандидатами с точки зрения времени выполнения, а именно: Aho-Corasick и Rabin-Karp . Однако я не смог найти исчерпывающего сравнения между этими двумя...