<div><div dir="auto">Добрый день!</div><div dir="auto"><br></div><div dir="auto">Отчёт засчитан?</div><br><div class="gmail_quote"><div>пн, 16 апр. 2018 г. в 21:11, Александр Портной <<a href="mailto:alexp239.14@gmail.com">alexp239.14@gmail.com</a>>:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div>В результате работы были найдены следующие быстрые алгоритмы:<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" target="_blank">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" target="_blank">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" target="_blank">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 class="m_-3052607172497143383gmail_signature" data-smartmail="gmail_signature">С уважением,<br>Александр Портной.</div></blockquote></div></div>-- <br><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature">С уважением,<br>Александр Портной.</div>