Информатика. 9-11 классы: подготовка учащихся к олимпиадам. Задачи, упражнения, методические рекомендации

Подробное описание

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

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

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

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

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

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

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

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

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

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

Содержание

Введение    3

Тема 1. Десятичные целые числа. Понятие целого числа. Операции над целыми числами:
сложение, вычитание, умножение, целочисленное деление, нахождение остатка от деления    5

   I. Натуральные, целые, рациональные числа и операции над ними. Действительные числа. Простые и составные числа
(теоретические материалы)    5

   II. Работа с целыми числами (методы и приемы решения задач)    10

   III. Упражнения и задачи к теме    14

Тема 2. Системы счисления. Понятие системы счисления. Основание системы счисления. Позиционная запись числа.
Перевод записи числа из одной системы счисления в другую. Получение цифровой записи числа    15

   I. Основные понятия о системах счисления (теоретический материал)    15

   II. Применение понятий о системах счисления к решению задач (методы и приемы решения задач)    21

   III. Упражнения и задачи к теме    24

Тема 3. Элементы математической логики. Логические операции. Конструирование логических выражений
с использованием отношений и логических операций    25

   I. Элементы математической логики (теоретические материалы)    25

   II. Применение элементов математической логики в программировании (методы и приемы решения задач)    35

   III. Упражнения и задачи к теме    39

Тема 4. Массивы. Поиск в массиве. Сортировка и индексация. Задачи на заполнение массивов    40

   I. Типовые задачи с использованием массивов (методы и приемы решения задач)    40

   II. Упражнения и задачи к теме    50

Тема 5. Задачи на перечисление    52

   I. Примеры задач на перечисление и их решения (методы и приемы решения задач)    52

   II. Упражнения и задачи к теме    56

Тема 6. Применение массивов для моделирования целых чисел. Задачи сложения, умножения, вычитания
и деления чисел, заданных массивами цифр    58

   I. Задачи сложения. Умножения, вычитания и деления чисел, заданные массивами цифр
(методы и приемы решения задач)    58

   II. Упражнения и задачи к теме    65

Дополнительные материалы для углубленной подготовки к олимпиадам    65

I. Элементы комбинаторики (теоретические материалы)    65

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

   Размещения и перестановки    67

   Сочетания. Бином Ньютона    71

II. Задачи по теме «Файлы в Паскале. Текстовые файлы»    

   Указания    74

   Задачи    74

III. Построение структур данных с применением динамических переменных и указателей    76

   Способы адресации данных    76

   Прямая адресация    77

   Индексная адресация    77

   Косвенная адресация    78

   Динамические переменные и указатели    80

   Связные списки    81

   Замкнутые списки    86

   Двусвязные списки    90

   Стеки и очереди    91

   Двоичные деревья    94

   Задачи    98

Приложения    99

Приложение 1. Краткий справочник по языку программирования Турбо-Паскаль    99

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

Приложение 3. Задачи для самостоятельного решения    132

   I. Различные задачи умеренной сложности    132

   II. Некоторые задачи из конкурсных заданий краевых и городских олимпиад школьников по информатике разных лет    133

Приложение 4. Решения некоторых олимпиадных задач    140