<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.3 20210610//EN" "JATS-journalpublishing1-3.dtd">
<article article-type="research-article" dtd-version="1.3" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xml:lang="ru"><front><journal-meta><journal-id journal-id-type="publisher-id">infojournal</journal-id><journal-title-group><journal-title xml:lang="ru">Информатика и образование</journal-title><trans-title-group xml:lang="en"><trans-title>Informatics and education</trans-title></trans-title-group></journal-title-group><issn pub-type="ppub">0234-0453</issn><issn pub-type="epub">2658-7769</issn><publisher><publisher-name>Publishing House Education and Informatics</publisher-name></publisher></journal-meta><article-meta><article-id custom-type="elpub" pub-id-type="custom">infojournal-220</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="ru"><subject>ПЕДАГОГИЧЕСКИЙ ОПЫТ</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="en"><subject>PEDAGOGICAL EXPERIENCE</subject></subj-group></article-categories><title-group><article-title>РАЗРАБОТКА ТЕСТОВЫХ ПРИМЕРОВ ДЛЯ АВТОМАТИЧЕСКОЙ ПРОВЕРКИ РЕШЕНИЙ ЗАДАЧ В УЧЕБНЫХ КУРСАХ И СОРЕВНОВАНИЯХ ПО ПРОГРАММИРОВАНИЮ</article-title><trans-title-group xml:lang="en"><trans-title>CREATING TEST EXAMPLES FOR AUTOMATIC CHECKING THE SOLUTIONS OF TASKS IN TRAINING COURSES AND COMPETITIONS IN PROGRAMMING</trans-title></trans-title-group></title-group><contrib-group><contrib contrib-type="author" corresp="yes"><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Евстропов</surname><given-names>Г. О.</given-names></name><name name-style="western" xml:lang="en"><surname>Evstropov</surname><given-names>G. O.</given-names></name></name-alternatives><bio xml:lang="en"><p>gevstropov@hse.ru</p></bio><email xlink:type="simple">glebshp@yandex.ru</email><xref ref-type="aff" rid="aff-1"/></contrib></contrib-group><aff-alternatives id="aff-1"><aff xml:lang="ru">Национальный исследовательский университет «Высшая школа экономики»<country>Россия</country></aff><aff xml:lang="en">National Research University High School of Economics<country>Russian Federation</country></aff></aff-alternatives><pub-date pub-type="collection"><year>2017</year></pub-date><pub-date pub-type="epub"><day>08</day><month>10</month><year>2018</year></pub-date><volume>0</volume><issue>8</issue><fpage>44</fpage><lpage>47</lpage><permissions><copyright-statement>Copyright &amp;#x00A9; Евстропов Г.О., 2018</copyright-statement><copyright-year>2018</copyright-year><copyright-holder xml:lang="ru">Евстропов Г.О.</copyright-holder><copyright-holder xml:lang="en">Evstropov G.O.</copyright-holder><license license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>This work is licensed under a Creative Commons Attribution 4.0 License.</license-p></license></permissions><self-uri xlink:href="https://info.infojournal.ru/jour/article/view/220">https://info.infojournal.ru/jour/article/view/220</self-uri><abstract><p>При автоматическом тестировании программ, решающих различные задачи теории потоков, использование тестовых примеров, построенных почти полностью случайно, не позволяет корректно оценить асимптотическую сложность реализованного алгоритма. Время работы большинства алгоритмов поиска потока на таких тестах будет существенно ниже верхней асимптотической оценки, а для продвинутых алгоритмов и вовсе будет расти линейно или почти линейно. В данной работе рассматривается построение тестовых примеров, на которых время работы наиболее распространенной реализации алгоритма Форда-Фалкерсона будет экспоненциально зависеть от размера теста.</p></abstract><trans-abstract xml:lang="en"><p>We consider automated testing (without manual code inspection) for problems that require implementation of flow algorithms. If only graphs that were generated almost at random are used, it is impossible to estimate whether the implemented algorithm has right complexity or not. For almost all algorithms real running time on such test cases will grow significantly below theoretical bounds, while for advanced algorithms it might even grow quasilinear. In this work we consider how to build a test cases that will force popular implementation of Ford—Fulkerson algorithm match the expected complexity with running time depending exponentially from the size of the test.</p></trans-abstract><kwd-group xml:lang="ru"><kwd>теория потоков</kwd><kwd>стоимостные потоки</kwd><kwd>автоматическое тестирование</kwd><kwd>соревнования по программированию</kwd></kwd-group><kwd-group xml:lang="en"><kwd>flow theory</kwd><kwd>cost flows</kwd><kwd>automated testing</kwd><kwd>programming competitions</kwd></kwd-group></article-meta></front><back><ref-list><title>References</title><ref id="cit1"><label>1</label><citation-alternatives><mixed-citation xml:lang="ru">Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ. 2-е изд. / пер. с англ. М.: Вильямс, 2009.</mixed-citation><mixed-citation xml:lang="en">Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ. 2-е изд. / пер. с англ. М.: Вильямс, 2009.</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">Dinitz Ye. Algorithm for solution of a problem of maximum flow in a network with power estimation // Doklady Akademii nauk SSSR. 1970. № 11.</mixed-citation><mixed-citation xml:lang="en">Dinitz Ye. Algorithm for solution of a problem of maximum flow in a network with power estimation // Doklady Akademii nauk SSSR. 1970. № 11.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref><ref id="cit5"><label>5</label><citation-alternatives><mixed-citation xml:lang="ru">Ford L. R., Fulkerson D. R. Maximal flow through a network // Canadian Journal of Mathematics. 1956. № 8. doi:10.4153/CJM-1956-045-5.</mixed-citation><mixed-citation xml:lang="en">Ford L. R., Fulkerson D. R. Maximal flow through a network // Canadian Journal of Mathematics. 1956. № 8. doi:10.4153/CJM-1956-045-5.</mixed-citation></citation-alternatives></ref><ref id="cit6"><label>6</label><citation-alternatives><mixed-citation xml:lang="ru">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.</mixed-citation><mixed-citation xml:lang="en">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.</mixed-citation></citation-alternatives></ref></ref-list><fn-group><fn fn-type="conflict"><p>The authors declare that there are no conflicts of interest present.</p></fn></fn-group></back></article>
