[dom] Итоговый отчет

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

В результате работы были найдены следующие быстрые алгоритмы:
1. алгоритм Ленгауэра-Тарьяна (
https://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/a%20fast%20algorithm%20for%20finding.pdf
)
2. алгоритм, реализованный в filldom (
https://scholarship.rice.edu/bitstream/handle/1911/96345/TR06-38870.pdf?sequence=1
)
3. алгоритм SNCA, описанный в статье (
https://renatowerneck.files.wordpress.com/2016/06/gwtta04-dominators.pdf)
Также были рассмотрены некоторые алгоритмы, основанные на микродеревьях, но
в статьях 2, 3 указано, что несмотря на их линейную теоретическую
сложность, на практике они оказываются медленнее других алгоритмов.

Были реализованы на языке C алгоритмы Ленгауэра-Тарьяна и SNCA.

Были написан генератор тестов и чеккер. Генератор может сгенерировать все
возможные ГПУ.

Были протестированы реализованные алгоритмы, а также алгоритм из filldom
(IBFS).
Проверка правильности работы производилась на тестах из ejudge (папка
ejudge_tests). Сгенерированные тесты на 500, 1000, 1500, 2000, 2500, 10000,
100000, 200000 блоков находятся в папке generated_tests. На каждом тесте
алгоритм запускался 3 раза, в итоговую таблицу попал усредненный результат.

-- 
С уважением,
Александр Портной.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://compilers.ispras.ru/pipermail/dom/attachments/20180416/0038a45c/attachment.html>