Чемпионаты мира по программированию (стр. 1 из 3)

Санкт-Петербургский государственный университет Информационных Технологий, Механики и Оптики

РЕФЕРАТ

ТЕМА

ЧЕМПИОНАТЫ МИРА ПО ПРОГРАММИРОВАНИЮ

ВЫПОЛНИЛ

НИКИТИН ДМИТРИЙ АЛЕКСАНДРОВИЧ

1 КУРС ГРУППА 1508

ФАКУЛЬТЕТ ИТиП

Санкт-Петербург 2008год

Введение

Командный чемпионат мира по программированию проводится начиная с 1977 года. Основными участниками чемпионатов мира являются сборные команды высших учебных заведений различных регионов мира.

В первые годы в соревнованиях участвовали в основном команды северо-американских вузов, а весь остальной мир был представлен одной европейской региональной группой. Однако, начиная с 1990 года, в связи с сильным ускорением распространения персональных компьютеров резко возрастает международный интерес к этим соревнованиям, и буквально каждый год начинают появляться новые региональные группы. Постепенно европейские, австралийские и новозеландские команды начинают занимать места в верхней части итоговой таблицы. Наконец, в 1995 году сенсационную победу в мировом чемпионате одерживает команда университета Альберта Людвига из немецкого города Фрайбурга - впервые европейская команда становится чемпионом мира. Однако, в следующем сезоне американцы берут реванш - чемпионом мира становится команда калифорнийского университета Беркли, второе место занимает команда Гарвардского университета, а лучшая из европейских команд - команда Софийского университета - остается на четвертом месте.

С 1996 года в списке участников чемпионата мира по программированию появляются страны нового Северо-Восточного Европейского региона (NEERC - NortheasternEuropeanRegionProgrammingContest), прежде всего - Россия, Белоруссия, страны Прибалтики, Кавказа, Средней Азии и Казахстана.

чемпионат мир программирование тренер

ГЛАВА IОРГАНИЗАТОРЫ ПРОВЕДЕНИЯ ЧЕМПИОНАТОВ МИРА ПО ПРОГРАММИРОВАНИЮ. ПОРЯДОК ПРОВЕДЕНИЯ ЧЕМПИОНАТОВ

Организатором первого чемпионата мира по программированию была Международная организация Association for Computing Machinery (ACM International Collegiate Programming Contest) АСМ, наряду с IEEE Computer Society и British Computer Society входит в тройку наиболее авторитетных ассоциаций ИТ-профессионалов в мире. Генеральным спонсором чемпионатов мира 1990 — 1993 гг. была корпорация AT&T, 1994 — 1997 гг. Microsoft, 1998 — 2004 гг. — IBM.

Международная организация Association for Computing Machinery (ACM) была основана в 1947 г. в Филадельфии сотрудниками Пенсильванского университета, создавшими первый в мире компьютер ENIAC. В настоящее время АСМ является наиболее авторитетной в мире международной организацией в области компьютеров, объединяющей более 80000 своих членов - ученых, инженеров, программистов, студентов - всех специалистов, занимающихся проблемами огромного современного компьютерного мира. Поле деятельности АСМ весьма широко - АСМ проводит конференции, издает журналы и книги, присуждает ежегодные премии за достижения в области теоретической информатики и компьютерных технологий и, в частности, знаменитую АСМ Annual Meeting Turning Award, называемую нобелевской премией в области компьютеров.

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

Ежегодно в феврале - марте АСМ проводит так называемую компьютерную неделю АСМ (АСМ Computing Week). В программу АСМ Computing Week входят флагманские конференции АСМ по основным направлениям информатики, выставки, демонстрации, встречи молодых программистов с предполагаемыми работодателями, различные специальные мероприятия и т.д. Одним из главных событий компьютерной недели является финал командного чемпионата мира по программированию (the ACM International Collegiate Programming Contest - ACM/ICPC), победители которого награждаются вместе с лауреатами различных научных премий на традиционном ежегодном торжественном банкете АСМ.

За более чем двадцатилетнюю историю состязаний сформировались международные правила этих соревнований, в соответствии с которыми команде, состоящей из трех участников, предоставляется один компьютер и предлагается в течение 5 часов решить максимальное число из предложенных задач. Количество задач обычно лежит в диапазоне от 6 до 10. Побеждает команда, решившая наибольшее число из предложенных задач, а в случае равенства числа решенных задач - команда, затратившая меньше времени. Характер традиционно предлагаемых на соревнованиях задач предполагает, что участники продемонстрируют свое мастерство как в искусстве компьютерной алгоритмизации задач, так и в составлении эффективных программ, реализующих выбранные для решения алгоритмы.

Это огромное мероприятие, охватывающее практически все регионы мира, в котором в настоящее время участвует более 3000 команд более 1450 университетов 75 стран мира. Поэтому мир разбит на много зон и регионов, а чемпионат проводится в три этапа.

Соревнования происходят так. Команда, состоящая из трех человек, получает конверт с головоломными заданиями (от восьми до двенадцати), компьютер (на котором ничего, кроме трансляторов и элементарных средств отладки для языков программирования С, С++ и Java, не установлено) и пять часов времени. Цель состоит в том, чтобы, во-первых, решить как можно больше задач. При равенстве числа решенных задач в зачет идет время решения и количество неудачных попыток сдать задание. Подробные правила довольно сложны, их описание занимает несколько страниц.

Как правило, для решения турнирных заданий используется свободно распространяемое программное обеспечение - то, что сообща разрабатывается мировым программистским сообществом.

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

Схема проведения чемпионата мира по программированию включает три этапа: четвертьфиналы (зональный), полуфиналы (региональный) и финалы. Команды-победительницы региональных групп (полуфиналов) выходят в финал и разыгрывают звания чемпионов мира и чемпионов разных регионов — Европы, Северной Америки, Азии, Латинской Америки, Тихоокеанского региона, Африки и Ближнего Востока.

Чемпионат проходит в три этапа: четвертьфинал, полуфинал и финал. В четвертьфинальных соревнованиях этого года приняли участие 6700 команд из 1821 университета 83 стран мира. При этом Северо-Восточный Европейский регион, в который входят страны бывшего СССР (кроме Украины), является самым крупным по числу участников среди всех 36 регионов мира. В этом году в четвертьфинальных соревнованиях региона приняло участие 699 команд, из них 196 вышли в полуфинал, в рамках которого проходит также студенческий командный чемпионат России.

Столь большое число участников соревнований привело организаторов чемпионата мира 2008 года к необходимости пригласить на финал 12 команд-победителей полуфинальных соревнований от нашего региона (не более чем по одной команде от университета), из которых 11 представляют Россию: Санкт-Петербургский государственный университет информационных технологий, механики и оптики (СПбГУ ИТМО, чемпион России 2007/2008 учебного года), Ижевский государственный технический университет (ИжГТУ), Ставропольский государственный университет, Петрозаводский государственный университет (ПетрГУ), Санкт-Петербургский государственный университет (СПбГУ), Московский государственный университет (МГУ), Орловский государственный технический университет, Уральский государственный университет, Московский физико-технический институт (государственный университет), Новосибирский государственный университет, Алтайский государственный университет.

Как это происходит?

Традиционно ACM ICPC представляет собой двухуровневый чемпионат среди студенческих команд, представляющих свои университеты и другие высшие учебные заведения. С октября по декабрь команды встречаются в региональных соревнованиях (полуфиналах) по всему миру. Затем, обычно в марте, победители всех региональных полуфиналов съезжаются на финал чемпионата мира ACM International Collegiate Programming Contest. Исключение составляют несколько регионов, в том числе регион Северо-Восточной Европы (Northeastern European Region Contest, NEERC), куда входит Россия и все государства бывшего Советского Союза, кроме Украины и Молдавии.

Соревнования полуфинала региона Северо-Восточной Европы проходят одновременно в трех городах. Основные – в Санкт-Петербурге на базе Санкт-Петербургского института точной механики и оптики. Сибирская группа (для команд из Сибири и с Дальнего Востока) – в Барнауле на базе Алтайского государственного технического университета. И созданная в 2000 году Транскавказская группа – в Тбилиси на базе Грузинского технического университета.