itmo Feb 13 2016 at 14:54

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

5 min

36K

ITMO corporate blogEntertaining tasksProgramming*Machine learning*

+13

Comments 6

lisang Feb 13 2016 at 18:10

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

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

harlong Feb 13 2016 at 22:24

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

harlong Feb 13 2016 at 22:35

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

Askon Feb 13 2016 at 22:49

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

harlong Feb 13 2016 at 23:16

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

yorko Feb 15 2016 at 01:33

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

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