?

Log in

No account? Create an account
November 20th, 2006 - Konstantin Savenkov [entries|archive|friends|userinfo]
Konstantin Savenkov

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

November 20th, 2006

О математике [Nov. 20th, 2006|12:43 pm]
Konstantin Savenkov
[Tags|]

Получение математического результата можно сравнить с сооружением моста* через водную преграду.

Самое главное требование -- видеть цель, противоположный берег. Камни для моста найдутся всегда, но если у вас есть много камней (аксиом, лемм и теорем), но вы не видите цели -- ничего не получится. Помимо цели нужно оценить поток, который вас от неё отделяет. Проблема не в расстоянии, проблема -- в глубине. Возможно, в этом месте -- огородомут, в который уже не одно поколение математиков кидает свои камни. Увидеть цель (основную теорему) и оценить её достижимость (глубину потока) -- самое трудное. Как только это сделано, в результате можно не сомневаться.

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

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

Здесь нужно предостеречь строителя от замешивания бетона в самом начале. Хотя иногда это кажется логичным (сначала всё формально определить), не стоит так делать. Основное преимущества бетона -- то, что в жидком виде он принимает нужную форму. Если же он застынет, пока вы будете раскладывать свои камешки, то всё, что у вас останется -- это ведро никуда негодных определений. Вы потеряете не только приготовленный бетон, но и ведро, увы. Всему своё время. Порядок изложения материала часто не совпадает с порядком его создания.

---------
* Ну, положим, не моста, а дамбы. Водный поток в аналогии не учитывается, равно как и последствия от его перекрывания :-)
LinkLeave a comment

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

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

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

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

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

(no subject) [Nov. 20th, 2006|05:48 pm]
Konstantin Savenkov

- Скажите, множество N -- бесконечно?
- Конечно!
LinkLeave a comment

navigation
[ viewing | November 20th, 2006 ]
[ go | Previous Day|Next Day ]