Антиплагиат (1231606), страница 2
Текст из файла (страница 2)
Действительно, круг изнесколькихдесятков одаренных молодых людей, реально претендующих на победу в мировом первенстве, и их тренеров весьмаузок, математико-программистское содержание состязаний понятно достаточно ограниченному числу специалистови педагогов высшей квалификации.Однако, результаты этих интеллектуальных игр мировойпрограммисткой элиты представляет интерес уже длягораздо более широких кругов, поскольку процесс формирования и подготовки команд опирается на всюобразовательную, научную, промышленную и культурную инфраструктуру данной страны. Эти результаты достаточноточноотражаютмеждународноераспределениемировогокомпьютерногоинтеллектуальногопотенциалапоразличным странам и позволяют оценить способность нации не только использовать разработанные в других странахкомпьютерные технологии, но и вносить свой вклад в их создание.[8]Проведение соревнований по программированию играет немалую роль при подготовке спец иалистов сферыинформац ионных технологий.
Подведение итогов подобных соревнований происходит по определенным правилам, и,зачастую, на награж дении используются стороннее от системы проведения соревнований программное обеспечение.Целью выпускной квалификац ионной работы является проектирование и разработка системы для проведения соревнованийпо программированию с модулем подведения итогов.В соответствии с указанной ц елью поставлены следующ ие задачи:– изучить предметную область: правила проведения и подведения итогов соревнований по программированию;– произвести анализ сущ ествующ их систем для проведения соревнований по программированию;– произвести анализ сущ ествующ их модулей подведения итогов, анализ способов и средств их реализац ии;– выполнить проектирование системы для проведения соревнований по программированию с модулем подведения итогов;– разработать спроектированную систему.Разработанная система будет внедрена и начнёт использоваться в подготовке студентов, проходящ их обучение на кафедреВычислительная техника и компьютерная графикаДальневосточного государственного университета путей сообщения.1[55]Обзор предметной областиСистемы для проведения соревнований по программированию могут автоматизировать проц есс подготовки студентов ксамим соревнованиям по программированию, а так ж е развить их навыки программирования в ц елом.1.1 Соревнования по программированиюМож но выделить следующ ие регулярные мировые соревнования по программированию [1]:– командный чемпионат АСМ ICPC, проводимый компанией IM [2];– командный чемпионат VK Cup [3];– чемпионат Facebook Hacker Cup [4];– чемпионатGoogle Code Jam [5];– чемпионат Russian Code Cup,[30]проводимый компанией Mail.ru Group [6];– чемпионат Алгоритм, проводимый компанией Яндекс [7].Самым престиж ным и развитым является командный чемпионат АСМ ICPC, в то время как остальные мировые соревнованияпроводятся по большей части в онлайн реж име.1.1.1 Командный чемпионат по программированию АСМ ICPCКомандные чемпионаты мира по программированию (International Collegiate Programming Contest) среди сборных командвысших учебных заведений проводятся с 1977 г.
под э гидой меж дународной организац ией Association for ComputingMachinery (ACM), которая была основана в 1947 г.сотрудниками Пенсильванского университета, создавшим первый в мире компьютер ENIAC [2].Схемаорганизациичемпионатавключаетдваэтапа:региональныйифинальный.Команды-победительницырегиональных групп выходят в финал и разыгрывают звания чемпионов мира, Европы, Азии и других континентов.Впервые о чемпионате мира российские вузы узнали осенью 1996 г., когда был образован новый ВосточноЕвропейский регион. За более чем двадцатилетнюю историю[8]полуфинала чемпионата мира в России, российские команды достойно выступали в финалах. Например, российские командыhttp://dvgups.antiplagiat.ru/ReportPage.aspx?docId=427.24091261&repNumb=15/2420.06.2016АнтиплагиатСанкт-Петербургского государственного университета информационных технологий, механики и оптики[8]занимали первое место в финалах в 2004, 2008, 2009, 2012, 2013, 2015 годах.1.1.2 Правила командных чемпионатовЗа почти сорокалетнююисторию состязаний сформировались международные правила [8] этих соревнований, в соответствии с которымикоманде, состоящей из трех участников, предоставляется один компьютер и предлагается в течение 5 часов решитьмаксимальное число из предложенных задач.
Количество задач обычно варьируется от 8 до 15. Побеждает команда,решившая наибольшее число задач, а в случае равенства числа решенных задач – команда, затратившая меньшевремени.[8]Время,затраченное на решение задач – это время в минутах, прошедшее с начала соревнований до посылкипервой принятой попытки для этой задачи плюс заданное количество штрафных минут за каждую неудачную попыткудля этой задачи. Время, затраченное на нерешенную задачу, равно нулю.
Общее время равно сумме времен,затраченных на решение всех задач.[21]Решением является программа на одном из предлож енных языков программирования.Тестирование производится автоматически по ходу соревнований в[21]спец иальной тестирующ ей системе на заранее подготовленном наборе тестов для каж дой задачи. Решения задач,посланные ж юри, называются попытками.Каждая попытка может быть принята или отвергнута. Попытка считается принятой, если программа выдает верныерезультаты и[21]укладывается в ограничения на всех тестах.В различных соревнованиях правила могут немного отличаться от описанных. Например, в соревнованиях Google Code Jam иFacebook Hacker Cup тестирование программ происходит на компьютере участника, после чего он отсылает результаты исвою программу ж юри.1.1.3 Подведение итогов соревнований по программированиюСистемы для проведения соревнований по программированию позволяют получать результаты тестирования решенийучастников в течение нескольких минут после их отправления.
Все участники и зрители в реальном времени могутнаблюдать за тем, какое количество задач решила каж дая команда посредством таблиц ы результатов. Такой форматпроведения соревнований исключает какую-либо интригу относительно победителя, так как он известен сразу по окончаниисоревнования.Для сохранения интриги, в соответствии с правилами, таблиц а результатов замораж ивается за час до конц а соревнования[9].
Так называемая «разморозка» таблиц ы происходит лишь на ц еремонии награж дения по определённому алгоритму.Вместо того чтобы просто показать участникам финальную таблиц у, её «размораж ивают» последовательно снизу вверх. Вслучае, если команда в последний час имела успешные посылки, она поднимается вверх по таблиц е, что увеличивает еёшансы на победу. Иначе, если удачных посылок у команды не осталось – она приглашается на сц ену для награж дения.В настоящ ее время сущ ествует множ ество модулей, позволяющ их «разморозить» таблиц у результатов, но все онифункц ионируют отдельно от систем для проведения соревнований. Такие модули не имеют открытого распространения,поэ тому слож но рассматривать способы их реализац ии.
Часто мож но встретить два способа реализац ии модуля подведенияитогов: в виде web-страниц ы и в виде исполняемого файла. Первый вид реализац ии является более универсальным, так какмож ет быть запущ ен с различных платформ, в отличие от исполняемого файла, который, скорее всего, будет привязан кконкретной операц ионной системе. Более того, web-страниц а не потребует установки, а будет иметь открытый доступчерез интернет.Исходя из э того, следует рассмотреть средства и технологии для разработки web-сайтов и определиться с требованиями,предъявляемыми к модулю подведения итогов.1.2 Обзор сущ ествующ их систем для проведения соревнований по программированиюНа данный момент сущ ествует множ ество систем для проведения соревнований по программированию:– системы Codeforces и Polygon;– системы РС2 и PCMS2;– система Timus Online Judge;– система Ejudge;– система Contester.Так ж е своими системами с автоматизированной проверкой решений обладают компании Facebook, Google и Яндекс, но обэ тих системах мало что известно.1.2.1 Системы Codeforces и PolygonCodeforces – сайт для проведения соревнований по программированию разработанный Михаилом Мирзаяновым в 2010 г.
приподдерж ке Саратовского государственного университета [10].Polygon – система для автоматизированной подготовки задач олимпиадного программировании, так ж е разработаннаяМихаилом Мирзаяновым [11]. Данная система напрямую связана с системой Codeforces: после того, как задача прошлаполную подготовку в Polygon – её мож но добавить в Codeforces.За пятилетнюю историю на базе Codeforces было проведено множ ество соревнований:– более 300-х регулярных раундов;– чемпионат Яндекс Алгоритм;http://dvgups.antiplagiat.ru/ReportPage.aspx?docId=427.24091261&repNumb=16/2420.06.2016Антиплагиат– чемпионат Russian Code Cup;– чемпионат АУУ Сир;– чемпионат КРОК;– чемпионат VK Cup;– множ ество тренировок, созданных на основе задач различных соревнований, который проводились не в рамкахCodeforces.Системы Codeforces и Poligon не имеют свободного распространения.1.2.2 Системы РС2 и PCMS2Системы РС2 и PCMS2 используются для проведения самых популярных соревнований по программированию – АСМ ICPC [12].Первая система используется на полуфинале и некоторых четвертьфиналах NEERC, в то время, как вторая системаиспользуется на финале.Система РС2 написана в Калифорнийском Государственном Университете, город Сакраменто, по гранту IM.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
