itmo 13 фев 2016 в 14:54

Работа с данными: Новая наука

5 мин

36K

Блог компании ИТМОЗанимательные задачкиМашинное обучение*Программирование*

+13

Комментарии 6

lisang 13 фев 2016 в 18:10

Чтобы ее решить, Эйлер построил модель из точек и линий и обнаружил, что задача имеет решение только в том случае, если к каждому «островку земли» будет вести четное количество мостов. Так как в Кёнигсберге было нечетное количество мостов, это путешествие оказалось невозможным.

Из второго предложения не следует, что не выполняется условие из первого предложения (3 моста, 1->2->3->1).

harlong 13 фев 2016 в 22:24

И «во всех вершинах должно сходиться четное число ребер» — достаточное, но не необходимое условие для решения задачи. Необходимое будет «существует не более двух вершин с нечетным числом ребер».

harlong 13 фев 2016 в 22:35

Кстати, в современном виде для центра города задача решаема.

Askon 13 фев 2016 в 22:49

еще бы, ведь их 8.

harlong 13 фев 2016 в 23:16

Ок, добавляем двухъярусный мост (красным). Их становится 9, но задача все еще решаема.

yorko 15 фев 2016 в 01:33

Кандес считает, что можно взять половину образцов (16) и провести повторный анализ. Если результат положительный, то инфицированный находится в этой группе, если нет, то в другой. Далее группа снова делится пополам, и тестирование повторяется. Таким образом, вы получите ответ за 5 тестов, вместо 32, если проверять каждого по отдельности. В этом суть метода Compressed sensing.

Простите, но мне описание бинарного поиска ничего нового про compressed sensing не говорит.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Работа с данными: Новая наука

zproxy.org