Реферат: 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. Возможности языков также сильно отличаются.Например, удобства процедур в Паскале и в «старом» Бейсике несопоставимы — иснова неравенство шансов.

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

По отношению к школьникам цели олимпиады две: выявить испособности, и образованность. Сформулируем их более точно:

1.  Выявить школьников с развитымиспособностями к логико-алгоритмическому мышлению. Неразвитость этого мышленияможет быть замаскирована использованием мощных готовых программных средств илибиблиотек мощного языка. Так, команда 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...

Ограничения на «программирование»

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

Характерной чертой такой деятельности являетсяпреобразование задачи, переход к другим типам данных, программ и команд.Например, целому числу можно сопоставить отрезок числовой оси илипоследовательность единиц.

Для такой деятельностинеобходимы:

1)  образованность, знание явных инеявныхвозможностейразличныхготовыхсредств, как в «любимом» языке, так и вне его;

2)  сформированностьсистемно-комбинаторных мыслительныхопераций — видение предметов иявлений в целостности, взаимосвязях; умение строить несколько взаимодополняющихточек зрения на один и тот же объект, умение оперировать понятийными иорудийными средствами из различных дисциплин (так, например, с точки зрения алгебрыфункция есть соответствие, с точки зрения геометрии — кривая, с точкизренияинформатики — алгоритм вычисления результата по заданному аргументу).

Для того чтобы проявить эти качества участника, нужно, таксказать, запретить ему программировать.

Это почти противоположно по отношению к ограничениям первоготипа: чтобы выявить способности и опыт творчества в области алгоритмизации, мывынуждали участника составлять довольно изощренные алгоритмы для решения«простых» задач (в примере — операция умножения). Теперь же он получает враспоряжение средства, но — кроме нужных для программирования. Теперь логичноразрешить только линейные алгоритмы. Ведь соответствующая деятельность«пользователя» — это построение последовательности шагов по преобразованию среды.Его легко обеспечить через запрет логических выражений: именно проверки условий«расщепляют» алгоритм на циклы и ветвления. Для избежания программированияснова запрещаем машинные коды и ассемблер. Всё остальное — можно. Команду типаНЦ ДЛЯ или 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.  Может ли одно и тоже явление иметьразные модели?

1)   Да;

2)   Нет.

 

2.  Какое минимальное количестводвоичных разрядов потребуется для того чтобы закодировать прописные и строчныебуквы русского алфавита и арабские цифры?

1)   2;

2)   3;

3)   4;

4)   5;

5)   6;

6)   7;

7)   8.

 

3.  В текущем каталоге находятсяпрограммы LOGIN.BAT, LOGIN.EXE, LOGIN.COM. Какая программа будет выполнена, если вы наберёте вкомандной строке LOGIN?

1)   LOGIN.BAT

2)   LOGIN.EXE

3)   LOGIN.COM

4.  Последовательность записей,размещённых на каких-либо запоминающих устройствах, рассматриваемая в процессепересылки и обработки как единое целое, называется:

1)   файлом;

2)   массивом;

3)   программой.

5.  Гипертекст – это:

1)   очень большой текст;

2)   структурный текст, в котором можноосуществлять переходы по «горячим» словам;

3)   текст, набранный на компьютере;

4)   текст, в котором используетсяшрифт максимального размера.

6.  Преимущество двоичной системысчисления состоит в том, что:

1)   двоичный код позволяет экономитьпамять компьютера;

2)   электронные элементы с двумясостояниями потребляют меньше электроэнергии;

3)   электронные элементы с двумясостояниями наиболее просты в конструктивном исполнении.

7.  Что можно рассматривать какалгоритм?

1)   инструкцию по пользованиюметрополитеном;

2)   схему метро;

3)   правила пользованиятелефоном-аппаратом;

4)   телефонный справочник.

8.  Минимальным объектом в текстовомредакторе является:

1)   символ;

2)   слово;

3)   пиксель;

4)   абзац;

5)   файл.

9.  Какое устройство компьютера можетоказать вредное воздействие на здоровье человека?

1)   гибкий диск;

2)   системный блок;

3)   монитор;

4)   клавиатура;

5)   жесткий диск;

6)   блок питания.

10.     Тексту объёмом в 2Кбайтасоответствует:

1)   символ;

2)   абзац;

3)   страница;

4)   книга.

11.     Основным элементом электроннойтаблицы является:

1)   ячейка;

2)   столбец;

3)   строка;

4)   таблица.

12.     Результатом деления 1101101 на 110в системе счисления с основанием 2 является:

1)   10010, остаток 1;

2)   1001, остаток 1;

3)   10110;

4)   1011.

13.     В электронной таблице выделенучасток 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.

/>

15.     Какое минимальное количество шаровдолжно быть в корзине, чтобы программа работала верно?

1)   любое;

2)   ни одного;

3)   один.

16.     Основным элементом базы данныхявляется:

1)   запись;

2)   форма;

3)   поле;

4)   таблица;

5)   тип.

17.     Принцип открытой архитектурыозначает, что:

1)   компьютер сделан единымнеразъёмным устройством;

2)   возможна лёгкая замена устаревшихчастей компьютера;

3)   новая деталь компьютера будетсовместима со всем тем оборудованием, которое использовалось ранее.

18.     Структура базы данных изменится,если:

1)   добавить или удалить запись;

2)   поменять местами запись;

3)   отредактировать строку;

4)   добавить или удалить поле.

19.     Электронная почта (E-mail)позволяет передавать:

1)   сообщения;

2)   файлы;

3)   сообщения и приложенные файлы;

4)   WWW-страницы.

20.     Модем обеспечивает:

1)   модуляцию (преобразование двоичнуюинформацию в аналоговую);

2)   демодуляцию (преобразованиеаналоговой информации в двоичную);

3)   модуляцию и демодуляцию;

4)   усиление сигнала.

21.     Кэш-память жесткого дискапредназначена для:

1)   увеличения объёма жесткого диска;

2)   ускорения доступа к данным нажестком диске;

3)   ускорения чтения информации изоперативной памяти;

4)   увеличение объёма видеопамяти.

22.     Микропроцессор служит для:

1)   сложения двоичных чисел;

2)   перевода чисел из двоичной системысчисления в десятеричную;

3)   оперативного запоминания команд;

4)   распознавания кода программы.

23.     На логическом диске А задан полныйпуть к файлу \DOC\PROBA.TXT. Каково полное имя файла?

1)   C:\DOC\PROBA.TXT;

2)   A:\PROBA.TXT;

3)   DOC\PROBA.TXT;

4)   TXT;

5)   A:\DOC\PROBA.TXT.

24.     Какой логической функциисоответствует следующая таблица истинности:

A

B

F

1 1 1 1 1 1 1

1)   F=/>

2)   F=/>

3)   F=/>

4)   F=/>

25.     Память какого вида используетсядля записи и чтения информации?

1)   ОЗУ;

2)   ПЗУ;

3)   гибкие диски;

4)   жесткие диски.

26.     Кто является основоположникомотечественной вычислительной техники?

1)   Д. Н. Лозинский;

2)   С. А. Лебедев;

3)   А. А. Марков;

4)   М. Р. Шура-Бура.

27.     Двоичное кодирование одногосимвола (буквы) требует количества информации, равное:

1)   1 биту;

2)   1 байту;

3)   4 битам;

4)   1 килобайту.

28.     Какая логическая функциятождественна логической функции

1)   />

2)   />

3)   />

4)   />

5)   />

29.     В компьютер Pentium(64-разрядная шина данных и 32-разрядная шина адреса) установлена память 16Мбайт. Каково адресное пространство этого процессора?

1)   264;

2)   232;

3)   16 Мбайт;

4)   64 бит.

30.     Какие файлы соответствуют маске?? Р*.А??

1)   PPEPSI.ABC;

2)   PEDDY.A1;

3)   PEPPER.ARJ;

4)   PEPSI.A1;

5)   PEPPY.A7F;

6)   CAPITAL.A3A;

7)   SUPPORT.A1.

31.     Какая часть текста программы невлияет на ее выполнение?

1)   оператор;

2)   директива;

3)   комментарий;

4)   скобки.

32.     Американский математик – автортеории игр:

1)   Джон Нейман;

2)   Бил Гейтс;

3)   Стив Джобс.

33.     Каково греческое распространённоеназвание «саламанской доски»?

1)   Суан-пака;

2)   серобяна;

3)   абак.

34.     Состояние системы, при котором онаперестаёт выдавать результаты и реагировать на запросы извне:

1)   зависание;

2)   зацикливание;

3)   отключение монитора.

35.     Умножьте два числа 121 и 21 всистеме счисления с основанием 3.

36.     Какая программа синтаксическипроверяет оператор и тут же его выполняет?

1)   компилятор;

2)   интерпретатор;

3)   редактор;

4)   отладчик.

37.     Каково количество цифр в двоичнойсистеме счисления?

1)   10;

2)   16;

3)   8;

4)   2.

38.     Переменная задана, если известныеё:

1)   тип;

2)   тип, имя, значение;

3)   имя, значение,

4)   значение.

39.     Во время начальной загрузки DOSпользуются двумя текстовыми файлами – CONFIG.SYS и AUTOEXEC.BAT.Какой из этих файлов загружается первым?

1)   CONFIG.SYS;

2)   AUTOEXEC.BAT.

40.     Основная технологическая цепочкарешения задачи с использованием компьютера:

1)   построение модели – постановказадачи – разработка и исполнение алгоритма – анализ результатов;

2)   постановка задачи — построениемодели – разработка и исполнение алгоритма – анализ результатов;

3)   постановка задачи – разработка иисполнение алгоритма — построение модели – анализ результатов.

41.     Задано дерево каталогов:

/>Какой каталог будет текущим после выполнения следующихкоманд:

CD\

CD F

CD F\S

CD ..\..

CD \S\F

CD ..\S

1)   \S\F\S;

2)   \F\S\F;

3)   \S\S;

4)   \S\S\S;

5)   \F\F\S.


Заключение

Итак, постановка олимпиадных задач как задач на преодолениеограничений позволяет, в принципе; выявить и способности в областиалгоритмизации, и образованность, и пользовательский стиль мышления. А ученик,успешно преодолевающий системы ограничений различных типов, — законныйпобедитель олимпиады. При замене и, особенно, при выключении «рентгеновскогоаппарата»  ограничений на олимпиаде следующего уровня его способностираскроются скачком на полной мере, так как именно опыт преодоления ограниченийпослужил формированию у него активных, системных и пробных знаний.

При такой постановке дела подготовка к олимпиаде становитсядля школьника естественным продолжением базового курса информатики даже бедспециальных занятий с учителем. Вводя для себя различные ограничения ипреодолевая их, он может заниматься тем же, что и весь класс на том же уроке, ипо той же теме, что и все остальные. Но решать задачи он будет не толькопростейшим путём, как большинство, но и по-своему: «вынужденно-творческим»методом. Нужно лишь сообщить ему об этом пути независимогосамосовершенствования. Это снимает и проблему индивидуализации обучения прифронтальных формах работы учителя с классом через «озадачивание» сильныхучащихся.

В заключение — практический совет разработчикам задач: можнопредварительно проверять целостность системы ограничений, порождающей задачу,привлекая для попытки их обхода одаренного и образованного школьника, илистудента. Уместно также сказать, что для данной проверки полностью задачураскрывать не обязательно.


Литература

o  БочкинА. И. Информатика: Справочник по решению задач повышенной трудности. ВГПИ,Витебск, 1994

o  Информатика иобразование, 1997, №4

o  Информатика иобразование, 1997, №5

o  Информатика иобразование, 1997, №8

o  Информатика иобразование, 1996, №6

o  Педагогика,2000, №9

еще рефераты
Еще работы по информатике, программированию