moglobi.ru Другие Правовые Компьютерные Экономические Астрономические Географические Про туризм Биологические Исторические Медицинские Математические Физические Философские Химические Литературные Бухгалтерские Спортивные Психологичексиедобавить свой файл
страница 1

Клуб творчества программистов


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

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

Некоторые из задач этих книг не являются абсолютно оригинальными. Так, к примеру, история задачи о 8 ферзях или задачи о поиске фальшивой монеты превышает две сотни лет. Тем не менее, в этом выпуске сборника олимпиадных задач по программированию мы указываем авторов, предложивших эти задачи, учитывая их несомненные заслуги в разработке эталонного алгоритма решения и набора, состоящего, как правило, из 10 тестов с ответами, что также не всегда достаточно просто.

В отличие от первой книги в этой не только значительно больше задач, но они и более разнообразны. Среди составителей задач для тренировок и соревнований появились имена студентов: Р.Сошкина, А.Смолия, Д.Власова и др. и даже учащихся школ г.Петрозаводска. И это, несомненно, хороший признак качественного роста мастерства и интересов участников олимпиад.

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

Одна из проблем, которая также достанется грядущему веку, - качественная подготовка программистов. Известно, насколько ценятся российские, самые изворотливые в мире программисты (компенсация за сочетание неуемного полета фантазии и не успевающую за ним вычислительную технику). Однако! Речь здесь идет о лучших представителях этой профессии, с обласканных зарубежными фирмами и их представительствами в России, но не всегда о массовых, рядовых тружениках дисплея и клавиатуры. На предприятиях, в организациях, ведомствах тысячи педагогов, инженеров, и просто замечательных людей успешно трудятся в качестве программистов, операторов, инженеров вычислительной техники. Известен случай, когда в коллективе отдела АСУ, почти из сотни человек, был всего лишь один с образованием математика - педагога, остальные работали совсем без- или не по образованию. Можно ответить: "Ну и что? Люди справляются с работой. А практика лучше любого университета". Действительно: и работают, и справляются. Вопрос лишь в том, что степень подготовки персонала определяет качество и уровень задач управления. Кроме того, в зависимости от квалификации в десятки раз меняется производительность программиста или прикладного математика - такова специфика его труда. А стратегические просчеты при выборе средств автоматизации для крупных предприятий оборачиваются потерями миллионов "у.е.".

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

Азарт, увлеченность, радость открытия - неотъемлемые свойства молодости. И как замечательно, если эти качества реализуются в форме интеллектуального развития личности! Именно этому служат командные олимпиады по программированию для студентов и школьников Петрозаводска которые проводит ПетрГУ.

Чем же характерны олимпиадные задачи по программированию? Чаще всего такие задачи - изящные программистские этюды и не имеют прямого прикладного значения. Надо ли решать подобные задачи? Безусловно - да. Собранные в сборнике задачи составлены в течение последних трех лет для организации олимпиад по программированию среди школьников и студентов Петрозаводска. Условно их можно разбить на две группы: задачи, путь решения которых, с первого взгляда, не виден и задачи, за решение которых может взяться любой человек, изучивший какой-либо из языков программирования и хорошо усвоивший школьный курс математики. Решение задач первой из этих групп открывает путь к принципиально новым средствам моделирования, построения или реализации алгоритмов, структурам данных, применение которых быстро приводит к поставленной цели. А это - инструментарий программиста высокого уровня, дающий возможность просто и эффективно выполнить непосильную для других трудную и практически значимую работу.

Хотя соревнования и считаются командными олимпиадами по программированию, эти от их участников требуются не только глубокие знания, но и серьезные навыки использования довольно сложного математического аппарата. Среди олимпиадных задач соревнований высокого уровня (четверть-, полуфинал командного чемпионата Мира можно встретить задачи, связанные такими науками как линейная и целочисленная оптимизация, теория игр, геометрическое программирование, теория формальных грамматик и автоматов, сложные, порою проблемные задачи, на решение которых отводятся считанные часы. Попробуйте запрограммировать алгоритм симплекного или "венгерского" метода, поиск наибольшего парросочетания сортировку пирамидой за несколько минут! Но, что самое удивительное, участники справляются с подобными задачами, иногда, даже не располагая специальными знаниями, за счет стремления к победе и интуиции.

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

Еще одно соображение. Вполне возможна ситуация, когда два программиста, сидящих за соседними столами, за одинаковое время способны выполнить объем работы, различающийся в несколько десятков раз. За которым из этих столов хотели бы сидеть Вы? Главное требование олимпиады - все делать быстро, надежно и эффективно. Научиться этому невозможно без большой самостоятельной работы (в программировании, как и в математике, нет царского пути).

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

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

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

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



Командные олимпиады по программированию в Петрозаводске
(недолгая современная история)


Командные чемпионаты мира по программированию среди сборных команд высших учебных заведений (ACM International Collegiate Programmind Contest) проводятся международной организацией ACM (Association for Computing Machinery) начиная с 1977 года.

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

Ежегодно в феврале-марте АСМ проводит так называемую компьютерную неделю, в программу которой входят флагманские конференции по основным направлениям информатики, встречи молодых программистов с работодателями, и множество других мероприятий. Одним из главных событий является финал командного чемпионата мира по программированию, победители которого награждаются вместе с лауреатами различных премий на традиционном торжественном банкете.

В первые годы в соревнованиях участвовали только команды американских ВУЗов, а весь остальной мир был представлен одной европейской региональной группой. С 1990 года, в связи с распространением персональных компьютеров, интерес к ним сильно возрастает и все новые и новые региональные группы не только появляются, но все увереннее начинают занимать места в верхней части итоговой таблицы.

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

Впервые о чемпионате мира по программированию российские ВУЗы узнали только в 1993 году, когда образовался новый Восточно-Европейский регион и его директорат направил приглашения в несколько крупнейших российских университетов. На соревнования в Вену поехала только одна команда Санкт-Петербургского госуниверситета, первые годы россиян ждала неудача.

Проанализировав результаты выступления российских команд, петербургские педагоги и ученые В.Г.Парфенов, А.А.Суханов и другие пришли к выводу о необходимости проведения в Санкт-Петербурге городских командных школьных и студенческих олимпиад по правилам АСМ, которые в 1996 году перешли в категорию региональных полуфинальных соревнований.

Именно тогда в них приняли участие и студенты Петрозаводского госуниверситета. Хотя мы довольно смутно представляли себе, как будут проходить соревнования, команда старшекурсников в составе А.Шабаева, Д.Корзуна, В.Прудевуса готовилась к ним достаточно серьезно. Принцип отбора был несложен - команду собрали из студентов, в школьные годы отличавшихся на олимпиадах по математике. Чтобы набирались опыта, на всякий случай прихватили команду младшекурсников в составе А.Гуртова, А.Теппонена и А.Стояновского.

Необычно было все: замечательный Санкт-Петербургский Дворец творчества детей и юношества на Фонтанке, встреча с десятками команд - участников, представителей множества городов России, азарт и атмосфера соревнований. Сюрприз ожидал в самом начале. Во время пробного тура была предложена довольно простая задача, в течение 8 минут решенная одной из команд МГУ. Второкурсникам университета для решения этой задачи потребовались все 2 часа, основной состав с задачей вообще не справился... Не так то просто решать олимпиадные задачи. Сказывались волнение, нехватка времени, отсутствие навыков и опыта быстрой работы, четкого распределения обязанностей внутри команды.

В итоге убедительную победу одержали хозяева соревнований, команда А.Гуртова получила почетный диплом третей степени и право выступать на полуфинале мира в следующем году. Результат парадоксальный, тем более, что подготовка первой команды была совсем неплохой, уже через час по окончанию соревнований задачи казались совсем простыми, а участники команды вовсе не лишены бойцовских качеств (в тот же год А.Шабаев и В.Прудевус блестяще выступили на студенческой олимпиаде по математике). Прошло немного времени и Д.Корзун стал неизменным организатором олимпиад и составителем чудесных задач по программированию, в чем с легкостью может удостовериться читатель этой книги.

Стало очевидно, что успеха не будет без проведения аналогичных соревнований в Петрозаводске. Один из тренеров сборной, преподаватель кафедры прикладной математики, Д.Подкопаев не без труда, с помощью неизменных организаторов соревнований профессоров В.Г.Парфенова и И.В.Романовского раздобыл программное обеспечение, необходимое для организации олимпиад и уже через год состоялись первые соревнования ПетрГУ.

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

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

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

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

Однако, вернемся к летописи олимпиад. Команда А.Гуртова представляла Петрозаводск и в последующие годы, ее состав незначительно менялся. В 1998 году в ПетрГУ появляются новые лидеры: команды "СЕМъ" (название составлено из имен участников: С.Резанова, Е.Филатова и М.Ким, а твердый знак - девиз стремления к победе). В 1999 году, одна из команд, имея шанс победить, уступила на отборочных соревнованиях чемпионата Мира лишь командам двух Санкт-Петербургских университетов: государственного и точной механики и оптики. О том, насколько серьезными были наши конкуренты, свидетельствуют 1 и 2 места этих команд в финале чемпионата Мира.

Успехи сборной ПетрГУ вовсе не случайны. В основе их - продолжительный и кропотливый труд, тысячи решенных задач. Команда "СЕМъ" больше не выступает в прежнем составе за честь Карелии. По правилам соревнований, их участником может быть только один студент 5 курса. Однако талант и опыт ребят нашли достойное применение, они активно занимаются организационной и тренерской работой, подготовкой других спортсменов-программистов.

Соревнования и подготовка к ним во многом объединила интересы ребят, сплотила их в дружный коллектив - Клуб творчества программистов (председатель - ректор ПетрГУ Васильев В.Н.). Кроме разбора задач, занятий и организации соревнований на счету у студентов немало больших и полезных дел: создание тренировочного сервера (А.Стояновский, Д.Подкопаев, М.Ким) и рейтинг-системы программистов (А.Алешина, С.Резанов, В.Сухов), проведение чемпионата по программированию игр (победители - О.Пономарев, и команда в составе М.Афанасьева, С.Анисимова и С. Егоренкова), летние сборы в замечательном загородном учебном центре "Урозеро". Участниками клуба составлены сотни олимпиадных задач (часть из них - в этом сборнике), проведены десятки олимпиад.



Ребятам приятно видеть внимание ведущих в Карелии компьютерных фирм, чувствовать востребованность своего труда и знаний. Да и для республики крайне важна забота о будущем талантливых и трудолюбивых учащихся, потребность не растерять свой, уже получивший признание в столичных городах интеллектуальный потенциал. Работа в Москве находит наших олимпиадников, порой даже не позволяя им закончить учебу в университете.

Таковы первые станицы летописи истории олимпиад в Петрозаводске. Главные дела, конечно, впереди.
страница 1
скачать файл


Смотрите также: