Информатика

9
Что такое «динамический» в динамическом программировании?

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

9
Оценка коллег - выбор графика, чтобы получить точные рейтинги / рейтинги

Фон. Я пишу некоторый код для полуавтоматической оценки, используя оценку сверстников как часть процесса оценки. Студентам дают пары эссе за один раз, и у студентов есть ползунок, чтобы выбрать, который лучше и насколько он лучше. например, слайдер может выглядеть примерно так: A---X-B На основе...

9
Нахождение k-кратчайшего пути между двумя узлами

Учитывая взвешенный орграф и весовую функцию , обычно можно использовать алгоритм Дейкстры для получения кратчайшего пути. Что меня интересует, так это как получить -короткий путь, -короткий путь и так далее.G = V, Eгзнак равноВ,ЕG=V,Ed( U , V )d(U,v)d(u,v)2н д2Nd2^{nd}3г д3рd3^{rd} Вопросов:...

9
Ищите комплексную реализацию с небольшим объемом памяти

Я ищу реализацию заданного типа данных. То есть мы должны поддерживать динамическое подмножество SSS (размера nnn ) из юниверса U={0,1,2,3,…,u–1}U={0,1,2,3,…,u–1}U = \{0, 1, 2, 3, \dots , u – 1\} размера uuu с операции insert(x)(добавить элемент xв SSS ) и find(x)(проверяет, xявляется ли элемент...

9
Выбор параметров для генетического алгоритма

Как можно выбрать правильное количество параметров для генетического алгоритма для моделирования данной системы? Например, скажем, вы хотите оптимизировать производство автомобилей, и у вас есть 1000 измерений почасовой эффективности для различных задач для каждого из 1000 различных сотрудников....

9
Когда я должен выйти за пределы k ближайшего соседа

Для многих проектов машинного обучения мы начинаем с классификатора k Nearest Neighbor. Это идеальный начальный классификатор, поскольку у нас обычно достаточно времени для расчета всех расстояний, а количество параметров ограничено (k, метрика расстояния и весовые коэффициенты). Однако это часто...

9
Распознавание водных путей на аэрофотоснимках - полигоны из изображений с обнаружением краев

Я пытаюсь распознать водные пути по аэрофотоснимкам (скажем, из Google Maps). Местные органы власти часто располагают данными ГИС, в которых указано, где находятся водные пути (и дороги, здания и т. Д.), Но данные о них в воде часто несколько неточны, и мы могли бы улучшить их, используя...

9
В чем недостаток метода обратимых вычислений «сохранить данные»?

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

9
Компактное представление путей в графе

У меня есть подмножество простых путей в графе. Длина путей ограничена .ddd Каким самым компактным способом (с точки зрения памяти) я могу представить пути так, чтобы не были представлены никакие другие пути, кроме выбранных? Обратите внимание, что я хочу использовать это представление в алгоритме,...

9
Могут ли методы проверки программы предотвратить появление ошибок жанра Heartbleed?

На вопрос об ошибке Heartbleed Брюс Шнайер написал в своей «Крипто-грамме» от 15 апреля: «Катастрофический» - правильное слово. По шкале от 1 до 10 это 11 '. Несколько лет назад я читал, что ядро ​​определенной операционной системы строго проверено современной системой проверки программ....

9
Вывод типа + перегрузка

Я ищу алгоритм вывода типов для разрабатываемого языка, но я не смог найти тот, который удовлетворял бы моим потребностям, потому что они обычно таковы: à la Haskell, с полиморфизмом, но без специальной перегрузки C ++ (авто), в котором у вас есть временная перегрузка, но функции мономорфны В...

9
Алгоритм замены страницы часов - уже существующие страницы

При моделировании алгоритма замены страницы часов, когда появляется ссылка, которая уже находится в памяти, стрелка часов все еще увеличивается? Вот пример: С 4 слотами, используя алгоритм замены страницы часов Список литературы: 1 2 3 4 1 2 5 1 3 2 4 5 Начальный список будет выглядеть так: ->...

9
Почему точность модуля с плавающей запятой имеет значение?

Большинство диалектов Smalltalk в настоящее время реализуют наивный неточный плавающий модуль (fmod / remainder). Я просто изменил это, чтобы улучшить Squeak / Pharo и, в конечном итоге, соблюдение стандартов Smalltalk (IEEE 754, ISO / IEC 10967), как я уже делал для других современных операций с...

9
Почему интросорт использует heapsort, а не mergesort?

В рамках домашнего задания, посвященного реализации интросорта, меня спрашивают, почему используется heapsort, а не mergesort (или другие алгоритмы в этом отношении). O(nlog(n))O(nlog⁡(n))O(n\log(n)) Интросорт - это гибридный алгоритм сортировки, который обеспечивает как быструю среднюю...

9
Каковы подходящие изоморфизмы между формальными языками?

Формальный язык над алфавитом является подмножеством , то есть, набор слов в этом алфавите. Два формальных языка и равны, если соответствующие множества экстенсивно равны как подмножества . Можно использовать языки в теории сложности, чтобы формализовать понятие «проблемы». Можно было бы...

9
Булевы функции Тьюринга завершены

Булева функция - это функция .е: { 0 , 1 }N→ { 0 , 1 }е:{0,1}N→{0,1}f:\{0,1\}^n\rightarrow\{0,1\} Известно, что логический базис является полным по Тьюрингу, поскольку он позволяет переворачивать любую последовательность или оставлять ее без изменений. То же самое можно сказать о воротах .( ∨ , ∧...

9
Какие существуют алгоритмы для решения линейных систем с натуральными числами?

Я смотрю на следующую проблему: Для заданных мерных векторов натуральных чисел v 1 , … , v m и некоторого входного вектора u , является ли u линейной комбинацией v i с коэффициентами натуральных чисел?nnnv1,…,vmv1,…,vmv_1, \ldots, v_muuuuuuviviv_i т.е. есть ли где u = t 1 v 1 + ⋯ + t m v m...

9
Распределение вероятностей и вычислительная сложность

Этот вопрос о пересечении теории вероятностей и сложности вычислений. Одним из ключевых замечаний является то, что некоторые распределения проще генерировать, чем другие. Например, проблема Для заданного числа вернуть равномерно распределенное число с .i 0 ≤ i < nnnniii0≤i<n0≤i<n0 \leq i <...

9
Как восстановить лес синтаксических деревьев из вектора Эрли?

Использовать вектор Эрли в качестве распознавателя довольно просто: когда достигается конец строки, вам просто нужно проверить завершенную аксиоматическую постановку, начатую в позиции 0. Если у вас есть хотя бы один, тогда строка принимается. Использование вектора Эрли для восстановления дерева...