<div dir="ltr">В результате работы были найдены следующие быстрые алгоритмы:<br>1. <span style="white-space:pre-wrap">алгоритм Ленгауэра-Тарьяна (<a href="https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf">https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf</a>)</span><div><span style="white-space:pre-wrap">2. алгоритм, реализованный в filldom (<a href="https://scholarship.rice.edu/bitstream/handle/1911/96345/TR06-38870.pdf?sequence=1">https://scholarship.rice.edu/bitstream/handle/1911/96345/TR06-38870.pdf?sequence=1</a>)</span></div><div><span style="white-space:pre-wrap">3. алгоритм SNCA, описанный в статье (<a href="https://renatowerneck.files.wordpress.com/2016/06/gwtta04-dominators.pdf">https://renatowerneck.files.wordpress.com/2016/06/gwtta04-dominators.pdf</a>)</span></div><div><span style="white-space:pre-wrap">Также были рассмотрены некоторые алгоритмы, основанные на микродеревьях, но в статьях 2, 3 указано, что несмотря на их линейную теоретическую сложность, на практике они оказываются медленнее других алгоритмов.</span></div><div><span style="white-space:pre-wrap"><br></span></div><div><span style="white-space:pre-wrap">Были реализованы на языке C алгоритмы </span><span style="white-space:pre-wrap">Ленгауэра-Тарьяна и SNCA. </span></div><div><br></div><div><span style="white-space:pre-wrap">Были написан генератор тестов и чеккер. </span><span style="font-family:-apple-system,BlinkMacSystemFont,Roboto,"Helvetica Neue",sans-serif;font-size:13px">Генератор может сгенерировать все возможные ГПУ.</span></div><div><span style="white-space:pre-wrap"><br></span></div><div><span style="white-space:pre-wrap">Были протестированы реализованные алгоритмы, а также алгоритм из filldom (IBFS).</span></div><div><span style="white-space:pre-wrap">Проверка правильности работы производилась на тестах из ejudge (папка ejudge_tests). </span><span style="white-space:pre-wrap">Сгенерированные тесты на 500, 1000, 1500, 2000, 2500, 10000, 100000, 200000 блоков находятся в папке generated_tests. На каждом тесте алгоритм запускался 3 раза, в итоговую таблицу попал усредненный результат.</span></div><div><span style="white-space:pre-wrap"><br></span></div></div>-- <br><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature">С уважением,<br>Александр Портной.</div>