Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Общество с ограниченной ответственностью Финансово-строительная компания «МОНОЛИТИНВЕСТ», ИНН 2465004805. Юридический адрес: 660049, г. Красноярск, п...полностью>>
'Документ'
Медицинский отдел Епархии в 2010 году, осуществлял свою деятельность, направленную на содействие диалога Церкви с практическим здравоохранением и мед...полностью>>
'Контрольная работа'
Великая Отечественная война 1941-1945 — справедливая, освободительная война советского народа за свободу и независимость Родины против фашистской Гер...полностью>>
'Документ'
как бы обзавестись детьми, чтобы докучать своим ближним? С моей племянницей Лидией вчера произошел странный случай, и я так разволновался, что жду во...полностью>>

Методические рекомендации по разработке заданий и требований к проведению школьного этапа всероссийской олимпиады школьников по информатике в 2011-2012 учебном году

Главная > Методические рекомендации
Сохрани ссылку в одной из сетей:

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

  • подготовка системы оценивания решений каждой задачи;

  • проверка корректности оценивания различных вариантов решений каждой задачи, включая частичные и полные решения;

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

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

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

    - оригинальная формулировка задачи или оригинальная идея ее решения для конкретного состава участников олимпиады;

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

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

    - задача не должна требовать для своего решения специальных знаний;

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

    - задача должна быть разумной сложности и трудоемкости.

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

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

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

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

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

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

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

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

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

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

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

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

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

    В решениях задач участникам запрещается:

    - создание каталогов и временных файлов при работе программы;

    - любое использование сетевых средств;

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

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

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

    Для обучающихся 8 класса рекомендуется использовать такие же типы задач, как и для учащихся 9-11 классов. Поэтому все, сказанное о типах задач для обучающихся 9-11 классов, справедливо и для типов задач для 8 класса.

    Формой представления результатов решения задач для обучающихся 8 класса должна быть либо программа, написанная с использованием определенных муниципальной предметно-методической комиссией по информатике языков и систем программирования, либо набор выходных данных, соответствующий заданному набору входных данных (для задач с открытым входом). Если решением задачи является программа, то допускается ввод данных либо из входного файла input.txt, либо из стандартного потока ввода, т.е. с клавиатуры, а вывод допускается как в выходной файл output.txt, так и в стандартный поток вывода, т.е. на экран монитора.

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

    При определении содержания задач для школьного этапа Олимпиады по информатике следует руководствоваться примерной программой по олимпиадной информатике, приведенной в книге [15]. Данная программа разработана с учетом Государственного образовательного стандарта по предмету «Информатика и ИКТ» (Приказ Минобразования 2004 года и дополнение к Приказу Минобрнауки России 2005 года) с перспективой введения стандарта второго поколения для всех ступеней школьного образования: начальной пропедевтической (3-6 классы), основной (7-8 классы), старшей предпрофильной (9 класс) и профильной (10-11 классы), а также на основе анализа структуры современного содержания олимпиад по информатике.

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

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

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

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

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

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

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

    1. Математические основы информатики

      1. Функции, отношения и множества

        1. Функции

        2. Отношения (рефлексивность, симметричность, транзитивность, эквивалентность)

        3. Множества (диаграммы Венна, дополнения)

        4. Обратная функция, композиция *

        5. Лексикографический порядок *

        6. Декартовы произведения *

        7. Вполне упорядоченные множества **

        8. Мощность и счетность множества. Конечные и бесконечные
          множества **

      2. Основные геометрические понятия

        1. Точка, прямая, отрезок, вектор, угол

        2. Треугольник, прямоугольник, многоугольник

        3. Выпуклые многоугольники

        4. Декартовы координаты в евклидовом пространстве

        5. Евклидово расстояние *

        6. Векторное и скалярное произведение на плоскости *

      3. Основы логики

        1. Логические переменные, операции, выражения

        2. Таблицы истинности

        3. Булевы функции

        4. Формы задания и синтез логических функций *

        5. Преобразование логических выражений *

        6. Минимизация булевых функций **

        7. Основные законы логики суждений **

        8. Логика предикатов **

      4. Основы вычислений

        1. Основы вычислений:

        • Правила суммы и произведения

        • Арифметические и геометрические прогрессии *

        • Числа Фибоначчи *

        • Принцип «включения-выключения» **

        1. Рекуррентные соотношения *

        2. Матрицы и действия над ними **

      1. Методы доказательства

        1. Прямые доказательства

        2. Доказательство методом «от противного»

        3. Доказательство методом исключения

        4. Доказательство через контрпример

        5. Математическая индукция *

        6. Структура формальных доказательств **

      2. Основы теории чисел

        1. Простые числа

        2. Деление с остатком

        3. Наибольший общий делитель

        4. Основная теорема арифметики *

        5. Взаимно простые числа *

        6. Делимость. Кольцо вычетов по модулю **

      3. Основы алгебры

        1. Многочлены и операции над ними. Решение квадратных уравнений. Теорема Виета *

        2. Общий случай теоремы Виета. Симметрические многочлены **

        3. Понятие группы **

        4. Теоремы о гомоморфизме и изоморфизме **

      4. Основы комбинаторики

        1. Перестановки, размещения и сочетания:

        • Основные определения

        • Тождество Паскаля *

        • Биномиальная теорема *

        1. Коды Грея: подмножества, сочетания, перестановки **

        2. Таблицы инверсий перестановок **

        3. Разбиения на подмножества. Числа Стирлинга **

        4. Скобочные последовательности **

      1. Теория графов

        1. Типы графов

        2. Маршруты и связность

        3. Деревья

        4. Операции над графами *

        5. Остовные деревья *

        6. Раскраска графов *

        7. Эйлеровы и гамильтоновы графы *

        8. Покрытия и независимость **

        9. Укладка графов. Плоские (планарные) графы **

        10. Двусвязность графа. Мосты, блоки, точки сочленения **

        11. Связь ориентированных ациклических графов и отношений порядка. Транзитивное замыкание **

        12. Двудольные графы **

        13. Потоки и сети **

      2. Основы теории синтаксического анализа

        1. Обратная польская запись

        2. Синтаксический анализ простых выражений *

        3. Регулярные выражения, конечные автоматы **

      3. Основы теории вероятностей

        1. Понятие вероятности и математического ожидания *

        2. Аксиомы теории вероятностей **

        3. Основы вычисления вероятностей **

      4. Основы теории игр

        1. Понятие игры и результата игры

        2. Простейшие игры

        3. Простейшие стратегии игры *

        4. Игры на матрицах **

        5. Решение игровых задач с использованием функции Гранди **

    1. Разработка и анализ алгоритмов

      1. Алгоритмы и их свойства

        1. Понятие алгоритма

        2. Концепции и свойства алгоритмов

        3. Запись алгоритма на неформальном языке

      2. Структуры данных

        1. Простые базовые структуры

        2. Множества

        3. Последовательности

        4. Списки

        5. Неориентированные графы *

        6. Ориентированные графы *

        7. Деревья *

        8. Пирамида и дерево отрезков **

        9. Сбалансированные деревья **

        10. Хэш-таблицы и ассоциативные массивы **

        11. Бор **

      3. Основы анализа алгоритмов

        1. Нотация О большое *

        2. Стандартные классы сложности *

        3. Асимптотический анализ поведения алгоритмов в среднем и крайних
          случаях *

        4. Компромисс между временем и объемом памяти в алгоритмах **

        5. Использование рекуррентных отношений для анализа рекурсивных алгоритмов **

        6. NP-полнота **

      4. Алгоритмические стратегии

        1. Алгоритмы полного перебора

        2. "Жадные" алгоритмы *

        3. Алгоритмы "разделяй и властвуй" *

        4. Перебор с возвратом *

        5. Эвристики **

      5. Рекурсия

        1. Понятие рекурсии

        2. Рекурсивные математические функции *

        3. Простые рекурсивные процедуры *

        4. Реализация рекурсии *

        5. Рекурсивный перебор с возвратами **

      6. Фундаментальные вычислительные алгоритмы

        1. Простые численные алгоритмы

        2. Классические комбинаторные алгоритмы

        3. Алгоритмы с подмножествами: генерация, восстановление по номеру и построение номера, генерация следующего и предыдущего (прибавление и вычитание единицы)

        4. Алгоритмы последовательного и бинарного поиска

        5. Алгоритмы с сочетаниями и перестановками (генерация, восстановление по номеру и построение номера, генерация следующего и предыдущего) *

        6. Квадратичные методы сортировки (сортировка методом выбора, сортировка вставками) *

        7. Сортировка подсчетом за линейное время *

        8. Алгоритмы сортировки за время O(N log N) (быстрая сортировка, пирамидальная сортировка, сортировка слиянием) **

        9. Цифровая сортировка **

        10. Алгоритм вычисления номера слова в лексикографически упорядоченном множестве перестановок его символов **

        11. Арифметика многоразрядных целых чисел **

      7. Числовые алгоритмы

        1. Разложение числа на простые множители

        2. Решето Эратосфена *

        3. Алгоритм Евклида *

        4. Расширенный алгоритм Евклида. Способы реализации алгоритма без деления **

        5. Решение линейных сравнений с помощью алгоритма Евклида **

        6. Эффективная реализация решета Эратосфена (O(n)) **

        7. Эффективная проверка числа на простоту **

        8. Быстрые алгоритмы разложения чисел на простые множители.
          Ро-эвристика **

      8. Алгоритмы на строках

        1. Поиск подстроки в строке. Наивный метод *

        2. Алгоритмы поиска подстроки в строке за O(N+M) **

        3. Периодические и циклические строки **

        4. Алгоритм поиска нескольких подстрок за линейное время **

      9. Алгоритмы на графах

        1. Вычисление длин кратчайших путей в дереве

        2. Обход графа в ширину и в глубину

        3. Способы реализации поиска в ширину (“наивный” и с очередью) *

        4. Проверка графа на связность *

        5. Алгоритмы поиска кратчайшего пути во взвешенных графах *

        6. Топологическая сортировка графа, нахождение компонент сильной связности и построение диаграммы порядка **

        7. Циклы отрицательной длины – критерий наличия, поиск **

        8. Задача о синхронизации времени и задача о системе неравенств **

        9. Алгоритм поиска эйлерова цикла (в том числе лексикографически минимального) **

        10. Нахождение транзитивного замыкания графа **

        11. Алгоритмы нахождения взвешенных остовных деревьев **

        12. Алгоритмы отыскания компонент двусвязности, точек сочленения, мостов с помощью поиска в глубину **

        13. Алгоритм нахождения максимального паросочетания и минимального вершинного покрытия в двудольном графе **

        14. Поиск максимального потока в сети **

      10. Динамическое программирование

        1. Основная идея динамического программирования. Рекурсивная реализация и развертывание в цикл *

        2. Задачи с монотонным направлением движения в таблице *

        3. Задача о рюкзаке – решение методом динамического программирования *

        4. Оптимизация решения задачи динамического программирования на примере задачи о рюкзаке (исключение лишних параметров) **

        5. Восстановление решения в задачах динамического программирования **

        6. Общая схема решения задач динамического программирования **

      11. Алгоритмы теории игр

        1. Динамическое программирование и полный перебор как методы решения игровых задач **

        2. Игры на ациклическом графе **

        3. Оценка позиций. Альфа-бета отсечение **

      12. Геометрические алгоритмы

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

        2. Представление точек, прямых и отрезков на плоскости *

        3. Нахождение расстояний между объектами на плоскости **

        4. Алгоритмы определения пересечения отрезков на плоскости **

        5. Алгоритмы вычисления площади многоугольника с заданными координатами вершин. Случай целочисленной решетки (формула Пика) **

        6. Алгоритмы построения выпуклой оболочки (алгоритмы Грэхема и Джарвиса) **

        7. Окружности на плоскости, пересечение их с другими геометрическими объектами **

        8. Эффективный алгоритм нахождения пары ближайших точек на
          плоскости **

    2. Основы программирования

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

        1. Классификация языков программирования

        2. Процедурные языки

        3. Основы синтаксиса и семантики языков высокого уровня *

        4. Формальные методы описания синтаксиса: форма Бэкуса-Наура **

        5. Объектно-ориентированные языки **

      2. Основные конструкции программирования

        1. Переменные, типы, выражения и присваивания

        2. Основы ввода/вывода

        3. Операторы проверки условия и цикла

        4. Функции и передача параметров *

        5. Структурная декомпозиция **

      3. Переменные и типы данных

        1. Концепция типа данных как множества значений и операций над ними

        2. Свойства объявлений (связывание, область видимости, блоки и время
          жизни) *

        3. Обзор проверки типов *

      4. Типы структур данных

        1. Примитивные типы

        2. Массивы

        3. Записи *

        4. Стратегии выбора подходящей структуры данных *

        5. Представление данных в памяти **

        6. Статическое, автоматическое и динамическое выделение памяти **

        7. Указатели и ссылки **

        8. Связанные структуры **

        9. Методы реализации стеков, очередей и хэш-таблиц **

        10. Методы реализации графов и деревьев **

      5. Механизмы абстракции.

        1. Классы и объекты, замыкания *

        2. Процедуры, функции и итераторы как механизмы абстракции *

        3. Механизмы параметризации (ссылки и значения) *

        4. Модули в языках программирования *

      6. Особенности программирования фундаментальных алгоритмов.

        1. Стратегии решения задач

        2. Роль алгоритмов в процессе решения задач

        3. Стратегии реализации алгоритмов *

        4. Реализация рекурсии *

        5. Стратегии отладки **

    3. Средства ИКТ



  • Скачать документ

    Похожие документы:

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

      Методические рекомендации
      Методические рекомендации по разработке заданий и требований к проведению школьного этапа всероссийской олимпиады школьников по основам безопасности жизнедеятельности в 2011-2012 учебном году
    2. Приказ управления образования, науки и молодежной политики администрации г. Рязани №844 от 16 сентября 2011 г. «О проведении I (школьного) этапа всероссийской олимпиады школьников в городе Рязани 2011-2012 уч г.»

      Документ
      ПРИКАЗ управления образования, науки и молодежной политики администрации г. Рязани № 844 от 16 сентября 2011 г. «О проведении I (школьного) этапа всероссийской олимпиады школьников в городе Рязани 2011-2012 уч.
    3. Методические рекомендации по разработке требований к проведению школьного и муниципального этапов всероссийской олимпиады школьников по информатике в 2011/2012 учебном году Москва 2011

      Методические рекомендации
      Настоящие методические рекомендации подготовлены центральной предметно-методической комиссией по информатике и направлены в помощь оргкомитетам школьного и муниципального этапов всероссийской олимпиады школьников по информатике по
    4. Методические рекомендации по разработке заданий для школьного и муниципального этапов всероссийской олимпиады школьников по информатике в 2011/2012 учебном году Москва 2011 (1)

      Методические рекомендации
      Настоящие методические рекомендации подготовлены центральной предметно-методической комиссией по информатике в соответствии с Положением о всероссийской олимпиаде школьников и направлены на помощь муниципальным и региональным предметно-методическим
    5. Методические рекомендации по разработке заданий для школьного и муниципального этапов всероссийской олимпиады школьников по информатике в 2011/2012 учебном году Москва 2011 (2)

      Методические рекомендации
      Методические рекомендации по разработке заданий для школьного и муниципального этапов всероссийской олимпиады школьников по информатике в 2011/2012 учебном году

    Другие похожие документы..