Вопросы, возникающие в связи с применением теоретической информатики в других областях исследований / практики компьютерных наук или по другим предметам.
Чтобы продемонстрировать важность алгоритмов (например, для студентов и преподавателей, которые не занимаются теорией или даже из совершенно разных областей), иногда полезно иметь под рукой список примеров, где основные алгоритмы были развернуты в коммерческих, государственных и или широко...
Для решения проблемы максимального потока , кажется, существует ряд очень сложных алгоритмов, по крайней мере один из которых был разработан совсем недавно, в прошлом году. Макс Орлина течет за O (MN) времени или лучше дает алгоритм, который работает в O (VE). С другой стороны, алгоритмы, которые я...
Изучение экологии и эволюции становится все более математическим, но большинство теоретических инструментов, похоже, исходит от физики. Однако во многих случаях проблемы носят весьма дискретный характер (см., Например, SLBS00 ) и могут быть полезны с точки зрения информатики . Тем не менее, я знаю...
Я не теоретик информатики, но думаю, что проблема реального мира здесь. Проблема У моей компании есть несколько подразделений по всей стране. Мы предложили сотрудникам возможность работать на другом блоке. Но есть условие: общее количество работников на единицу не может измениться. Это означает: мы...
Я работал над внедрением некоторых результатов вычислительной сложности в теоретическую биологию, особенно эволюцию и экологию , с целью быть интересным / полезным для биологов. Одна из самых больших трудностей, с которыми я столкнулся, заключается в обосновании полезности асимптотического анализа...
В последнее время я начал изучать алгоритмы аппроксимации для NP-сложных задач и интересовался теоретическими причинами их изучения. (Вопрос не должен быть подстрекательским - мне просто любопытно). Из исследования алгоритмов аппроксимации возникла действительно прекрасная теория - связь между...
Проводились ли исследования по внедрению конструкций экстракторов случайности? Кажется, что доказательства экстрактора используют Big-Oh, оставляя возможность для больших скрытых констант, делая программные реализации потенциально нереальными. Некоторый контекст: я заинтересован в использовании...
Я хотел бы выступить с математикой о системе контроля версий git . В настоящее время он широко используется в математике, а также в индустрии компьютерных наук. Например, сообщество HoTT (Homotopy Type Theory) использует его, и это система перехода к совместному редактированию текстовых файлов,...
Давайте предположим, что мы создали универсальный квантовый компьютер. За исключением вопросов, связанных с безопасностью (криптография, конфиденциальность, ...), какие текущие проблемы реального мира могут извлечь выгоду из его использования? Я заинтересован в обоих: проблемы, в настоящее время...
При попытке убедить экономистов в актуальности теории сложности в печати, есть ли стандартная ссылка для цитирования? Я знаком с постом в блоге Ноама Нисана , опросом Тима Раугардена и 11-й статьей эссе Скотта Ааронсона . Эти посты доступны для компьютерных ученых, но не используют язык экономистов...
Я задал этот вопрос о переполнении стека некоторое время назад: Проблема: продажа Боба . Кто-то предложил также разместить здесь вопрос. Кто-то уже задавал вопрос, связанный с этой проблемой, здесь - минимальный вес леса данной мощности - но, насколько я понимаю, это не помогает мне с моей...
Какие проблемы реального мира были решены с использованием генетического алгоритма? В чем проблема? Какой фитнес-тест используется для решения этой
Рассмотрим следующую проблему: Учитывая набор из положительных чисел { a 1 , … , a n }, в которых k ≥ 3 является константой, мы хотим разбить набор на m подмножеств размера k так, чтобы произведение суммы каждого подмножества максимальноn=kmn=kmn = k m{a1,…,an}{a1,…,an}\{ a_1, \dots, a_n \}k≥3k≥3k...
Пусть x1,…,xnx1,…,xnx_1, \ldots, x_n - точки на плоскости R2R2\mathbb{R}^2 . Рассмотрим полный граф с точками в виде вершин и весами ребер . Вы всегда можете найти вес, который составляет не менее \ 2 2 от общего веса? Если нет, то какая константа должна заменить \ frac 2 3 ?2∥xi−xj∥2‖xi−xj‖2\|x_i...
Концепция секретной схемы обмена часто приписывается Шамиру (A. Shamir, Как поделиться секретом , Comm. ACM, 22 (1979), pp. 612-613.) И Blakey (GR Blakey, Защита криптографических ключей , в Proc. NCC, vol. 48, 1979, pp. 313-317.). Общая идея заключается в том, что какой-то секрет S скрыт от...
Я ищу высокоэффективную структуру данных для хранения данных, аналогичную следующей. Идентификационные метки Order1 Order2 -------------------------- 1 1,2 1 1 2 2,5 2 3 3 1,7 4 7 4 6 3 0 Мне нужно иметь возможность запрашивать эту структуру таким образом, чтобы она выдала мне список всех...
Меня интересуют комбинаторные свойства социальных сетей в виде графиков. Люди смотрели на такие вещи, как распределение степеней, коэффициент кластеризации и сжимаемость этих графиков. Один основной вопрос: действительно ли эти графики являются хорошими графами расширителей? Кто-нибудь проверял,...
Я студент CS. Мы делали теорию графов в одном курсе. Я нашел это интересным. Каковы реальные применения теории графов в области компьютерных наук? Например, я обнаружил, что некоторые понятия в теории графов могут использоваться для проектирования сетей. Какие есть другие похожие...
Пусть x=(x1,…,xn)x=(x1,…,xn)x=(x_1,\dots,x_n) - вектор булевых переменных. Пусть C,DC,DC,D две булевы схемы на xxx . Скажите, что CCC похож на DDD если: x { 0 , 1 } nPr[C(x)≠D(x)]Pr[C(x)≠D(x)]\Pr[C(x) \ne D(x)]xxx{0,1}n{0,1}n\{0,1\}^n C,DC,DC,D различаются по расстоянию редактирования графика...
Этот вопрос был мотивирован вопросом, заданным на stackoverflow . Предположим, вам дано корневое дерево (т. Е. Есть корень, а у узлов есть дочерние элементы и т. Д.) На n узлах (обозначены 1 , 2 , … , n ).TTTNnn1 , 2 , … , n1,2,…,n1, 2, \dots, n Каждая вершина имеет неотрицательный целочисленный...