Методика підготовки учнів до олімпіад з інформатики.

Методика підготовки учнів до олімпіад з інформатики.

Підготовка учня до олімпіади починається з підготовки вчителя. Проблеми, що постають перед учителем:

• Вивчення нових форм проведення олімпіад.
• Знання алгоритмів розв'язання олімпіадних завдань.
• Наявність самих завдань.
• Знання мов програмування.
• Навчання учнів правильної організації діяльності на олімпіаді.

Всім давно відомо, що шкільний курс інформатики - це одне, а олімпіади з інформатики - це зовсім інше. Але, навіть якщо застосувати диференційований підхід до навчання школярів, навряд чи годин інформатики вистачить для підготовки до олімпіад окремих школярів.

Підготовка учнів до олімпіад частіш за все - особистий ентузіазм учителя. Але освіта не повинна триматися на ентузіазмі. Інакше виходить, що поки є ентузіазм - справа іде, закінчився - і все ...

Школярі можуть готуватися до олімпіад  і в позаурочний час, але у них як мінімум повинен бути домашній комп'ютер. В ідеалі має бути ще й Інтернет. При наявності ПК та Інтернету можна розв’язувати задачі на одному зі спеціалізованих сайтів з автоматизованою перевіркою рішень, наприклад на сайті Школа програміста. На таких сайтах ведуться рейтинги учасників за кількістю розв'язаних задач, проводяться онлайн-змагання, які зазвичай носять тренувальний характер. Два найбільших російських архіву завдань:

1. Онлайн-система тестування олімпіадних завдань Саратовського державного університету. http://acm.sgu.ru;
2. Онлайн-система тестування олімпіадних завдань Уральського державного університету. http://acm.timus.ru.

Незважаючи на те, що коло завдань на олімпіадах з програмування обмежений, розв’язання задачі може бути складним не тільки для учня, але і для вчителя, так як деякі завдання вимагають знання вищої математики. Завдання можна класифікувати по ряду ознак: за тематикою, за очікуваною складності алгоритму, складності структур даних і довжиною програми. Всі ці характеристики важливі при виборі завдання для розв’язання, однак, тут навряд чи вдасться дати будь-які рекомендації - ставлення до них істотно залежить від знань, досвіду, пристрасті і техніки учасника. Алгоритм і програма багато в чому залежать від проблемної області завдання. Тому корисно знати основні класи завдань і типові прийоми їх вирішення.

Оскільки багато завдань вельми і вельми схожі, необхідно навчитися розв’язувати завдання з усього діапазону. Можна виділити наступні групи алгоритмів:

1. Алгоритми над цілими числами.
2. Рекурсія.
3. Сортування.
4. Переборні задачі.
5. Геометричні задачі.
6. Динамічне програмування.
7. Графи і дерева.
8. Текстові перетворення.

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

На самому початку корисно набити універсальну заготовку для розв’язання  олімпіадної задачі (процедури введення даних та виводу результату). Школярі часто забувають самостійно час від часу запам'ятовувати зроблені ними зміни в тексті програм, тому у розділі OPTIONS \ enviroment \ preferences корисно встановити параметр Auto save [X] Editor Files (автозбереження редагованих файлів). Це гарантує автоматичне збереження тексту програми при кожному її запуску.

На наступному етапі учню необхідно уважно прочитати умову, не пропускаючи жодної фрази. Неправильне розуміння умови може призвести до того, що він буде розв’язувати  зовсім інше завдання, а не те, що задано. Зазвичай в умові є так зване "літературне введення", що додає завданню сюжет. Читання такого опису зазвичай стомлює, відволікає, а також розслабляє, так як автори завдань зазвичай мають почуття гумору. Проте у введенні може, прямо або побічно, міститися важлива інформація, що стосується умови. Якщо " літературне введення " не винесено в окремий розділ, то його доведеться прочитати цілком. Зазвичай це роблять не дуже уважно, вишукуючи початок змістовного тексту. Ключова умова також може бути схована, наприклад, у форматі вихідних даних. Без цієї умови завдання може бути зовсім іншим, але теж цілком коректним. Помилки при читанні умови дорого обходяться. Якщо з точки зору формальної логіки умова задачі можне трактуватися неоднозначно - слід ставити запитання експертам. Часто трапляється, що після детального прочитання задачі, не знаєш, як до неї підступитися. У такому випадку рекомендується відкласти її і читати наступну. Наш мозок здатний працювати підсвідомо, навіть у той час, коли працює над іншою задачею.

Якщо учень приступив до розв’язання конкретного завдання і основна структура даних для нього зрозуміла, можна описати основні глобальні змінні і набити процедуру введення даних

(procedure readdata;

begin

    assign (input ,'');

    reset (input);

    ...

 end;),

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

(procedure outdata;

 begin

     assign (output ,'');

     rewrite (output);

     ...

     close (output)

 end;).

Під час запису результатів роботи програми в файл зазвичай проблем практично не виникає. Помилки у форматі виводу можуть бути пов'язані з відсутністю роздільників (прогалин чи символів переведення рядка) між виведеними в файл числами або з формою запису дійсного числа.

Зверніть увагу, що для організації введення даних з текстового файлу наявність файлової змінної типу text в програмі зовсім не обов'язково. Більш того, перенаправлення стандартного потоку введення input і потоку виведення output у файли є і більш зручним при програмуванні і позбавляє від ряду помилок. Після подібного перенаправлення введення даних з файлу здійснюється за допомогою звичайних процедур read і readln, а вивід - за допомогою write і writeln без вказівки в якості першого параметра імені  файлової змінної. Такий підхід позбавляє від типової помилки при роботі з текстовими файлами, яка полягає в тому, що в деяких зверненнях до процедур введення або виведення ім'я файлової змінної виявляється пропущеним. Це не порушує роботу програми в цілому, так як частина інформації може бути записана в файл, а частина - виведена на екран. Друга типова помилка при роботі з файлом, відкритим на запис - відсутність в кінці програми команди, що закриває файл. У такому випадку, створюваний програмою вихідний файл виявиться порожнім. Справа в тому, що реальний запис даних на жорсткий диск відбувається при виконанні команди close. Але і від цієї помилки робота зі стандартним потоком виводу рятує. Справа в тому, що файл output закривається при закінченні роботи програми автоматично, незалежно від наявності або відсутності команди close (output).

Далі учню необхідно побудувати математичну модель задачі, пошукати той клас стандартних завдань і алгоритмів, який пов'язаний з даним завданням. Чітко сформулювати базовий клас задачі. Якщо одне із значень виражається через інше необхідно записати рекурентне співвідношення. Особливо важливо побудова моделі в геометричних задачах. Любитель цікавих завдань повинен знати всі способи подання прямої на площині, в просторі та зв'язок між ними. Задачі дискретної математики, до яких належить більшість олімпіадних завдань з інформатики, часто зводяться до перебору різних комбінаторних конфігурацій об'єктів та вибору серед них найкращого, з точки зору умови тієї або іншої задачі. Тому знання алгоритмів генерації найбільш поширених комбінаторних конфігурацій є необхідною умовою успішного розв’язання олімпіадних завдань в цілому. Важливо також знати кількість різних варіантів для кожного типу комбінаторних конфігурацій, так як це дозволяє реально оцінити обчислювальну трудомісткість вибраного алгоритму розв'язання того чи іншого завдання на перебір варіантів і, відповідно, його прийнятність для вирішення даної задачі, з урахуванням її розмірності. Крім того, при розв’язанні завдань корисним виявляється вміння для кожної з комбінаторних конфігурацій виконувати наступні операції: за наявною конфігурації одержувати наступну за нею в лексикографічному порядку; визначати номер даної конфігурації в лексикографічній нумерації всіх конфігурацій, і, навпаки, за порядковим номером виписувати відповідну йому конфігурацію. Перераховані підзадачі в програмуванні зазвичай розглядають для наступних комбінаторних конфігурацій: перестановки елементів множини, підмножини множини, сочетання з n елементів множини по k елементів, розміщення, розбиття множини, розбиття натуральних чисел на складові. При генерації різних конфігурацій використовуються в основному нерекурсивні алгоритми. Досвідчені ж учасники олімпіад у подібних випадках при програмуванні використовують в основному саме рекурсію, за допомогою якої рішення розглянутих завдань часто можна записати більш коротко і прозоро.

Учню треба запрограмувати рішення задачі у вигляді викликів процедур і функцій, які поки що слід описати у вигляді "заглушок" (уявної чи порожньої дії або імітації справжнього дії, які повинна виконувати програма). Таким чином він зможе налагодити логіку програми, яка знову ж таки повинна залишатися робочою. При необхідності треба витратити півхвилини і дописати коментарі про те, що за значення зберігаються в кожній із змінних, що повертає та чи інша функція і т.д.

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

Якщо ж учень не придумав ефективного розв’язку  завдання, то нехай вирішить  його по-простому: наприклад, за допомогою повного перебору. Якщо і це складно, то хай спростить собі завдання, тобто відкине умови, які йому заважають або доб’ється, щоб програма проходила на самих простих тестах. Аналогічно слід вчинити з завданнями, на вирішення яких у нього не вистачило часу. Рекомендація ж прочитати умову задачі ще раз вже після рішення задачі, тільки на перший погляд здається парадоксальним. Часто виявляється, що школярі вирішували все ж трохи не те завдання, яке потрібно.

Домігшись того, щоб програма компілювалась, учню необхідно переконатися в її правильності. Проблеми можуть бути в дрібних помилках, допущених в процесі написання: переплутані імена змінних, невірний знак у формулі і т.д. Рішення може бути принципово неправильним або неефективним. Розмір масивів може бути недостатнім або, навпаки, надмірним, що буде викликати помилку "перевищено межу пам'яті". Тому програму необхідно тестувати, якщо, звичайно, мова йде не про останні хвилини змагань.  Перше правило тестування - перевіряти завдання на тесті (наборі вхідних даних) з прикладу. Далі, хай не лінується придумувати свої тести, та використовує багато "маленьких" тестів. Друге правило – нехай уважно перевіряє, що програма видала на тесті. Окрім "маленьких" тестів, необхідно завжди перевіряти рішення на так званому "максимальному" тесті. Для кожного завдання слід, якщо це можливо, згенерувати "максимальний" тест - повністю випадковий великий тест з максимальними обмеженнями. Часто такий тест призводить до помилки часу виконання. Звичайно, відповідь до такого тесту перевірити нелегко, але часто за ним легко зрозуміти, що вона - неправильна. Додавання в програму численних перевірок, краще всього - вичерпних, полегшує використання максимальних тестів. Вічна дилема: що краще - тестувати або перевіряти логіку? Якщо в програмі є невелика частина, що викликає великі сумніви, краще її обміркувати і відразу написати правильно. Бо якщо в програмі є й інші помилки, тестування може виявитися довгим і виснажливим. Необхідно витримувати баланс між цими підходами. По ходу змагань учню доводиться регулярно приймати тактичні рішення. Перевіряти рішення далі або відправити його у журі? Тестувати, налагоджувати програму або шукати помилки? Важливо правильно розставляти пріоритети. Що важливіше в останню годину змагань - надійне рішення однієї задачі або ризикована спроба вирішити ще дві? На практиці складно приділити тактиці достатньо уваги.

Одна з типових помилок при програмуванні олімпіадних завдань - відсутність ініціалізації глобальних змінних. Нульові значення всім статичним змінним у програмі дати досить легко. Зробити це можна, наприклад, так: fillchar (i, ofs (Last)-ofs (i) + sizeof (Last), 0). Тут i - ім'я обов'язково першою з описаних в програмі змінних , Last-останньої. Таким чином дана стандартна процедура заповнить нулями всі байти пам'яті, які використовують статичні змінні. Після виконання цієї операції всі числові змінні, в тому числі й елементи масивів, отримають нульові значення, всім символьним буде присвоєно символ з кодом 0, а всім строковим - порожні рядки. Якщо ж кількість глобальних змінних у програмі невелика і не для всіх з них нуль підходить в якості початкового значення, то ініціалізацію можна проводити для кожної змінної окремо. Іноді масиви зручно описувати і задавати в розділі констант шляхом безпосереднього перерахування значень всіх елементів масивів. Для розміщення усіх глобальних змінних програмі відводиться не більше 64 кілобайт оперативної пам'яті. Однак при вирішенні завдань іноді потрібно завести декілька масивів, розмір кожного з яких не менше 32 кілобайт. Досить просто вирішити подібну проблему:

 const n = 150;

 type aa = array [1 .. n, 1 .. n] of integer;

 var a: aa; {a - масив}

       b: ^ aa; {b - покажчик на масив}

       i, j: integer;

 begin

    fillchar (a, sizeof (a), 0);

    new (b); {створення динамічного масиву}

    b ^: = a; {копіювання масиву a у динамічний масив}

    for i: = 1 to n do

    for j: = 1 to n do b ^ [i, j]: = i + j; {звернення до елементів динамічного масиву}

    ...

 end.

З прикладу видно, що робота з динамічними масивами не набагато відрізняється від роботи зі статичними. Причому використовувати цей прийом можна "за зразком", не вдаючись в механізм роботи з вказівниками. Якщо ж розмір двовимірного масиву перевершує 64 кілобайт, то створити його за допомогою динамічних змінних можна, наприклад, наступним чином:

 const n = 500; m = 100;

 type aa = array [1 .. n] of integer;

 var b: array [ 1 .. m] of ^ aa; {b - масив покажчиків на одновимірний масив}

       i, j: integer;

 begin

      for i: = 1 to m do new (b [i]); {створення m динамічних масивів}

      for i: = 1 to m do

      for j: = 1 to n do b [i] ^ [j]: = i + j; {звернення до елементів двовимірного масиву}

      ...

 end.

Таким чином, використання динамічних змінних дозволяє практично не змінювати алгоритм розв'язання задачі у випадку, коли використання статичних масивів вже неможливо. Використання ж таких змінних вимагає лише невеликий акуратності в їх створенні та коректного поводження з уже створеними динамічними змінними.

Отже, під час підготовки до олімпіади з інформатики необхідно не тільки вчити учнів методів розв’язування задач та основним алгоритмам.  Учнів потрібно вчити вмінню керування своєю діяльністю, розподілом часу на розв’язання кожної задачі, вмінню розбивати процес розв’язання задачі на етапи, виділяти певні етапи та їх виконувати. До олімпіади учнів необхідно готувати теоретично, практично та психологічно. У процесі психологічної підготовки необхідно налаштувати учасника на бажання і вміння максимально реалізувати свої потенційні можливості (зауважте - не перемогти, а максимально реалізувати) в екстремальних умовах, які пред'являє олімпіада.

І взагалі, щоб навчитися розв’язувати олімпіадні завдання з інформатики, треба розв’язувати завдання з інформатики...