Проблеми олімпіад з інформатики. 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 і * 20 PRINT "Введіть множники"
40 M1 = А 'передати параметри
Навряд чи це олімпіадних завдання, скоріше - ілюстрація стіляпрограммірованія в умовах «штучних» обмежень.
Якщо не заборонити використання функцій, можливий обхід «зверху» в такому стилі:
В = 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. Який пристрій комп'ютера можетоказать шкідливий вплив на здоров'я людини?