Личный кабинет

ЕГЭ по информатике (2)

Продолжаем тему "ЕГЭ по информатике"
Денис Кириенко ( Пользователь )
Относительно ruby - формально школьник имеет право писать на любом языке программирования.
Формально его работа должна быть оценена независимо от языка программирования по прилагаемым критериям.

По критериям оценивания верное, но неэффективное решение оценивается в три балла. Именно так я бы оценил первое решение этой задачи на ruby.

Второе решение по критериям оценивания должно быть оценено в четыре балла, ибо оно верное и эффективное (все входные данные не сохраняются в массиве-строке, а сразу же подсчитываются частоты).

Другое дело, в том, что проверяет работы региональная комиссия. И она вполне может сказать "Мы этого языка не знаем, в школах его не проходят, мы этого понять не можем, поэтому 0 баллов". А поскольку в 2009 году федеральная конфликтная комиссия была упразднена, то добиваться правды можно только в регионе и решение региональной комиссии, увы, оспорить невозможно.

Андрей Сидоров ( Пользователь )
Цитата (Денис Кириенко, 29.01.2010, 23:14) <{POST_SNAPBACK}>
Извините, я не очень люблю, когда на мой ЖЖ ставят ссылки. Эти записи закрыты.


Хорошо, ссылок ставить не буду. На ЕГЭ приносят решения С4 на Ruby, PHP, C#, Python, Perl - и все это надо проверять, отклонять работу за язык нельзя.

Дело в том, что никакого официального списка допустимых на ЕГЭ языков нет - полная свобода. 
Александр Чернов ( Пользователь )
Вообще, по ЕГЭ-2009 4 балла за задание C4 получили 112 человек, а 3 балла - 329 человек. И это из примерно 60000 сдававших.
То есть школьников, которые вообще хоть как-то в состоянии решить C4 пренебрежимо мало от общего числа сдававших. Поэтому вся дискуссия об оптимальности решений на общем фоне сдающих почти бессмысленна.

Цитата (Михалкович Станислав, 29.01.2010, 22:36) <{POST_SNAPBACK}>
Да, я уже забыл это. Действительно - посмотрел стандарт Паскаля - и нигде этого не нашел. Частично беру слова назад. Но буду настаивать на следующем. Пусть ученик напишет версию языка. Например, Delphi. Любая. Всё. Вы уже не сможете ему снизить за это балл. Особенно, если он напишет в комментарии, что в Delphi глобальные переменные инициализируются нулями. По незнанию - одно, я согласен, но по знанию - другое.


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

Цитата (Михалкович Станислав, 29.01.2010, 22:36) <{POST_SNAPBACK}>
Да, я немного утрирую. Я не сомневаюсь в компетентности авторов. Я понимаю, ПОЧЕМУ они так пишут. Но - они вертятся в рамках выбранной ими системы ограничений - пишут на подмножестве всех языков. А для Паскаля таким подмножеством являются чрезвычайно древние версии. К счастью, не исходный виртовский Паскаль, но очень древние. Психологически они стимулируют школьников жить в старом мире. Это - плохо. Более того, они пугают школьников, что отход от этого стиля череват снижением оценки. В результате у школьника вырабатывается страх перед новым и - как следствие - неправильные ориентиры.


Показывая такие минималистичные решения авторы говорят, что для решения задач уровня C4 _достаточно_ такого минимума языка. Никто не заставляет писать именно так. Более того, сдающий может вообще писать на любом языке программирования. Хоть на Лого. А Вы делаете совершенно необоснованное утверждение, что для сдачи ЕГЭ _необходимо_ писать так. И про "пугание" и снижение оценки, ну это, извините, уж точно Ваши домыслы.

Цитата (Михалкович Станислав, 29.01.2010, 22:36) <{POST_SNAPBACK}>
Авторы могут выйти из этого старого стиля в силу своей квалификации - да. Из бывших школьников это приходится потом выжигать каленым железом.


То есть, Вы считаете, что во всем виноват такой стиль написания решений задач ЕГЭ в методических пособиях? Ну вот чтобы было предметно, скажите, пожалуйста, каков процент из поступивших к Вам в этом году был в состоянии решить C4?

Цитата (Михалкович Станислав, 29.01.2010, 22:36) <{POST_SNAPBACK}>
Про процедуры - я понимаю, почему - трудно переводить на другие языки, но - так жить плохо. Ну что же это такое: процедуры нельзя, нормальные библиотеки нельзя, новые версии нельзя, и еще требуется какая-то эффективность на асимптотически больших объемах данных, вводимых с клавиатуры. Причем, нигде - заметьте, не оговаривается, что вводимые данные могут иметь большой объем. Надо догадываться? По тому, что данные вводятся с клавиатуры, я догадался, что данных не будет очень много. Видимо, неправильно.


А где Вы прочитали, что "данные вводятся с клавиатуры"? Что-то я такого не нашел. Формулировка нейтральная: "на вход программе подается".

Задача C4 - это задача начального олимпиадного уровня. Такие обычно даются в качестве утешительных на олимпиадах по программированию. Школьники, которые рассчитывают решить эту задачу, должны понимать, что вводимые данные могут иметь большой объем. Иначе это задача не для них.

Цитата (Михалкович Станислав, 29.01.2010, 22:36) <{POST_SNAPBACK}>
Конструкция такова, что используется по ходу трижды. В не inline-функцию это - нехорошо, но избавиться вообще от вычитания, индексируя массив не с нуля - более хорошая идея. Читалось бы точно лучше. И - чем Вам не нравится индексация символами?


Ну и что, что трижды используется. Вы и a - b будете выносить в функцию, если используется более одного раза?
А по смыслу, это именно конструкция вида a - b, в которой ORD появляется только из-за ограничений Паскаля.

Почему не используется индексация символами - я свое предположение высказал. Для того, чтобы это решение 1-в-1 переводилось, например, на Си, где массивы индексируются от 0. И опять-таки, школьникам никто не запрещал использовать индексацию 'a'..'z', если бы они хотели.

Цитата (Михалкович Станислав, 29.01.2010, 22:36) <{POST_SNAPBACK}>
Я, несомненно, не спорю, что решение на очень больших объемах данных неоптимальное. На небольших - почему не пооптимизировать - оно мне нравится и оно компактное. Еще раз повторюсь - мне не нравится неявное предположение, что вводится миллион символов. Если бы это явно было оговорено, то да, тогда бы и разговор был другой. Но не оговорено. Поэтому - ваше предположение против моего предположения. Только и всего. А я смотрю просто - в большинстве своем будут вводить малые объемы данных. Скажем, символов 30.


Простите, Вы своих студентов тоже так учите?

Цитата (Михалкович Станислав, 29.01.2010, 22:36) <{POST_SNAPBACK}>
Будем спорить, что приведенное в ЕГЭ решение неоптимально на 30 символах?


Это абсурд. На входе в 30 символов никакой разницы во времени выполнения Вы не заметите. А вот на входе в миллионы символов "альтернативное" решение будет работать в ~30 раз медленнее.

Цитата (Михалкович Станислав, 29.01.2010, 22:36) <{POST_SNAPBACK}>
Преждевременной оптимизацией я называл оптимизацию под большие данные если это явно не оговаривается.


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

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

Цитата (Михалкович Станислав, 29.01.2010, 22:36) <{POST_SNAPBACK}>
Если говорить об асимптотиках, то, мне кажется (может, я ошибусь - вспоминаю коды по памяти), что предложенное решение имеет асимптотическую сложность 26*N - ну, там во внешнем цикле внутренний - по всем английским буквам. А это - одна и та же сложность: O(N), константа только разная. Вот если бы было N*N, тогда да. Так в ЕГЭ-шном решении в цикле выполняется больше действий на каждой итерации - константа при N тоже увеличится :)


А я где-то говорил про асимптотики? И, извините, константы тоже играют роль. И задача C4 об этом тоже.

Цитата (Михалкович Станислав, 29.01.2010, 22:36) <{POST_SNAPBACK}>
Да. Если бы было написано Sort(a,26), я бы гораздо меньше критиковал программу. Кстати, не понял, почему Вы против Swap.


Ваше исходное высказывание звучало примерно так: "если вы не пишите функцию sort, то хотя бы пишите функцию swap" :)

Цитата (Михалкович Станислав, 29.01.2010, 22:36) <{POST_SNAPBACK}>
Основное, что нас останавливало от написания программ на нормальных версиях языка - если хотите знать - это наше неявное допущение, что при проверке попадется какой-нибудь не очень грамотный учитель и скажет что-то типа, что так низзя и это не будет работать. В Турбо-Паскале, а значит, нигде. Нам просто жалко детей. На апелляции они ничего не смогут доказать. Прецедентов этого - хоть отбавляй.


Некомпетентные проверяющие - это не проблема только ЕГЭ по информатике. Точно также эта проблема стоит у математиков, физиков и далее везде. Как-то пытаться ее решить можно перенеся проверку ЕГЭ в вузы. О чем, кстати, Денис Кириенко здесь тоже писал.
Андрей Сидоров ( Пользователь )
Я не говорю что мой алгоритм эффективен. Мне это даже неинтересно.

Мне интересна точка зрения человека, которой подходит к решению этой задачи с официальными критериями оценивания - как это делает Денис Кириенко - снижается балл за такое решение или нет? К сожалению, он ответил только по решениям на Руби. Надеюсь, что он ответит и на этот вопрос тоже.
Денис Кириенко ( Пользователь )
Цитата (Андрей Сидоров, 29.01.2010, 23:54) <{POST_SNAPBACK}>
Мне интересна точка зрения человека, которой подходит к решению этой задачи с официальными критериями оценивания - как это делает Денис Кириенко - снижается балл за такое решение или нет? К сожалению, он ответил только по решениям на Руби. Надеюсь, что он ответит и на этот вопрос тоже.


В 2009 году общие критерии были такие - за верную и эффективную программу ставится 4 балла, за верную, но неэффективную - три балла.

За последние годы менялись как критерии оценивания, так и формулировки задач C4 и в настоящий момент как формулировки, так и критерии продуманы лучше, чем в прошлые годы. Поэтому не очень хорошо брать за образцы страрые задачи прошлых лет - на них могу просто не работать современные критерии.

Что касается приведенных выше примеров программ, то они в большинстве своем подпадают как раз под критерии верного, но неэффективного решения.
Андрей Сидоров ( Пользователь )
Цитата (Денис Кириенко, 30.01.2010, 00:05) <{POST_SNAPBACK}>
За последние годы менялись как критерии оценивания, так и формулировки задач C4 и в настоящий момент как формулировки, так и критерии продуманы лучше, чем в прошлые годы. Поэтому не очень хорошо брать за образцы страрые задачи прошлых лет - на них могу просто не работать современные критерии.
Извините, но это не "старая задача прошлых лет", это задача из сборника "ЕГЭ 2010. Типовые тестовые задания от разработчиков ФИПИ" Якушкин, Лещинер, Кириенко! По этому сборнику народ готовится к предстоящему экзамену!!


Цитата (Денис Кириенко, 30.01.2010, 00:05) <{POST_SNAPBACK}>
Что касается приведенных выше примеров программ, то они в большинстве своем подпадают как раз под критерии верного, но неэффективного решения.



Можно чуть подробней о решении на паскале без сортировки? Оно будет считаться неээффективным на основании чего?
Денис Кириенко ( Пользователь )
Цитата (Андрей Сидоров, 30.01.2010, 00:14) <{POST_SNAPBACK}>
Можно чуть подробней о решении на паскале без сортировки? Оно будет считаться неээффективным на основании чего?


Ссылку дайте, а то их тут много разных было...
Андрей Сидоров ( Пользователь )
http://pedsovet.org/forum/index.php?showto...st&p=141851
Денис Кириенко ( Пользователь )
Цитата (Андрей Сидоров, 30.01.2010, 00:21) <{POST_SNAPBACK}>


Это решение является неэффективным, т.к. вторая часть решения может быть реализована за O(1), а не за O(длина входа).

Как следовало бы оценивать это решение по формальным критериям - не могу ответить, так как критерии оценивания к этой задаче не прилагаются.

Андрей Сидоров ( Пользователь )
Цитата (Денис Кириенко, 30.01.2010, 00:25) <{POST_SNAPBACK}>
Это решение является неэффективным, т.к. вторая часть решения может быть реализована за O(1), а не за O(длина входа).

Как следовало бы оценивать это решение по формальным критериям - не могу ответить, так как критерии оценивания к этой задаче не прилагаются.

Ну, то что у нее уровень сложности выше, это понятно... меня интересовал формальный подход....


Кстати, а "новые, лучше продуманные" задачи С4 - это не те, что в новом сборнике Якушкин-Ушаков? Там же косяки минимум в трех задачах из десяти! 

footer logo © Образ–Центр, 2019. 12+