Подготовка школьников к олимпиадам по информатике в лицее. Программа индивидуальной подготовки к муниципальному этапу Всероссийской олимпиады школьников по предмету «Информатика и ИКТ Подготовка учеников к олимпиадам по информатике
Сайт, поддерживаемый Московским центром непрерывного математического образования, содержит большое количество задач по программированию различного уровня. Идеально подходит для тех, кто делает первые шаги в программировании: во многих разделах есть ссылки на теоретический материал по соответствующий теме, к большинству задач приложен подробный разбор. Для всех заданий доступна автоматизированная проверка решений.
Олимпиада Всероссийская олимпиада по информатике Региональный этап пройдет 16 и 18 января 2020 года
Состязание для школьников 5-11 классов. Победители и призеры финала получают льготы при поступлении в вузы
Информатика
Codeforces.com . Портал, объединяющий огромное количество участников соревнований по программированию по всему миру. На сайте регулярно проводятся онлайн-соревнования для школьников самого разного уровня: от начинающих до многократных чемпионов мира. Многие известные компании, в том числе ВКонтакте, Mail.Ru, Тинькофф Банк и AIM Tech проводят на платформе официальные соревнования.
Помимо этого, на портале обсуждается все, что связано с программированием, начиная от только-только опубликованных статей о структурах данных и заканчивая эмоциями о недавно прошедшем соревновании. На сайте также содержится большой архив задач, доступных для автоматизированной проверки.
Вики-конспекты . Энциклопедия по дискретной математике и теории алгоритмов, составленная студентами ИТМО. В ней описано большинство алгоритмов, используемых на олимпиадах по программированию. Многие статьи содержат примеры задач и псевдокоды приведенных алгоритмов. Конспекты написаны очень подробно и качественно. Это один из немногих ресурсов на русском языке по данной теме.
Maximal . Мини-энциклопедия, содержащая наиболее популярные алгоритмы в олимпиадной информатике, к большинству из которых приведены реализации и примеры использования. Сайт отличается чуть более неформальным стилем изложения (что иногда может сказаться на качестве статей или корректности алгоритмов), однако он облегчает восприятие информации. На сайте размещены ссылки на полезные книги для более детального изучения приведенных алгоритмов, а также разобраны некоторые конкретные задачи, представляющие особенный интерес.
Олимпиады по информатике . Сайт, посвященный олимпиадам школьников по программированию в Санкт-Петербурге, официальный сайт Всероссийской командной олимпиады школьников (ВКОШП), индивидуальной олимпиады школьников по информатике и программированию (ИОИП). Одним из главных достоинств этого сайта является очень богатый архив проводимых в России мероприятий, в том числе Всероссийской олимпиады: сайт содержит презентации с разбором задач и результатами соревнований. Также здесь регулярно проводятся личные и командные соревнования для школьников.
Olympiads.ru . Сайт, посвященный олимпиадам школьников по программированию в Москве, официальный сайт Открытой олимпиады школьников по программированию, задачи на которой не уступают по сложности заданиям Всероссийской, а иногда изящнее и интереснее. Помимо этого, олимпиада включает заочный тур, задачи которого часто требуют изучения новых алгоритмов в течение соревнования. На сайте опубликованы материалы прошедших соревнований, а также ссылки на информацию о предстоящих событиях.Книги
Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ . Данная книга является классическим учебным пособием с подробным описанием алгоритмов и структур данных, а также базовыми сведениями из дискретной математики, необходимыми каждому программисту. Помимо этого книга содержит огромное количество упражнений различной сложности, которые будут интересны и самому искушенному читателю. В ней очень удачный стиль изложения, и хотя она ориентирована на студентов, большая часть материала будет доступна и школьникам.
Элективный курс
«Олимпиадная информатика»
Программа 1. «Олимпиадная информатика» для учащихся 5-6 классов
Программа 2. «Олимпиадная информатика» для учащихся 7-8 классов
Программа 3. «Олимпиадная информатика» для учащихся 9-11 классов
Разработчик: Ярошевская Вера Ивановна
г. Москва 2016 г.
Программа содержат:
Пояснительную записку;
Методических указания по изучению тем;
Учебно-тематический план и программы подготовки к олимпиадам по информатике.
Электронные учебные материалы
Пояснительная записка.
Важной задачей образования является работа с одаренными учащимися, их подготовка к предметным олимпиадам. Олимпиада по информатике занимает одно из ведущих мест, в связи с интенсивным развитием информационных технологий как в нашей стране, так и за рубежом.
Участие в олимпиадах позволяет развивать творческие способности школьников и обеспечивает высокую мотивацию к образовательной деятельности.
Классическая олимпиада по информатике - это олимпиада по программированию, которая предполагает наличие обширных познаний в математике и языках программирования.
Решение олимпиадных задач позволяет раскрыть творческий потенциал школьника во время подготовки к олимпиаде, учитывая возрастные особенности ребенка и перспективу его развития. Использование многоуровневых олимпиадных задач, позволяет школьникам применить свой творческий потенциал, независимо от уровня подготовки.
Курс занятий по Олимпиадной информатике (решение олимпиадных задач по информатике) ориентирован на учащихся 5-11х классов, обладающих повышенной мотивацией к изучению информатики и имеющих начальные знания в области алгоритмизации на уровне понимания простейших алгоритмов.
Данный элективный курс позволяет провести непрерывную подготовку к олимпиадам по информатике начиная с 5-го класса, используя методическую коллекцию олимпиадных задач. В курсе использован системный подход при разработке модулей непрерывной подготовки одаренных детей к олимпиадам по информатике.
Основная цель курса: раскрыть значение программирования и суть профессии программиста, ознакомление учащихся со средой и основами программирования на языке PascalABC.NET, подготовить учащихся к практическому использованию полученных знаний при решении учебных задач, а затем профессиональной деятельности, вовлечение учащихся в участие в олимпиадах по программированию разного уровня.
Основные задачи курса: развитие навыков программирования алгоритмических структур; развитие логического мышления учащихся; развитие интеллекта учащихся.
Данная программа представляет большую практическую значимость с точки зрения совершенствования непрерывной работы с одаренными школьниками в рамках олимпиадного движения по информатике и школьного образования.
Методические указания по изучению тем
Олимпиадные задачи по информатике охватывают следующие ключевые разделы:
1. Математические основы информатики.
Этот раздел является фундаментальной основой информатики. В олимпиадах по информатике это особенно важно, так как школьникам сложно достичь успешности на олимпиадных состязаниях без хорошей подготовки в области теории множеств, логики, теории графов и комбинаторики.
Для успешного выступления на олимпиаде по информатике школьники должны
знать/понимать:
основы терминологии функций, отношений и множеств;
перестановки, размещения и сочетания множества;
формальные методы символической логики высказываний
основы построения рекуррентных соотношений;
основные методы доказательств;
основы теории чисел;
уметь:
выполнять операции, связанные с множествами, функциями и отношениями;
вычислять перестановки, размещения и сочетания множества, а также интерпретировать их значения в контексте конкретной задачи;
решать типичные рекуррентные соотношения;
осуществлять формальные логические доказательства и логическое рассуждение для моделирования алгоритмов;
определять, какой вид доказательства лучше подходит для решения конкретной задачи;
использовать основные алгоритмы теории чисел;
1. Отношения, функции и множества.
2. Основные геометрические понятия.
3. Основы логики.
4. Основы вычислений.
5. Методы доказательства.
6. Основы теории чисел.
7. Основы алгебры.
8. Основы комбинаторики.
9. Теорию графов.
10. Основы теории вероятностей.
11. Основы теории игр.
2. Разработка и анализ алгоритмов.
В этом разделе определяется основная способность учащихся знать классы алгоритмов, которые предназначены для решения определенного набора известных задач, понимать их сильных и слабых сторон, применять различные алгоритмы в заданном контексте с оценкой его эффективности.
элементы теории алгоритмов;
основные структуры данных;
основные понятия теории графов, а также их свойства и некоторые специальные случаи;
связь графов и деревьев со структурами данных, алгоритмами и вычислениями;
свойства, присущие «хорошим» алгоритмам;
вычислительную сложность основных алгоритмов сортировки, поиска;
понятие рекурсии и общую постановку рекурсивно-определенной задачи;
простые численные алгоритмы;
основные комбинаторные алгоритмы;
основные алгоритмы вычислительной геометрии;
наиболее распространенные алгоритмы сортировки;
наиболее важные алгоритмы на строках;
фундаментальные алгоритмы на графах: поиск в глубину и в ширину, нахождение кратчайших путей от одного источника и
основы динамического программирования;
основные положения теории игр;
уметь:
выбирать подходящие структуры данных для решения задач;
использовать вышеназванные алгоритмы в процессе решения задач;
определять сложность по времени и памяти алгоритмов;
определять вычислительную сложность основных алгоритмов сортировки, поиска;
реализовывать рекурсивные функции и процедуры;
использовать при решении практических задач вышеназванные знания и умения.
Основными темами этого раздела являются:
1. Алгоритмы и их свойства.
2. Структуры данных
3. Основы анализа алгоритмов.
4. Алгоритмические стратегии.
5. Рекурсия.
6. Фундаментальные вычислительные алгоритмы.
7. Числовые алгоритмы.
8. Алгоритмы на строках.
9. Алгоритмы на графах.
10. Динамическое программирование.
11. Алгоритмы теории игр.
3. Основы программирования.
В этом разделе закладывается условие успешного выступления учащихся на олимпиадах по информатике. Данный раздел включает в себя материал по фундаментальным концепциям программирования, основным структурам данных и алгоритмам, а также собственно языки программирования.
В рамках этого раздела школьники должны знать/понимать:
основные конструкции программирования;
концепцию типа данных как множества значений и операций над ними;
основные типы данных;
основные структуры данных: массивы, записи, строки, связные списки, стек;
представление данных в памяти;
альтернативные представления структур данных с точки зрения производительности;
основы ввода/вывода;
операторы, функции и передача параметров;
статическое, автоматическое и динамическое выделение памяти;
управление памятью во время исполнения программы;
методы реализации стеков, очередей;
методы реализации графов и деревьев;
механизм передачи параметров;
особенности реализации рекурсивных решений;
стратегии, полезные при отладке программ;
уметь:
анализировать и объяснить поведение простых программ, включающих фундаментальные конструкции;
модифицировать и расширить короткие программы, использующие стандартные условные и итеративные операторы и функции;
разработать, реализовать, протестировать и отладить программу, которая использовать все наиболее важные конструкции программирования;
применять методы структурной (функциональной) декомпозиции для разделения программы на части;
реализовать основные структуры данных на языке высокого уровня;
реализовать, протестировать и отладить рекурсивные функции и процедуры;
использовать при решении практических задач вышеназванные знания и умения и уверенно программировать на олимпиадах по информатике на языке программирования Pascal.
Основными темами этого раздела являются:
1. Язык программирования Pascal.
2. Основные конструкции программирования.
3. Переменные и типы данных.
4. Типы структур данных.
4. Методы вычислений и моделирование.
Раздел «Методы вычислений и моделирование» представляет область информатики, тесно связанную с вычислительной математикой и численными методами.
В рамках этого раздела школьники должны знать/понимать:
понятия ошибки, устойчивости, машинной точности и погрешности приближенных вычислений;
источники погрешности в приближенных вычислениях;
основные алгоритмы решения задач вычислительной математики: вычисление значения и корней функции; вычисление периметра, площади и объема, вычисление точки пересечения двух отрезков и др.;
понятия модели и моделирования, основные типы моделей;
компоненты компьютерной модели и способы их описания: входные и выходные переменные, переменные состояния, функции перехода и выхода, функция продвижения времени;
основные этапы и особенности построения и использования компьютерных моделей;
уметь:
вычислять оценку погрешности приближенных вычислений;
использовать при решении задач основные методы вычислительной математики;
формализовывать объекты моделирования;
разрабатывать компьютерные модели простейших объектов;
использовать при решении практических задач компьютерные модели в виде «черного ящика»;
использовать при решении практических задач вышеназванные знания и умения.
Основными темами этого раздела являются:
1. Основы вычислительной математики.
2. Введение в моделирование.
Учебно-тематическое планирование к программе «Олимпиадная информатика»
На основании выше сказанного составлены программы 1, 2 и 3, которые учитывают возрастные особенности учащихся.
Программа 1. Для учащихся 5-6 классов
| Тема | Количество часов |
| 1 |
|
| Типы олимпиадных задач по информатике для 5-6 классов. | 2 |
| Отношения (рефлексивность, симметричность, транзитивность, эквивалентность, лексикографический порядок) Точка, прямая, отрезок, вектор, угол Декартовы координаты в евклидовом пространстве Треугольник, прямоугольник, многоугольник Выпуклые многоугольники Основы логики Логические переменные, операции Таблицы истинности Булевы функции Основы вычислений Основы вычислений: Правила суммы и произведения Рекуррентные соотношения Методы доказательства Прямые доказательства Доказательство через контрпример Доказательство через противопоставление Основы теории чисел Простые числа. Деление с остатком Наибольший общий делитель Основы комбинаторики Перестановки, размещения и сочетания: Основные определения Теория графов Типы графов Маршруты и связность Деревья Остовные деревья Основы теории вероятностей Понятие вероятности Основы теории игр Понятие игры и результата игры Простейшие игры и стратегии | 20 |
| Этапы решения олимпиадной задачи: формализация условия задачи, выбор метода решения задачи. План разбора олимпиадной задачи по информатике. | 5 |
| Алгоритмы Алгоритмы и их свойства Понятие алгоритма Концепции и свойства алгоритмов Запись алгоритма на неформальном языке Структуры данных Простые базовые структуры Множества Последовательности Списки Неориентированные графы Алгоритмические стратегии Алгоритмы полного перебора Рекурсия Понятие рекурсии Простые численные алгоритмы Классические комбинаторные алгоритмы Алгоритмы с подмножествами: генерация, восстановление по номеру и построение номера, генерация следующего и предыдущего (прибавление и вычитание единицы) Алгоритмы с сочетаниями и перестановками: генерация, восстановление по номеру и построение номера, генерация следующего и предыдущего. Алгоритмы последовательного и бинарного поиска Числовые алгоритмы Разложение числа на простые множители Решето Эратосфена Алгоритм Евклида Алгоритмы на строках Поиск подстроки в строке. Наивный метод Алгоритмы на графах Вычисление длин кратчайших путей в дереве Обход графа в ширину и в глубину Способы реализации поиска в ширину (“наивный” и с очередью) Геометрические алгоритмы Алгоритмы определения совпадения точек, лучей, прямых и отрезков Решение / моделирование алгоритмических задач в среде Исполнителя | 20 |
| Введение в реальную среду программирования как инструмент реализации алгоритмов на компьютере Типовые инструменты среды программирования (режим помощь, режим редактирования, режим отладки) Среда программирования. Начало программирования. Языки программирования Переменные и типы данных Типы структур данных Особенности программирования фундаментальных алгоритмов. Введение в моделирование. Классификация языков программирования Процедурные языки Переменные, типы, выражения и присваивания Основы ввода/вывода Операторы проверки условия и цикла Концепция типа данных как множества значений и операций над ними Примитивные типы Массивы Стратегии решения задач Роль алгоритмов в процессе решения задач Среды программирования Понятия модели и моделирования Основные типы моделей www.olympiads.ru . | 20 |
Программа 2. Для учащихся 7-8 классов
| Тема | Количество часов |
| Положение о Всероссийской олимпиаде школьников. Методические рекомендации по проведению школьного, муниципального и регионального этапов Всероссийской олимпиады школьников по информатике. | 1 |
| Типы олимпиадных задач по информатике для 7-8 классов. | 2 |
| Основные разделы математической информатики. Функции, отношения и множества Обратная функция, композиция Множества (дополнения, декартовы произведения) Основные геометрические понятия Евклидово расстояние Векторное и скалярное произведение на плоскости Основы логики Логические выражения Формы задания и синтез логических функций Преобразование логических выражений Основы вычислений Основы вычислений: Арифметические и геометрические прогрессии Числа Фибоначчи Методы доказательства Доказательство через противоречие Математическая индукция Основы теории чисел Основная теорема арифметики Взаимно простые числа Основы алгебры Многочлены и операции над ними. Решение квадратных уравнений. Теорема Виета Основы комбинаторики Тождество Паскаля Биномиальная теорема Теория графов Операции над графами Раскраска графов Эйлеровы и гамильтоновы графы Основы теории вероятностей Понятие математического ожидания. | 20 |
| Алгоритмы Алгоритмы и их свойства Ориентированные графы Деревья Основы анализа алгоритмов Стандартные классы сложности Асимптотический анализ поведения алгоритмов в среднем и крайних случаях Алгоритмические стратегии "Жадные" алгоритмы Рекурсия Рекурсивные математические функции Простые рекурсивные процедуры Реализация рекурсии Фундаментальные вычислительные алгоритмы Квадратичные методы сортировки (сортировка методом выбора, сортировка вставками) Сортировка подсчетом за линейное время. Алгоритмы сортировки за время (быстрая сортировка, пирамидальная сортировка Алгоритмы на строках Проверка графа на связность Алгоритмы поиска кратчайшего пути во взвешенных графах Основная идея динамического программирования. Рекурсивная реализация и развертывание в цикл. Задачи с монотонным направлением движения в таблице Задача о рюкзаке - решение методом динамического программирования Геометрические алгоритмы Представление точек, прямых и отрезков на плоскости | 20 |
| Среда программирования . Языки программирования Переменные и типы данных Типы структур данных Механизмы абстракции. Особенности программирования фундаментальных алгоритмов. Основы синтаксиса и семантики языков высокого уровня
Функции и передача параметров Свойства объявлений (связывание, область видимости, блоки и время жизни) Обзор проверки типов Записи Стратегии выбора подходящей структуры данных Процедуры, функции и итераторы как механизмы абстракции Модули в языках программирования Стратегии реализации алгоритмов Реализация рекурсии Введение в моделирование. Компоненты компьютерной модели и способы их описания: входные и выходные переменные, переменные состояния, функции перехода и выхода, функция продвижения времени Основные этапы и особенности построения компьютерных моделей Основные этапы использования компьютерных моделей при решении практических задач Типовые примеры решения задач по разделам из коллекции www.olympiads.ru | 25 |
Программа 3. Для учащихся 9-11 классов
| Тема | Количество часов |
| Положение о Всероссийской олимпиаде школьников. Методические рекомендации по проведению школьного, муниципального и регионального этапов Всероссийской олимпиады школьников по информатике. | 1 |
| Типы олимпиадных задач по информатике для 9-11 классов. | 2 |
| Основные разделы математической информатики. Функции, отношения и множества Вполне упорядоченные множества Мощность и счетность Основы логики Минимизация булевых функций Основные законы логики суждений Логика предикатов Основы вычислений Основы вычислений: Принцип включения-выключения Матрицы и действия над ними Методы доказательства Структура формальных доказательств Основы теории чисел Кольцо вычетов по модулю Основы алгебры Симметрические многочлены Понятие группы Свойства групп Теоремы о гомоморфизме и изоморфизме Основы комбинаторики Коды Грея: подмножества, сочетания, перестановки Таблицы инверсий перестановок Разбиения на подмножества. Числа Стирлинга Скобочные последовательности Теория графов Покрытия и независимость Укладка графов. Плоские (планарные) графы Двусвязность графа. Мосты, блоки, точки сочленения Связь ориентированных ациклических графов и отношений порядка. Транзитивное замыкание Двудольные графы Потоки и сети Основы теории вероятностей Аксиомы теории вероятностей Формула полной вероятности и формула Байеса. Условное математическое ожидание Основы теории игр Игры на матрицах | 20 |
| Алгоритмы Алгоритмы и их свойства Пирамида и дерево отрезков Сбалансированные деревья Хэш-таблицы и ассоциативные массивы Бор Основы анализа алгоритмов Компромисс между временем и объемом памяти в алгоритмах Использование рекуррентных отношений для анализа рекурсивных алгоритмов NP-полнота Алгоритмические стратегии Алгоритмы "разделяй и властвуй" Перебор с возвратом Эвристики Рекурсия Стратегия "разделяй и властвуй" Рекурсивный перебор с возвратами Фундаментальные вычислительные алгоритмы Алгоритмы сортировки ( сортировка слиянием) Цифровая сортировка Алгоритм вычисления номера слова в лексикографически упорядоченном множестве перестановок его символов Арифметика многоразрядных целых чисел Числовые алгоритмы Расширенный алгоритм Евклида. Способы реализации алгоритма без деления Решение линейных сравнений с помощью алгоритма Евклида Эффективная проверка числа на простоту Быстрые алгоритмы разложения чисел на простые множители. Алгоритмы на строках Алгоритмы поиска подстроки в строке за Периодические и циклические строки Алгоритм поиска нескольких подстрок за линейное время Алгоритмы на графах Топологическая сортировка графа, нахождение компонент сильной связности и построение диаграммы порядка Циклы отрицательной длины - критерий наличия, поиск Задача о синхронизации времени и задача о системе неравенств Алгоритм поиска эйлерова цикла (в том числе лексикографически минимального) Нахождение транзитивного замыкания графа Алгоритмы нахождения взвешенных остовных деревьев Алгоритмы отыскания компонент двусвязности, точек сочленения, мостов с помощью поиска в глубину Алгоритм нахождения максимального паросочетания и минимального вершинного покрытия в двудольном графе Поиск максимального потока в сети Динамическое программирование Оптимизация решения задачи динамического программирования на примере задачи о рюкзаке (исключение лишних параметров) Восстановление решения в задачах динамического программирования Общая схема решения задач динамического Алгоритмы теории игр Динамическое программирование и полный перебор как методы решения игровых задач. Игры на ациклическом графе Оценка позиций. Альфа-бета отсечение Геометрические алгоритмы Нахождение расстояний между объектами на плоскости Алгоритмы определения пересечения отрезков на плоскости Алгоритмы вычисления площади многоугольника с заданными координатами вершин. Случай целочисленной решетки (формула Пика) Алгоритмы построения выпуклой оболочки (алгоритмы Грэхема и Джарвиса) Окружности на плоскости, пересечение их с другими геометрическими объектами Эффективный алгоритм нахождения пары ближайших точек на плоскости | 20 |
| Среда программирования. Языки программирования Основные конструкции программирования Типы структур данных Особенности программирования фундаментальных алгоритмов. Программные средства и окружения. Проверка соответствия программного обеспечения. Формальные методы описания синтаксиса: Объектно-ориентированные языки Структурная декомпозиция Представление данных в памяти Статическое, автоматическое и динамическое выделение памяти Связанные структуры Методы реализации стеков, очередей и хэш-таблиц Методы реализации графов и деревьев Стратегии отладки Инструментальные средства тестирования Основы тестирования, включая создание тестового плана и генерацию тестов Тестирование методом "черного ящика" и "белого ящика" Тестирование элементов, интеграционное, системное тестирование и проверка соответствия Основы вычислительной математики. Основные методы вычислительной математики
Вычисление функций с шагом. Метод сеток Арифметика с плавающей точкой Ошибка, устойчивость, сходимость Типовые примеры решения задач по разделам из коллекции www.olympiads.ru . | 25 |
Диагностические задания
В качестве диагностических заданий используются представленные ниже типы олимпиадных задач и требуется провести их методический разбор.
Анализ всех задач, предлагавшихся на олимпиадах по информатике, позволил выделить следующие темы, тесно связанные с соответствующими разделами информатики и прикладной математики:
1) комбинаторика;
2) сортировка и поиск;
3) обработка последовательностей;
4) перебор вариантов и методы его сокращения;
5) алгоритмы на графах;
6) динамическое программирование;
7) элементы вычислительной геометрии;
8) задачи на технику программирования;
9) задачи на идею.
Методические указание для изучения
Алгоритмическая компьютерная среда
Набор задач по нескольким уровням сложности
Разные типы алгоритмических заданий (перестановки, переливания, взвешивания, переправы, переезды, работа с числами) (Виртуальные Лаборатории по информатике)
Алгоритмы на координатной плоскости (управление перемещением с условиями)
система автоматической проверки решений и оценивания
/ video / kuris . php
Адрес ресурса: http://school-collection.edu.ru , раздел «Информатика», 2-6 классы, выбрать «Интерактивный задачник по информатике для 2-6 классов»
Методическое пособие и 100 алгоритмических задач http :// lbz . ru / books /264/5211
Виртуальные лаборатории по информатике в начальной школе: методическое пособие Авторы: Цветкова М. С., Курис Г. Э.
Коллекции олимпиадных задач с 1989 по 2016 год и методические материалы к ним представлены на сайтах:
http://old.info.rosolymp.ru/
Представлены интернет-ресурсы олимпиадной информатики:
1. Интернет-ресурсы для теоретической подготовки к олимпиадам:
http://www.intuit.ru/courses.html (сайт Интернет-университета информационных технологий);
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/ (сайт открытой Всесибирской олимпиады по программированию им. И.В. Поттосина).
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 (сайт тренировочных олимпиад школьников, поддерживаемый Новосибирским государственным университетом).
Список литературы
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/
Модуль поддержан видеолекциями членов Центральной предметно-методической комиссии на сайте
Муниципальное бюджетное общеобразовательное учреждение
основная общеобразовательная школа №2 р.п. Солнечный
Солнечного муниципального района Хабаровского края
Рассмотрено: Утверждаю:
Руководитель МО директор МБОУ ООШ № 2
________(Л.Т.Климова) р.п. Солнечный
Протокол № _1_ от 30 .08.2015г _________(О.В.Зверева)
приказ от31.08.2015 № 121.
ПРОГРАММА
индивидуальной подготовки
к муниципальному этапу Всероссийской олимпиады школьников
по предмету «Информатика и ИКТ»
для ученицы 7 «А» класса
Составила:
Молчанова Светлана Николаевна,
учитель информатики, ВКК
2015– 2016 учебный год
п. Солнечный
Пояснительная записка:
Необходимость создания индивидуальной программы по информатики ученицы 7 класса обусловлена имеющимися результатами ученика в образовательной деятельности: отличная учёба, участия в конкурсах школьного уровня, олимпиадах, высокая познавательная активность, нестандартность мышления и т.д.
Изменения, которые происходят сегодня в обществе, коренным образом влияют на задачи школы. Приоритет ученика, формирование базовых компетентностей современного человека заставляют взглянуть на проблему развития одаренности школьников. Ведь одаренность – это не только данные природой качества и способности, это, прежде всего, целенаправленная работа по развитию природного дара.
Информатика в нашей школе изучается с 7 по 9 классы 1 час в неделю на базовом уровне, что явно недостаточно для подготовки к олимпиаде по информатике. Так как олимпиада по информатике является, по сути, своей олимпиадой по программированию. Решение олимпиадных задач представляет собой самостоятельный учебный раздел с обширными теоретическими и практическими частями.
Решения олимпиадных задач, базируются на определенных алгоритмах, широко известных в математике и информатике. И чтобы успешно решать олимпиадные задачи, необходимо, прежде всего, освоить эти алгоритмы, уметь видеть их, применить в предлагаемых заданиях, а уж если не знаешь, то суметь их придумать, изобрести. Но знакомство с этими алгоритмами чаще всего происходит только в вузе, и это вполне объяснимо, так как освоение этих алгоритмов требует знания некоторых разделов математики.
Данная образовательная программа направлена на подготовку учащихся к участию в муниципальном этапе Всероссийской олимпиады школьников. Изучение данной программы позволит учащимся более глубоко изучить данный предмет, расширить кругозор, научиться применять полученные знания для решения задач.
Цель обучение, развитие, воспитание и поддержка ученика при создание условий для оптимального развития ученика выработки у учащихся навыков быстрого решения задач по программированию в нестандартной постановке, типичных для олимпиад.
Задачи программы:
на этапе входной диагностики выявить уровень творческих и индивидуальных возможностей учащихся;
определить и использовать при организации образовательного процесса методы и приемы, способствующие развитию возможностей ученика;
организовать мероприятия для повышения социального статуса ученика;
обучить учащихся реализации как стандартных, так нестандартных алгоритмов;
развивать у учащихся навыки решения олимпиадных задач;
привить учащимся навыки исследовательской работы;
расширение кругозора учащихся и совместно с родителями поддерживать ученика в реализации его интересов в школе и семье;
развитие рефлексивных умений.
Данная программа отличается от существующих школьных программ более углубленным изучением материала.
Образовательная направленность, в рамках которой реализуется программа - социально-педагогическая. Возраст обучающихся школьников - 7 класс основной общеобразовательной школы. Срок реализации программы составляет 1 месяц.
Ожидаемый результат: готовность учащегося к участию в муниципальном этапе Всероссийской олимпиады школьников по информатике.
Используемая литература:
Кирюхин В. М., Окулов С. М. Методика решения задач по информатике. Международные олимпиады. - М. : БИНОМ. Лаб. знаний,2007
Кирюхин В. М., Окулов С. М. Методика решения задач по информатике. Международные олимпиады. - М. : БИНОМ. Лаб. знаний,2009
Программирование в алгоритмах: учебное пособие / С.М.Окулов. - М. : БИНОМ. Лаб. знаний, 2004. - 341, с.
Задачник по программированию / А.Г. Юркин. – СПб.: Питер, 2002. – 192 с.
http://olymp.ifmo.ru/rus/11-12/inf-it/
Интернет Олимпиады для школьников 7-11 классов.
http://www.olympiads.ru
Олимпиадная информатика. События, задачи, тесты, решения, комментарии.
http://olympiads.win.tue.nl/ioi/
Архивы всех международных олимпиад школьников по информатике.
Карта достижений Фиц Маргариты:
| Учебный год | Уровень участия в олимпиадах | Результат |
| Школьный этап | ||
| Школьный этап | Участник |
|
| Школьный этап | Победитель |
График занятий :
| Тема | Изучаемые вопросы |
|
| Целочисленная арифметика | 1.Алгоритм Евклида. Нахождение НОД(а,b), НОК(a,b) рекурсивная и прямая реализация 2. Определение простоты числа. 3. Нахождение всех простых чисел из промежутка (a,b). 4. Разложение данного натурального числа на простые множители. 5. Дано разложение данного натурального числа на простые множители. Найти все делители этого числа. 6. Нахождение всех делителей натурального числа. 7. Нахождение цифрового корня натурального числа. 8. Алгоритм Евклида. Нахождение НОД(а,b), НОК(a,b) рекурсивная и прямая реализация 9. Длинная арифметика: a) Считывание длинного числа из файла. b) Запись длинного числа в файл. c) Сложение двух длинных чисел d) Умножение длинного числа на короткое в системе счисления с основанием 1000. e) Умножение длинного числа на длинное. f) Деление длинного на короткое g) Вычисление n! и степени an при маленьких и больших значениях a и n, рекурсивная и нерекурсивная реализация. h) Индийский алгоритм вычисления an i) Дано натуральное число N. Найти последнюю ненулевую цифру суммы a1+a2+…+ak, где N=p1a1*p2a2*…*pkak. j) Дано натуральное число N. Найти последнюю ненулевую цифру числа N! k) Даны натуральные числа N и M. Найти последнюю ненулевую цифру числа сочетаний C из N по M. 10) Даны натуральные числа N и M. Вычислить число сочетаний C из N по M. 1 11) Найти все натуральные числа, не превосходящие данного натурального N, десятичная запись которых есть строго убывающая или строго возрастающая числовая последовательность. (длинная арифметика). |
|
| Алгоритмы над целыми числами |
||
| Одномерные массивы | 1. Объявление и использование массивов. 2. Создание массивов:.вручную, по формуле, генератором случайных чисел, чтение из файла 3. Виды сортировок. Внешняя и внутренняя сортировка 4. Сортировка выбором. 5. Сортировка "пузырьком". 6. Сортировка Шелла. 7. Сортировка слиянием. 8. Внешняя сортировка слиянием. 9. Кучи. Сортировка с помощью кучи. 10. Сортировка подсчётом. 11. Хэширующая сортировка. 12. Цифровая сортировка 13. Сквозной поиск элемента в массиве. 14. Бинарный поиск элемента в массиве. 15. Извлечение корня n-ой степени из данного натурального числа. 16. Вычисление значения многочлена по схеме Горнера. |
|
| Двумерные массивы | Создание двумерных массивов. Задачи на двумерные массивы: 1 Нахождение максимального и минимального элементов массива. 2 Сортировка массива по возрастанию и убыванию в строках и столбцах. 3 Поменять местами первую и последнюю строки (столбцы). 4 Отобразить массив симметрично относительно горизонтальной оси. 5 Отобразить массив симметрично относительно вертикальной оси. 6 Отобразить массив n*n симметрично относительно главной диагонали 7 Отобразить массив n*n симметрично относительно побочной диагонали 8 Повернуть массив n*n против часовой стрелки на 90 градусов. 9 На шахматной доске стоит слон и еще несколько фигур. Сколько клеток контролирует слон? |
|
| Рекурсия. Комбинаторные объекты | 1. Понятие "комбинаторных" алгоритмов. 2. Получение комбинаторных объектов. 3. Задачи: Сгенерировать все последовательности длины n из чисел от 1 до k. Сгенерировать все подмножества n-элементного множества. Сгенерировать все перестановки чисел от 1 до N. Сгенерировать все k-элементные подмножества n-элементного множества. Сгенерировать все представления числа N в виде суммы натуральных чисел. Код Грея и сходные задачи. Генерация перестановок методом транспозиции соседних элементов. Числа Каталана. Расстановка скобок. |
|
| Сортировка |
||
| Переборные задачи |
||
| Геометрические задачи | 1. Логические функции сравнения вещественных чисел. 2. Площадь ориентированного треугольника (многоугольника). 3. Уравнение прямой проходящей через две точки 4. Общего вида ax+by+c=0 5. Каноническое (x-x1)/(x2-x1)=(y-y1)/(y2-y1) 6. параметрическое x:=x1+t(x2-x1); 7. Уравнение прямой перпендикулярной данной ax+by+c=0 и проходящей через данную точку (x0,y0). 8. Длина отрезка 9. Функция принадлежности точки отрезку |
|
| Численные методы | 1. Элементарная структура данных - запись. Линейный список. 2. Специальные структуры данных: стек, очередь, дек. 3. Деревья. Упорядоченные деревья. 4. Обходы деревьев. 5. Двоичные деревья, деревья поиска. 6. Обходы двоичных деревьев. 7. Поиск элемента в дереве поиска. 8. Добавление/удаление элемента. 9. Характеристики кучи. 1. Способы представления графа. 2. Обход в глубину. 3. Обход в ширину. 4. Кратчайшие пути. 1 Алгоритм Форда-Беллмана. 2 Алгортим Флойда. 3 Алгоритм Дейкстры 5. Поиск Эйлерова цикла 6. Поиск Гамильтонова цикла 7. Поиск компонент сильной связности 8. Поиск мостов 9. Поиск точек сочленения 10. Поиск максимального потока 11. Топологическая сортировка. |
|
| Статистическое моделирование |
||
| Динамическое программирование |
||
| Графы и деревья |
||
| Текстовые преобразования | 1.Процедуры и функции обработки текста на Паскале 2. Функции eof и eoln. 3. Функции seekeof и seekeoln. 4. Посимвольная обработка текста. 5. Отличие процедур read и readln. 5. Поиск заданной подстроки в тексте. Алгоритм Бойера-Мура. 7. Использование хэш-функции для поиска произвольной подстроки в строке. 8. Рекурсивный синтаксический анализ скобочных выражений. Динамическое программирование Концепция динамического программирования Сохранение решений, подзадач, которые приходится решать повторно или несколько раз. Построение динамических таблиц промежуточных результатов. |
|
| Решение олимпиадных задач | 1. Перебор и его значение в программировании. 2. Методы оптимизации перебора. 3. Задача о расстановке ферзей. 4. Задача об обходе конём шахматной доски. 5. Задача комивояжора. |
|
| Решение олимпиадных задач |
Методика подготовки к олимпиадам по информатике
Актуальность темы
В связи с актуализацией и активизацией олимпиадного движения все острее встает проблема подготовки учащихся к участию в олимпиадах. Подготовка «ученика-олимпиадника» начинается с подготовки учителя.
Проблемы, встающие перед учителем:
1. Изучение новых форм проведения олимпиад.
2. Знание алгоритмов решения олимпиадных задач.
3. Наличие самих задач.
4. Знание языков программирования.
5. Время на изучение, отладку и проверку задач.
6. Обучение учащихся правильной организации деятельности на олимпиаде.
Несмотря на то, что круг задач рассматриваемых на олимпиаде по программированию ограничен, решение задачи может быть сложным не только для ученика, но и для учителя, так как некоторые задачи требуют знания высшей математики. Проверка решений и подготовка тестов обычно занимает много времени.
Вот некоторые особенности подготовки школьников к олимпиадному программированию :
· В школьной программе нет такого предмета «программирование» и даже такого раздела. То есть, обучаемый должен иметь собственную, довольно сильную мотивацию.
· Действует ограничение, что при решении задач желательно использовать только один из языков программирования (СИ или ПАСКАЛЬ).
· Постоянные тренировки идут почти на спортивном уровне.
· Большие затраты времени, длительность олимпиады с разбором часто превышает 6 часов.
· Алгоритмы и формулы, применяемые при решении большинства задач, изучаются только в ВУЗах.
Разумеется, подготовка более высокого уровня необходима и учителям для работы с одаренными учащимися, участвующими в олимпиадах по программированию:
· Возможно второе образование, профильный ВУЗ по программированию.
· ИПК учителей, курсы по изучению языков программирования, по олимпиадному программированию.
· Самостоятельная подготовка с использованием материалов из дополнительных источников.
Но даже хорошее знание языка программирования не дает стопроцентную гарантию, что учащийся победит даже на школьной или районной олимпиаде.
Педагогическая идея
Основным стимулом к участию в олимпиадах для школьника является мотивация. Это не только возможность улучшить свою отметку, но и возможность показать знания и эрудицию по решаемой проблеме, свои организаторские способности, дать возможность «заработать отметку» другим учащимся (даже не участвующим в олимпиаде).
Стремление школьника к лидерству, демонстрации собственных достижений является одним из основополагающих условий для участия в олимпиадном движении. Разумеется, при такой мотивации желающих работать достаточно, но в ходе работы происходит частичная ротация и это неизбежно при современной загруженности школьников. В основном остаются трудолюбивые дети, те учащиеся, которые не боятся поражений и ставят перед собой конкретные цели.
Одними из основных направляющих сил участия учащегося в олимпиадах по программированию являются желание и заинтересованность учителя, а также помощь, терпение и доверие родителей.
В 1964 г. В. Врум предложил «теорию ожиданий». Он считал, что стимул к эффективному и качественному труду зависит от сочетания трех факторов - ожиданий человека:
1. Ожидание того, что усилия приведут к желаемому результату.
2. Ожидание того, что результаты повлекут за собой вознаграждение.
3. Ожидание того, что вознаграждение будет иметь достаточную ценность.
Чем больше вера человека, что все эти ожидания оправдаются, тем более сильным будет стимул к деятельности. Если немного изменить формулировки В. Врума в образовательном контексте, то вот что получится:
· Теория ожидания указывает на то, что должны делать учителя, чтобы стимулы к учебе у учеников были сильными:
o Учить учеников получать требуемые результаты и создавать для этого все необходимые условия;
o Устанавливать непосредственную связь между результатами труда и оценкой учеников;
o Изучать потребности учеников, чтобы знать, какие вознаграждения имеют для них ценности.
· Исходя из этого, механизмы мотивации и основные факторы эффективности стимулирования можно выразить как:
o Знание учителями потребностей, интересов, нужд учеников.
o Установление справедливой непосредственной связи между результатами и вознаграждением.
o Безотлагательность вознаграждения.
o Степень удовлетворения ожиданий.
Для подготовки к олимпиадам по программированию можно применить методику с использованием системы тестирования «NSUTS» , разработанной на базе НГУ, которая позволяет оперативно решать многие из этих пунктов.
Технология использования системы « NSUTS »
Система находится по адресу https://olympic. *****/nsuts-test/nsuts_new_login. cgi . При переходе по этой ссылке попадаем на страницу авторизации , где, введя свой логин и пароль, можно войти в систему.
https://pandia.ru/text/78/392/images/image002_97.jpg" width="623" height="258 src=">
В данном случае выберем, например, Школьные тренировки , после чего вы попадёте на страницу «Страница регистрации на Школьные тренировки », где регистрация проста и понятна. Только нужно учесть, что данные, вводимые вами, должны быть достоверными.
https://pandia.ru/text/78/392/images/image004_80.jpg" width="623" height="306">
На вкладке «Help » можно прочесть краткую инструкцию по работе в системе. Рассмотрим содержимое этой страницы.
Система тестирования NSUTS. Очень краткое Описание.
Вы находитесь в автоматической системе тестирования NSUTS для проведения и проверки олимпиад по программированию. В верхней части экрана отображается текущий раздел. В правом верхнем углу - название текущей олимпиады, название вашей команды и кнопка завершения работы с системой - «Выйти ».
В разделе «Тур » вы можете выбрать текущий тур олимпиады.
В разделе «Новости » вы можете прочитать объявления и комментарии от жюри и оргкомитета олимпиады. А так же узнать время начала и конца олимпиады. После начала олимпиады на этой странице появляются ссылки на условия задач.
В разделе «Сдать » осуществляется отправка задач на тестирование. Для того чтобы отправить задачу на тестирование, укажите язык, на котором написано решение, и номер задачи. Вставьте текст решения в поле ввода и нажмите кнопку «Отправить ». Или выберите файл, пользуясь строкой выбора файла, а затем нажмите кнопку «Отправить ». Ваше решение появится в списке отправленных задач в секции «Результаты ».
Ваши решения должны считывать входную информацию из файла input. txt и выдавать результат в файл output. txt . Запрещено читать из стандартного потока ввода, писать в стандартный поток вывода, стандартный поток ошибок. Программа участника не должна открывать, читать и модифицировать файлы, кроме input. txt и output. txt или иных, указанных в условии задачи. Доступ к файловой системе и другим ресурсам, кроме перечисленных в формулировке задачи, запрещен. Нарушение этого требования может быть основанием для дисквалификации команды. Ограничение на размер исходного кода - 100 килобайт. Формат вывода должен точно соответствовать требованиям, описанным в условии задачи.
Участник может использовать любой компилятор из перечисленных в разделе «Сдать ».
Опции компиляции:
Visual C++ 6.0 | |
Visual C++ 2005 | cl. exe /EHsc /Ox task. cpp /link /STACK: |
MinGW 5.1.4 (GCC 3.4.5) | c++.exe - Wall - Wl,--stack= - O2 task. cpp |
Freepascal 2.2.0 | ppc386.exe - O2 - Cs task. pas |
Java 1.6.0_07 | javac. exe Task. java |
Запуск Java | java - Xmx480m - Xss32m - Djava. security. manager - Duser. language=en_US Task |
Borland Delphi 2006 |
В секции «Результаты » вы можете просмотреть статус тестирования и результаты тестирования отправленных вами задач. В строке «Время » указано время на момент сдачи решения, язык программирования который вы указали, сдавая это решение. Ссылка «V iew source » покажет текст сданного решения.
В строке «Результат » отображается результат тестирования:
Queued - решение стоит в очереди на тестирование.
Testing... - тестируется прямо в этот момент.
Source code limit exceeded - превышено ограничение на исходный код программы.
Compile Error - не удалось скомпилировать (причина указывается).
Когда решение протестировано, статус принимает одно из следующих значений:
ACCEPTED! - решение засчитано как верное.
Wrong Answer - неверный ответ на тесте.
Time limit exceeded - решение не уложилось в отведенное процессорное время.
Timeout - решение не уложилось в отведенное время.
Run-time Error - решение вернуло код ошибки, отличный от нуля.
Memory limit exceeded - решение не уложилось в отведенное ограничение по памяти.
No output file - отсутствует файл output. txt.
Security violation - решение совершило действие запрещенное правилами.
При этом указывается номер теста, на котором произошла ошибка (для олимпиад ACM).
Краткое правило построения рейтинга для олимпиад ACM таково: из двух команд, та будет выше в рейтинге, у которой решено большее число задач; если число задач одинаково, то выше оказывается команда, имеющая меньшее штрафное время. Если число задач и штрафное время одинаково у нескольких команд, то эти команды занимают несколько подряд идущих мест.
Штрафное время - это сумма штрафного времени по всем задачам. Штрафное время для одной задачи равно 0, если задача не сдана. Если же задача сдана, то её штрафное время считается по формуле:
время_сдачи_правильного_решения + (количество_неудачных_попыток * 20).
Cекция «Вопросы и ответы » предназначена для общения с Жюри олимпиады. Вы можете задать жюри вопросы по условиям задач или указать на неточность формулировки задач.
Кроме того, если Жюри считает необходимым внести какие-либо изменения в условия задач, поправки будут опубликованы в этой секции либо в новостях.
Теперь, когда мы познакомились с основами работы в системе, рассмотрим, как можно получить задание для олимпиады .
На вкладке «Тур» выбираем необходимый нам тур по олимпиаде, например, «Подготовка к Всероссийской олимпиаде 2010.03.21 (Геометрия) » . После этого переходим на вкладку «Новости» и по ссылке «Условие тура» скачиваем файл формата MS Office Word, в котором находятся задачи, представленные к решению на данном туре.
Решив задачу, на вкладке «Сдать» отправляем её на проверку, выставив все необходимые параметры (язык, текст программы либо файл с программой). Результаты проверки можно узнать на вкладке «Результаты».
Основные классы задач, выдвигаемых на олимпиады по информатике
Для успешного выполнения не только олимпиадных, но и внутриурочных задач, требуется:
1. В совершенстве владеть языком и средой программирования (в нашем случае - это Free Pascal), уметь строить и воплощать с помощью этого языка различные алгоритмы.
2. Владеть необходимым математическим аппаратом.
3. Знать алгоритмы решения основных классов задач, их оптимизацию.
Задачи олимпиадного программирования охватывают очень большой спектр знаний, но наиболее часто встречаемые и вызывающие наибольшую сложность - это следующие:
1. Задачи, использующие сложные структуры данных, такие, как массивы, очереди, стеки, связанные списки и деревья.
2. Графы, как множество объектов с множеством связей.
3. Задачи, использующие аналитическую геометрию и опирающиеся на понятие «вектор».
4. Задачи динамического программирования.
Рассмотрим данные классы задач подробнее.
Задачи, использующие сложные структуры данных, такие, как массивы, очереди, стеки, связанные списки и деревья.
Программы состоят из алгоритмов и структур данных. Хорошие программы используют преимущества их обоих. Выбор и разработка структуры данных столь же важна, как и разработка процедуры, которая манипулирует ими. Организация информации и методы доступа к ней обычно определяются характером стоящей перед программистом задачи. Поэтому каждый программист должен иметь в своем «багаже» соответствующие методы представления и поиска данных, которые можно применить в каждой конкретной ситуации.
В действительности структуры данных в ЭВМ строятся на основе базовых типов данных, таких как «char», «integer», «real». На следующем уровне находятся массивы, представляющие собой наборы базовых типов данных. Затем идут записи, представляющие собой группы типов данных, доступ к которым осуществляется по одному из данных, а на последнем уровне, когда уже не рассматриваются физические аспекты представления данных, внимание обращается на порядок, в котором данные хранятся и в котором делается их поиск. По существу физические данные связаны с «машиной данных», которая управляет способом доступа к информации в вашей программе. Имеется четыре такие «машины»:
1. очередь;
3. связанный список;
4. двоичное дерево.
1) http://ru. wikipedia. org/wiki/%D0%A1%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D1%8B_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85.
2) http://valera. *****/delphi/struct/ocher. html.
3) http://www. *****/informatika/pascal/struktury_dannyh.
4) Т. Кормен. Алгоритмы. Построение и анализ. 2-е изд. Стр.255
5) Задачи и решения http://*****/olimp/str_prb. php.
Графы, как множество объектов с множеством связей.
Граф – это абстрактный математический объект. Он состоит из вершин и ребер. Каждое ребро соединяет пару вершин. Если одну и ту же пару вершин соединяют несколько ребер, то эти ребра называются кратными. Ребро, соединяющее вершину с ней самой, называется петлей. По ребрам графа можно ходить, перемещаясь из одной вершины в другую. В зависимости от того, можно ли по ребру ходить в обе стороны, или только в одну, различают неориентированные и ориентированные графы соответственно. Ориентированные ребра называются дугами. Если у всех ребер графа есть вес (т. е. некоторое число, однозначно соответствующее данному ребру), то граф называется взвешенным. Вершины, соединенные ребром, называются соседними. Для неориентированного графа степень вершины – число входящих в нее ребер. Для ориентированного графа различают степень по входящим и степень по исходящим ребрам. Граф называется полным, если между любой парой различных вершин есть ребро.
Граф – объект абстрактный, и интерпретировать его мы можем по-разному, в зависимости от конкретой задачи. Рассмотрим пример. Пусть вершины графа - города, а ребра - дороги, их соединяющие. Если дороги имеют одностороннее движение, то граф ориентированный, иначе неориентированный. Если проезд по дорогам платный, то граф взвешенный.
На бумаге граф удобно представлять, изображая вершины точками, а ребра - линиями, соединяющими пары точек. Если граф ориентированный, на линиях нужно рисовать стрелочку, задающую направление; если граф взвешенный, то на каждом ребре необходимо еще надписывать число - вес ребра.
Есть несколько способов представления графа в памяти компьютера. Далее с теорией можно ознакомиться по ссылкам:
1. http://*****/sng/index. shtml
2. http://*****/sng/4/index. shtml
3. https://sites. /site/vzsitgnovosibirsk/distancionnye-kursy/distancionnyj-kurs-graf
4. http://book. *****/10/grap1021.htm
5. http://ru. wikipedia. org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2
6. Задачи и решения http://*****/olimp/gra_prb. php
Задачи, использующие аналитическую геометрию и опирающиеся на понятие «вектор»
Вычислительная геометрия - это раздел информатики, изучающий алгоритмы решения геометрических задач. Такие задачи возникают в компьютерной графике, проектировании интегральных схем, технических устройств и др. Исходными данными в такого рода задачах могут быть множество точек, набор отрезков, многоугольник и т. п. Результатом может быть либо ответ на какой-то вопрос (типа «пересекаются ли эти прямые»), либо какой-то геометрический объект (например, наименьший выпуклый многоугольник, содержащий заданные точки).
В «Информатике» № 14 была опубликована статья одного из авторов, посвященная задачам вычислительной геометрии в олимпиадах по информатике. В частности, там был сформулирован ряд элементарных подзадач, на которые опирается решение большинства задач вычислительной геометрии. Однако занятия даже с математически хорошо подготовленными учащимися старших классов показали, что решение таких подзадач вызывает у них большое затруднение. Задача либо ставит их в тупик, либо выбранный «лобовой» способ решения настолько сложен, что довести его до конца без ошибок учащиеся не могут. Анализ результатов решения «геометрических» задач на всероссийских олимпиадах по информатике приводит к тем же выводам. По ссылкам ниже вы сможете изучить подходы к решению геометрических задач на плоскости, которые позволяют достаточно быстро и максимально просто получать решения большинства элементарных подзадач.
1) http://*****/?page=lib_viewarticle&article_id=12.
2) http://*****/article. asp? id_sec=1&id_text=1332.
3) Задачи и решения http://*****/olimp/geo_prb. php
Задачи динамического программирования.
Многие олимпиадные задачи, а также задачи практического программирования, являются задачами на перебор вариантов и выбор среди этих вариантов допустимого или наилучшего по тому или иному критерию. Однако рассмотреть все варианты, в силу чрезвычайно большого их количества, зачастую не представляется возможным.
К счастью, для ряда задач, сходных по формулировке с проблемами, действительно требующими полного перебора вариантов, можно найти гораздо более эффективное решение. Чаще всего в таких случаях решение сводится к нахождению решений подзадач меньшей размерности, которые запоминаются в таблице и никогда более не пересчитываются, а подзадачи большей размерности используют эти уже найденные решения. Такой метод называется динамическим программированием, еще его называют табличным методом. В общей же форме под динамическим программированием понимают процесс пошагового решения задачи оптимизации, при котором на каждом шаге из множества допустимых решений выбирается одно, которое оптимизирует заданную целевую или критериальную функцию. Иногда, вместо оптимизационной, тем же методом решается задача подсчета количества допустимых решений. В этом случае на каждом шаге вместо выбора оптимального решения производится суммирование решений подзадач меньшей размерности, причем они по формулировке не всегда полностью совпадают с исходной задачей (соответствующие примеры будут рассмотрены ниже). В обоих случаях найденное на текущем шаге решение обычно заносится в таблицу. Как правило, связь задач и подзадач формулируется в виде некоторого “принципа оптимальности” и выражается системой уравнений (рекуррентных соотношений).
Основы теории динамического программирования были заложены Р. Беллманом. Заметим, что слово программирование в приведенном названии (dynamic programming), также как и в “линейном программировании” (linear programming) не означает составление программ для компьютера.
Для решения задачи оптимизации, в которой требуется построить решение с максимальным или минимальным (оптимальным) значением некоторого параметра, алгоритм, основанный на динамическом программировании, можно сформулировать так:
1) выделить и описать подзадачи, через решение которых будет выражаться искомое решение,
2) выписать рекуррентные соотношения (уравнения), связывающие оптимальные значения параметра для подзадач,
3) вычислить оптимальное значение параметра для всех подзадач,
4) построить самое оптимальное решение, используя полученную информацию.
Если нас интересует только значение параметра, то шаг 4 в алгоритме не нужен (такая ситуация характерна, например, для задач подсчета количеств допустимых вариантов или некоторых конфигураций, в том числе и комбинаторных). Однако, в случае необходимости построения самого оптимального решения иногда приходится в процессе выполнения шага 3 алгоритма получать и хранить дополнительную информацию. Зачастую именно шаг 4 оказывается самым сложным при реализации подобных алгоритмов.
1) http://*****/blogs/algorithm/113108/.
2) http://www. *****/Olympiads/Rules_Olympiads/Rules21.htm.
3) http://*****/tag/%D0%B4%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5%20%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5/
4) Задачи и решения http://*****/olimp/rec_prb. php
Вопрос 1. Как научиться решать олимпиадные задачи по информатике?
Чтобы научиться решать олимпиадные задачи по информатике, надо решать задачи по информатике... Естественно при этом заглядывая в соответствующею литературу.
Вопрос 2. Сколько необходимо решить задач, чтобы достойно выступать на олимпиадах по информатике?
Вопрос задан конечно не корректно и ответить на него, пожалуй вряд ли возможно, но сказать пару слов по этому поводу стоит. Как мне соощил специалист в области подготовки к олимпиадам ACM Михаил Медведев , то создать принципиально новую олимпиадную задачу не так то просто, как может показаться на первый взгляд. По этой причине, лица ответственные за проведения олимпиад просто берут задачи за прошлые годы и подают их под "новым соусом". Часто случается, что задачи для районных и зональных олимпиад по информатике "сдирают" без каких либо изменений с сайтов посвященных олимпиадному программированию.
Итак, поскольку многие задачи весьма и весьма схожи, то необходимо научиться решать задачи из всего диапазона: сортировка, динамическое программирование, длинная арифметики и т.д.
Вопрос 3. Можно ли подготовить школьников к олимпиадам по информатике в рамках школьной программы?
Думаю, что это нереально. Всем давно известно, что школьный курс информатики - это одно, а олимпиады по информатике - это совсем другое. Да, в примерной программе по информатике, в 9 классе, довольно большое количество часов уделено изучению программирования. В учебнике Семакина для 9 класса обучение программированию основано на языке Паскаль, у Угриновича примеры дана применительно к Visual Basic . Но, даже если применить дифференцированный подход к обучению школьников, вряд ли этих часов хватит для подготовки к олимпиадам отдельных школьников с "нуля".
Вопрос 4. Если часов по программе не достаточно для подготовки школьникам к олимпиадами, то как тогда готовиться?
По первым двум вариантам все понятно, но должно быть понимание со стороны руководства школы. Частенько, между учителями бывает "битва за часы", на кружок или факультатив по программированию часов может и не перепасть.
Личный энтузиазм доведенный до крайней меры - это весьма пагубное, на мой взгляд, явление. Российское образование не должно держаться на энтузиазме. Иначе получается, что пока есть энтузиазм - дело идет, закончился запал и все рухнуло. На энтузиазме долго не протянешь, но его иногда стоит проявлять в надежде, что дело сдвинется с "мертвой точки".
Вопрос 5. У меня 25 (26, 30...) часов основной нагрузки, реально ли еще заниматься с учащихся на кружке по программированию?
Как мне кажется, при такой нагрузке реальней сойти с ума, чем готовить учащихся к олимпиадам. Искренне сочувствую всем учителям с большой нагрузкой. Я понимаю, что брать большое количество часов приходится не от хорошей жизни, но не понимаю, как можно работать в таких условиях.
Вопрос 6. Могут ли школьники готовиться к олимпиадам во внеурочное время и если могут, то как лучше организовать подготовку?
Могут, но у них как минимум должен быть домашний компьютер. В идеале должен быть еще и Интернет. При наличии ПК и Интернета можно решать задачи на одном из специализированных сайтов с автоматизированной проверкой решений, например на сайте Школа программиста .
Вопрос 7. Что требуется от учителя для качественной подготовки школьников к олимпиаде?
- Умение учиться. Ведь как случается, закончил человек учебное учреждение и на этом его развитие в плане получения информации порой и заканчивается. Для работы в школе вроде хватит, так зачем еще заморачитваться...
- Всегда быть на связи. У вашего ученика может возникнуть вопрос в любое время, есть ведь и такие, которые решают задачки по ночам. Если вам не спится, то почему бы, при возможности, ему не ответить при помощи той же "Аськи" или программы Skype .
