Реферат: Cостязания по информатике олимпиады

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

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

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

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

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

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

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

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

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