<div dir="ltr">Добрый день.<div><br></div><div>1. Реализован генератор тестов, чеккер, были сгенерированы большие тесты.</div><div>2. Реализован <span style="color:rgb(33,33,33)">алгоритм Ленгауэра-Тарьяна. Протестирован на тестах с ejudge (задача на доминаторы) для задачи поиска непосредственных доминаторов. По тестам, где обычное решение работает секунд 15-30, реализованный алгоритм работает за 0.03 - 0.05 секунд, но при этом алгоритм, реализованный в исходном коде (filldom), работает на 15-30% быстрее.<br>3. Планируется реализовать его на С++, разобраться с получившейся асимптотикой, улучшить текущую версию алгоритма на С.<br><br></span></div><br><div class="gmail_quote"><div dir="ltr">вт, 10 апр. 2018 г. в 13:13, Vladislav Ivanishin <<a href="mailto:vlad@ispras.ru" target="_blank">vlad@ispras.ru</a>>:<br></div></div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Добрый день,<br>
<br>
Александр Портной <<a href="mailto:alexp239.14@gmail.com" target="_blank">alexp239.14@gmail.com</a>> writes:<br>
<br>
> Добрый день,<br>
><br>
> Было найдено 3 быстрых алгоритма:<br>
> 1. алгоритм Ленгауэра-Тарьяна, асимптотика O(m*logn) или O(m * a(n, m)) в<br>
> зависимости от реализации.<br>
> 2. <a href="http://www.iis.nsk.su/files/articles/sbor_kas_10_laki" rel="noreferrer" target="_blank">http://www.iis.nsk.su/files/articles/sbor_kas_10_laki</a>..<br>
> <<a href="https://vk.com/away.php?to=http%3A%2F%2Fwww.iis.nsk.su%2Ffiles%2Farticles%2Fsbor_kas_10_lakiichuk.pdf&cc_key=" rel="noreferrer" target="_blank">https://vk.com/away.php?to=http%3A%2F%2Fwww.iis.nsk.su%2Ffiles%2Farticles%2Fsbor_kas_10_lakiichuk.pdf&cc_key=</a>><br>
> -<br>
> линейный.<br>
> 3. <a href="https://www.researchgate.net/publication/2382311_Domi" rel="noreferrer" target="_blank">https://www.researchgate.net/publication/2382311_Domi</a>..<br>
> <<a href="https://vk.com/away.php?to=https%3A%2F%2Fwww.researchgate.net%2Fpublication%2F2382311_Dominators_in_Linear_Time&cc_key=" rel="noreferrer" target="_blank">https://vk.com/away.php?to=https%3A%2F%2Fwww.researchgate.net%2Fpublication%2F2382311_Dominators_in_Linear_Time&cc_key=</a>><br>
> -<br>
> линейный.<br>
<br>
Удалось ли вам сделать выбор? Есть ли продвижение в реализации<br>
чего-нибудь из этого?<br>
<br>
Если какой-нибудь обмен кодом происходил, пожалуйста, заведите git<br>
репозиторий на сервере.<br>
<br>
--<br>
Влад<br>
</blockquote></div></div>-- <br><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature">С уважением,<br>Александр Портной.</div>