HelpInformatik.COM

Інтернет-олімпіади з програмування

Кожна держава прагне до зміцнення свого наукового потенціалу. Це запорука її розвитку, добробуту громадян, а також необхідна умова визнання іншими країнами світу.

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

На виконання наказу Міністерства освіти і науки України від 01 листопада 2010 року № 1033 «Про заходи щодо розвитку системи виявлення та підтримки обдарованих і талановитих дітей та молоді», відповідно до Положення про Всеукраїнські учнівські олімпіади, турніри, конкурси з навчальних предметів, конкурси-захисти науково-дослідницьких робіт, олімпіади зі спеціальних дисциплін та конкурси фахової майстерності, затвердженого наказом Міністерства освіти і науки, молоді та спорту України від 22 вересня 2011 року №1099, зареєстрованого в Міністерстві юстиції України 17 листопада 2011 року за №1318/20056, з метою виявлення, розвитку та підтримки обдарованої молоді, сприяння широкому залученню школярів до інтелектуальних змагань, що проводяться з використанням мережі Інтернет.

Інформатика — це наука теоретична та прикладна (технічна, технологічна) дисципліна, що вивчає структуру і загальні властивості інформації, а також методи і (технічні) засоби її створення, перетворення, зберігання, передачі та використання в різних галузях людської діяльності

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

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

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

Головною особливістю олімпіади з інформатики є те, що учні реалізовують розв’язки завдань на комп’ютері. Завдяки тому, що розв’язок задачі – це практично реалізована програма є можливість автоматизувати процес перевірки учнівських робіт, що значно підвищує об’єктивність оцінки результату. В той же час, рівень складності завдань виходить за межі шкільної програми з інформатики, вимагає не тільки знань особливостей конкретної мови програмування, а й знань спеціальних розділів інших предметів [1].

 

Причинами спаду зацікавленості є особливості підготовки учнів до олімпіад з інформатики:

1. На відміну від олімпіад з інших предметів, учням 8-11 класів даються однакові задачі і завдання для розв’язання;

2. Щоб правильно розв’язати олімпіадні задачі, школяреві потрібно знати підвищений курс вивчення математики, і не тільки шкільний, а й на базі вищого навчального закладу. Наприклад, такі теми як «Рекурентні рівняння», «Числа Фiбoнaчi та Катaлaна», «Основні алгоритми на графах», що відносяться до курсу дискретної математики ВНЗ. За останні роки в олімпіадах використовують задачі з теорії ігор, математичного програмування, обчислювальної геометрії, елементів лексичного та синтаксичного аналізу, які теж не відносяться до тем шкільної математики.

3. Учні вже повинні знати і володіти навичками мови програмування, навіть якщо вони її ще не вивчали в школі. Також вони повинні оволодівати частиною алгоритмів, які відносяться до курсу інформатики вищих навчальних закладах: «жадібні алгоритми», динамічне програмування, використання динамічних структур, методи оптимізації алгоритмів.

 

Виділяють п’ять кроків підготовки учнів до олімпіади.

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

Другий крок. Коли розпочинається вивчення програмування і на наступних заняттях починають вводитися різні прийоми розв’язування задач і завдань за допомогою стандартних алгоритмів, які реалізовані на мові програмування. Вводиться термін «налагодження програми». Також рекомендується розглядати кілька вирішень розв’язання, для того, щоб дітей навчити елементам оптимального і стислого пошуку.

Третій крок. «Навчальна рефлексiя». Можливість учня навчати інших розв’язувати завдання. Це відбувається, коли учень розбирає завдання, і це допомагає йому визначити ознаку стислості і зрозумілості, оптимальності, також навчитися конкретно і чітко простежувати і пояснити роботу програми.

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

П’ятий крок. «Творча рефлексія». На цьому етапі учень вже складає завдання маючи авторське рішення, з різними тестами, за всіма вимогами .

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

Отже, щоб успішно виступити на олімпіаді вчитель повинен розпочати готувати учнів з 5-6 класів, а згідно думки М. Долинського – з першого класу. Підготовка до олімпіад може проводитися на факультативних та індивідуальних заняттях. У ході вивчення основ програмування відбувається й поступове уведення в суть та методику розв’язання простих олімпіадних задач.

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

Курс «Інформатики» має багато можливостей для розвитку творчого інтелекту учнів. Прикладом може бути робота школярів з моделями, пошук інформації в мережі Інтернет та багато іншого. Одним із видів творчої діяльності на уроках інформатики є розв'язування учнями різноманітних задач із програмування. Даний тип навчальної діяльності розвиває в учня творчі здібності та необхідні для цього процеси уяви, мислення, уваги й пам'яті.

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

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

Спробуємо сконструювати методичну схему організації навчальної діяльності у процесі розв'язування задач із програмування та підготовки до участі у предметній олімпіаді.

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

 

1. Схема розв’язування задач з програмування

Загальна схема розв’язування задач з програмування може мати такий вигляд:

 

I. Аналіз умови задачі. Зрозуміти зміст задачі, фабулу задачі. Учням треба відповісти на запитання:

—  що дано, що треба виконати для розв'язання задачі, що треба знайти;

— чи умова задачі є повною (повнота умови), тобто чи достатньо даних для її розв'язання, чи завжди задача має розв'язок;

— чи коректна умова (коректність умови), тобто чи не суперечить зміст задачі відомим учням знанням, означенням, фабулі.

 

II. Пошук шляхів розв'язування задачі

Замінити всі терміни умови задачі на їх означення, виписати всі необхідні формули.

Пошукати зворотні шляхи від невизначеного до даних умови задачі.

Спробувати уявити, що задача вже розв'язана.

Спробувати розбити задачу на окремі простіші задачі. Подивитися, чи вже розв'язували такі задачі?

Намагатися побудувати математичну модель.

 

III. Складання алгоритму розв'язування задачі

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

 

IV. Реалізація задачі мовою програмування. Набір її на комп'ютері

У разі наявності блок-схеми це вже досить просте завдання для учня.

 

V. Запуск, тестування, аналіз результатів. У разі необхідності зробити налагодження

Перед запуском програми треба підготувати варіанти тестів. Треба, щоб вони охоплювали всі можливі варіанти початкових даних. Наприклад, якщо треба розв'язати стандартну задачу з трьома відгалуженнями, то треба підібрати значення для них усіх. Для перевірки треба знати очікувані результати. Для цього учні повинні виконати деякі дії, наприклад, зробити обчислення за допомогою комп'ютера. Часто на цьому етапі не все складається так, як бажалося. Тому треба навчити учнів навичок налагодження. На початку це може бути виведення проміжних результатів, наприклад, оператор виведення тимчасово розміщений усередині циклу тощо.

 

VI. Повторне проходження всіх етапів розв'язування задачі. Пошук більш раціональних шляхів її розв'язування

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

 

2. Правила поведінки на олімпіаді

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

Перше правило.

На самому початку виконання завдань корисно набрати наведену нижче універсальну для розв’язку олімпіадної задачі програму (вона є працюючою!!!). Особливу увагу варто звернути на директиви компілятора (при використанні Pascal), наведені в зразку. За допомогою комбінації клавіш Ctrl+O+О поточні директиви компілятора можна записати на початку тексту програми й виправити так, як показано нижче.

{$A+,B-,D+,E+,F+,G-,I+,L+,N+,O-,P-,Q+,R+,S+,T+,V+,X+,Y+}
{$M 65520,0,655360}
var
  i,j,k:longint;
procedure readdata;
begin
  assign(input,'');
  reset(input);
end;
procedure outdata;
begin
  assign(output,'');
  rewrite(output);
  close(output)
end;
procedure initial;
begin
  fillchar(i,?,0);
end;
procedure run;
begin
end;
begin
    readdata;
    initial;
    run;
    outdata
end.

Далі можна скопіювати цю заготовку стільки разів, скільки завдань запропоновано,  й відразу назвати кожний файл так, як це потрібно за технічними вимогами олімпіади. У результаті вам не доведеться при переході від одного завдання до іншого починати роботу з самого початку. Спроба правити текст із рішенням одного завдання для прискорення набору тексту іншого веде тільки до породження помилок, на виправлення яких буде витрачено набагато більше часу. У розділі OPTIONSenviromentpreferences середовища програмування Turbo Pascal корисно встановити параметр Auto save [X] Editor Files (автозбереження файлів, які редагуються). Це гарантує автоматичне збереження тексту програми при кожному її запуску. Таким чином, якщо, наприклад, програма зависне і середовище програмування прийдеться запускати заново, то результат останнього редагування буде збережений (на жаль, під час змагань школярі найчастіше забувають самостійно час від часу запам'ятовувати зроблені ними зміни в тексті програм).

Друге правило

Потім варто дуже уважно прочитати умови всіх завдань і постаратися правильно (!!!) зрозуміти, в чому полягає кожне завдання. Якщо щось незрозуміло, у тому числі у форматі введення та виводу, то краще поставити запитання. Журі олімпіади має право не давати відповідь, якщо все очевидно з умови задачі. 

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

Третє правило

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

Четверте правило

У процедурі initial треба обнулити або присвоїти відповідні початкові значення всім глобальним змінним, за винятком тих, які будуть використовуватися як параметри циклів. Потім запрограмувати вивід результату в процедурі outdata так, як це потрібно в умові завдання. Це допоможе подальшому налагодженню програми й надалі не буде потрібно “простий” вивід переробляти в “правильний”. Таким чином, до цього моменту у вас уже повинна бути “працююча” програма. Вона, принаймні, повинна компілюватися, зчитувати дані й виводити результат, нехай і нульовий, але в потрібному форматі.

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

П’яте правило

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

  1. Перевірити дані на фактичну коректність, тобто чи завжди завдання має розв’язок для введеного набору даних, наприклад, чи немає ділення на 0 і т.п., якщо тільки в умові не сказано, що всі дані коректні у даному змісті.
  2. Визначити, чи відноситься дане завдання до знайомого вам класу, чи його розв’язання доведеться шукати “з нуля”.
  3. Спробувати знайти на папері точний розв’язок, хоча б тільки для малих розмірностей. Такий підхід найчастіше дозволяє виявити закономірності, які потім можна спробувати розширити й на загальний випадок. 
  4. Спробувати сформулювати умову існування розв’язку, нехай тільки необхідну або тільки достатню.
  5. Продумати й виписати достатню систему тестів.

Шосте правило

Запрограмуйте розв’язок завдання у вигляді викликів процедур і функцій, які поки що варто описати у вигляді “заглушок” (мнимої або порожньої дії або імітації дійсної дії, яку повинна виконувати ваша програма). У такий спосіб ви зможете налагодити логіку вашої програми, яка повинна залишатися працюючою.

Сьоме правило

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

Восьме правило

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

Дев’яте правило

Перш ніж остаточно створювати exe-файл, змініть ряд директив компілятора на наступні: D-,I-,L-,R-,Q-.

Десяте правило

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

Одинадцяте правило

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

 

Список рекомендованих сайтів для підготовки до олімпіади з інформатики

  • http://schoololymp.byethost32.com – школа олімпійського резерву при ВІППО
  • http://www.olymp.vinnica.ua – Всеукраїнські Інтернет-олімпіади з різних предметів (фізика, інформатика). На сайті розміщена цікава інформація про Всеукраїнські олімпіади по інформатиці, фізиці. Проводилася мережна олімпіада по інформатиці.
  • http://www.uoi.in.ua – Всеукраїнська олімпіада з інформатики
  • http://www.e-olimp.com.ua E-Olimp система підготовки та проведення олімпіад зі спортивного програмування
  • http://www.qbit.org.ua/ -Молодёжное научное общество QBit – Кубит – г. Харьков
  • http://algolib.chat.ru –алгоритми: методи розв’язання
  • http://algolist.manual.ru –алгоритми: методи розв’язання
  • http://olympiads.win.true.nl/ioi – Міжнародна олімпіада з інформатики
  • http://www.olympiads.ru – Події, задачі, тести, рішення, коментарі. На сайті також можна викачати бібліотеку для написання “перевірялок” до задач – Testlib.
  • http://neerc.ifmo.ru/School/ – На цьому сайті міститься інформація про олімпіади школярів по інформатиці, які проходять в Росії, в яких беруть участь Петербурзькі школярі
  • http://www.olympiada.km.ua/ – Задачі заочних і обласних олімпіад Хмельницької області. Архіви турнірів, конкурсів. Багато іншої корисної інформації.
  • http://comp-science.narod.ru/ – Матеріали олімпіад школярів по програмуванню в Пермській області; підготовка до олімпіад по програмуванню; дидактичні матеріали по алгебрі і геометрії; технологія генерації дидактичних матеріалів по математиці; дидактичні матеріали по інформатиці (задачі, тести); методична скарбничка; посилання на освітні ресурси Internet.
  • http://acm.timus.ru – Тут ви можете знайти деяку кількість задач з різних змагань. Перевіряюча система дозволяє вам перевірити ваш розв’язок для кожної задачі.
  • http://www.informatics.ru/ – Даний сайт присвячений російським олімпіадам школярів по інформатиці. Автори сайту – члени журі і наукового комітету Всеросійської олімпіади, а також тренери збірної команди Росії для міжнародної олімпіади. Тут викладаються матеріали Всеросійських олімпіад, учбово-тренувальних зборів по інформатиці, різні книги і статті, присвячені даній тематиці.
  • http://g6prog.narod.ru – Сайт присвячений докладному розбору олімпіадних задач по інформатиці. Рівень задач від міської до міжнародної олімпіад. Програмні тексти до задач не додаються (представлений словесний опис рішення). До деяких задач додаються тести. Є багато корисних книг по олімпіадних задачах і велика кількість посилань на аналогічні ресурси.
  • http://byoi.narod.ru – Архів республіканських, міських, районних олімпіад, зборів до IOI. Підбір рідкісних, ефективних алгоритмів.
  • http://homepages.compuserve.de/chasluebeck – Дуже великий архів задач по інформатиці на російській мові.
  • http://www.stream.newmail.ru/index.html – Тут можна отримати відповідь на питання про олімпіади, взнати останні новини, підготуватися до олімпіад. На сайті є бібліотека книг і докладний каталог ресурсів.

Дану публікацію підготували для Вас команда сайту HelpInformatik.COM
Автор: Сергій Дорошенко
Дата створення: 15.02.2017
Переглядів: 3441