Preview

Информатика и образование

Расширенный поиск
Доступ открыт Открытый доступ  Доступ закрыт Только для подписчиков

РАЗРАБОТКА ТЕСТОВЫХ ПРИМЕРОВ ДЛЯ АВТОМАТИЧЕСКОЙ ПРОВЕРКИ РЕШЕНИЙ ЗАДАЧ В УЧЕБНЫХ КУРСАХ И СОРЕВНОВАНИЯХ ПО ПРОГРАММИРОВАНИЮ

Полный текст:

Аннотация

При автоматическом тестировании программ, решающих различные задачи теории потоков, использование тестовых примеров, построенных почти полностью случайно, не позволяет корректно оценить асимптотическую сложность реализованного алгоритма. Время работы большинства алгоритмов поиска потока на таких тестах будет существенно ниже верхней асимптотической оценки, а для продвинутых алгоритмов и вовсе будет расти линейно или почти линейно. В данной работе рассматривается построение тестовых примеров, на которых время работы наиболее распространенной реализации алгоритма Форда-Фалкерсона будет экспоненциально зависеть от размера теста.

Об авторе

Г. О. Евстропов
Национальный исследовательский университет «Высшая школа экономики»
Россия


Список литературы

1. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ. 2-е изд. / пер. с англ. М.: Вильямс, 2009.

2. Dean B. C., Goemans M. X., Immorlica N. Finite termination of “augmenting path” algorithms in the presence of irrational problem data // Algorithms - ESA 2006. Azar Y., Erlebach T. (eds). Lecture Notes in Computer Science. 2006. V. 4168. Berlin, Heidelberg: Springer, 2006.

3. Dinitz Ye. Algorithm for solution of a problem of maximum flow in a network with power estimation // Doklady Akademii nauk SSSR. 1970. № 11.

4. Edmonds J., Karp R. M. Theoretical improvements in algorithmic efficiency for network flow problems // Journal of the ACM. Association for Computing Machinery. 1972. № 19 (2). doi:10.1145/321694.321699.

5. Ford L. R., Fulkerson D. R. Maximal flow through a network // Canadian Journal of Mathematics. 1956. № 8. doi:10.4153/CJM-1956-045-5.

6. Orlin J. B. Max flows in O(nm) Time, or better // STOC ‘13 Proceedings of the forty-fifth annual ACM symposium on Theory of computing (Palo Alto, California, USA - June 01-04, 2013). New York, USA: ACM, 2013.


Для цитирования:


Евстропов Г.О. РАЗРАБОТКА ТЕСТОВЫХ ПРИМЕРОВ ДЛЯ АВТОМАТИЧЕСКОЙ ПРОВЕРКИ РЕШЕНИЙ ЗАДАЧ В УЧЕБНЫХ КУРСАХ И СОРЕВНОВАНИЯХ ПО ПРОГРАММИРОВАНИЮ. Информатика и образование. 2017;(8):44-47.

For citation:


Evstropov G.O. CREATING TEST EXAMPLES FOR AUTOMATIC CHECKING THE SOLUTIONS OF TASKS IN TRAINING COURSES AND COMPETITIONS IN PROGRAMMING. Informatics and education. 2017;(8):44-47. (In Russ.)

Просмотров: 3


ISSN 0234-0453 (Print)
ISSN 2658-7769 (Online)