ИТОГИ I ТУРА ОТКРЫТОЙ ВСЕСИБИРСКОЙ ОЛИМПИАДЫ

Для тестирования было предоставлено четыре программы от команд:

rip (Московский Государственный Университет),
TSU_UPS (Томский Государственный Университет),
nfikemsu2 (Новокузнецкий Филиал-Институт Кемеровского Государственного Университета)
NSU2 (Новосибирский Государственный Университет).

Небольшое количество предоставленных задач позволяет нам изложить результаты тестирования не в виде таблицы, а в жанре "редакции для тестирования было предоставлено четыре мыши".

Тестирование осуществлялось вручную. Для анализа результатов использовалась написанная на коленке программа-визуализатор: viewer.zip.

Первой при тестировании с дистанции сошла программа TSU_UPS: все, что она делала - это делила пополам все отрезки исходной кривой. Никакого другого поведения ни на одном из тестов нам от этой программы добиться не удалось.

Более интеллектуальное поведение продемонстрировала программа nfikemsu2: она честно заменяла каждый отрезок ломаной на уменьшенную копию всей ломаной. Но никаких попыток найти в ломаной уже существующие самоподобия не делалось. Кроме того, на не очень-то больших тестах (второе приближение треугольника Серпинского) программа просто падала.

Попытки поиска самоподобий продемонстрировали две программы: RIP и NSU2, поэтому основные состязания развернулись между ними.

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

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

Расстроившись, мы не стали заниматься генерацией более сложных тестов, например кривой Гильберта или квадрата Серпинского.

По итогам тестирования жюри пришло к решению:

Первое место не присуждать.
Второе место присудить командам RIP и NSU2
Третье место присудить команде nfikemsu2.
Выразить сожаление по поводу того, что распознавание векторых образов почему-то оказалось задачей гораздо более сложной, чем прошлогоднее распознавание образов растровых.