Проблеми олімпіад з інформатики. 3
Постановка проблем методами накладення обмежень. 3
Обмеження на використання готових засобів. 5
Обмеження на «програмування». 6
Проведення олімпіад з інформатики на основі тестів. 8
Тестові запитання олімпіади з інформатики для старшої вікової групи (X-XI класи) 9
Проблеми олімпіад з інформатики
При проведенні олімпіад з інформатики різного рівня протягом тривалого періоду часу виявився цілий ряд негативних моментів, пов'язаних як з організацією самих олімпіад, так і з викладанням інформатики в школах. Наведемо тут деякі з них.
1. Нерідко відзначається «занедбаність» деяких учасників олімпіад: їх утворення і розвиток відбувається стихійно, і іноді їм навіть незнайома частина матеріалу шкільного курсу інформатики. Ця стихійність проявляється в хитромудрих прийомах типу ELSE NEXT або навіть ELSE DIM на тлі незнання типових методів вирішення завдань. При вирішенні простих завдань такі школярі демонструють особливо витончені і сумнівні «трюки», але перед більш важким завданням стають у глухий кут. Їх увага спрямована не так на алгоритмізацію як особливий вид людського мислення і діяльності, не на постановку і рішення задач, а на мову програмування (часто - доступну версію Бейсика). Але відзначимо їх інтуїтивну тягу до інших, нестандартних шляхів вирішення завдань.
2. У міру вичерпання тематики завдань, поширення професійних ПЕОМ, потужних мов намітилася тенденція до вирішення на олімпіадах громіздких задач. Тексти до них теж громіздкі. Перевіряючі не встигають поглянути на рішення і «женуть» тести. А в них, особливо якщо окремі випадки очевидні, «хитрун» може написати:
ЯКЩО N = I то ВІДПОВІДЬ: = 1
ЯКЩО N = 2 то ВІДПОВІДЬ: = 3
(Авось вгадаю пару тестів)
3. Швидкодія різних мовних трансляторів, не кажучи вже про різні типи шкільної ВТ, істотно розрізняється. Тому єдине обмеження за часом на тести веде до дискримінації, наприклад, учасника, що працює на «Корвет», У порівнянні з тим, хто має доступ до ППЕВМ.
4. Можливості мов також сильно відрізняються. Наприклад, зручності процедур в Паскалі і в «старому» Бейсіку непорівнянні - і знову нерівність шансів.
Постановка проблем методами накладення обмежень
По відношенню до школярів мети олімпіади дві: виявити і здібності, і освіченість. Сформулюємо їх більш точно:
1. Виявити школярів з розвиненими здібностями до логіко-алгоритмічного мислення. Нерозвиненість цього мислення може бути замаскована використанням потужних готових програмних засобів або бібліотек потужного мови. Так, команда SORT в середовищі DBASE дозволяє взагалі не вміти складати алгоритми сортування. Можливо, цим пояснюється такий парадокс: школярі, які знають Турбо Паскаль, нерідко гірше вирішують невеликі «хитрі» завдання, ніж ті, хто працює на вільнюському Бейсике. Боротьба з цим Бейсиком - хороша школа виживання.
2. Виявити школярів освічені, з розвиненим системно-комбінаторних мисленням, що має виявлятися в умінні використовувати не тільки за призначенням, але і оригінально, нестандартно, творчо різноманітні готові програмні засоби і команди і вміти уникати програмування. Відсутність такого стилю мислення і освіченості, кругозору може бути замаскована високим рівнем техніки «голого» програмування.
В основі запропонованої нами концепції лежить припущення про те, що по суті своїй розумова діяльність і користувача готових ПС, і програміста однотипна і не залежить від потужності ВТ і ПС.
Метою цієї діяльності завжди є приведення комп'ютерного середовища в бажаний стан при обмежених коштах: кінцеве число команд і реалізованих алгоритмів і функцій, які є в наявності пам'ять і час. Нові покоління ЕОМ і мов програмування лише знімають старі обмеження, але людина неминуче наштовхується на нові.
Основною ідеєю пропонованої концепції є те, що саме при подоланні обмежень не тільки проявляються творчі здібності, але і, більш того, відбувається розвиток людини. Так, обмеженість можливостей кігтів і зубів стародавнього людини призвела до появи кремнієвих ножів.
Спробуємо викласти зміст нашої концепції на прикладі спорту, де обмеження виникли давно і не є чимось дивовижним, а становлять невід'ємну частину всіх змагань: стрибуни у висоту не використовують драбину, штангісти - важелі, марафонці - велосипеди. Як приклад постановки проблеми в спорті методом «штучних» обмежень уявімо таку ситуацію: перед початком велогонок у всіх велосипедів видалені передні колеса.
Звичайно, учасник може сісти в рейсовий автобус (заборонене засіб). Він може і піти пішки (в інформатиці - обійтися без ЕОМ). Але нас зараз цікавлять тільки ті, хто зуміє:
1) відремонтувати велосипед, виготовивши втрачені частини з підручного матеріалу (написати процедури, що розширюють «звужений» обмеженнями мова);
2) проїхати це відстань на одному колесі, нічого не вигадуючи і не конструюючи (нестандартно використовувати наявні засіб);
3) взагалі винайти і виготовити новий велосипед (несподівано для суддів). Повертаючись до інформатики, відзначимо, що сама тривіальна задача може стати надзвичайно важкою, якщо умова доповнити низкою обмежень на використовувані засоби.
При введенні обмежень важливі рівень і повнота їх системи: дуже сильні обмеження зроблять завдання нерозв'язною; занадто слабкі - тривіальної, нетворчих; неповна система обмежень дає можливість знайти «лазівку» - «законно» скористатися «незаконним» прийомом (в нашому прикладі - вчепитися за бампер автобуса).
Обмеження на використання готових засобів
Ознакою здібностей до алгоритмізації ми вважаємо вміння обходитися малими засобами, але комбінувати їх вільно, розширюючи свій арсенал, по суті - мова.
Тому замість чергової дискусії про те, «чий» мову краще, пропонуються обмеження, які, по-перше, вирівнюють умови для учасників, а по-друге, самі по собі є джерелом завдань, в тому числі і олімпіадних. Так, наприклад, при будь-якій мові реалізації можна заборонити:
1) GOTO і будь-які команди циклів (FOR, WHILE, REPEAT, заодно «постраждають» і команди типу REPLACE. FOR з середовищ DBASE);
2) всі функції і процедури з параметрами, крім введення-виведення;
3) асемблер, машинні команди (щоб уникнути обходу «знизу»);
4) безпосереднє звернення до пам'яті (PEEK, MEM та ін.).
Типовий прийом побудови завдання - заборонити операцію, функцію і запропонувати реалізувати її будь-якими залишилися засобами. Тим самим виконується і Внутріпредметние моделювання в стилі методики підручника А. Г. Кушніренко та ін.
Скласти алгоритм обчислення А'В (для простоти при В> = 0. А та В - цілі). Крім зазначених вище обмежень забороняється множення і ділення «в лоб».
Рішення на «старому» Бейсіку може бути таким
10 'Множення А * В без циклів і goto і *
Навряд чи це олімпіадних завдання, скоріше - ілюстрація стилю програмування в умовах «штучних» обмежень.
Якщо не заборонити використання функцій, можливий обхід «зверху» в такому стилі:
В = INT (ЕХР (LOG (A) + LOG (B) + 0.5))
що теж непогано, але не виявить уміння алгоритмізації. Це вже протилежний підхід - використання готових алгоритмів. Інший приклад - постановка явно рекурсивної завдання при забороні рекурсії. Формально заборонені виклики з підпрограм, все інше - можна, і особливо - бажане для деяких GOTO.
Обмеження на «програмування»
Ознакою іншого стилю мислення (назвемо його для користувача, на відміну від логіко-алгоритмічного «програміста») можна вважати уникнення программиро-вання, прагнення застосувати до свого завдання готові засоби, а якщо вони не годяться - знайти нестандартне, оригінальне застосування інших доступних засобів, провідне до мети, знову проявити здатність до творчості.
Характерною рисою такої діяльності є перетворення завдання, перехід до інших типів даних, програм і команд. Наприклад, цілого числа можна зіставити відрізок числової осі або послідовність одиниць.
Для такої діяльності необхідні:
1) освіченість, знання явних і неявних можливостей різних готових коштів, як в «улюбленому» мовою, так і поза ним;
2) сформованість системно-комбінаторних розумових операцій - бачення предметів і явищ в цілісності, взаємозв'язках; вміння будувати кілька взаємодоповнюючих точок зору на один і той же об'єкт, вміння оперувати понятійним і гарматними коштами з різних дисциплін (так, наприклад, з точки зору алгебри функція є відповідність, з точки зору геометрії - крива, з точки зору інформатики - алгоритм обчислення результату по заданому аргументу).
Для того щоб проявити ці якості учасника, потрібно, так би мовити, заборонити йому програмувати.
Це майже протилежно по відношенню до обмежень першого типу: щоб виявити здібності та досвід творчості в області алгоритмізації, ми змушували учасника складати досить витончені алгоритми для вирішення «простих» завдань (в прикладі - операція множення). Тепер же він отримує в розпорядження кошти, але - крім потрібних для програмування. Тепер логічно дозволити тільки лінійні алгоритми. Адже відповідна діяльність «користувача» - це побудова послідовності кроків по перетворенню середовища. Його легко забезпечити через заборону логічних виразів: саме перевірки умов «розщеплюють» алгоритм на цикли і розгалуження. Для уникнення програмування знову забороняємо машинні коди і асемблер. Все інше - можна. Команду типу НЦ ДЛЯ або FOR теж необхідно дозволити; вона потрібна для введення таблиць (теоретично і в майбутньому може виконуватися на N паралельних процесорах одне тимчасово, як би за один крок).
В ідеалі рішення завдання тепер має бути представлено у вигляді лінійної послідовності звернень до бібліотечних і стандартних функцій, процедур і програм (або навіть у вигляді командного файлу).
Доречно сказати тепер про електронні таблиці. З вбудованих в них циклів доведеться заборонити ітераційний цикл ДО заданої точності: він дозволяє «майже всі».
Наведемо спрощені приклади для ілюстрації завдань другого типу. Перший приклад - це множення через логарифми (див. Вище).
Потрібно з'ясувати, чи лежить точка всередині контуру, заданого координатами ланок.
Рішення (запропоновано школярами).
Вивести колір перевіряється точки, розташованої на екрані.
Намалювати на екрані контур (цикл FOR!).
Залити його кольором.
Знову вивести колір перевіряється точки.
Тонкі питання про «товстих» лініях контуру на екрані тут не ставимо: приклад показує нестандартне, лукаве і в той же час «наївне» рішення через пряме моделювання задачі на екрані,
Потрібно знайти максимальне з двох чисел А і В. функції МАХ і MIN, природно, заборонені.
Якщо забути заборонити функцію MIN, то можливий «обхід збоку»:
Рішення подібних завдань не зводяться до складання, алгоритмів, отримані алгоритми всього лише лінійні, але відрізняються яскравим творчим началом.
Проведення олімпіад з інформатики на основі тестів
Останнім часом все частіше піднімається питання про методику викладання олімпіад з інформатики. Традиційні олімпіади, як правило, орієнтовані на перевірку програмістських навичок і припускають наявність в учнів широким знанням в математиці і мовами програмування, що є пріоритетом фізико-математичних шкіл. Що ж робити основній масі захоплених хлопців? Як організувати олімпіаду для дітей, що навчаються в різних школах, за різними програмами, які вивчають різні мови програмування (а може, чи не тих, хто вивчає їх?), Що працюють на «різношерстої» обчислювальній техніці? З цього положення можна знайти вихід, якщо проводити окремо олімпіаду з програмування та інформатики. У деяких школах такі олімпіади проводяться на основі тестів.
Питання тестів підібрані таким чином, що дозволяють перевірити загальний рівень підготовки учнів і дають можливість вирішити головні проблеми, що виникають при проведенні з інформатики:
· Різноманітність обчислювальної техніки, що знаходиться в школах;
· Різний рівень викладання інформатики;
· Великий спектр алгоритмічних мов, що вивчаються в школах;
· Обмеження кількості обчислювальної техніки в школі, що проводить олімпіаду, а значить і кількості учасників олімпіади.
Принцип тестування дозволяє легко і швидко перевірити роботи учнів, а значить, в короткий термін визначити переможців.
Пропоновані тести розбиті за віковими группамVII - IX і X - XI класи. При підрахунку балів рекомендується використовувати принцип: кожну правильну відповідь - «+1» бал, неправильна відповідь - «-1» бал (якщо не знаєш відповіді, не намагайся вгадати його) і «0» балів за питання, на який відповіді немає.
В даному рефераті пропонується варіант тестового завдання олімпіади з інформатики для старшої вікової групи.
Тестові запитання олімпіади з інформатики для старшої вікової групи (X-XI класи)
1. Чи може одне і теж явище мати різні моделі?
2. Яку мінімальну кількість двійкових розрядів потрібно для того щоб закодувати великі та малі літери російського алфавіту і арабські цифри?
3. У поточному каталозі знаходяться програми LOGIN.BAT, LOGIN.EXE, LOGIN.COM. Яка програма буде виконана, якщо ви наберете в командному рядку LOGIN?
4. Послідовність записів, розміщених на будь-яких пристроях, що запам'ятовують, що розглядається в процесі пересилання і обробки як єдине ціле, називається:
5. Гіпертекст - це:
1) дуже великий текст;
2) структурний текст, в якому можна здійснювати переходи по «гарячим» словами;
3) текст, набраний на комп'ютері;
4) текст, в якому використовується шрифт максимального розміру.
6. Перевага двійкової системи числення полягає в тому, що:
1) двійкового коду дозволяє економити пам'ять комп'ютера;
2) електронні елементи з двома станами споживають менше електроенергії;
3) електронні елементи з двома станами найбільш прості в конструктивному виконанні.
7. Що можна розглядати як алгоритм?
1) інструкцію з користування метрополітеном;
9. Який пристрій комп'ютера може зробити шкідливий вплив на здоров'я людини?
2) системний блок;