[dom] Выбор алгоритма и реализация (Re: Промежуточный отчёт)

[Александр Портной]

Добрый день.

1. Реализован генератор тестов, чеккер, были сгенерированы большие тесты.
2. Реализован алгоритм Ленгауэра-Тарьяна. Протестирован на тестах с ejudge
(задача на доминаторы) для задачи поиска непосредственных доминаторов. По
тестам, где обычное решение работает секунд 15-30, реализованный алгоритм
работает за 0.03 - 0.05 секунд, но при этом алгоритм, реализованный в
исходном коде (filldom), работает на 15-30% быстрее.
3. Планируется реализовать его на С++, разобраться с получившейся
асимптотикой, улучшить текущую версию алгоритма на С.


вт, 10 апр. 2018 г. в 13:13, Vladislav Ivanishin <vlad at ispras.ru>:

> Добрый день,
>
> Александр Портной <alexp239.14 at gmail.com> writes:
>
> > Добрый день,
> >
> > Было найдено 3 быстрых алгоритма:
> > 1. алгоритм Ленгауэра-Тарьяна, асимптотика O(m*logn) или O(m * a(n, m)) в
> > зависимости от реализации.
> > 2. http://www.iis.nsk.su/files/articles/sbor_kas_10_laki..
> > <
> https://vk.com/away.php?to=http%3A%2F%2Fwww.iis.nsk.su%2Ffiles%2Farticles%2Fsbor_kas_10_lakiichuk.pdf&cc_key=
> >
> > -
> > линейный.
> > 3. https://www.researchgate.net/publication/2382311_Domi..
> > <
> https://vk.com/away.php?to=https%3A%2F%2Fwww.researchgate.net%2Fpublication%2F2382311_Dominators_in_Linear_Time&cc_key=
> >
> > -
> > линейный.
>
> Удалось ли вам сделать выбор? Есть ли продвижение в реализации
> чего-нибудь из этого?
>
> Если какой-нибудь обмен кодом происходил, пожалуйста, заведите git
> репозиторий на сервере.
>
> --
> Влад
>
-- 
С уважением,
Александр Портной.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://compilers.ispras.ru/pipermail/dom/attachments/20180411/def8a958/attachment.html>