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

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

Продолжаем тему "ЕГЭ по информатике"
Александр Чернов ( Пользователь )
Цитата (Михалкович Станислав, 30.01.2010, 11:37) <{POST_SNAPBACK}>
Вот мои данные:
0. Файл создается 700 мс.
1. Программа ЕГЭ - 850 мс.
2. "Неэффективная", но понятная программа Андрея Сидорова - 500 мс.
3. Эффективная" программа Андрея Сидорова по мотивам решения ЕГЭ - 400 мс.
4. Неэффективная", но понятная программа Андрея Сидорова с моей идеей пессимизации о подсчете максимума - 400 мс.

При увеличении размера файла в 10 раз эти цифры увеличиваются пропорционально.

Таким образом, я бы выбирал решение 2. Простая и понятная программа. А 1 балл уже снижен - прошу заметить. За более быстрое решение.


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

Оставшаяся часть программы (1) - сортировка массива из 26 элементов и его печать выполняется, ну, возьмем грубую оценку сверху, за 10000 операций.

Оставшаяся часть программы (2) - проход по массиву, ну, возьмем грубую оценку снизу - 26000000 операций.

Получается, что 10000 операций в программе (1) выполняются 450 мс, в то время, как 26000000 операций в программе (2) выполняются за 100 мс. Что противоречит здравому смыслу и материальной части.

Обсуждать эти числа бессмысленно, пока Вы не дадите обоснование, почему это так.

Сразу скажу, что я скомпилировал программы (1) и (2) нормальным компилятором и замерил время работы. И эти числа согласуются со здравым смыслом. Но числа эти я пока здесь приводить не буду.


Цитата (Михалкович Станислав, 30.01.2010, 12:47) <{POST_SNAPBACK}>
Я прошу еще раз заметить, что я считаю решение ЕГЭ асимптотически более эффективным, чем первое решение Андрея. Я с этим не спорю. То есть, я не спасаю (кстати, не свое) решение. Но я не вижу причин снижать школьнику за такое решение балл. Оно - хорошее и не такое уж неэффективное. И мне обидно, если кто-то из проверяющих снизит за это решение балл.


Асимптотические сложности у них как раз и одинаковы - O(N). А вот временные - разные.

Цитата (Михалкович Станислав, 30.01.2010, 12:47) <{POST_SNAPBACK}>
Еще я, честно говоря, потрясен, что Вы так запросто пробросили то, что видно глазами - ВРЕМЯ. Неэффективное решение работает быстрее эффективного, сколько бы Вы ни запускали тест.


Приведенные Вами цифры абсурдны.

Цитата (Михалкович Станислав, 30.01.2010, 12:47) <{POST_SNAPBACK}>
Я предлагаю посчитать вероятность того, что случайно будет сгенерирован наихудший тест - она будет ничтожно малой, и вдобавок в этом случае "плохое" решение будет хуже "хорошего" всего в 26 раз. А в остальных случаях - в 2 раза быстрее.


Мда... Ну что тут скажешь...
Что, все данные, подаваемые на вход программе в реальной жизни, получаются генератором равномерно распределенных случайных чисел? Что, в реальных текстах частоты букв совпадают? На основе чего Вы делаете абсурдное предположение о случайности и равномерной распределенности входных данных?

Цитата (Михалкович Станислав, 30.01.2010, 12:47) <{POST_SNAPBACK}>
И еще, я не согласен, что надо оценивать эффективность алгоритма по самому худшему тесту. В первую очередь оценивается эффективность алгоритма в среднем. Эффективность в худшем случае - рассматривается - да, но требовать это от школьников - это уже слишком. Это - удел спецкурса "Алгоритмы и анализ сложности".


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


Как-то не хотите Вы находить общие точки.
Давайте еще раз. Тут нет ничего противоречащего здравому смыслу. Если мы будем замерять времена после считывания из файла и до конца, то тут все понятно - сортировка массива из 26 элементов не зависит от размера. А во втором решении пропорциональна размеру. Так что, если не включать ввод, то второе решение - убийственно. Я это и не оспаривал - посмотрите - я говорил о том, что согласен, что ЕГЭ-шное решение асимптотически, несомненно, лучше. Это же говорил и Денис Кириенко - он упоминал про O(1). Я считал, что это утверждение уже нами пройдено и однозначно понято.

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

Цитата (cher, 30.01.2010, 22:15) <{POST_SNAPBACK}>
Обсуждать эти числа бессмысленно, пока Вы не дадите обоснование, почему это так.

Ну, надеюсь, Вы попробовали запустить. Я, кстати, не особо задумывался - просто скопировал тексты в компилятор и запустил.
Обоснование - ну, пожалуйста. В PascalABC.NET - неэффективная реализация Ord. Надо не забывать, что символы в .NET - двухбайтовые, а Ord переводит символ в код в кодировке Windows (для совместимости с Delphi). После замены записи Ord© на byte(с) алгоритм стал работать в 3 раза лучше и стал самым эффективным :) Таким образом, вот эти самые Ord и съедали основное время, что входило в алгоритм - прошу заметить.

Цитата (cher, 30.01.2010, 22:15) <{POST_SNAPBACK}>
Сразу скажу, что я скомпилировал программы (1) и (2) нормальным компилятором и замерил время работы. И эти числа согласуются со здравым смыслом. Но числа эти я пока здесь приводить не буду.

Ну прямо мальчишество какое-то - "не покажу пока ты не покажешь". Я вот не боюсь ошибиться.

Резюмирую. Я считаю формулировку задачи неполной. Не сказаны неявные условия. Можно было сказать, что ввод считается мгновенной операцией и предполагается, что чисел достаточно много (миллион, миллиард). Вот тогда всё бы было четко. Хотя и в этом случае, как видите, Ord съедало основное время.

Цитата (cher, 30.01.2010, 22:15) <{POST_SNAPBACK}>
Мда... Ну что тут скажешь...
Что, все данные, подаваемые на вход программе в реальной жизни, получаются генератором равномерно распределенных случайных чисел? Что, в реальных текстах частоты букв совпадают? На основе чего Вы делаете абсурдное предположение о случайности и равномерной распределенности входных данных?

Давайте не бросаться словами "абсурдное" и т.д. Нормальное предположение. Опять-таки, приходится догадываться по контексту. В задаче не сказано, что там есть пробелы, поэтому вряд ли там осмысленные слова. Если же считать, что буквы встречаются с частотой их появления в большом тексте, то, на мой взгляд, оценка будет отличаться от средней ну максимум в 3-4 раза, но никак не в 26.

И - мы, несомненно, расходимся в том, насколько важна оценка в худшем. Я считаю, что она в этих задачах нужна мало если вообще нужна. Может, есть случаи, но в голову они не приходят.

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

Отмечу, что меня не особо волнуют глобальные проблемы, вроде засилья плохих программистов, некачественного софта, кризиса народного образования, мировой науки и мира во всем мире. Лишний балл детей на предстоящем ЕГЭ для меня важнее. Такая у меня узкая цель.
Виталий Потопахин ( Пользователь )
Цитата (Андрей Сидоров, 31.01.2010, 02:57) <{POST_SNAPBACK}>
Лишний балл детей на предстоящем ЕГЭ для меня важнее. Такая у меня узкая цель.


Для грамотной реализации узкой цели необходимо широкое понимание. Так вот о широком понимании узкой цели.

1. Обучая программированию мы учим еще и некоторой аккуратности мышления. Вы же помните из школы, что писать нужно грамотно, а не просто понятно, что задачу надо еще и оформить а не только решить. Это моменты аккуратности. Инициализация это аккуратность в программировании.

2. Переменные в Турбо-Паскале инициализируются нулями не всякие а только глобальные, а это принципиальная разница, а не маленький технический нюанс.

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

4. Из своего опыта я делаю заключение, что человек не думающий о инициализации нулями вообще не думает о том, что каждая величина на момент своего первого использования должна иметь определенное, необходимое по логике алгоритма значение, а стало бы легко может наткнуться на проблему когда первое значение должно быть не нулевое. Пример даже не буду приводить, это ситуация банальная.

5. О ЕГЭ. Не дело учителя готовить к ЕГЭ. Да и бессмысленно это. Разве в ЕГЭ какое-то особое программирование или особая математика. Да все то же самое. Будем хорошо учить они будут сдавать, будем плохо учить не будут сдавать. Результат экзамена это следствие системной подготовки по предмету, а не специального натаскивания.

Федор Ткачев ( Пользователь )
Цитата (Андрей Сидоров, 30.01.2010, 19:42) <{POST_SNAPBACK}>
Федор Васильевич, если не секрет, вы лично подготовкой скольких школьников к будущему ЕГЭ занимаетесь?

По мере сил я занимаюсь проблемой качественной подготовки по алгоритмике, по необходимости учитывая феномен ЕГЭ.

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


После Ваших исправлений в программах решение (1) стало устойчиво работать в 3-4 раза быстрее, чем решение (2). Я правильно понимаю? При моих прогонах у меня получился множитель 4. Это конечно, не 26, признаю, был не прав, но и 4 более чем достаточно. И это даже при условии того, что основное время занимает чтение из файла.

Цитата (Михалкович Станислав, 31.01.2010, 01:47) <{POST_SNAPBACK}>
Ну, надеюсь, Вы попробовали запустить. Я, кстати, не особо задумывался - просто скопировал тексты в компилятор и запустил.
Обоснование - ну, пожалуйста. В PascalABC.NET - неэффективная реализация Ord. Надо не забывать, что символы в .NET - двухбайтовые, а Ord переводит символ в код в кодировке Windows (для совместимости с Delphi). После замены записи Ord© на byte(с) алгоритм стал работать в 3 раза лучше и стал самым эффективным :) Таким образом, вот эти самые Ord и съедали основное время, что входило в алгоритм - прошу заметить.


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

Для меня загадка, как можно написать перевод из однобайтовой в двухбайтовую кодировку настолько медленным.
Кроме того, ведь и массивы, индексируемые по символам, тоже переводятся в массивы, индексируемые от 0, и для этого там должна использоваться та же самая операция вычитания ORD© - ORD('a')...

Цитата (Михалкович Станислав, 31.01.2010, 01:47) <{POST_SNAPBACK}>
Давайте не бросаться словами "абсурдное" и т.д. Нормальное предположение. Опять-таки, приходится догадываться по контексту. В задаче не сказано, что там есть пробелы, поэтому вряд ли там осмысленные слова. Если же считать, что буквы встречаются с частотой их появления в большом тексте, то, на мой взгляд, оценка будет отличаться от средней ну максимум в 3-4 раза, но никак не в 26.


А зачем Вы вообще делаете какие-то предположения в условиях неполной информации. И опять же, эти новые Ваши предположения могут легко оказаться неверными. Например, на вход программе подаются записи молекул ДНК, то есть файлы большой длины, содержащие только 4 буквы, и без пробелов.

Цитата (Михалкович Станислав, 31.01.2010, 01:47) <{POST_SNAPBACK}>
И - мы, несомненно, расходимся в том, насколько важна оценка в худшем. Я считаю, что она в этих задачах нужна мало если вообще нужна. Может, есть случаи, но в голову они не приходят.


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

Цитата (Михалкович Станислав, 31.01.2010, 01:47) <{POST_SNAPBACK}>
По поводу задачи - мы немного отошли от мысли, которую я высказывал по поводу ЕГЭ-шного решения. Я говорил, что оно мне не нравится своей неряшливой формой. Я принимаю, что такое решение хорошо переводится на родственные языки - это Вы точно подметили. Но - мне оно не нравится - формой. Решение, приведенное по его мотивам Андреем Сидоровым мне нравится больше - оно записано как-то чище. И, обобщая, я хочу сказать, что большинство решений ФИПИ оформлено примерно также. Да и не ФИПИ тоже.


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

Если же Вы хотите в решениях использовать максимум возможностей языка с учетом всего зоопарка используемых в настоящее время языков и сред, то Вам придется писать по решению на Borland Pascal, Free Pascal, Delphi, PascalABC, Borland C, Borland C++, Microsoft C++, GNU C, GNU C++, QuickBasic, Visual Basic и далее по списку...
Андрей Сидоров ( Пользователь )
Цитата (Потопахин Виталий, 31.01.2010, 04:37) <{POST_SNAPBACK}>
Для грамотной реализации узкой цели необходимо широкое понимание. Так вот о широком понимании узкой цели.

1. Обучая программированию мы учим еще и некоторой аккуратности мышления. Вы же помните из школы, что писать нужно грамотно, а не просто понятно, что задачу надо еще и оформить а не только решить. Это моменты аккуратности. Инициализация это аккуратность в программировании.

2. Переменные в Турбо-Паскале инициализируются нулями не всякие а только глобальные, а это принципиальная разница, а не маленький технический нюанс.

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

4. Из своего опыта я делаю заключение, что человек не думающий о инициализации нулями вообще не думает о том, что каждая величина на момент своего первого использования должна иметь определенное, необходимое по логике алгоритма значение, а стало бы легко может наткнуться на проблему когда первое значение должно быть не нулевое. Пример даже не буду приводить, это ситуация банальная.

5. О ЕГЭ. Не дело учителя готовить к ЕГЭ. Да и бессмысленно это. Разве в ЕГЭ какое-то особое программирование или особая математика. Да все то же самое. Будем хорошо учить они будут сдавать, будем плохо учить не будут сдавать. Результат экзамена это следствие системной подготовки по предмету, а не специального натаскивания. 


Вы видели вообще задачи С4? Приведите мне хоть одну ЕГЭшную задачу (из фотокопий с экзамена или пособий с грифом ФИПИ), в которой необходимо использовать локальные переменные? 

Знаете, у меня такое ощущение, что один я здесь пишу о ЕГЭ по информатике. Что я только один читал КИМы, документы ФИПИ, прорешивал официальные сборники и реальные варианты. (Конечно, тут есть те, кто это все делал, но они в разговор почти не вступают.) Все остальные - большие ученые и высококвалифицированные программисты, которые не в состоянии понять, что ребенок может на 4 часу ЕГЭ запутаться в алгоритме сортировки

Все  пишут о программировании вообще. Какое программирование "аккуратное", какая алгоритмика "правильная"... Я это все знаю, все эти шаблонные правильные решения мне давно известны, какой интерес о них говорить? 

Я давно уже сказал детям - инициализируйте все что можно на всякий случай, лучше преребдеть, чем недобдеть. И все равно считаю, что снижать балл знание умолчаний - неправильно.

"Не дело учителя готовить к ЕГЭ". Видимо, многие учителя с вами согласны, и к ЕГЭ не готовят. Приходится мне.

"Разве в ЕГЭ какое-то особое программирование или особая математика. Да все то же самое."

Вы что, не в курсе, насколько мала корреляция заданий ЕГЭ со школьной программой? Вы открывали учебники по информатике для старшеклассников и сравнивали их с КИМами?
Федор Ткачев ( Пользователь )
Цитата (Андрей Сидоров, 31.01.2010, 12:10) <{POST_SNAPBACK}>
Все остальные - большие ученые и высококвалифицированные программисты, которые не в состоянии понять, что ребенок может на 4 часу ЕГЭ запутаться в алгоритме сортировки

Андрей Николаевич, вы в состоянии представить себе, сколько всяких экзаменов, начиная со вступительных -- сдают люди, прежде чем стать "всеми остальными" по вашей терминологии?
И что за их высказываниями -- их опыт?

Представьте себе, как вы пытаетесь, опираясь на свою философию подготовки, получить зачет за практикум на третьем курсе у того же cher'а (который -- при всех моих к нему очень больших претензиях -- как препод находится на своем месте).
Я вот представил себе, как вы пытаетесь объехать его на кривой кобыле, -- а получив отлуп, рассказываете в коридоре страшилки однокурсникам -- и становится очень-очень смешно.

Если вы занимаетесь натаскиванием на С4 юных раздолбаев, которым в лом потренироваться писать элементарную сортировку,
то вы можете находить в этом повод чувствовать удовлетворение (в том числе, возможно, и материальное),
но отсюда вовсе не следует, что на всероссийском педагогическом форуме следует бросаться словечками вроде "стародуб" -- и превращать образование в профанацию.
Андрей Сидоров ( Пользователь )
info21, уверен - вы уже поняли, что меня не интересует зачет на любом курсе у кого угодно? Я уже сказал, мир во всем мире - это не ко мне.

Представьте, что вы приходите к врачу с острой болью в груди, а он вместо укола начинает вам читать лекцию о здоровом образе жизни!

Объясняю еще раз: передо мной стоит чрезвычайно конкретная задача - в условиях крайне ограниченного времени обеспечить максимально возможный балл ЕГЭ детям, которых в школе к тесту фактически не готовят. Это значит: свести к минимуму лишнюю информацию, дать набор легкозапоминаемых приемов, дать запасные способы решений и простые способы самопроверки. 

Если вы своим ученикам при подготовке их к ЕГЭ читаете развернутые лекции по алгоритмике - это ваше дело. Может, у ваших учеников времени вагон. 
Федор Ткачев ( Пользователь )
Цитата (Андрей Сидоров, 31.01.2010, 13:05) <{POST_SNAPBACK}>
Я уже сказал, мир во всем мире - это не ко мне.

Зачем повторяться? Все это прекрасно поняли.

Кстати, аналогия с острой болью грубо неправильная.

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