?

Log in

No account? Create an account
О транзитивности - Konstantin Savenkov [entries|archive|friends|userinfo]
Konstantin Savenkov

[ website | My Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

О транзитивности [Nov. 20th, 2006|12:55 pm]
Konstantin Savenkov
[Tags|]

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

Как раз недавно я наткнулся на яркий пример того, что получается, когда так не делают. Одни очень уважаемые люди описали последовательность из двух алгоритмов, сформулировав для первого из них более жёсткие условия на результат, чем должны быть на данные для второго. В результате -- впиющая сложность в О(n^5). Их ошибку можно описать при помощи следующей аналогии.

Множество точек на карте можно связать двумя отношениями -- "можно дойти по прямой" и "можно дойти". Легко заметить, что второе отношение, в отличие от первого, не обладает свойством транзитивности. Если вы хотите знать, можно ли из одной точки попасть в другую, достаточно построить отношение "можно дойти" -- для этого нужно обойти все точки и вернуться в исходную. Построение отношения "можно дойти по прямой" потребует куда более активных и многочисленных перемещений.

То, что авторы статьи строят в первом алгоритме, можно соотнести с отношением "можно дойти по прямой", а во втором -- всего лишь интересуются, достижима ли одна точка из другой. Вот так.
LinkReply

Comments:
[User Picture]From: kstoor
2006-11-21 02:07 pm (UTC)
Костя, а можно оффтопичный вопрос? Начал задумываться над ~постепенным~ (это ключевое слово) переходом на нормальную операционку ;), так вот: найти (или сделать силами чайника) live cd с линуксом для ThinkPad -- реально ли?
(Reply) (Thread)
[User Picture]From: savenkov
2006-11-21 04:40 pm (UTC)
Knoppix, например.

Правда, всякие фишки вроде спецклавиш и гибернейта работать с livecd, скорее всего, не будут. Можно второй системой к виндам поставить Kubuntu, например.
(Reply) (Parent) (Thread)