Обобщение опыта по теме "Подготовка обучающихся к олимпиадам по информатике"

МУНИЦИПАЛЬНОЕ КАЗЕННОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА № 6

 

Подготовка обучающихся к олимпиадам по информатике.

ОБОБЩЕНИЕ ПЕДАГОГИЧЕСКОГО ОПЫТА ПО ТЕМЕ  САМООБРАЗОВАНИЯ

Прядкина Вера Николаевна,

учитель информатики и ИКТ

МКОУ СОШ № 6

г. Бирюсинска,  Иркутская область

г. Бирюсинск

2015

Научиться можно только тому, что любишь.
Гёте И.

Образование – это индустрия, направленная в будущее.

С. П. Капица

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

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

Важную роль в подготовке играют олимпиадные задачи. Они должны быть такими, чтобы как можно больше раскрыть творческий потенциал ребенка во время соревнований и помочь ему развивать свои способности в процессе подготовки к олимпиадам. Кроме того, баланс составляющих олимпиадной задачи должен учитывать возрастные особенности ребенка, определяющие зону ближайшего развития и горизонт развития школьника. Этим требованиям в полной мере удовлетворяют многоуровневые олимпиадные задачи, которые составлены таким образом, чтобы в процессе их решения каждый школьник смог сделать для себя небольшое открытие и в полной мере раскрыть имеющийся у него творческий потенциал, независимо от класса обучения и уровня подготовки. В настоящее время большинство олимпиадных задач не только регионального и заключительного этапов Всероссийской олимпиады школьников (ВсОШ) по информатике, но и МОИ, строятся именно по такому принципу. Поскольку олимпиадные задачи по информатике носят не традиционный характер, то и методика их проверки и оценивания также существенно отличается от методик, которые часто используются на олимпиадах по другим предметам. Проверка решений участников осуществляется с использованием комплекта тестов, и они разрабатываются таким образом, чтобы можно было в максимальной степени оценить все возможные типы алгоритмов, которые могут быть использованы в решениях участников, и продифференцировать полученные участниками решения по степени их сложности, корректности и эффективности. Существующая в настоящее время нормативная база ВсОШ и международных предметных олимпиад определяется Положением о всероссийской олимпиаде школьников и Порядком формирования сборных команд Российской Федерации для участия в международных олимпиадах по общеобразовательным предметам, утвержденными соответствующими приказами Минобрнауки России и зарегистрированными в Минюсте России. Понятно, что эти документы постоянно совершенствуются с учетом требований модернизации российского образования, и авторский коллектив данной работы принимает в этом непосредственное участие. Многие предложения, основанные на результата данной научно-практической работы, учтены в действующей в настоящее время редакции Положения о всероссийской олимпиаде школьников, что позволило существенно активизировать работу с одаренными школьниками в учреждениях образования и органах управления образованием различных уровней. Важной частью организационно-методического обеспечения Системы являются документы, устанавливающие форму проведения и требования к техническому обеспечению каждого этапа ВсОШ по информатике, принципы формирования комплекта олимпиадных заданий и подведения итогов соревнования, а также процедуры регистрации участников, проверки и оценивания выполненных олимпиадных заданий, разбора олимпиадных заданий с участниками и рассмотрения апелляций участников. Такими документами являются методические рекомендации по разработке заданий и требований к проведению школьного и муниципального этапов, а также требования к организации и проведению регионального и заключительного этапов ВсОШ. В настоящее время названные документы определяют лицо ВсОШ по информатике и используются при проведении всех этапов ВсОШ по информатике на территории Российской Федерации.

Система подготовки к всероссийской олимпиаде школьников по информатике В СРЕДЕ РАЗВИВАЮЩЕГО ОБУЧЕНИЯ

Рис 1. Модель репродуктивного обучения «Воспроизводство образцов с опорой на память»

 

Рис. 2.  Модель продуктивного обучения «Ступени развития»

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

Второе правило при работе с талантливыми детьми – методически поддержать их индивидуальную траекторию развития. Роль учителя и методик обучения такова: «Учитель – это наставник, он направляет деятельность ученика, помогая ей, где это необходимо, и оставляя ее действовать там, где она может действовать сама». Следует отметить, что это правило пока слабо реализовано во многих школах.

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

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

Использование зоны ближайшего развития при подготовке к олимпиадам по информатике позволяет в итоге достигать ближайшую границу развивающего обучения – порог сложности. Первыми шагами в проявлении таланта детьми можно считать преодоление порогов сложности. В сочетании с индивидуальным или в малых группах дополнительным обучением талантливых детей в зоне их познавательных интересов по методикам опережающего обучения формируется горизонт развития конкретного одаренного ребенка, который назван «умственным горизонтом» [4], как верхняя граница развивающего обучения в данный возрастной период.

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

Продвижение к индивидуальному горизонту развития с помощью наставника реализуется в полной мере при решении олимпиадных задач. Олимпиадные задачи в этом смысле являются опережающими заданиями, а сами олимпиады представляют собой пороги сложности для ученика. Несомненно, они составляют основу модели опережающего обучения, которую можно назвать «Горизонтом развития» (Рис. 3).

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

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

Рис. 3. Модель опережающего обучения «Горизонт развития»

В общем случае модель «Горизонт развития» в рамках ВсОШ по информатике должна реализовываться в среде опережающего обучения одаренных школьников в области информатики, которая представлена на рис. 4. Среда включает три неразрывно связанные между собой зоны обучения одаренных детей:

·               зону школьного курса информатики;

·               зону ближайшего развития по информатике (углубленное изучение информатики);

·               индивидуальный горизонт развития (олимпиада по информатике).

Все три зоны органично дополняют друг друга и доминируют по-разному на каждой ступени обучения [11].

Рис ниже. Среда опережающего обучения одаренных школьников в области информатики

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

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

Для учеников 7-9 классов доминирует зона ближайшего развития – факультатив по информатике для малых групп школьников (силами учителя информатики), дополняет его школьный курс информатики (возможно экстернат по информатике), а горизонтом развития является индивидуальная подготовка по задачам муниципального и регионального этапов олимпиады (силами регионального тренера из курирующего университета).

Достижением горизонта развития является диплом победителя муниципального и регионального этапов олимпиады.

Для учеников 9-11 классов доминирует горизонт развития, а дополняет его зона ближайшего развития: элективный курс по информатике и профильный школьный курс информатики (силами педагога информатики). Горизонтом развития является индивидуальная самоподготовка по задачам заключительного и международного этапов олимпиады при поддержке регионального тренера из курирующего вуза, а также обязательное регулярное участие в специализированных тренировочных сборах (силами всероссийских тренеров).

Достижением горизонта развития является диплом победителя заключительного этапа и высокие мотивация добиться права участия в международной олимпиаде и достигнуть там как можно более высокого результата.

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

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

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

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

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

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

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

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

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

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

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

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

Курс начинающего олимпиадника.

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

Список тем

 Тема 01: Введение. Понятие олимпиадной задачи. Работа с файлами.

Тема 02: Разветвляющиеся алгоритмы.

Тема 03: Циклические алгоритмы.

Тема 04: Массивы.

Тема 05: Сортировка.

Тема 06: Двумерные массивы.

Тема 07: Системы счисления.

 Тема 08: Теория чисел.

Тема 09: Длинная арифметика.

Тема 01: Введение. Понятие олимпиадной задачи. Работа с файлами.

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

// Язык Си freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);

 {Язык Паскаль} assign(input, 'input.txt'); reset(input); assign(output, 'output.txt'); rewrite(output);

Перед выполнением заданий данного раздела рекомендуем ознакомиться с разделом «Олимпиадная информатика», в котором дана классификация олимпиадных задач, разобрана структура олимпиадной задачи и приведены примеры работы с файлами на языках Паскаль и Си. С особенностями работы автоматизированной системы проверки и видами возможных ошибок можно ознакомиться в разделе «Работа в системе». В этой теме мы предлагаем решить простейшие задачи, которые помогут ознакомиться с вводом-выводом данных. Подобные задачи обычно используются на пробных турах олим- пиад по программированию. Список задач Задача 001: A+B. Задача 108: Неглухой телефон. Задача 033: Два бандита. Задача 092: Журавлики. Задача 004: Игра. 10 Тема 02: Разветвляющиеся алгоритмы. Мы полагаем, что Вы уже сталкивались с условным оператором и понимаете, как он работает. Хотелось бы, чтобы в этом разделе Вы закрепили свои знания на примере решения простых олимпиадных задач с использованием условий. Напомним так же, что в языке Си наряду с условным оператором существуют так же операторы switch и «?», а в языке Pascal – оператор case. Например, в языке Си при нахожде- нии максимального элемента из двух чисел вместо следующего условного оператора: if(a > b) max=a; else max=b; можно использовать следующий вариант записи: max=(a>b)?a:b; Список задач Задача 025: Больше – меньше. Задача 021: Зарплата. Задача 008: Арифметика. Задача 052: Счастливый билет. Задача 026: Две окружности. Тема 03: Циклические алгоритмы. Сложно представить серьезную программу без циклов. Мы полагаем, что вы уже зна- комы с циклами. В этом разделе будет рассмотрен ряд задач, для решения которых необхо- димо использовать циклы. Напомним, что существуют три вида циклов: 1. Оператор цикла с параметром for i=1..n{ Операторы; } 2. Оператор цикла с предусловием while(Условие){ Операторы; } 3. Оператор цикла с постусловием do{ Операторы; }while(Условие); Список задач Задача 106: Монетки. Задача 081: Арбузы. Задача 043: Нули. Задача 063: Загадка. Задача 002: Сумма. Тема 04: Массивы. Массив – это упорядоченная совокупность переменных, объединенных общим типом и име- нем. Число элементов массива фиксируется при описании и в процессе выполнения программы не меняется. Каждый элемент массива определяется именем, совпадающим с именем массива, а также индексом. Индекс – это величина, характеризующая положение элемента в массиве. В языке Си нумерация элементов массива начинается с нуля, таким образом номер по- следнего элемента массива соответствует значению n-1, где n – количество элементов масси- ва. В Паскале при описания массива можно определять диапазон индексов, что более удобно. Приведем пример описания целочисленного массива на разных языках: // Язык Си, элементы массива имеют номера от 0 до 9 int a[10]; {Язык Паскаль, нумерация элементов от 1 до 10} var a : array [1..10] of integer; //Алгоритмический язык этого курса, нумерация от 1 до 10 int a[1..10]; 11 Схематическое изображение массива из 10 элементов: К каждому элементу массива можно обращаться отдельно так же как к обычной пере- менной установленного типа. Элемент массива с номером i имеет обозначение a[i]. Благода- ря такой записи данные можно обрабатывать массово в цикле. Входные данные задачи, ко- торые необходимо хранить в массиве, обычно задаются следующим образом: сначала идет число N – количество элементов массива, а за ним следуют отделенные пробелом значения N элементов массива. Алгоритм чтения N элементов массива и вывод их в файл может выгля- деть следующим образом: const MaxN=100; int i,n,a[1..MaxN]; read(n); //чтение элементов из файла в массив for i=1..n{ read(a[i]); } //вывод элементов из массива в файл for i=1..n{ write(a[i],' '); } Список задач Задача 149: Разворот. Задача 082: Пересечение множеств. Задача 039: Волосатый бизнес. Тема 05: Сортировка. Сортировка – преобразование последовательности элементов в неубывающую (или не- возрастающую) последовательность. Последовательность элементов {Ai} называют неубы- вающей, если для любых i и j, таких что i < j выполняется неравенство Ai ≤ Aj. Для строго возрастающей последовательности неравенство принимает вид Ai < Aj. Аналогичным обра- зом определяется невозрастающая и убывающая последовательности. При решении олимпиадных задач часто необходима сортировка данных. Обычно дан- ные представлены в виде массива из N элементов, где элементы – это чаще всего числа или строки. Для этого существует множество алгоритмов, которые с помощью замены значений элементов исходного массива приводят его к отсортированному виду. Для лучшего понимания того, в каких случаях нужно применить тот или иной алгоритм необходимо знать, что понимают под показателем сложности алгоритма. Речь идет о том, как зависит число операций, которые нужно произвести согласно алгоритму от объема данных, в нашем случае от количества элементов массива N. Сложность задачи может быть логариф- мической, линейной, квадратичной, экспотенциальной и т.д., где для решения задачи необ- ходимо выполнение O(ln(N)), O(N), O(N2 ) и O(eN ) операций соответственно. Например, квад- ратичный порядок сложности O(N2 ) означает, что задача может использовать N2 операций, а может и 100*N2 , здесь коэффициент перед N2 не имеет значения: важен порядок, важно знать во сколько раз программа будет работать дольше, если число N увеличится вдвое, втрое или в 10 раз. В нашем случае независимо от этого коэффициента получим, что программа будет выполняться соответственно в 4, 9 и 100 раз дольше. 12 Наилучшие универсальные алгоритмы сортировки имеют порядок сложности O(n*ln(n)), что позволяет в олимпиадных задачах сортировать массивы для N = 300 000 (при- близительно). В качестве примера подобных алгоритмов можно привести следующие сорти- ровки: быстрая, пирамидальная, слиянием, бинарным деревом. Простейшие алгоритмы сортировки имеют порядок O(N2 ), что позволяет решать задачу с сортировкой только для N ≤ 5000 (так же примерно). Несмотря на то, что квадратичные алгоритмы дают меньший эффект, их разумно использовать, когда скоростью сортировки данных можно пренебречь, повысив скорость реализации программы. Примеры подобных сортировок: выбором, пузырьком, вставками. В частных случаях отсортировать данные возможно с линейным порядком сложности, когда есть некоторые ограничения на данные (например, массив уже частично отсортирован или диапазон элементов массива ограничен). С таким порядком сложности возможна сорти- ровка массива, состоящего из 107 элементов! Например, следующие алгоритмы дают такой результат: цифровая и поразрядная сортировки. Многие считают, что достаточно знания двух сортировок (например, «пузырьком» и «быстрой»), чтобы решать любые олимпиадные задачи. Но на самом деле это далеко не так. Далее, рассмотрим алгоритмы сортировки, наиболее часто используемые программистами. Во всех примерах будем сортировать по неубыванию полагая, что a[i] – целочисленный мас- сив, состоящий из n элементов, с индексами от 1 до n. Сортировка выбором Пожалуй, это самый легкий для реализации алгоритм среди существующих, идея кото- рого сводится к последовательному позицированию нужных элементов с 1-го по n-ый. Вна- чале среди всех элементов определяется наименьший и меняется с 1-ым, далее среди всех оставшихся снова находится наименьший и меняется со 2-ым. Далее, среди элементов, начи- ная с 3-го так же находится наименьший и меняется с 3-им и т.д. до (n-1)-го элемента. Квад- ратичная сложность алгоритма очевидна, а алгоритм решения может выглядеть следующим образом: for i=1..n-1{ for j=i+1..n{ if(a[i] > a[j]) a[i] <---> a[j]; } } Сортировка пузырьком Это, наверное, самый популярный алгоритм сортировки, идея которого чем то похожа на предыдущий алгоритм: так же реализация сводится к позицированию нужных элементов с 1-го по последний. Сама процедура установки текущего элемента в нужную позицию чем то напоминает всплытие пузырька. Для того, чтобы первый элемент (наименьший) встал на свое место необходимо справа налево пройтись по массиву, попарно сравнивая соседние элементы и в том случае, когда левый больше правого менять их местами. Для позицирова- ния второго элемента, нужно пройтись еще раз по массиву, но не до 1-го а уже до 2-го эле- мента и т.д. Данный алгоритм, который как и предыдущий имеет квадратичную сложность, можно представить следующим образом: for i=1..n-1{ for j=n-1..i{ if(a[j] > a[j+1]) a[j] <---> a[j+1]; } } Быстрая сортировка Этот алгоритм является одним из самых популярных и наиболее часто используемым среди алгоритмов, имеющих порядок сложности O(n*ln(n)). Сам алгоритм является рекур- сивным и его идея заключается в следующем: для сортировки массива достаточно разбить его на две части так, чтобы все элементы левой части были меньше либо равны всех элемен- тов правой части, далее следует выполнить подобную операцию с левой и правой частью, 13 рассматривая их как отдельные массивы. Алгоритмическое представление процедуры, кото- рая сортирует подмассив с l-го по r-й элемент можно представить следующим образом: sub QuickSort(l,r){ x=(l+r) div 2; i=l; j=r; do{ while(a[i] < p) i=i+1; while(a[j] > p) j=j-1; if (i <= j) { a[i] <---> a[j]; i=i+1; j=j+1; } }while(i <= j); if(j > l) QuickSort(l, j); if(r > i) QuickSort(i, r); } Для сортировки массива достаточно вызвать процедуру QuickSort(1, n). Список задач Задача 119: Сортировка времени. Задача 032: Годовой баланс. Задача 041: Цифровая сортировка. Тема 06: Двумерные массивы Двумерный массив – это одномерный массив, элементами которого являются одно- мерные массивы. Другими словами, это набор однотипных данных, имеющий общее имя, доступ к элементам которого осуществляется по двум индексам. Наглядно двумерный мас- сив удобно представлять в виде таблицы, в которой n строк и m столбцов, а под ячейкой таб- лицы, стоящей в i-й строке и j-м столбце понимают некоторый элемент массива a[i][j]. Действительно, если разобраться с тем, что такое a[i] при фиксированном значении i, то увидим, что это одномерный массив, состоящий из m элементов, к которым можно обра- щаться по индексу: a[i][1], a[i][2], ... , a[i][m]. Схематически это вся i-я строка строка табли- цы. Аналогично, если мы рассмотрим одномерный массив строк, то сможем заметить, что это так же двумерный массив, где каждый отдельный элемент – это символ типа char, а a[i] – это одномерный массив, представляющий отдельную строку исходного одномерного масси- ва строк. Исходя из идеи определения двумерного массива, можно определить рекуррентное понятие многомерного массива: n-мерный массив – это одномерный массив, элементами которого являются (n-1)- мерные массивы. Несложно догадаться, что 3-мерный массив визуально можно представить в виде куба с ячейками (похоже на кубик Рубика), где каждый элемент имеет вид a[i][j][k]. А вот с боль- шими размерностями возникают сложности с визуальным представлением, но математиче- ская модель ясна. По-другому двумерный массив также называют матрицей, а в том случае, когда n=m (число строк равно числу столбцов) матрицу называют квадратной. В матрицах можно хра- нить любые табличные данные: содержание игрового поля (шашки, шахматы, Lines и т.д.), лабиринты, таблицу смежности графа, коэффициенты системы линейных уравнений и т.д. Матрицы часто используют для решения олимпиадных и математических задач. В задачах табличные данные часто определяются во входном файле следующим обра- зом: сначала в первой строке указываются значения n и m через пробел, а далее идут n строк по m элементов в каждой, также друг от друга отделенные пробелом и входной файл может иметь, например, следующее содержание, понятно отражающее содержимое матрицы при обычном просмотре: 3 5 7 8 2 3 1 5 3 2 6 3 9 3 5 2 0 14 В приведенном примере определена матрица, состоящая из трех строк и пяти столбцов. Рассмотрим пример чтения этих данных в матрицу и вывода матрицы в файл. Для этого удобно использовать двойной цикл, где внешний цикл по i будет пробегать по всем строкам, а внутренний цикл по j будет для текущей строки i перебирать все ее элементы. Алгоритми- ческая реализация этого процесса может выглядеть следующим образом: int a[1..100][1..100]; //Чтение данных двумерного массива из файла read(n,m); for i=1..n{ for j=1..m{ read(a[i][j]); } } //Вывод матрицы в файл for i=1..n{ for j=1..m{ write(a[i][j], ' '); } writeln; //новая строка } В качестве примера рассмотрим задачу о транспонировании квадратной матрицы отно- сительно главной и побочной диагонали, где необходимо симметричным образом поменять элементы двумерного массива относительно одной из диагонали. Алгоритмическое решение данной задачи может быть представлено следующим образом: for i=2..n{ for j=1..i-1{ a[i][j] <---> a[j][i]; } } for i=1..n-1{ for j=1..n-i{ a[i][j] <---> a[n-j+1][n-i+1]; } } Список задач Задача 027: Художник. Задача 058: Проверка на симпатичность. Задача 088: Судоку. Тема 07: Системы счисления Обычно мы имеем дело с десятичной системой счисления, в которой используется ров- но 10 цифр: 0..9, и мы все к этому сильно привыкли. Но для обозначения чисел возможно ис- пользование других систем, отличных от десятичной. Особенностью таких систем является, отличное от 10 количество используемых цифр. Например, в двоичной системе используется только две цифры - 0 и 1; и любое число может быть представлено в такой системе. Если система имеет порядок, больший чем 10, то в качестве следующих цифр используются ла- тинские буквы; например, в шестнадцатеричной системе присутствуют следующие цифры: 0..9, A, B, C, D, E и F. 15 Для того чтобы представить какое либо число в десятичной системе счисления, следует вычислить сумму всех цифр данного числа, умноженных на порядок системы счисления, возведенной в степень, равную номеру разряда данной цифры. Следующие примеры демон- стрируют суть данного метода: Для перевода из десятичной системы счисления в систему с основанием k необходимо производить деление исходного числа на k, запоминая остатки от деления и продолжая дан- ную операцию с целочисленным значением деления до тех пор, пока результатом деления не будет ноль. Искомым представлением числа будет запись, составленная из полученных ос- татков от деления, записанных в обратном порядке. Ниже представлены примеры перевода: При решении олимпиадных задач обычно рассматривают системы счисления с основа- ниями от 2 до 36. Это связано с тем, что в латинском алфавите 26 букв (10 цифр + 26 букв = 36 символов). Для хранения цифр числа можно использовать как целочисленный массив, так и строку. Пусть S – число, записанное в K-ой системе счисления, а X – число в десятичной системе. Тогда алгоритм перевода из любой системы в десятичную можно записать следую- щим образом: read(S); X=0; for i = 1..len(S){ X = X*K+S[i]; } write(X); Алгоритм перевода из десятичной системы числа X в систему с основанием К и записи его в S может быть представлен так: read(X); l=0; do{ l=l+1; S[l] = X mod K; X = X div K; }while(X>0); write(reverse(S)); Для того чтобы перевести из k-ой системы счисления в систему с основанием m, можно воспользоваться «принципом чайника» и перевести сначала из k-ой системы в 10-ую, а затем из 10-ой в m-ую. Однако иногда этой двойной операции можно избежать. Речь идет о случае, когда мы имеем дело с кратными системами счисления. Например, несложно переводить из 2-ой в 4-ую, 8-ую, 16-ную и обратно; аналогично можно сказать о 3-ой и 27-ой системах или о 5-ой и 25-ой. В подобных случаях каждая цифра числа в системе с большим основанием представляется в виде нескольких цифр системы с меньшим основанием. Так, в 4-ой сис- теме каждая цифра представляется 2-мя цифрами 2-ой системы, в 8-ой – 3мя цифрами 2-ой, а в 16-ой каждая цифра есть ничто иное как 4 цифры 2-ой системы. Например, для перевода двоичного числа 101100101010011011 в 16-ую систему достаточно разбить число на 4-ки: 16 0010 1100 1010 1001 1011 и записать каждую из них в 16-ом формате: 2CA9B, т.к. 0010 = 2, 1100 = B, 1010 = A, 1001 = 9 и 1011 = B. Несложно догадаться, что обратное преобразование из 16-ой в 2-ую систему происходит аналогичным образом. Список задач Задача 022: Единицы. Задача 059: Несложное вычисление. Задача 275: Делимость на 7. Тема 08: Теория чисел Теория чисел – раздел математики, занимающийся изучением чисел непосредственно как таковых, их свойств и поведения в различных ситуациях. Достаточно сложно дать пол- ное определение теории чисел, т.к. точного определения и не существует вовсе. Мы же бу- дем рассматирать только ту ее часть, которая используется при решении олимпиадных задач. В большей степени будем уделять внимание целым числам. Для этого определим некоторые разновидности чисел ... Множество всех целых чисел обычно обозначают буквой Z и понимают под ним набор всех действительных чисел без дробной части: {... , -3, -2, -1, 0, 1, 2, 3, ...}. Натуральные чис- ла являются подмножетством целых чисел и образуют множество N: {1, 2, 3, ...}. Простым числом называют натуральное число, большее единицы, которое делится только на 1 и на само себя. Все остальные числа называют составными. Первые 10 простых чисел: 2, 3, 5, 7, 11, 13, 17, 19, 23 и 29. Перечислим несколько свойств простых чисел: • любое составное число представляется уникальным образом в виде произведения простых чисел; иначе еще говорят, что разложение числа на простые множители од- нозначно. • простых чисел бесконечно много, причем существует примерно n/ln(n) простых чи- сел, меньших числа n. • наименьший простой делитель составного числа n не превышает sqrt(n), поэтому для проверки простоты числа достаточно проверить его делимость на 2 и все нечетные (а еще лучше простые) числа, не превосходящие sqrt(n). • любое четное число, большее двух представимо в виде суммы двух простых чисел; а любое нечетное, большее чем 5 представимо в виде суммы трех простых чисел • для любого натурального n, большего единицы существует хотя бы одно простое чис- ло на интервале (n, 2*n) Числа Мерсена – это числа, представимые в виде 2n -1. Особый интерес представляют простые числа Мерсена, которые получаются при n=2, 3, 5, 7, 13, 17, 19, 41, 47, 61, 89, 10, 127, ... На сегодняшний день известно 44 простых числа Мерсена и самое большое из них получается при n=32582657 и содержит в себе почти 10 миллионов цифр, оно же является самым большим из найденных на сегодняшний день. Это же число является наибольшим среди всех известных простых чисел. На сегодняшний день неизвестно: конечно ли число простых чисел Мерсена. Числа Ферма – это числа, представимые в виде 2 1 2 + n . Простыми среди чисел вида 2 n +1 могут быть только числа Ферма. На данный момент известно всего 5 простых чисел Ферма: 3, 5, 17, 257, 65537; так же известно, что для 5 ≤ n ≤ 32 все числа Ферма – составные. Совершенное число – это натуральное число, равное сумме всех своих делителей, не включая самого себя. Например, число 28 – совершенное число, т.к. 28=1+2+4+7+14. Вот первые 10 совершенных чисел: 6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128, 2658455991569831744654692615953842176, 191561942608236107294793378084303638130997321548169216. Известно, что любое четное совершенное число может быть представлено в виде 2p-1(2p -1), где число 2p -1 является про- стым числом Мерсена. На сегодняшний день не известно конечно ли количество совершен- ных чисел и существуют ли нечетные совершенные числа. 17 Дружественные числа – два натуральных числа, для которых сумма всех делителей первого числа (кроме него самого) равна второму числу и сумма всех делителей второго числа (кроме него самого) равна первому числу. Иногда частным случаем дружественных чисел считаются совершенные числа: каждое совершенное число дружественно себе. Обыч- но же, говоря о дружественных числах, имеют в виду пары из двух разных чисел. Первые 8 пар таких чисел: 220 и 284, 1184 и 1210, 2620 и 2924, 5020 и 5564, 6232 и 6368, 10744 и 10856, 12285 и 14595, 17296 и 18416. Число Армстронга – натуральное число, которое равно сумме своих цифр, возведённых в степень, равную количеству его цифр. Например, 1634 = 14 + 64 + 34 + 44 . Последователь- ность чисел Армстронга начинается так: 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834, 1741725, 4210818, 9800817, 9926315, 24678050, 24678051, 88593477, 146511208, 472335975, 534494836, 912985153, 4679307774, 32164049650, 32164049651 ... С одним из алгоритмов поиска таких чисел Вы можете ознакомиться здесь. m-самовлюбленное число – натуральное число, которое равно сумме своих цифр, возве- дённых в степень m, где m – некоторое натуральное число. Числа Армстронга – частный случай таких чисел. Число Смита – такое составное число, сумма цифр которого (в данной системе счисле- ния) равняется сумме цифр всех его простых сомножителей. Так, примером числа Смита может служить 202, поскольку 2 + 0 + 2 = 4, и 2 + 1 + 0 + 1 = 4 (202 = 2 * 101). У. Л. МакДэ- ниел доказал, что существует бесконечно много чисел Смита. Насчитывается 29 928 чисел Смита в пределах до 1 000 000. Первые 50 чисел Смита: 4, 22, 27, 58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, 378, 382, 391, 438, 454, 483, 517, 526, 535, 562, 576, 588, 627, 634, 636, 645, 648, 654, 663, 666, 690, 706, 728, 729, 762, 778, 825, 852, 861, 895, 913, 915, 922, 958, 985, 1086. Список задач Задача 148: Наибольший общий делитель. Задача 014: Наименьшее общее кратное. Задача 147: Числа Фибоначчи. Задача 349: Простые числа. Задача 323: Гипотеза Гольбаха. Задача 036: Постулат Бертрана. Тема 09: Длинная арифметика Длинная арифметика – раздел олимпиадного программирования, в котором рассматрива- ется реализация действий с большими числами, не умещающихся в стандартных типах данных. На сегодняшний день единственным языком, используемым для решения олимпиадных задач и поддерживающим длинную арифметику, является Java, где все необходимые функции для рабо- ты с длинными числами встроены и можно обойтись без трудоемких реализаций. В основном мы будем рассматривать работу с целыми числами. Для хранения длинного числа можно использовать целочисленный массив, где в качестве элемента массива будет одна цифра числа. В 1-ом элементе массива будем хранить последнюю цифру числа, во 2-ом – предпоследнюю и т.д. до последней цифры. В 0-ом элементе можно хранить общее количе- ство цифр в числе. В простейшем случае, для хранения числа 154 достаточно будет исполь- зовать следующую запись: const maxsize=100; int a[maxsize]; a[0]=3; a[1]=4; a[2]=5; a[3]=1; Элементом массива может быть не одна цифра, возможно использовать один элемент для хранения 4х цифр, т.к. мы понимаем, что на современных ЭВМ все операции как мини- мум 32-разрядные, поэтому время на сложение двух цифр такое же как и на сложение чисел, состоящих из 4х цифр. Поэтому часто используют порядок системы счисления base=10000 и фактически длинные числа хранятся как бы в 10000-й системе счисления, это позволяет уве- личить скорость выполнения операций над ними в 3–4 раза. 18 Идея реализации всех необходимых операций (сложение, вычитание, умножение, деле- ние и т.д.) основана на тех принципах, которыми мы пользуемся при расчетах на бумаге. Даже когда мы реализуем деление «в столбик», фактически мы работаем с небольшими чис- лами, сводя более сложную задачу к набору из более простых подзадач. Задачи, которые рассматриваются в данном разделе, представляют собой базовый на- бор, достаточный для формирования первоначальных навыков овладения принципами длин- ной арифметики. Практически все задачи на длинную арифметику требуют чтения из файла и запись в файл длинных чисел, поэтому приведем реализацию этих функций в данном раз- деле, а в разборе задач будем их использовать: void readlong(int *a){ int i; string s; read(s); a[0]=len(s); for i=1..len(s){ a[i]=ord(s[i])-48; } } void writelong(int *a){ for i=a[0]..1{ write(a[i]); } } Так же часто возникает необходимость сравнивать длинные числа. Опишем следую- щую функцию, которая будет возвращать 0 в случае равенства чисел, -1 когда первое число меньше второго и 1 когда первое больше: void complong(int *a, int *b){ if (a[0] < b[0]) return -1; if (a[0] > b[0]) return 1; for i=a[0]..1{ if(a[i] < b[i]) return -1; if(a[i] > b[i]) return 1; } return 0;
Список литературы:

1.       Kiryukhin V.M., Tsvetkova M.S. Strategy for IСT Skills Teachers and Informatics Olympiad Coaches Development. International Journal «Olympiads in informatics», 2010. Vol. 4, Стр. 30-51

2.       Амонашвили Ш.А. Размышления о гуманной педагогике. – М.: Изд-ский Дом Ш. Амонашвили, 2001. – 464 с.

3.       Выготский Л.С. Воображение и творчество в детском возрасте. 3-е изд.– М.: Просвещение, 1991. – 93 с.

4.       Дьюи Дж. Школа и общество: пер. с англ. – 2-е изд. – Берлин-М.: Работник просвещения, 1925. 127 с.

5.       Занков Л.В. Избранные педагогические труды. – 3-е изд., дополн. – М.: Дом педагогики, 1999. – 608 с.

6.       Кирюхин В.М. Информатика. Всероссийские олимпиады. Вып. 3. – М.: Просвещение, 2011. – 222 с. –
(Пять колец).

7.       Кирюхин В.М. Методика проведения и подготовки к участию в олимпиадах по информатике. Всероссийская олимпиада школьников. – М.: БИНОМ. Лаборатория знаний, 2011. – 271 с.

8.       Пейперт С. Переворот в сознании: Дети, компьютеры и плодотворные идеи. – М.: Педагогика, 1989. – 220 с.

9.       Пиаже Ж. Избранные психологические труды. М., 1994

10.        Ушинский К.Д. Антология гуманной педагогики. – М.: Издательский Дом Ш. Амонашвили, 1998. – 224 с.

11.        Цветкова М.С. Модели непрерывного информационного образования. – М.: БИНОМ. Лаборатория знаний, 2009. – 326 с.