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

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

Добрый день!

Отчёт засчитан?

пн, 16 апр. 2018 г. в 21:11, Александр Портной <alexp239.14 at gmail.com>:

> В результате работы были найдены следующие быстрые алгоритмы:
> 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/20180419/101d9c42/attachment.html>