Главная стр 1стр 2
скачать


ВСЕРОССИЙСКАЯ ОЛИМПИАДА ШКОЛЬНИКОВ ПО ИНФОРМАТИКЕ

В.М. Кирюхин


МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ

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

в 2011/2012 учебном году

Москва 2011

ОГЛАВЛЕНИЕ

Введение ……………………………………………………………………..……....…..… 3



  1. Порядок разработки олимпиадных задач ……………....………………....…….…… 5

  2. Общие требования к олимпиадным задачам …………...………………….…....….... 6

  3. Формирование комплектов олимпиадных задач …...............................................…... 7

  4. Типы олимпиадных задач …......................................................................................…. 8

    1. Типы задач для 9 – 11 классов …….…………….………...........................…….. 8

    2. Типы задач для 7 – 8 классов ………..…………………………………….…… 10

    3. Типы задач для 5 – 6 классов ……………….……………………….….……… 11

  1. Содержание олимпиадных задач ……………….…………………………..….……. 13

  2. Примеры олимпиадных задач …………………………...….………………….……. 25

  3. Рекомендации по проверке и оцениванию решений задач ………………….…….. 27

7.1. Методика проверки решений задач участников …….......……………….……. 27

7.2. Система оценивания решений участников ………….…………………....…… 30

7.3. Технология проверки решений участников …………...………………………. 32

Список рекомендуемой литературы ……………………….…..……………………...…. 38



Введение

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

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

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

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

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



Председатель центральной

предметно-методической комиссии

по информатике В.М. Кирюхин




  1. Порядок разработки олимпиадных задач

В соответствии с п.п. 22 и 31 Положения о всероссийской олимпиаде школьников (далее – Олимпиада) школьный этап Олимпиады по информатике проводится по олимпиадным заданиям, разработанным муниципальной предметно-методической комиссией по информатике, а муниципальный этап  по олимпиадным заданиям, разработанным региональной предметно-методической комиссией по информатике.

В общем случае процесс создания олимпиадной задачи по информатике включает следующие основные этапы:



  1. разработка идеи и подготовка текста условия задачи;

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

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

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

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

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

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

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



  • тексты олимпиадных задач;

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

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

  • методические рекомендации по разбору предложенных олимпиадных задач.

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

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



  1. Общие требования к олимпиадным задачам

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

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

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

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

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

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

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

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

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



  1. Формирование комплектов олимпиадных задач

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

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

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

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

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


  1. Типы олимпиадных задач

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

    1. Типы задач для 9 – 11 классов

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

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

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

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

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

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

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

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



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

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

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

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

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



    1. Типы задач для 7 – 8 классов

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

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

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

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



    1. Типы задач для 5 – 6 классов

Если ранее рассмотренные типы задач характерны как для школьного, так и для муниципального этапа Олимпиады, то типы задач для 5 – 6 классов ориентированы только на проведение школьного этапа. К сожалению, во многих регионах категория обучающихся 5 – 6 классов практически не привлекается к участию в школьном этапе. Считается, что такие школьники не готовы к решению олимпиадных задач по информатике в силу того, что в соответствии с Базисным учебным планом предмет «Информатика и ИКТ» не входит в федеральный компонент для 5-6 классов, а относится к школьному компоненту, и во многих школах обучающиеся 5-6 классов не имеют возможности в той или иной форме изучать этот предмет. При этом следует учитывать, что этот предмет представлен в федеральном компоненте Базисного учебного плана для 3 и 4 классов начальной ступени обучения, то есть, к 5 классу у учащихся многих школ уже могут быть сформированы элементы информационных знаний и умений.

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

Целесообразность вовлечения в школьный этап Олимпиады по информатике младших школьников поддерживается также новым Федеральным государственным образовательным стандартом начального общего образования, утвержденным Приказом Минобрнауки России от 6 октября 2009 г. № 373 (http://www.edu.ru/db-mon/mo/Data/d_09/m373.html), который уже с первого класса реализуется во всех школах страны. В частности, этим стандартом предусматривается изучение особо важных для олимпиадной ориентации школьников тем, включая алгоритмы, множества, элементы комбинаторики, введение в понятие моделирования, начала логики, знакомство с информационными структурами, а также использование исполнителей для реализации алгоритмов. Особое внимание обращается на освоение младшими школьниками правил клавиатурного ввода, графического интерфейса, работы на компьютере и в компьютерной сети.

Понятно, что предъявлять к задачам для обучающихся 5 – 6 классов такие же требования, как и к задачам для старшеклассников, о которых речь шла выше, не совсем оправдано. Однако опыт проведения школьного этапа для таких школьников в ряде регионов страны (например, см. сайт http://imcs.dvgu.ru/works/work?wid=12124 ) показывает, что для выявления ранней одаренности у школьников младших классов могут с успехом использоваться следующие типы олимпиадных задач:



  • задачи с упрощенными исполнителями;

  • лабиринтные задачи;

  • конечные клеточные игры, включая игры, основанные на шахматных сюжетах;

  • задачи на геометрические построения;

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

  • задачи типа «черный ящик», включая задачи на выявление закономерностей;

  • задачи на тестирование заданных программ.

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

Заменой бумажной формы представления результатов решения олимпиадных задач для обучающихся 5 – 6 классов является запись решения в форме программы, предполагаемой достаточно распространенными программными системами учебного назначения, которые вполне доступны для младших школьников. Такими системами являются, например, КуМир, Скретч, Роботландия, различные вариации Лого и т.п. Использование этих систем на школьном этапе Олимпиады позволяет школьникам применить на практике возможности компьютера при решении задачи, представлять результаты своего труда на формальном языке, использовать элементы моделирования в процессе решения задачи и продемонстрировать свои умения работать с компьютером. Кроме того, в этом случае у жюри школьного этапа появляется возможность автоматизировать процесс проверки решений задач, что немаловажно при проведении олимпиады любого уровня.

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


  1. Содержание олимпиадных задач

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

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

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

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



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

  • дидактическая единица с одним символом «*» соответствует основному уровню сложности для 7-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. скачать

следующая >>
Смотрите также:
Методические рекомендации по разработке заданий для школьного и муниципального этапов всероссийской олимпиады школьников по информатике в 2011/2012 учебном году
519.31kb.
Методические рекомендации по разработке заданий для школьного и муниципального этапов всероссийской олимпиады школьников по математике в 2011/2012 учебном году
89.08kb.
Методические рекомендации по разработке заданий для школьного и муниципального этапов всероссийской олимпиады школьников по искусству (мхк) в 2010/2011 учебном году
269.15kb.
Методические рекомендации по разработке заданий для школьного и муниципального этапов всероссийской олимпиады школьников по информатике в 2010/2011 учебном году
551.12kb.
Методические рекомендации по разработке заданий для школьного и муниципального этапов всероссийской олимпиады школьников по информатике в 2010/2011 учебном году
551.12kb.
Методические рекомендации по разработке заданий для школьного и муниципального этапов Всероссийской олимпиады школьников по информатике в 2008/2009 учебном году
195.03kb.
Методические рекомендации по разработке заданий для школьного и муниципального этапов всероссийской олимпиады школьников по биологии в 2010/2011 учебном году
388.45kb.
Методические рекомендации по разработке заданий для школьного и муниципального этапов всероссийской олимпиады школьников по основам безопасности жизнедеятельности
642.42kb.
Методические рекомендации по разработке заданий для школьного и муниципального этапов всероссийской олимпиады школьников по русскому языку в 2010/2011 учебном году
166.29kb.
Методические рекомендации по разработке требований к проведению школьного и муниципального этапов всероссийской олимпиады школьников по математике в 2010/2011 учебном году
73.36kb.
Методические рекомендации по разработке заданий и требований к проведению школьного этапа всероссийской олимпиады школьников по английскому языку в 2011-2012 учебном году
281.35kb.
Методические рекомендации по разработке заданий для школьного и муниципального этапов всероссийской олимпиады школьников по английскому языку в 2010/2011 учебном году
656.44kb.