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

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

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

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

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

(Реферат).

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

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

Улан-Удэ.

Зміст Проблеми олімпіад з інформатики 3 Постановка проблем методами накладення обмежень 3 Обмеження використання готових засобів 5 Обмеження на «програмування» 6 Проведення олімпіад з інформатики з урахуванням тестів 8 Тестові питання олімпіади з інформатики для старшої вікової групи (XXI класи) 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. Проте й У — цілі). Крім зазначених вище обмежень забороняється множення і розподіл «в лоб».

Рішення на «старому» Бейсике може бути такою |10 «Множення, А * У без циклів і goto і * | |20 PRINT «Запровадьте множники «| |30 INPUT А, У | | |40 M1 = А |‘передати параметри | |50 М2 = У |‘ | |60 R = 0 |‘нагромаджувач твори | |70 GOSUB 110 |‘ | |80 PR = У |‘забрати відповідь | |90 PRINT «твір = «; PR | | |100 END | | |110 IF М2 = 0 THEM RETURN |‘підпрограма для R:=R+M1*M2 | |120 М2 = М2 — 1 | | |130 R = R + Ml |‘множення зводиться додаванню | |140 GOSUB 110 |‘цикл через рекурсию | |150 RETURN |‘——-(|.

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

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

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

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

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

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

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

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

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

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

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

Приклад 2.

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

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

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

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

Залити його цветом.

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

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

Приклад 3.

Нужно знайти максимальне з цих двох чисел Проте й До функцій МАХ і MIN, природно, запрещены.

Решение.

Max := (A+B+abs (A-B))/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) таблица.

Результатом розподілу 1 101 101 на 110 у системі числення з повним правом 2 є: 1) 10 010, залишок 1; 2) 1001, залишок 1; 3) 10 110; 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) додати чи видалити поле.

Электронная пошта (Е-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=[pic] 2) F=[pic] 3) F=[pic] 4) F=[pic].

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

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

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

Какая логічна функція тотожна логічного функції 1) [pic] 2) [pic] 3) [pic] 4) [pic] 5) [pic].

В комп’ютер 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. A7 °F; 6) CAPITAL. A3A; 7) SUPPORT. A1.

Какая частина тексту програми впливає їхньому виконання? 1) оператор; 2) директива; 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.

CD F.

CD FS.

CD …

CD SF.

CD .P.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.

Куля белый?

[pic].