?

Log in

No account? Create an account

Ср, 24 ноя, 2010, 17:32
Теорема связности

Почти месяц доказывал математическую теорему, которая необходима для алгоритмов скелетизации в моих библиотеках AlgART. Оказывается, все эти годы эти библиотеки применялись без всяких гарантий, что скелетизация действительно сохраняют связность. Старые, довольно простые алгоритмы, практиковавшиеся на Паскале и C++ с 1992 года, при всем своем несовершенстве (это были плохо оптимизированные 3x3-скелеты), все же сохраняли связность, а вот новые скелеты 3x5, реализованные весной 2008 года, оказывается, рвали некоторые конфигурации — отчасти именно обнаружение этой ошибки побудило меня разработать формальное доказательство. Новая теорема позволяет утверждать: если выполнены некоторые простые условия, которые можно проверить в переборной программе-тесте, и если некая другая переборная программа-тест, применяющая скелетизацию к маленьким матрицам 3x7 и 4x6, не нашла ни одного случая разрыва скелета, то тогда данный алгоритм скелетизации гарантированно не нарушает связность.

Теорема скелетизации опубликована в виде статьи:
Теорема связности для параллельной скелетизации растрового изображения

Опубликовал ссылку здесь:
http://forum.algolist.ru/algorithm-maths-mathematical/4449-teorema-sviaznosti-dlia-parallelnyh-rastrovyh-skeletov.html
(Удалённый комментарий)

Ср, 19 янв, 2011 20:53 (UTC)
danielalievsky: Re: С праздником Вас

Спасибо!