Методичні рекомендації щодо проведення II етапу (районного, міського) Всеукраїнської олімпіади з інформатики. Метою проведення Всеукраїнських олімпіад з інформатики є : · стимулювання творчого самовдосконалення учнів, зацікавлення їх у якісному і поглибленому вивченні інформатики; · виявлення та розвиток обдарованих учнів, надання їм допомоги у виборі фаху, залучення до навчання їх у провідних вищих навчальних закладах України; · дотримання принципу наступності освіти шляхом залучення викладачів, аспірантів, студентів вищих навчальних закладів до активної допомоги у підвищені рівня знань, умінь і навичок учнівської молоді; · сприяння розвитку алгоритмічного мислення у школярів, підвищення інтересу до програмування; · формування команди для участі в Міжнародній олімпіаді з інформатики. Документом, що визначає завдання, структуру, технологію проведення Всеукраїнських олімпіад, є Положення про Всеукраїнські учнівські олімпіади з базових дисциплін, турніри, конкурси - захисти науково - дослідницьких робіт та конкурси Фахової майстерності (Наказ Міністерства освіти України № 305 від 18.08.98р.) Відповідно до Положення, ІІ етап олімпіади з інформатики проводиться в один або у два тури ( теоретичний + практичний або два практичних за рішенням журі). Практичні тури бажано проводити на комп'ютерах сумісних з IBM, та операційних системах DOS, Windows 9x/NT/2000/XP. На комп'ютері бажано встановити файловий менеджер (Far, Volkov Commander, Norton Commander і т.п.), або повідомити про його відсутність учасникам заздалегідь. Бажано, на час проведення туру олімпіади, фізично відключити локальну мережу від комп'ютерів учасників. На практичному турі бажано запропонувати учасникам олімпіади, на вибір, одну з мов програмування Pascal, C, C++ та систем програмування Turbo Pascal 7.0, Borland C++ 3.1. Саме такі компілятори буде використано на ІІІ та IV-му етапах. Не рекомендується дозволяти учасникам користуватися власною літературою, друкованими або рукописними матеріалами, засобами комунікації (Інтернет, мобільні телефони і таке інше). Завдання олімпіади в основному мають бути алгоритмічного типу. Основними результатами роботи учасника має бути: · алгоритм, що правильно та ефективно розв'язує поставлену задачу; · програма, що реалізує запропонований алгоритм. Запропоновані задачі можуть бути наступних типів: 1) Розробити та обґрунтувати алгоритм (теоретичний тур). 2) Розробити програму, що за вхідним файлом буде отримувати вихідний, згідно з умовами задачі. Задачі саме такого типу найчастіше пропонуються на олімпіадах в останні роки. 3) Розробити програму, що буде отримувати вхідні дані, та повідомляти про результати взаємодіючі з бібліотекою журі. Такий підхід зручний, коли необхідно, щоб програма учасника не мала на початку роботи всієї інформації, та отримувала її за допомогою звертання до бібліотеки. Наприклад, у такий спосіб можуть бути оформлені задачі-ігри. Задача такого типу "Нім" була запропонована на IV етапі Всеукраїнської олімпіади з інформатики у 1997 році. 4) За відомими вхідними даними отримати результати, що відповідають умові задачі. У цьому випадку необхідно здати не програму, а саме вихідний файл для кожного тесту. Звичайно, вхідні файли настільки великі, що розв'язки для них неможна знайти без комп'ютера. Задачі такого типу іноді пропонуються на міжнародній олімпіаді. Час, що учасник витратить на розв'язок задачі має приблизно ділитись у відношенні 2 (побудова алгоритму) до 1 (написання програми). На теоретичному турі можна не вимагати написання програми на одній з перелічених вище мов, замість цього бажано отримати від учасника обґрунтування правильності запропонованого алгоритму. Не рекомендується пропонувати задачі, розв'язання яких потребує використання архітектурних особливостей комп'ютерів, знань з області системного програмування (переривання, системні виклики), організації складного інтерфейсу користувача (меню, графіка), використання нестандартних бібліотек. Бажано, щоб задачі висвітлювали деякі з наступних тем: · робота з великими числами; · зберігання інформації в динамічній пам'яті; · сортування та пошук; · метод перебору варіантів, відсікання перебору; · елементи обчислювальної геометрії; · принцип динамічного програмування; · "жадібні" алгоритми; · алгоритми на графах; · елементи лексичного та синтаксичного розбору. При підготовці умов завдань бажано звернути особливу увагу на: обмеження на вхідні дані; формат вхідних та вихідних даних; імена файлів (назва файлу з вихідним текстом програми, що повинен здати учасник; назви вхідного та вихідного файлів); приклади вхідних та вихідних даних; описання функцій, що доступні у бібліотеці журі (для 3-го типу задач). Учасники олімпіади повинні мати змогу задавити питання по умовах задач. Як свідчить практика ІІІ та IV етапів Всеукраїнських та міжнародних олімпіад, бажано надавати цю можливість лише на протязі першої години кожного з турів. Якщо за цей час учасники знайдуть помилку або двозначність в умові, тоді до умови можна буде внести поправку, та вчасно оголосити про неї усім учасникам. Питання, що задає учасник, повинні передбачати відповідь "Так" або "Ні". В тих випадках, коли: на питання неможна відповісти "Так" або "Ні"; відповідь на питання учасника міститься у явному вигляді в умові задачі; питання стосується розв'язку задачі; відповідь на питання вимагає обчислень, що можуть бути проведені учасником самостійно виходячи з умов задачі, та загальних знань, - член журі повинен відповідати: "Без коментарів". Бажано, щоб на питання, які стосуються задачі, відповідала одна й та сама людина - автор задачі. У такому випадку учасники отримують однакові відповіді на однакові питання. При перевірці завдань теоретичного туру для кожної задачі повинна бути розроблена єдина система оцінок, що отримають учасники за більш, або менш ефективні розв'язки, відсутність або наявність доведення коректності застосованого методу, відсутність або наявність тексту відповідної програми (якщо це передбачено в умові). Задачі практичного туру рекомендується перевіряти за системою тестів. До кожної задачі необхідно підготувати набір тестових даних, які б дозволяли розрізнити вірні та невірні розв'язки, а серед вірних - більш та менш ефективні. Програму учасника необхідно відкомпілювати та запустити на кожному тесті окремо. Якщо програма видає результат, що задовольняє вимогам задачі, та працює не більше ніж час, що було виділено на цей тест, то учаснику нараховуються бали за цей тест. На міжнародній олімпіаді в останні роки практикується нарахування неповної кількості балів за тест, у випадку якщо програма видає неоптимальну відповідь (яка повністю задовольняє умовам задачі, та якщо час обчислення тесту не перевищує відповідне обмеження). На Всеукраїнських олімпіадах бали за тест або нараховуються, або не нараховуються. Рекомендована кількість тестів в наборі для однієї задачі - 10. Для більш складних задач це число можна збільшити до 15, для простих - зменшити до 7. Серед тестів мають бути тести невеликого розміру, виконання яких свідчить про правильність запропонованого алгоритму, тести які перевіряють коректність роботи програми у спеціальних випадках (вироджені випадки, відсутність розв'язку), та тести великого розміру, виконання яких свідчить про ефективність запропонованого алгоритму. Бажано вимагати від учасників олімпіади суворого дотримання форматів введення та виведення даних. У випадку порушення таких вимог (наприклад, зайвий пропуск у кінці рядку; зайве переведення рядку в кінці вихідного файлу; невірна назва вхідного або вихідного файлу і таке інше) учасники повинні каратися відчутним відсотком штрафних балів, або незарахуванням тесту чи задачі взагалі. Особливості проведення олімпіади При проведенні олімпіади з інформатики: · учасникам дозволено користуватися лише тими програмними засобами і довідниками, які надаються організаційним комітетом; · на ІІІ і ІV етапах передбачено використання лише IBM - сумісної техніки; · роботи виконуються за єдиними завданнями для всіх учасників, а присудження місць може проходити як за єдиними критеріями для всіх учнів усіх класів, так і для кожної паралелі зокрема - за рішенням журі. Додаткову інформацію можна отримати за адресою: http://olympiada.km.ua Сайт Хмельницької обласної Інтернет-олімпіади http://www.uoi.kiev.ua Сайт українських олімпіад з інформатики. За адресою http://www.uoi.kiev.ua/downloads/uoi/1998.txt знаходиться Положення про Всеукраїнські учнівські олімпіади з базових дисциплін, турніри, конкурси-захисти науково-дослідницьких робіт та конкурси Фахової майстерності. http://www.olymp.vinnica.ua/ Центр підтримки та проведення олімпіад школярів з використанням можливостей Internet. http://algolist.manual.ru/ Широкий огляд алгоритмів і методів розв'язання задач. http://olympiads.win.tue.nl/ioi/ Сайт міжнародних олімпіад з інформатики. Список рекомендованої літератури: · Д. Кнут Искусство программирования для ЭВМ - М.: Мир, 1976 - 3 тома (Основные алгоритмы, получисленные алгоритмы, сортировка и поиск) · Липский В. Комбинаторика для программистов. - М.: Мир, 1988 . · Грузман М.З. Эвристика в информатике. - Винница: Арбат, 1998. - 308 с. · Оре О. Теория графов. - М.: Hаука 1968. · Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. - М.: Мир 1979. · Кирюхин В.М., Лапунов А.В., Окулов С.М. Задачи по информатике. Международные олимпиады 1989-1996 гг. - М.: ABF, 1996 - 272 с. · BLIS3-BLIS9. Електронні журнали Хмельницького ОІППО.