Cостязанія з інформатики (олімпіади )

Інформатика, програмування

Міністерство освіти республіки Бурятія

Бурятський державний університет

Коледж інформаційних технологій

Змагання з інформатики в школі (олімпіади)

( Реферат)

Виконав: Павлов А.І.

Перевірив: Цибікова Т. С.

Улан-Уде

2002

Зміст
Проблеми олімпіад з інформатики 3
Постановка проблем методами накладення обмежень 3
Обмеження на використання готових засобів 5
Обмеження на «програмування» 6
Проведення олімпіад з інформатики на основі тестів 8
Тестові запитання олімпіади з інформатики для старшої вікової групи (X-
XI класи) 9
Висновок 16
Література 17

Проблеми олімпіад з інформатики

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

1. Нерідко відзначається «занедбаність» деяких учасників олімпіад: їхосвіта та розвиток відбувається стихійно, і іноді їм навіть незнайомачастина матеріалу шкільного курсу інформатики. Ця стихійність проявляється вхитромудрих прийомах типу ELSE NEXT або навіть ELSE DIM на тлі незнаннятипових методів вирішення задач. При вирішенні простих завдань такі школярідемонструють особливо витончені та сумнівні «трюки», але перед більшважким завданням стають у глухий кут. Їх увага спрямована не наалгоритмізацію як особливий вид людського мислення і діяльності, не напостановку і вирішення завдань, а на мову програмування (часто - доступнуверсію Бейсіка). Але відзначимо їх інтуїтивне тягу до іншим, нестандартним шляхамвирішення завдань.

2. У міру вичерпання тематики завдань, поширення професійних
ПЕОМ, потужних мов намітилася тенденція до вирішення на олімпіадах громіздкихзавдань. Тексти до них теж громіздкі. Оцінювачі не встигають поглянути нарішення і «женуть» тести. А в них, особливо якщо окремі випадки очевидні,
«Хитрун» може написати:
ЯКЩО N = I то ВІДПОВІДЬ: = 1
ЯКЩО N = 2 то ВІДПОВІДЬ: = 3
ЯКЩО N = 9 то ...

(авось вгадаю пару тестів)

3. Швидкодія різних мовних трансляторів, не кажучи вже прорізних типах шкільної Вт, істотно відрізняється. Тому єдинеобмеження за часом на тести веде до дискримінації, наприклад, учасника,що працює на «Корвет», У порівнянні з тим, хто має доступ до ППЕВМ.

4. Можливості мов також сильно відрізняються. Наприклад, зручностіпроцедур в Паскалі і в «старому» Бейсіку неспівставними - і знову нерівністьшансів.

Постановка проблем методами накладення обмежень

По відношенню до школярів мети олімпіади два: виявити і здібності, іосвіченість. Сформулюємо їх більш точно:
Виявити школярів з розвиненими здібностями до логіко-алгоритмічногомислення. Нерозвиненість цього мислення може бути замаскованавикористанням потужних готових програмних засобів або бібліотек потужногомови. Так, команда SORT в середовищі DBASE дозволяє взагалі не вміти складатиалгоритми сортування. Можливо, цим пояснюється такий парадокс: школярі,знаючі Турбо Паскаль, нерідко гірше вирішують невеликі «хитрі» завдання, ніжті, хто працює на вільнюському Бейсіку. Боротьба з цим Бейсік - хорошашкола виживання.
2. Виявити школярів освічені, з розвиненим системно-комбінаторним мисленням, що має виявлятися в умінні використовувати не тільки за призначенням, але й оригінально, нестандартно, творчо різноманітні готові програмні засоби і команди і вміти уникати програмування.
Відсутність такого стилю мислення і освіченості, кругозору може бути замаскована високим рівнем техніки «голого» програмування.

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

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

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

Спробуємо викласти зміст нашої концепції на прикладі спорту, деобмеження виникли давно і не є чимось дивовижним, а становлятьневід'ємну частину всіх змагань: стрибуни у висоту не використовуютьдрабину, штангісти - важелі, марафонці - велосипеди. Як прикладпостановки проблеми у спорті методом «штучних» обмежень представимонаступну ситуацію: перед початком велоперегонів у всіх велосипеда видаленіпередні колеса.

Звичайно, учасник може сісти в рейсовий автобус (забороненезасіб). Він може і піти пішки (в інформатиці - обійтися без ЕОМ). Аленас зараз цікавлять тільки ті, хто зуміє:

1) відремонтувати велосипед, виготовивши втрачені частини з підручного матеріалу (написати процедури, що розширюють «звужений» обмеженнями мова);

2) проїхати це відстань на одному колесі, нічого не вигадуючи і не конструюючи (нестандартно використовувати наявні засіб);

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

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

При введенні обмежень важливі рівень і повнота їх системи: занадтосильні обмеження зроблять завдання нерозв'язною; занадто слабкі --тривіальною, нетворча; неповна система обмежень дає можливістьзнайти «лазівку» - «законно» скористатися «незаконним» прийомом (у нашомуприкладі - вчепитися за бампер автобуса).

Обмеження на використання готових засобів

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

Тому замість чергової дискусії про те, «чий» мову краще,пропонуються обмеження, які, по-перше, вирівнюють умови дляучасників, а по-друге, самі по собі є джерелом завдань, у томучислі й олімпіадних. Так, наприклад, при будь-якій мові реалізації можназаборонити:
1) GOTO і будь-які команди циклів (FOR, WHILE, REPEAT, заодно «постраждають» і команди типу REPLACE .. FOR з середовищ DBASE);
2) всі функції і процедури з параметрами, крім введення - висновку;
3) асемблер, машинні команди (щоб уникнути обходу «знизу»);
4) безпосереднє звернення до пам'яті (PEEK, MEM та ін.)

Цим вирівнюються можливості процедурних мов . Залишаються рекурсіябез параметрів і умовні команди. Цього достатньо для реалізації будь-якоїконструкції мови. Крім того, це зближує можливості звичайних мовпрограмування з «наскрізь» рекурсивними засобами алгоритмізації длявиконавців проекту «Пілотні школи». У конкретних випадках ці обмеженняможуть бути ослаблені або розширені автором завдання. Але що вводяться обмеженняповинні бути ретельно зважені, абсолютно прозорі для журі та учасника ів сукупності однозначні і сумісний.

Типовий прийом побудови завдання - заборонити операцію, функцію ізапропонувати реалізувати її будь-якими засобами, що залишилися. Тим самимвиконується і внутріпредметное моделювання в стилі методики підручника А.
Г. Кушніренко та ін

Прімер1.

Скласти алгоритм обчислення А (В (для простоти при В> = 0. А і В --цілі). Крім зазначених вище обмежень забороняється множення і ділення «улоб ».

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

Якщо не заборонити використання функцій, можливий обхід «зверху» втакому стилі:

В = INT (ехр (LOG (A) + LOG (B) + 0.5))що теж непогано, але не виявить уміння алгоритмізації. Це вжепротилежний підхід - використання готових алгоритмів. Інший приклад --постановка явно рекурсивної завдання при забороні рекурсії. Формальнозаборонені виклики з підпрограм, все інше - можна, і особливо --бажане для деяких GOTO ...

Обмеження на «програмування»

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

Характерною рисою такої діяльності є перетворення завдання,перехід до інших типів даних, програм і команд. Наприклад, цілоїможна зіставити відрізок числової осі або послідовність одиниць.
Для такої діяльності необхідні:освіченість, знання явних та неявних можливостей різних готовихкоштів, як у «любимого» мовою, так і поза ним;сформованість системно-комбінаторних розумових операцій - баченняпредметів і явищ в цілісності, взаємозв'язках; вміння будувати кількавзаємодоповнюючих точок зору на один і той самий об'єкт, вміння оперуватипонятійним і гарматними коштами з різних дисциплін (так, наприклад,з точки зору алгебри функція є відповідність, з точки зору геометрії
- Крива, з точки зору інформатики - алгоритм обчислення результату позаданому аргументу).

Для того щоб виявити ці якості учасника, потрібно, так би мовити,заборонити йому програмувати.

Це майже протилежно по відношенню до обмежень першого типу:щоб виявити здібності та досвід творчості в галузі алгоритмізації, мизмушували учасника складати досить витончені алгоритми для вирішення
«Простих» завдань (у прикладі - операція множення). Тепер же він отримує врозпорядження кошти, але - крім потрібних для програмування. Теперлогічно вирішити тільки лінійні алгоритми. Адже відповіднадіяльність «користувача» - це побудова послідовності кроків зперетворення середовища. Його легко забезпечити через заборону логічнихвиразів: саме перевірки умов «розщеплюють» алгоритм на цикли ірозгалуження. Для уникнення програмування знову забороняємо машинні коди іасемблер. Все інше - можна. Команду типу НЦ ДЛЯ або FOR тежнеобхідно розв'язати, вона потрібна для введення таблиць (теоретично і в майбутньомуможе виконуватися на N паралельних процесорах одне тимчасово, як би заодин крок).

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

Доречно сказати тепер про електронні таблиці. З вбудованих в нихциклів доведеться заборонити ітераційний цикл ДО заданої точності: віндозволяє «майже всі».

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

Приклад 2.

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

Рішення (запропоновано школярами).

Вивести колір перевіряється точки, розташованої на екрані.

Намалювати на екрані контур (цикл FOR !).

Залити його кольором.

Знову вивести колір перевіряється точки.

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

Приклад 3.

Потрібно знайти максимальне з двох чисел А і В. функції МАХ і MIN,природно, заборонені.

Рішення.

Max: = (A + B + abs (AB))/2.

Якщо забути заборонити функцію MIN, то можливий «обхід збоку»:

Max: = A + B-min (A, B).

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

Проведення олімпіад з інформатики на основі тестів

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

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

. різноманітність обчислювальної техніки, що знаходиться в школах;

. різний рівень викладання інформатики;

. великий спектр алгоритмічних мов, що вивчаються у школах;

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

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

Пропоновані тести розбиті за віковими группамVII - IX і X - XIкласи. При підрахунку балів рекомендується використовувати принцип: коженправильна відповідь - «1» бал, неправильна відповідь - «-1» бал (якщо незнаєш відповіді, не намагайся вгадати його) і «0» балів за питання, на якевідповіді немає.

У даному рефераті пропонується варіант тестового завдання олімпіади зінформатики для старшої вікової групи.

Тестові запитання олімпіади з інформатики для старшої вікової групи (X-

XI класи)

може одне і теж явище мати різні моделі?
1) Да;
2) Ні.

Яку мінімальну кількість двійкових розрядів потрібно для того, щобзакодувати великі/малі літери російського алфавіту та арабські цифри?
1) 2;
2) 3;
3) 4;
4) 5;
5) 6;
6 ) 7;
7) 8.

У поточному каталозі знаходяться програми LOGIN.BAT, LOGIN.EXE, LOGIN.COM.
Яка програма буде виконана, якщо ви наберете у командному рядку LOGIN?
1) LOGIN.BAT
2) LOGIN.EXE
3) LOGIN.COM

Послідовність записів, розміщених на яких -небудь запам'ятовуючихпристроях, що розглядається в процесі пересилання і обробки як єдинеціле, називається:
1) файлом;
2) масивом;
3) програмою.

Гіпертекст - це:
1) дуже великий текст;
2) структурний текст, у якому можна здійснювати переходи по «гарячим» словами;
3) текст, набраний на комп'ютері;
4) текст, у якому використовується шрифт максимального розміру.

Перевага двійкової системи числення полягає в тому, що:
1) двійковий код дозволяє економити пам'ять комп'ютера;
2) електронні елементи з двома станами споживають менше електроенергії;
3) електронні елементи з двома станами найбільш прості в конструктивному виконанні.

Що можна розглядати як алгоритм?
1) інструкцію з користування метрополітеном;
2) схему метро;
3) правила користування телефоном-апаратом;
4) телефонний довідник.

Мінімальним об'єктом у текстовому редакторі є:
1) символ;
2) слово;
3) піксель;
4) абзац;
5) файл.

Яке пристрій комп'ютера може зробити шкідливий вплив на здоров'ялюдини?
1) гнучкий диск;
2) системний блок;
3) монітор;
4) клавіатура;
5) жорсткий диск;
6) блок живлення.

Тексту обсягом у 2Кбайта відповідає:
1) символ;
2) абзац;
3) сторінка;
4) книга.

Основним елементом електронної таблиці являєтся:
1) осередок;
2) стовпець;
3) рядок;
4) таблиця.

Результатом поділу 1101101 на 110 в системі числення з основою 2є:
1) 10010, залишок 1;
2) 1001, залишок 1;
3) 10110;
4) 1011.

В електронній таблиці виділена ділянка A2: B4. Скільки осередків він займає?
1) 3;
2) 4;
3) 5;
4) 6.

14. Розшифруйте значення рядки:

486DX2/66/4/256/210/3, 5''/ 5,25''/ 2s1p/512/14''SVGA.28.

Яку мінімальну кількість кульок має бути в кошику, щоб програмапрацювала вірно?
1) будь-який;
2) ні одного;
3) один.

Основним елементом бази даних є:
1) запис;
2) форма;
3) поле;
4) таблиця;
5) тип.

Принцип відкритої архітектури означає, що:
1) комп'ютер зроблений єдиним нероз'ємним пристроєм;
2) можлива легка заміна застарілих частин комп'ютера;
3) нова деталь комп'ютера буде сумісна з усім тим обладнанням, яке використовувалося раніше.

Структура бази даних зміниться, якщо:
1) додати або видалити запис;
2) поміняти місцями запис;
3) відредагувати рядок;
4) додати або видалити поле.

Електронна пошта (E-mail) дозволяє передавати:
1) повідомлення;
2) файли;
3) повідомлення та додані файли;
4) WWW-сторінки.

Модем забезпечує:
1) модуляцію (перетворення двійкову інформацію в аналогову);
2) демодуляцію (перетворення аналогової інформації в двійкову);
3) модуляцію і демодуляцію;
4) посилення сигналу.

Кеш-пам'ять жорсткого диска призначена для:
1) збільшення обсягу жорсткого диска;
2) прискорення доступу до даних на жорсткому диску;
3) прискорення читання інформації з оперативної пам'яті;
4) збільшення обсягу відеопам'яті.

Мікропроцесор служить для:
1) складення двійкових чисел;
2) переведення чисел із двійкової системи числення в десяткової;
3) оперативного запам'ятовування команд;
4) розпізнавання коду програми.

На логічному диску А задано повний шлях до файлу DOCPROBA.TXT. Якеповне ім'я файлу?
1) C: DOCPROBA.TXT;
2) A: PROBA.TXT;
3) DOCPROBA.TXT;
4) TXT;
5) A: DOCPROBA . TXT.

Який логічної функції відповідає наступна таблиця істинності:
| A | B | F |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

1) F =
2) F =
3) F =
4) F =

Пам'ять якого виду використовується для запису та читання інформації?
1) ОЗУ;
2) ПЗУ;
3) гнучкі диски;
4) жорсткі диски.

Хто є основоположником вітчизняної обчислювальної техніки?
1) Д. М. Лозинський;
2) С. О. Лебедєв;
3) А. А. Марков;
4) М. Р. Шура-Бура.

Двійкове кодування одного символу (букви) вимагає кількості інформації,рівне:
1) 1 биту;
2) 1 байту;
3) 4 бітам;
4) 1 кілобайт.

Яка логічна функція тотожна логічної функції
1)
2)
3)
4)
5)

У комп'ютер Pentium (64-розрядна шина даних і 32-розрядна шина адреси)встановлена пам'ять 16 Мбайт. Яке адресний простір цього процесора?
1) 264;
2) 232;
3) 16 Мбайт;
4) 64 біт.

Які файли відповідають масці?? Р *. А??
1) PPEPSI.ABC;
2) PEDDY.A1;
3) PEPPER.ARJ;
4) PEPSI.A1;
5) PEPPY.A7F;
6) CAPITAL.A3A;
7) SUPPORT.A1.

Яка частина тексту програми не впливає на її виконання?
1) оператор;
2) директива; < br> 3) коментар;
4) дужки.

Американський математик - автор теорії ігор:
1) Джон Нейман;
2) Біл Гейтс;
3) Стів Джобс .

Яке грецьке поширена назва «саламанской дошки»?
1) Суан-пака;
2) серобяна;
3) абак.

Стан системи, при якому вона перестає видавати результати іреагувати на запити ззовні:
1) зависання;
2) зациклення;
3) відключення монітора.

Помножте два числа 121 і 21 в системі числення з основою 3.

Яка програма синтаксично перевіряє оператор і тут же його виконує?
1) компілятор;
2) інтерпретатор;
3) редактор;
4) відладчик.

Яка кількість цифр у двійковій системі числення?
1) 10;
2) 16;
3) 8;
4) 2.

Змінна задана, якщо відомі її:
1) тип;
2) тип, ім'я, значення;
3) ім'я, значення,
4) значення.

Під час початкового завантаження DOS користуються двома текстовими файлами -
CONFIG.SYS та AUTOEXEC.BAT. Який з цих файлів завантажується перший?
1) CONFIG.SYS;
2) AUTOEXEC.BAT.

Основна технологічний ланцюжок рішення задачі з використаннямкомп'ютера:
1) побудова моделі - постановка задачі - розробка та виконання алгоритму - аналіз результатів;
2) постановка завдання - побудова моделі - розробка і виконання алгоритму - аналіз результатів;
3) постановка задачі - розробка і виконання алгоритму - побудова моделі - аналіз результатів.

Визнач дерево каталогів:
Який каталог буде поточним після виконання наступних команд:

CD F

CD FS

CD ....

CD SF

CD .. S
1) SFS;
2) FSF;
3) SS;
4) SSS;
5) FFS.

Висновок

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

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

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

Література

o Бочкін А. І. Інформатика: Довідник за рішенням задач підвищеної труднощі. ВГПИ, Вітебськ, 1994 o Інформатика і освіта, 1997, № 4 o Інформатика і освіта, 1997, № 5 o Інформатика і освіта, 1997, № 8 o Інформатика і освіта, 1996, № 6 o Педагогіка, 2000, № 9
-----------------------немає

немає

так

Кошик порожній?

початок

кінець

Опустити в ящик 1

взяти куля

Опустити в ящик 2

Шар білий?