Есть две функции

но ведь решаемая задача — не задача о выполнимости, ибо тут очень сильно сужен класс рассматриваемых функций. она вообще остается NP-полной для выбранного класса функций?

Есть две функции

но не получится ли так, что понять ответ в искомой задаче можно будет с меньшей сложностью просто посмотрев на структуру и связи используемых логических элеменов в этой функции, без необходимости запускать функцию вообще?

Есть две функции

а на возникает тут сразу проблема следующего вида: вот дан черный ящик, нам сказали (или нам кажется) что этот ящик это оракул для функции f. как быстро можно проверить что черный ящик — действительно оракул для f и с какой точностью?

Есть две функции

и все-таки, в момент появления оракула сразу возникает вопрос о том, что таки понимается в этом случае под сложностью алгоритма, почему она осталась O(1) и как должна быть задана функция f на вход алгоритму так, чтобы при этом ее вычисление было более затратно нежели сама подача представления этой функции на вход алгоритму?

Первый частный город в России, быть или не быть? Часть 1

а перекрестки из 3х дорог каждый с возможностью повернуть в любом направлении не будут чересчур сильно тормозить трафик?

Выборы-2016. Часть 2 — удивительное рядом и оно разрешено

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

Выборы-2016. Часть 2 — удивительное рядом и оно разрешено

и если для d2 и d3 уменьшить дисперсию так, чтобы график был более похож на тот что в статье — то диагонали будут заметны и при больших диапазонах ограничения на d1

тут я взал такие параметры:

d2 = int( max(0,np.random.normal(0.05, 0.02) * d1))
d3 = int( max(0,np.random.normal(0.03, 0.02) * d1))

границы диапазона для d1 подписаны у картинок

Выборы-2016. Часть 2 — удивительное рядом и оно разрешено

у меня при тестировании получилось что наличие явно выраженных диагоналей зависит и от минимальной и от максимальной границы для d1

при этом наиболее выраженная картина с диагоналями в случае диапазона [150,200]

Выборы-2016. Часть 2 — удивительное рядом и оно разрешено

r1 = []
r2 = []
for _ in xrange(100000):
    d1 = random.randint(10,200)
    d2 = int( max(0,np.random.normal(0.05, 0.1) * d1))
    d3 = int( max(0,np.random.normal(0.03, 0.1) * d1))
    r1 += [ float(d2) / d1 ]
    r2 += [ float(d3) / d1 ]

Выборы-2016. Часть 2 — удивительное рядом и оно разрешено

нагенерировал ради интереса синтетических данных следующего вида: размер участка — равномерно распределен от 10 до 200, одна партия набирает ~N(0.05, 0.1) % голосов, другая ~N(0.03, 0.1). выборка из 100000 участков. график соотношения процентов:

Роскомнадзор разместил вакансию «хакера»

ну например это можно перевести на человеческий язык как «проведение аудита информационной безопасности» в подразделениях в регионах и, например, у коллег в Беларуси

Роскомнадзор разместил вакансию «хакера»

ну а в перечне обязанностей этого и нет. а специалист по инфобезу с опытом white/blackhat может оказаться куда более полезным для тех обязанностей, которые указаны. как минимум сможет сам проводить penetration testing собственной инфраструктуры, возможно у него есть адекватные источники информации по новым 0day-уязвимостям, и т.п.

Роскомнадзор разместил вакансию «хакера»

это уже спорный вопрос. со стороны тех, у кого без их спроса понарушали информационную безопасность — вполне себе блек. особенно если цели атак иностранные.

Роскомнадзор разместил вакансию «хакера»

опыт работы black-hat тоже мог быть санкционирован. мало ли, вдруг прошлое место работы/службы было в каком-нибудь специальном подразделении госструктур, имеющих санкцию на подобные спецмероприятия

б

В задаче о клике (которая является NP-полной) граф произвольной формы. Задача о максимальной клике без весов на ребрах в полносвязном графе очевидно решается за O(1). Тут задача maximum weighted clique в полносвязном графе (я сходу не уверен что она NP-полная, хочется почитать обоснование), и судя по всему предлагается ее решать жадным алгоритмом методом последовательного удаления вершин с минимальной суммарной стоимостью удаленных ребер, и все равно непонятно что делать если после удаления одной вершины получатся подклики одинакового суммарного веса и почему делается всего один шаг.

б

а можно где-нибудь увидеть обоснование принадлежности этой задачи к классу NP?

«Роскосмос» начинает работу над созданием многоразовой ракеты

тополь-м — длина 22м (полная)
falcon 9 — длина 70м (полная, первая ступень меньше)
и емнип грузовик для тополя без хотя бы грунтовой дороги тоже не очень мобилен (через лес не проедет например), а будь перевозимая сущность в 2 раза длиннее — тем более

«Роскосмос» начинает работу над созданием многоразовой ракеты

море удобно тем, что по нему плавать можно в произвольных направлениях. а с посадочной площадки в лесу за 100500км от ближайшей реки или железной дороги ступень будет очень неприятно забирать

Спросите Итана №51: является ли астрология наукой?

будет очень интересно есть покажут влияние количества витамина Д в организме матери на формирование мозговых структур ребенка. из википедии:

Research suggests that vitamin D may function as a modulator in brain development and as a neuroprotectant. In recent studies, vitamin D has exhibited an association with the regulation of nerve growth factor (NGF) synthesis. NGF is responsible for the growth and survival of neurons. This relationship has also been studied in embryonic and neonatal rats. Developmental vitamin D deficient (DVD) rats have decreased levels of neurotrophic factors, increased mitosis, and decreased apoptosis. These findings suggest that vitamin D potentially affects the development of neurons as well as their maintenance and survival. Current research is underway investigating whether vitamin D is a factor contributing to normal brain functioning.

Rutracker перешёл на HTTPS

[sarcasm on] а следующим шагом будет введение администрацией рутрекера блокировок exit-нод тора и этого списка проксей например потому что «с них регистрируются боты и рассылают спам в форуме»? [sarcasm off]

а если серьезно — обязаловка использования https ломает тривиально настраиваемую удобную тулзу от доверенного разработчика для обхода ограничений доступа. получаемый бонус в виде шифрования трафика выглядит не на столько убедительным, ибо это все-таки не интернет-банкинг.