Календарно-тематическое планирование курса по информатике «Подготовка к олимпиаде» 8 класс

Всего - 68 часа (по 2 ч . в неделю)

	Раздел/тема	Кол-во часов	Основные виды учебной деятельности	Дата проведения
				по плану
Республиканская олимпиада школьников по информатике. Нормативное обеспечение Республиканской олимпиады по информатике - 10 ч
	Положение о Республиканской, Всероссийской, Международной олимпиаде школьников.
			восприятие, осмысление и запоминание информации
			восприятие, осмысление и запоминание информации
	План самостоятельной работы по программе олимпиадной информатики.		восприятие, осмысление и запоминание информации
	Заполнение учащимся индивидуальной карты подготовки.		восприятие, осмысление и запоминание информации
- 8 ч
	Структура олимпиадной задачи. Типы олимпиадных задач по информатике. Основные разделы математической информатики. Типовые примеры решения задач по разделам из коллекции		Конспектирование, полученной информации, ответы на вопросы, после объяснения материала
	Этапы решения олимпиадной задачи: формализация условия задачи, выбор метода решения задачи. План разбора олимпиадной задачи по информатике.		Решать логические задачи различными способами; осуществлять системный анализ объекта, выделять среди его свойств существенные свойства с точки зрения целей моделирования; выявлять различие в унарных, позиционных и непозиционных системах счисления;
	Автоматизированная среда проверки решений олимпиадных задач.		выявлять общее и отличия в разных задачах
	Коллекция олимпиадных задач в Интернете. Полезные ресурсы для подготовки к олимпиадам. Тренировочные туры в Интернете.		позиционных системах счисления;
Технологические ресурсы олимпиадной информатики. Среда программирования - 27 ч
	Основные инструменты среды программирования.		строить цепочки команд, дающих нужный результат при конкретных исходных данных для исполнителя, преобразующего строки символов; анализировать логическую структуру высказываний.
	Сравнение сред программирования для разных языков программирования.		преобразовывать запись алгоритма с одной формы в другую; восприятие, осмысление и запоминание информации,участие в дискуссии
	Среда программирования в свободном доступе. Инсталляция, шаги для освоения.		выполнять операции сложения и умножения над небольшими двоичными числами; восприятие, осмысление и запоминание информации
	Проведение тренировочного тура в реальном времени.		Участие в разные очных, дистанционных олимпиад
	Разбор задач тура. Диагностика дефицитов в теоретической, практической и технической подготовке.
	Кодирование числовой информации. Кодирование текстовой информации		строить таблицы истинности для логических выражений; восприятие, осмысление и запоминание информации
	Кодирование графической информации. Кодирование звуковой информации.		Двоичный код. Кодирование. Декодирование. Недостаток двоичного кодирования.Система счисления.Позиционные. Непозиционные
	Равномерное и неравномерное кодирование.		определять по блок-схеме, для решения какой задачи предназначен данный алгоритм; слушание,конспектирование, ответы на вопросы после объяснение материала
	Рещение задач на количество информации. Скорость передачи информации.		анализировать изменение значений величин при пошаговом выполнении алгоритма; конспектирование.
	Абсолютная и относительная адресация в Excel. Формулы в Excel. Решение задач с графами.		определять по выбранному методу решения задачи, какие алгоритмические конструкции могут войти в алгоритм; восприятие, осмысление и запись в тетради
	Языки программирования. Переменные и типы данных		восприятие, осмысление и запоминание информации, конспектирование полученной информации
	Механизмы абстракции. Особенности программирования фундаментальных алгоритмов		восприятие, осмысление и запоминание информации, конспектирование полученной информации
	Основы синтаксиса и семантики языков высокого уровня. Основные конструкции программирования		рассмотреть этапы развития языков программирования. познакомить с интегрированной средой программирования
- 6 ч
	Нахождение НОД и НОК. Алгоритмы Евклида.		в беседе по данной теме
	Пифагоровы тройки. Простые числа. Числа близнецы.		слушание, конспектирование, участие в беседе по данной теме
	Совершенные числа. Числа палиндромы, Мерсенна, Армстронга, Фибоначчи. Диофантовы уравнения. «Длинная» арифметика		восприятие, осмысление и запоминание информации
- 17 ч
	Стратегии реализации алгоритмов Реализация рекурсии		практическая работа за компьютером, работа с дополнительными источниками
	Введение в моделирование. Компоненты компьютерной модели и способы их описания: входные и выходные переменные, переменные состояния, функции перехода и выхода, функция продвижения времени		оценивать адекватность модели моделируемому объекту и целям моделирования; определять вид информационной модели в зависимости от стоящей задачи; подготовка сообщений по выбранным темам, анализ выполненных работ
	Компьютерные сетевые технологии. Основные этапы и особенности построения компьютерных моделей.		выявлять общие черты и отличия способов взаимодействия на основе компьютерных сетей; анализировать доменные имена компьютеров и адреса документов в Интернете; работа с Интернет - ресурсами, конспектирование, анализ найденной информации
	Основные этапы использования компьютерных моделей при решении практических задач		практическая работа на компьютере
	Организация олимпиадной подготовки: режим дня, занятия спортом, . Методы самодиагностики уровня подготовленности.		восприятие, осмысление и запоминание информации
	Основные критерии олимпиадной подготовки: теоретические, практические, технологические, технические, психологические.		восприятие, осмысление и запоминание информации
	Мониторинг школьником выполнения индивидуального плана для самостоятельной олимпиадной подготовки. Настройка индивидуального плана по итогам мониторинга.		восприятие, осмысление и запоминание информации
	Рефлексия
ИТОГО		68 час.

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
ВВЕДЕНИЕ.

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

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

ЦЕЛИ И ЗАДАЧИ

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

Структура курса включает в себя следующие разделы:

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

Интеллектуальные ресурсы олимпиадной информатики. Коллекции олимпиадных задач

Технологические ресурсы олимпиадной информатики. Среда программирования

Вычислительные задачи, использующие свойства натуральных чисел

Методы вычислений и моделирование. Индивидуальная траектория олимпиадной подготовки

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

Методические указание для изучения курса

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

Виртуальные лаборатории по информатике в начальной школе: методическое пособие Авторы: Цветкова М. С., Курис Г. Э.

Коллекции олимпиадных задач с 1989 по 2016 год и методические материалы к ним представлены на сайтах:

http://old.info.rosolymp.ru/

Представлены интернет-ресурсы олимпиадной информатики:

1. Интернет-ресурсы для теоретической подготовки к олимпиадам:

2. Интернет-ресурсы с коллекциями олимпиадных задач:

http://olimpic.nsu.ru/nsu/ (сайт открытой Всесибирской олимпиады по программированию им. И.В. Поттосина).

3. Интернет-ресурсы с коллекциями олимпиадных задач и возможностью их тестирования в реальном масштабе времени:

4. Сайты интернет-олимпиад для школьников:

Список литературы

1. Алексеев А. В., Беляев С. Н. Подготовка школьников к олимпиадам по информатике с использованием веб-сайта: учеб.-метод. пособие для учащихся 7-11 классов. Ханты-Мансийск: РИО ИРО, 2008. 284 с.

2. Волчёнков С. Г., Корнилов П. А., Белов Ю. А. и др. Ярославские олимпиады по информатике. Сборник задач с решениями. М.: БИНОМ. Лаборатория знаний. 2010. 405 с.

3. Долинский М. С. Алгоритмизация и программирование на TurboPascal: от простых до олимпиадных задач: учеб.пособие. СПб.: Питер Принт, 2004. 240 с.

4. Иванов С. Ю., Кирюхин В. М., Окулов С. М. Методика анализа сложных задач по информатике: от простого к сложному // Информатика и образование. 2006. № 10. С. 21-32.

5. Кирюхин В. М. Всероссийская олимпиада школьников по информатике. М.: АПК и ППРО, 2005. 212 с.

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

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

8. Кирюхин В. М. Информатика. Международные олимпиады. Вып. 1. М.: Просвещение, 2009. 239 с. (Пять колец).

9. Кирюхин В. М., Лапунов А. В., Окулов С. М. Задачи по информатике. Международные олимпиады 1989-1996 гг. М.: ABF, 1996. 272 с.

10. Кирюхин В. М., Окулов С. М. Методика анализа сложных задач по информатике // Информатика и образование. 2006. № 4. С. 42-54.

11. Кирюхин В. М., Окулов С. М. Методика анализа сложных задач по информатике // Информатика и образование. 2006. № 5. С. 29-41.

12. Кирюхин В. М., Окулов С. М. Методика решения задач по информатике. Международные олимпиады. М.: БИНОМ. Лаборатория знаний, 2007. 600 с.

13. Кирюхин В. М., Цветкова М. С. Всероссийская олимпиада школьников по информатике в 2006 году. М.: АПК и ППРО, 2006. 152 с.

14. Кирюхин В. М., Цветкова М. С. Методическое обеспечение олимпиадной информатики в школе / Сб. трудов XVII конференции-выставки «Информационные технологии в образовании». Ч. III. М.: БИТ про, 2007. С. 193-195

15. Кирюхин В. М. Информатика. Всероссийские олимпиады. Вып. 1. М.: Просвещение, 2008. 220 с. (Пять колец).

16. Меньшиков Ф. В. Олимпиадные задачи по программированию. СПб.: Питер, 2006. 315 с.

17. Московские олимпиады по информатике. 2002-2009 / под ред. Е. В. Андреевой, В. М. Гуровица и В. А. Матюхина. М.: МЦНМО, 2009. 414 с.

18. Нижегородские городские олимпиады школьников по информатике / под ред. В. Д. Лелюха. Нижний Новгород: ИПФ РАН, 2010. 130 с.

19. Никулин Е. А. Компьютерная геометрия и алгоритмы машинной графики. СПб.: БХВ-Петербург, 2003. 560 с.

20. Окулов С. М. Основы программирования. М.: БИНОМ. Лаборатория знаний, 2005. 440 с.

21. Окулов С. М. Программирование в алгоритмах. М.: БИНОМ. Лаборатория знаний. 2002. 341 с.

22. Окулов С. М. Дискретная математика. Теория и практика решения задач по информатике: учеб.пособие. М.: БИНОМ. Лаборатория знаний. 2008. 422 с.

23. Окулов С. М. Алгоритмы обработки строк: учеб.пособие. М.: БИНОМ. Лаборатория знаний, 2009. 255 с.

24. Окулов С. М., Пестов А. А. 100 задач по информатике. Киров: Изд-во ВГПУ, 2000. 272 с.

25. Окулов С. М., Лялин А. В. Ханойские башни. М.: БИНОМ. Лаборатория знаний. 2008. 245 с. (Развитие интеллекта школьников).

26. Просветов Г. И. Дискретная математика: задачи и решения: учеб.пособие. М.: БИНОМ. Лаборатория знаний. 2008. 222 с.

27. Скиена С. С., Ревилла М. А. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям. М.: Кудиц-образ, 2005. 416 с.

28. Сулейманов Р. Р. Организация внеклассной работы в школьном клубе программистов: методическое пособие. М.: БИНОМ. Лаборатория знаний. 2010. 255 с.

29. Цветкова М. С. Система развивающего обучения как основа олимпиадного движения / Сборник трудов XVII конференции-выставки «Информационные технологии в образовании». Ч. III. М.: БИТ про, 2007. С. 205-207

30. Кирюхин В.М., Цветкова М.С. Образовательные программы по развитию одаренности у детей и подростков, составленные с учетом уровня подготовленности, направлений интересов, по направлению информационных технологий, 2012 .

Сайт Методического центра олимпиадной информатики:

http://metodist.lbz.ru/lections/6/

Портал Всероссийской олимпиады школьников:

http://www.rosolymp.ru/

Сайт с архивом олимпиадных задач:

http://old.rosolymp.ru/

1. Интернет-ресурсы для теоретической подготовки к олимпиадам:

http://www.intuit.ru/courses.html (сайт Интернет-университета информационных технологий);

http://ips.ifmo.ru/ (сайт Российской Интернет-школы информатики и программирования);

http://www.olympiads.ru/sng/index.shtml (сайт МИОО, МЦНМО, и оргкомитета Московской олимпиады по информатике для проведения дистанционных семинаров по подготовке к олимпиадам по информатике);

http://vzshit.net.ru/ (сайт Всесибирской заочной школы информационных технологий).

2. Интернет-ресурсы с коллекциями олимпиадных задач:

http://old.info.rosolymp.ru (сайт с самой большой в России коллекцией задач международных и всероссийских олимпиад по информатике с методическими рекомендациями по их решению);

http://www.olympiads.ru/moscow/index.shtml (сайт московских олимпиад по информатике);

http://neerc.ifmo.ru/school/russia-team/archive.html (сайт с архивом задач Всероссийских командных олимпиад школьников по программированию);

http://contest.ur.ru (сайт Уральских олимпиад по информатике);

http://www.olympiads.ru/ (сайт по олимпиадной информатике);

http://olimpic.nsu.ru/nsu/archive/2005/index.shtml (сайт открытой Всесибирской олимпиады по программированию им. И.В. Поттосина).

3. Интернет-ресурсы с коллекциями олимпиадных задач и возможностью их тестирования в реальном масштабе времени:

http://acm.timus.ru/ (сайт Уральского государственного университета, содержащий большой архив задач с различных соревнований по спортивному программированию);

http://acm.sgu.ru (сайт Саратовского государственного университета, содержащий архив задач с системой онлайн-проверки).

4. Сайты интернет-олимпиад для школьников:

http://info-online.rusolimp.ru/ (сайт интернет-туров заключительного этапа Всероссийской олимпиады школьников по информатике);

http://olymp.ifmo.ru/ (сайт городских интернет - олимпиад школьников Санкт-Петербурга);

http://neerc.ifmo.ru/school/io/index.html (сайт интернет-олимпиад по информатике, проводимых жюри Всероссийской командной олимпиады школьников по программированию);

http://www.olympiads.ru/online/index.shtml (сайт московских онлайн-олимпиад);

http://olimpic.nsu.ru/acmSchool/archive/2006-2007/train2006/index.shtml (сайт тренировочных олимпиад школьников, поддерживаемый Новосибирским государственным университетом).

5. Олимпиадные сайты зарубежных стран:

http://acm.uva.es (сайт университета Valladolid с крупнейшей в интернете общедоступной коллекцией задач с возможностью проверки в реальном времени и проведения соревнований по программированию );

http://train.usaco.org/usacogate (сайт подготовки к американским олимпиадам по информатике);

http://www.acsl.org (Сайт организации American Computer Science League, которая организует соревнования по программированию среди школьников);

http://www.topcoder.com/tc (сайт интернет-соревнований компании TopCoder);

http://www.inf.bme.hu/contests/tasks (сайт с большим количеством задач, предлагавшихся на соревнованиях по информатике во многих странах); http://www.i-journals.org/olympiads_in_informatics/ (сайт международного журнала «Олимпиады по информатике» (Olympiadsininformatics);

http://www.ut.ee/boi (сайт Балтийских олимпиад по информатике);

http://ipsc.ksp.sk (сайт ежегодных интернет-соревнований по командному программированию);

http://www.hsin.hr/coci/ (англоязычный сайт проведения Интернет-олимпиад в Хорватии);

http://uoi.kiev.ua (сайт украинских олимпиад школьников по информатике);

http://byoi.narod.ru (сайт белорусских олимпиад школьников по информатике).

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

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

Об обучении

Учусь я в школе с углубленным изучением физики, математики и информатики.

Что же это за школа, как в ней учиться и как в нее поступить?

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

Меня всегда привлекало программирование (что это такое я понял аж в 4 классе). Я был очень рад, когда в седьмом классе начали преподавать Pascal и различные вычислительные алгоритмы. Именно тогда я написал первый «Hello World!», алгоритм Евклида; изучил условные операторы, циклы, массивы.
С восьмого класса учителя приглашали на факультативы по информатике, где мы изучали графы, алгоритмы сортировки массивов и многое другое.

Задачи

Посмотрим на совершенно типичную задачу для начинающих программистов-олимпиадников

Пятью пять - двадцать пять!
(Время: 1 сек. Память: 16 Мб Сложность: 8%)
Вася и Петя учатся в школе в одном классе. Недавно Петя поведал Васе о хитром способе возведения в квадрат натуральных чисел, оканчивающихся на цифру 5. Теперь Вася может с легкостью возводить в квадрат двузначные (и даже некоторые трехзначные) числа, оканчивающиеся на 5. Способ заключается в следующем: для возведения в квадрат числа, оканчивающегося на 5 достаточно умножить число, полученное из исходного вычеркиванием последней пятерки на следующее по порядку число, затем остается лишь приписать «25» к получившемуся результату справа. Например, для того, чтобы возвести число 125 в квадрат достаточно 12 умножить на 13 и приписать 25, т.е. приписывая к числу 12*13=156 число 25, получаем результат 15625, т.е. 1252=15625. Напишите программу, возводящую число, оканчивающееся на 5, в квадрат для того, чтобы Вася смог проверить свои навыки.
Входные данные
В единственной строке входного файла INPUT.TXT записано одно натуральное число А, оканчивающееся на цифру 5, не превышающее 4*10^5.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно натуральное число - A2 без лидирующих нулей.
Примеры:
INPUT.TXT
5
75
4255
OUTPUT.TXT
25
5625
18105025

Требования

От олимпиадника требуется написать программу на одном из принимаемых языков (обычно этот набор состоит из Pascal (сам пишу, никогда проблем не было), Delphi, C++, Java, Visual Basic, в последнее время добавляют C#, Python). После этого исходный файл отправляется в систему-песочницу, где он компилируется и выполняется на группе тестов. За каждый тест участник олимпиады получает некоторый балл, которые потом складываются. После олимпиады результаты становятся видны всем. Чем больше суммарный балл - тем выше место.
Стоит отметить, что обычно проверяющими системами плохо обрабатывается управляемый код (Java, C#). Мой друг лично на региональном этапе получил на трех из четырех задач 0 баллов из-за ошибки во время выполнения (писал на C#), хотя проверялось все нормально. Что делать в таком случае не понял ни я, ни он; на апелляции жюри просто пожали плечами.

Риски

На чем можно проиграть? Существуют 7 типов ошибок:

Скрытый текст

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

Time limit exceeded
Превышен указанный в задаче лимит времени. Программа выполняется дольше установленного времени
Неэффективное решение или алгоритмическая ошибка в программе

Presentation Error
Отсутствие выходного файла OUTPUT.TXT
Файл не создан, неверное имя файла или сбой программы до открытия выходного файла

Compilation error
Ошибка компиляции. В результате компиляции не создан исполняемый файл
Синтаксическая ошибка в программе или неверно указано расширение файла. Возможно, что при реализации на языке Java был использован класс, отличный от Main

Memory limit exceeded
Превышен указанный в задаче лимит памяти. Программа использует больше установленного размера памяти.
Неэффективный алгоритм, либо нерациональное использование памяти

Runtime error
Ошибка исполнения. Программа завершила работу с ненулевым кодом возврата. В этом случае результат работы не проверяется
Возможно, в программе произошло обращение к несуществующему элементу массива, деление на ноль и т.д. Возможно, программа на C++ не завершается оператором «return 0» или по иной причине вернула ненулевой код возврата

Олимпиады

Как проходит всероссийская олимпиада по информатике?
Я прошел всего 5 этапов: 8-9 классы в школе, 8-11 классы в школе, муниципальный этап, дистанционный тур региональной олимпиады, региональная олимпиада. Далее идет всероссийский тур, но я на него, к сожалению, не попал. Сейчас я расскажу про те задачи, которые мне очень понравились.

Этап среди старшеклассников

Во время тура среди 8-11 классов была задача «Полиномиальные хэш функции» условие которой было записано на двух страницах формата A5. В этом условии была приведена краткая информация о хэш функциях, их истории, была предложена одна такая функция. Задача заключалась в её вычислении для массива входных данных. Нас испугало очень страшное название, сложная терминология, запись суммы её значком (тот который выглядит как буква E) и в результате её мало кто вообще начал решать. Условие сейчас найти, к сожалению, не смогу.

Муниципальный этап

Муниципальный этап получился просто убийственным по сложности.

Вот задача оттуда

Б. Бобр

Ограничения по памяти: 64 Мб
Бобр собирается построить каскад плотин и уютную хатку в русле неширокой реки. Так получилось, что река протекает по идеально прямой траектории, и ширина реки настолько мала, что в рамках данной задачи мы можем ею пренебречь. На берегах реки стоят деревья, которые бобр может использовать для строительства. Ученые решили выяснить, насколько оптимально бобр выбирает места для строительства плотин и хатки с точки зрения минимального суммарного расстояния, на которое необходимо переносить деревья.
Напишите программу, которая по заданным координатам деревьев относительно начала прямого участка реки, если считать ось сонаправленной течению определяет координаты объектов, соответствующие минимальному суммарному расстоянию, на которое необходимо переносить деревья.
Формат входных данных:
<=T<=10 – количество тестовых блоков, идущих друг за другом. В первой строке каждого тестового блока содержится два целых положительных числа 1<=N<=1000, 0<=М<=10, 0<=L<=100 – соответственно количество деревьев, растущих на берегах реки, количество деревьев, необходимое для возведения одного объекта и количество объектов, которые необходимо возвести. В каждой из следующих N строчек записано единственное положительное вещественное число – расстояние в метрах от начала прямого участка реки (самого высокого по течению) до места, где растет соответствующее дерево. Известно, что деревьев гарантированно хватает, чтобы построить все объекты (N>=M*L)
Формат выходных данных:
Для каждого тестового блока в отдельной строке необходимо вывести единственное число - сумму координат мест, в которых необходимо возвести объекты, чтобы суммарное расстояние, на которое потребуется перенести деревья для строительства, было минимальным, указав три точных знака после десятичного разделителя.

Входные данные
2
5 3 1
0.1
1.2
5.6
7.3
9.4
2 2 1
1
2
Выходные данные
7.300
1.000

Решить задачу, если объект один достаточно просто. Но когда объектов больше - приходится применять достаточно сложный раздел программирования, «Динамическое программирование». Учитель, который вел у нас факультатив признался в том, что он плохо представляет как решить эту задачу (совместными усилиями мы вывели значение, которое нужно минимализировать, просто построив несколько графиков, даже не спрашивайте что это за значение - я его благополучно забыл).
В результате задачу на полный балл решил лишь один участник олимпиады.

А вот еще одна задача, решение жюри на которой было пересмотрено (из того же муниципального этапа):

А. Альбатрос
Ограничения по времени: 1 секунда на тест
Ограничения по памяти: 64 Мб
Альбатрос может совершать длительные перелеты, преодолевая длинные расстояния над просторами океана. Орнитологи решили определить, сколько километров может пролететь альбатрос, не посещая сушу. Для этого флотилия плавучих исследовательских лабораторий рассредоточилась по океану и записала данные об изучаемой особи, к которой прикреплена радиометка. Ученые фиксируют момент времени и текущие координаты того места, где они обнаружили альбатроса.
Напишите программу, определяющую расстояние, которое преодолел альбатрос в течение эксперимента, если считать, что в зоне наблюдений наша планета представляет собой идеальный шар радиусом 6366,197 километров.
Формат входных данных:
В первой строке входных данных содержится единственное целое положительное число 1<=T<=10 – количество тестовых блоков, идущих друг за другом. В первой строке каждого тестового блока содержится единственное целое положительное число 2<=N<=1000, количество записей о появлении альбатроса. В каждой из следующих N строчек записаны по двенадцать целых неотрицательных чисел (0<=d1<=90, 0<=m1<=90, 0<=s1<=90, 0<=d2<=90, 0<=m2<=90, 0<=s2<=90, 0<=h<=23, 0<=mt<=59, 0<=sec<=59, 1<=dd<=31, 1<=mm<=12, 2000<=yy<=2012) – соответственно градусы минуты и секунды северной широты, градусы, минуты и секунды западной долготы того места, где плавучая исследовательская лаборатория заметила альбатроса; время в формате часы, минуты, секунды и дата наблюдения в формате день, месяц, год.
Формат выходных данных:
Для каждого из тестовых блоков в отдельной строке необходимо вывести единственное целое число – расстояние, которое преодолел альбатрос, округленное до ближайшего четного целого числа.
Пример входных и выходных данных:
Входные данные
2
3
0 0 0 0 0 0 0 0 0 1 1 2012
0 0 0 0 2 0 0 0 0 3 1 2012
0 0 0 0 1 0 0 0 0 2 1 2012
2
0 0 0 0 0 0 0 0 0 1 1 2012
0 0 0 0 1 0 0 0 0 2 1 2012
Выходные данные
4
2

Достаточно простая задача: необходимо отсортировать значения по дате появления Альбатроса, вычислить длину каждой дуги между двумя точками, а потом их все сложить. В решении принимается допущение, которое позволяет использовать теорему Пифагора.
Но почему же решение было пересмотрено? Взглянем на диапазон минут и секунд.
0<=m1<=90, 0<=s1<=90
Вы, наверное, наивно предположили, что в одном градусе 60 минут? Или что в одной минуте 60 секунд? Ха-ха! Тут же явно написано «90».
Тесты были составлены именно с учетом перевода: в одном градусе 60 минут, в одной минуте 60 секунд. Это безобразие было успешно оспорено нашими учителями.
Самое обидное, что даже пример получился неправильный
В результате задачу не решил, по-моему, вообще никто.

Полный текст муниципального этапа можно найти .

Дистанционный тур

Задачи дистанционного тура были гораздо интереснее. Мне запомнились две задачи.

Вот первая

Г. Герой дня
Ввод/вывод: стандартный

Медиахолдинг «Пермь Великая» отслеживает сообщения блоггеров Пермского края и каждый день пытается выяснить, кто является наиболее популярным в записях для того чтобы включить этого человека в традиционную рубрику «Герой дня».
Для каждой записи, попавшей в список отслеживания, известно количество просмотров и те персоналии, которые в ней упоминаются. Напишите программу, определяющую человека, для которого суммарное количество просмотров для записей, где он упоминается, максимально.
Формат входных данных:
В первой строке входных данных приводится единственное целое число 1<=L<=10000 – количество записей, попавших в обзор за текущий день. В каждой из следующих строк вначале указывается число – количество просмотров соответствующей записи и затем имена и фамилии людей, упоминающихся в записи. Имена и фамилии состоят из букв английского алфавита, число, а также все соседние слова отделяются друг от друга ровно одним пробелом. Суммарная длина строки составляет не более 200 символов.
Формат выходных данных:
В единственной строке выходных данных необходимо вывести имя и фамилию человека, записи с упоминанием которого набрали больше всего просмотров. Если таких людей несколько нужно вывести того, кто идет раньше других по алфавиту.

Входные данные
1
100500 John Travolta John Lennon

5
5 Vasya Pupkin Sergey Syroezhkin
10 Harry Potter
5 Garry Potter Vasya Pupkin
5 Sergey Syroezhkin
12341234463456234123466543342 Arnold Schwarzenegger
Выходные данные
John Lennon
Arnold Schwarzenegger

Именно после этой задачи мне пришла идея «словаря», тип данных с удобным поиском по людям. Если кому интересно - напишу в комментариях, можете спросить в ЛС, но чувствую что это тот еще велосипед.
Необходимо составить список из людей с общим количеством просмотров (посмотрите на человека с идентификатором Arnold Schwarzenegger, требуется длинная арифметика), а затем просто выбрать нужного человека из нашего списка. Чтобы упростить алгоритм наши одиннадцатиклассники использовали хэш-функцию для имени (сумма всех ASCII номеров символов в имени), что существенно ускорило работу программы, коллизии получились небольшими.

Вторая задача или задача архивации

В. Великий архиватор
Ввод/вывод: стандартный
Ограничения по времени: 1 секунда
На планете роботов очень любят автоматическую обработку текстов. Для этого роботы ввели специальную должность Великого Архиватора. В обязанности Великого Архиватора входит составление списка всех слов текста и замена слов на число, обозначающее номер этого слова в списке.
Напишите программу, выполняющую функции Великого Архиватора.
Формат входных данных:
В единственной строке входных данных приводится строка длиной не более миллиона символов, состоящая из строчных и заглавных букв английского алфавита и пробелов. Любые два соседних слова в тексте разделены ровно одним пробелом. Слова считаются одинаковыми, если они равны с точки зрения сравнения строк, причем строчные и заглавные буквы считаются различными.
Формат выходных данных:
В единственной строке выходных данных необходимо вывести последовательность номеров слов текста, причем слова в списке должны быть упорядочены в порядке их появления в тексте. Нумерация слов должна начинаться с единицы.
Примеры входных и выходных данных:
Входные данные
To be or not to be
Why do you cry Willie Why do you cry Why Willie Why Willie Why Willie Why
Выходные данные
1 2 3 4 5 2
1 2 3 4 5 1 2 3 4 1 5 1 5 1 5 1

Пояснение к примерам входных и выходных данных: текст во втором примере не содержит символов перевода строки и возврата каретки.

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

Региональный этап

На этапе региональном было не так весело, тура было два. Я боялся подвести школу и не пройти на следующий этап, плохо показать нашу школу. Поэтому и задания воспринимались не так весело и приятно. В общем: ничего не запомнил оттуда, но получил заветный диплом. Да и условия мне не удалось найти.
На второй день к нам приехали представители местной компании «Прогноз», поиграли с нами в «Что? Где? Когда?», провели викторину. Победителям раздали призы.

Подготовка

Как же я готовился?
Ответ достаточно прост: у меня хорошие учителя. Мне это было интересно и я получал от всего происходящего удовольствие. Я усердно готовился и добился того, чего хотел.

Что делать, если Вам это тоже интересно и Вы хотите принять во всем этом участие?

1. Существуют системы подготовки школьников к олимпиадам по программированию, на них есть тестовая система и куча условий с решениями. Насколько я понимаю, на всех таких системах нужна регистрация. Я готовился при помощи двух:
   • acmp.ru Есть достаточно много задач разной сложности, так же интересен раздел «Курс олимпиадника»
   • http://acm.timus.ru/ Куча задач с самых разных олимпиад, некоторые на английском. В разделе http://acm.timus.ru/offline у нас проводился дистанционный и региональный этапы.
2. Существуют онлайн олимпиады, я участвовал лишь в одной: NetOI от украинцев. Отзыв такой: ХАРДКОР!!! Дальше второго тура не прошел. Код нужно писать ужасно оптимально (я так не умею), для каждого теста индивидуальные условия (удвоенное время программы жюри).

Что же дальше?

Говоря это, я подразумеваю вопрос о том, насколько олимпиадники приспособлены к работе в реальных условиях.
Хоть я и не работал еще в IT индустрии, но я считаю: олимпиадники никак не приспособлены к реальной работе. На таких олимпиадах требуется уметь быстро изобрести «велосипед», знать хорошо алгоритмы. Я с другом занимаюсь написанием небольших игр и понимаю, что гораздо важнее уметь выбрать правильную технологию для твоих целей, уметь найти готовое решение чтобы ускорить разработку, «Велосипеды не нужны». Поправьте меня, если это не так.
Если кого интересует то, чего я в жизни хочу: на самом деле я не очень-то люблю IT и информатику, мечта моя - выучиться на физика-теоретика и заниматься исследованиями. А так как в РФ с этим проблемы я планирую уехать в Канаду или США.

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

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

В лицее города Фрязино эта проблема решается комплексно :

· В профильных математических 8-х классах выделяется дополнительно к программе один час в неделю на предмет информатика

· В профильных классах старшей школы Программирование выделено как отдельный предмет

· С 2007 года у нас действует учреждение дополнительного образования Школа «Юный программист», которая не заменяет, а дополняет школьный курс информатики

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

В последние 6 лет ученики Лицея неоднократно становились победителями и призерами олимпиад самого различного уровня: Заключительного этапа Всероссийской олимпиады, Московской областной олимпиады, Открытой олимпиады «Информационные технологии»», Олимпиады школьников «Ломоносов», Открытой олимпиады школьников по информатике и программированию, Муниципальных олимпиад, Московской олимпиады по программированию, Всероссийского конкурса КИТ и других.

Как готовить к олимпиадам по информатике в таких условиях?

· Найти способных учеников и увлечь их программированием

· Удержать от «соблазнов» on-line жизни

· Стать им другом и сформировать из них команду

· Тесно взаимодействовать с родителями, администрацией, классными руководителями и учителями - предметниками

· Быть готовым к тому, что на каком-то этапе кто-то из них вас перерастет

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

Не секрет, что уровень подготовленности по информатике городских и сельских школьников резко отличается. К середине 90-х годов сложилась такая практика, что призерами олимпиад областного уровня становились в основном ученики из городов области, прежде всего, из самого Белгорода. Причина этого – недостаточное оснащение компьютерной техникой , острая нехватка педагогических кадров на селе и недостаточная их квалификация. Учитель информатики сельской школы в 90% случаев совместитель (обычно учитель математики или физики), что приводит к перегрузке, и как следствие к невозможности уделять достаточно времени методике преподавания информатики и индивидуальной работе с учащимися. С другой стороны, сельские ученики часто не имеют возможности посещать кружки, занятия, курсы компьютерной грамотности вне школы.

Подготовка к олимпиаде требует отбора детей с определённым уровнем мотивации. Каждый учитель начинает учебный год с поиска таких детей – поиска одарённых детей для участия в предметных олимпиадах.

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

Как правило, при подготовке к олимпиаде у каждого учителя возникают следующие вопросы:

1. Как, среди уменьшающегося количества часов, выкроить время на подготовку?

2. Как можно мотивировать учеников?

3. И где найти силы учителю, который завален отчетами, документацией, должен вести воспитательную работу ?

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

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

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

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

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

Задачи, которые я ставлю перед собой при работе с одарёнными детьми:

1. учесть степень и меру самораскрытия одарённых учащихся;

2. удовлетворить их потребности в информатизации.

Основные направления деятельности с одарёнными детьми:

3. самообразование.

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

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

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

Факультатив должен работать по определенной программе, которая не дублирует учебную.

Факультативное занятие может проходить следующим образом:

1. называется тема;

2. перечисляются задания на данную тему;

3. выбирается одна из наиболее популярных или интересных задач;

4. устно совместно с ребятами обсуждается алгоритм решения;

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

6. раздаётся материал для изучения новой темы следующего занятия.

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

Для хорошей подготовки ученика важно, в первую очередь, «не только наполнить чашу знаний, но и зажечь факел».

Так как ребята приходят с разным уровнем подготовки приходиться использовать индивидуальные и групповые формы работы. Индивидуальные формы работы зачастую сопряжены с самообразованием. Здесь учитель выступает в роли консультанта.

Групповые формы работы используются для ребят с определённым багажом знаний.

Есть еще один метод работы с учащимися – работать индивидуально. Один на один. А «работать индивидуально» исходит уже не от учителя, а от ученика. Такие встречи носят характер консультаций, хотя иногда это совместный поиск решения какой-либо задачи.

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

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

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

Олимпиады однозначно нужны детям как путь к самовыражению, к развитию. С одаренными детьми следует работать в течение всего года, нельзя понимать олимпиады как определенное мероприятие на 3 - 4 часа.

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

Как же готовиться к все время усложняющимся олимпиадам?

Я считаю наиболее правильной систему моих преподавателей.

На факультативном занятии (научить решать олимпиадные задачи можно только на факультативе, где занимается не более 6-7 человек, иначе - бардак) преподаватель кратко объясняет теорию. Затем предлагает задачи по только что объясненной теме не объясняя (но отлично зная!) решения ни одной из них. Ученики предлагают свои идеи по поводу решения, т. е. занятие проходит в форме семинара под руководством преподавателя. В случае затруднения преподаватель может помочь ученикам, предложив некоторую идею. Затем, в случае если есть возможность написать программу за достаточно короткое время, программа реализуется на компьютере. Однако здесь есть свои трудности: в случае разного уровня подготовки учащихся, время, затрачиваемое на написание программы, сильно различается, что приводит к тому, что уже решившие задачу сидят и скучают (при этом постепенно теряют интерес к занятиям), а те, кто еще пишет нервничают, смотрят на тех кто скучает, завидуют и также теряют интерес к занятиям. Здесь надо найти золотую середину. Время от времени следует организовывать мини или полномасштабные олимпиады по информатике, с задачами уровня не ниже областной городской, но со сниженными требованиями к участникам (разрешается ходить по кабинеты, иногда общаться, пить чай и т. п.). Важной частью подготовки является разбор нерешенных задач с олимпиады (такие чаще всего остаются, особенно после олимпиад достаточно высокого уровня). Здесь учитель часто находится в равных условиях с учеником, так как и он сам не знает решения такой задачи. Домашнее задание следует давать в разумных количествах (лучше больше) и по теме или, при подготовке к олимпиаде (обычно за 2 недели) задачи с прошлых олимпиад. Те кто не сильно хочет заниматься информатикой задание все равно не сделают, а те, кто хочет - сделают все. Для любимого предмета каждый человек может найти время.

Чтобы научиться решать задачи необходимо выполнить 7 пунктов:

1) Знать математику. Очень часто встречаются математические задачи.

2) Уметь общаться. В ходе обсуждения рождается множество новых идей.

3) Иметь способности. Я так и не научился играть на пианино:)

4) Осознавать, что тебе это нужно. На самом деле олимпиадные задачи - всего лишь "массаж для мозгов", но если бы их не было, вы бы умели писать программы так хорошо?

5) Сильно хотеть победить. Но не до умопомрачения.

6) Научить других решать задачи. Не обязательно. Но когда объясняешь другим, начинаешь лучше понимать сам.

7) (Самое главное) Быть хорошим человеком. Если вы плохой человек, то со всем вашим умение писать программы вы никому не нужны.

Чтобы научиться хорошо решать задачи необходимо кроме этого выполнить еще один пункт:

ПОСТОЯННЫЕ ТРЕНИРОВКИ . Каждая решенная задача должна доставлять вам удовольствие, и чем дольше вы над ней сидели тем больше радости от успешного ее решения (главное не перегибать палку - после 10 бессонных ночей над задачей ее решение вряд ли доставит вам радость).

Литература

1. , ., Москвина преподавания основ программирования в процессе создания компьютерных игр. // Мат-лы междунар. конференции "Новые информационные технологии в университетском образовании". Новосибирск, 1995, с.145-147.

2. Моя первая программа на Паскале: от компьютерных игр к профессиональному программированию. / и др. Вып. 1-3. Прилож. Новосибирск: НГУ, 1996.

Разбор задач олимпиадного характера.

Методика подготовки к районному этапу Всероссийской олимпиады школьников по информатике.

Материалы мастер-класса (презентация)

на РМО учителей информатики.

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

МОУ «Лицей №23»

Шуваловой Светланы Юрьевны.

В данной работе обобщены материалы, представленные мною на РМО учителей информатики в 2011, 2012 годах по итогам школьных этапов Всероссийской олимпиады школьников по информатике.

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

Слайд 1.

Цель олимпиады по информатике - способствовать поиску наиболее одаренных школьников .

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

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

Слайд 2.

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

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

Слайд 3.

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

Из опыта олимпиад можно выделить наиболее часто встречающиеся разделы информатики, к которым с можно отнести тематику задач:

• комбинаторика;
• сортировка и поиск;
• обработка последовательностей;
• алгоритмы на графах;
• элементы вычислительной геометрии.
• перебор вариантов и методы его сокращения;
• динамическое программирование.

Слайд 4.

Этапы решения олимпиадных задач:

• Разбор условия задачи.
• Формализация условия задачи.
• Разработка алгоритма решения задачи.
• Программная реализация алгоритма.
• Отладка и тестирование программы.
• Отправка решения на проверку.

Слайд 5.

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

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

Необходимо помнить при написании программы, - это сохранение редактируемых файлов во время тура.

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

Слайд 6.

Часто встречающиеся ошибки:

• Не соответствует формат ввода-вывода данных условию задачи

• Рассмотрены не все возможные случаи

• Не правильно задан тип данных (размерность)

• Потеря редактируемых файлов во время тура

Слайд 7.

Минимальная база знаний для олимпиады по информатике.

Язык программирования:

• базовые алгоритмические конструкции,
• стандартные математические функции,
• процедуры и функции для обработки строковых переменных,
• процедуры и функции для работы с массивами.

Типовые алгоритмы.

Слайд 8.

Задачи на олимпиадах по информатике не всегда соответствуют «Стандарту основного и среднего (полного) общего образования по информатике и ИКТ». Более того, в качестве решения этих задач на олимпиаде требуется предъявить отлаженные программы, написанные на языке программирования высокого уровня, а не описания алгоритмов.

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

Слайд 9.

Интернет-ресурсы для подготовки к олимпиадам по информатике:

http://algolist.manual.ru/

Разбор задач школьного тура олимпиады 2011 года.

Задача №1 «Запись музыки» (15 баллов)

Проверить, поместится ли на диске компьютера музыкальная композиция, которая длится m минут и n секунд, если свободное дисковое пространство 6 мегабайт, а для записи одной секунды звука необходимо 16 килобайт.

Алгоритм решения:

Использование расчетной формулы и условного оператора

Задача №2 «Кодовый замок сейфа» (20 баллов)

Из 10 букв нужно набрать 3. Повторение букв допустимо. Подсчитать количество возможных комбинаций кодов.

Алгоритм решения:

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

Задача №3 «Прямоугольник» (30 баллов)

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

Алгоритм решения:

Если максимальная координата по оси Х левых нижних вершин прямоугольников будет меньше минимальной координаты правых верхних вершин и максимальная координата по оси У левых нижних вершин прямоугольников будет меньше минимальной координаты правых верхних вершин, то общая площадь есть.

Используется типовой алгоритм нахождения максимального (минимального) элемента массива.

Задача №4 «Магический квадрат» (35 баллов)

В квадрате размером 3x3 клетки поставить числа 1, 2, ... ,9 так, чтобы суммы чисел, стоящих в каждом ряду, столбце, в каждой диагонали, были равны.

Алгоритм решения. Задача на способ заполнения двумерного массива.

(индийский способ):

1. В середине верхней строки ставим 1 , в последней строке соседнего справа столбца 2 .
2. Следующие числа ставят в диагональном направлении.
3. Дойдя до правого края квадрата, переходят к крайней левой клетке ближайшей вышележащей строки.
4. Дойдя до верхнего края квадрата, переходят к самой нижней клетке соседнего справа столбика. Примечание. Дойдя до правой верхней угловой клетки, переходят к левой нижней.
5. Дойдя до уже занятой клетки, переходят к клетке, лежащей непосредственно под последней заполненной клеткой.
6. Если последняя заполненная клетка находится в нижнем ряду квадрата, переходят к самой верхней клетке в том же столбце.

Разбор задач школьного тура олимпиады 2012 года.

Задача 1.

Напечатать все трехзначные десятичные числа, сумма цифр которых равна данному числу.

Алгоритм решения:

Один из вариантов решения перебором:

var a,b,c,n,k:integer;

begin

write("n="); readln (n);

for a:=1 to 9 do

For b:=0 to 9 do

For c:=0 to 9 do

If a+b+c=n then

begin

writeln (a,b,c," ");

k:=k+1;

end;

Writeln;

Writeln ("k=",k) ;

Writeln;

end.

Второй вариант решения перебором:

Var a,b,c,n,k,m: integer;

begin

write("n="); readln(n);

for m:=100 to 999 do

begin

c:=m mod 10;

b:= m div 10 mod 10;

a:= m div 100;

if a+b+c=n then

begin

write(m:5);

k:=k+1;

end;

end;

writeln("k=",k)

end.

Задача 2. «Малыш и Карлсон».

Малыш и Карлсон живут в прямоугольной комнате размером А х В . Как им посчитать, сколько понадобится квадратных ковриков со стороной С , чтобы полностью покрыть пол комнаты? (Малыш и Карлсон не умеют ни делить, ни умножать.) Напишите программу для решения этой задачи.

Алгоритм решения:

Во внешнем цикле по одной из сторон комнаты (while p) резервируем место для ряда (р:=р+с ), затем во внутреннем цикле по другой стороне (while m) проверяем, сколькими ковриками можно закрыть ряд, оператор m:=m+с резервирует место для коврика, а оператор kovrik:=kovrik+1 подсчитывает общее количество уложенных ковриков.

var a, b, с, kovrik, m, p: integer;

begin

readln(a, b, с);

kovrik:= 0;

p:= 0;

while p

begin

p:= p + c;

m:= 0;

while m

begin

m:= m + c;

kovrik:= kovrik + 1

end;

writeln (kovrik)

end.

Задача 3. «Бактерии».

Колония состояла из n бактерий (не более 30000). В нее попал вирус, который в первую минуту уничтожил одну бактерию, а затем разделился на два новых вируса. Одновременно каждая из оставшихся бактерий тоже разделилась на две новые. В следующую минуту возникшие два вируса уничтожили две бактерии, а затем все вирусы и бактерии снова разделились и так далее. Будет ли эта колония жить бесконечно долго или вымрет?

Ваша программа должна:

• Запросить число бактерий n ;
• Выяснить и сообщить: через сколько суток, часов и минут колония бактерий прекратит свое существование или выдать сообщение, что колония вечна.

Пример ответа: Для n=A. Ответ – B суток C часов D минут (где A, B, C, D – числовые значения).

Алгоритм решения:

Программа на языке программирования Паскаль.

Var a, b, c: shortint;

t, n, v: longint;

begin

Write (‘Начальная численность колонии -"); readln (n);

v:=1;

while n>0 do

Begin

t:= t + 1; { минуты}

n:= (n - v) * 2; { бактерии}

v:= v * 2; { вирусы}

end;

a:= t div 1440;

b:= (t – a * 1440) div 60;

c:= t – a - b;

Write ("Колония прекратит существование через ",a, " суток ", b, " часов ", c , " минут");

end.

Задача 4.

Дан прямоугольник со сторонами А и В, где А, В - натуральные числа. Начинаем отсекать от него квадраты (рис.1). Сколько таких квадратов можно отсечь, если каждый раз отсекается самый большой квадрат?

Алгоритм решения:

1 способ.

Для решения этой задачи нам нужны функции МАХ и MIN , для их определения используем подпрограммы-функции.

Введем:

• вспомогательные переменные X и Y (Y>=X) , соответствующие уменьшающимся сторонам прямоугольника;
• вспомогательную переменную D , которая определяет уменьшение размеров прямоугольника после очередного отсечения наибольшего квадрата, сторона которого находится как X:=MIN(D,X).

Организуем цикл, в котором сторона Y уменьшается каждый раз на MIN(D,X) до тех пор, пока не останется последний квадрат или Y не станет меньше X. В последнем случае переименовываем стороны оставшегося прямоугольника как Y:=MAX(D,X) и X:=MIN(D,X) и продолжаем цикл.

Программа на языке программирования Паскаль.

var a, b, d, k, x, y: integer;

function min (i, j: integer): integer;

begin

if i

else min:=j

end;

function max (i, j: integer): integer;

begin

if i

else max:=i

end;

begin

repeat

Writeln ("vvedite dva naturalnix chisla");

Readln (a, b);

until (a>0) and (b>0);

k:=1;

x:=min(a,b);

y:=max(a,b);

while x y do

begin

k:=k+1;

d:=y-x;

y:=max(d,x);

x:=min(d,x);

end;

Writeln ("iskomoe chislo kvadratov:", k)

end.

2 способ.

Задачу можно решить с помощью стандартных функций PASCAL : Y DIV X и Y MOD X, используя алгоритм Евклида.

Алгоритм решения:

Организуем цикл, в котором формируем остатки от деления r 0 , r 1 , r 2 ,..., r n , r n+1 до тех пор, пока один из этих остатков не станет равен нулю r n+i =0 . Таким образом, мы строим функцию порождения остатка от деления r n+i = r n mod r n-i , где r 0 = А и r i =В . Для той же самой системы остатков мы можем посчитать, сколько раз нацело укладывается остаток r n-i в r n .

{алгоритм Евклида}

var А, В, R0, R, R1, K: integer;

begin

repeat

Write ("ВВЕДИТЕ НАТУРАЛЬНОЕ ЧИСЛО А = ");

Readln (А);

Write ("ВВЕДИТЕ НАТУРАЛЬНОЕ ЧИСЛО В

Readln (В);

until (В > 0) and (А > 0) and (А >=В);

R0:= А;

R1:= В;

К:= R0 div R1;

while R0 mod R1 0 do

begin

R:= R0 mod R1;

R0:= R1;

R1:= R;

К:= К + R0 div R1

end;

Writeln ("ИСКОМОЕ ЧИСЛО КВАДРАТОВ К = ",К);