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

[Vladislav Ivanishin]

Добрый день, да!

Александр Портной <alexp239.14 at gmail.com> writes:

> Добрый день!
>
> Отчёт засчитан?
>
> пн, 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 раза, в итоговую таблицу попал усредненный
>> результат.
>>
>> --
>> С уважением,
>> Александр Портной.
>>

-- 
Влад