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

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

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

Про преждевременную пессимизацию - я согласен - красивый термин. Еще раз повторюсь - я бы писал какой-то алгоритм в стиле написанного в ЕГЭ - я ведь не убийца детей и желаю им добра :) Но решение было бы без обилия Ordов и со Swapами, правда, без Sort - передавать массив в подпрограммы - дети в критический момент запутаются.

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

Цитата (cher, 29.01.2010, 23:49) <{POST_SNAPBACK}>
Вообще, по ЕГЭ-2009 4 балла за задание C4 получили 112 человек, а 3 балла - 329 человек. И это из примерно 60000 сдававших.
То есть школьников, которые вообще хоть как-то в состоянии решить C4 пренебрежимо мало от общего числа сдававших. Поэтому вся дискуссия об оптимальности решений на общем фоне сдающих почти бессмысленна.

Да! Здорово! Учитывая это, я предложил бы первое решение и сказал бы детям, что они потеряют на нем всего 1 балл! А риск совершить с испугу кучу ошибок в ЕГЭ-решении гораздо выше - скостят 1 или 2 балла. Я - за прагматизм.

Цитата (cher, 29.01.2010, 23:49) <{POST_SNAPBACK}>
А Вы делаете совершенно необоснованное утверждение, что для сдачи ЕГЭ _необходимо_ писать так. И про "пугание" и снижение оценки, ну это, извините, уж точно Ваши домыслы.

Хорошо, если так. Страх многих спасал. Вот и Денис подтверждает: если с этого года все будут решать только региональные комиссии, то в нашем Ростове я могу себе представить - Вы ничего не докажете.

Цитата (cher, 29.01.2010, 23:49) <{POST_SNAPBACK}>
То есть, Вы считаете, что во всем виноват такой стиль написания решений задач ЕГЭ в методических пособиях? Ну вот чтобы было предметно, скажите, пожалуйста, каков процент из поступивших к Вам в этом году был в состоянии решить C4?

Стиль решений в книгах по ЕГЭ, несомненно, виноват (ИМХО). Мне трудно проанализировать, сколько из моих поступивших и как написало C4 - они мне не докладывают. В прошлом году в состоянии было решить меньше - времени на подготовку было мало, в этом будет больше - мы решаем подобные задачи тотально. Но C4 - это рулетка - я не рекомендую для большинства их решение - только при условии уверенного решения остальных задач.

Цитата (cher, 29.01.2010, 23:49) <{POST_SNAPBACK}>
Простите, Вы своих студентов тоже так учите?

Давайте я отвечу без иронии. И - прошу меня понять. Я учу ИТ-шников, не олимпиадников. Этот мир прагматичен. Я прошу их анализировать стандартные и пиковые условия, в которых работает задача. Если в 99 случаях из 100 вводится маленькая последовательность, я буду настаивать на понятном способе, который быстро пишется, понятен при прочтении, легко модифицируется. Если в 99 случаях из 100 последовательность - длинная, я буду просить их придумать по возможности оптимальное решение. В любом случае я буду просить их пользоваться всеми доступными библиотечными подпрограммами и структурами данных. Чем сложнее задача, тем активнее я буду от них требовать это сделать. Решения, где все сделано с нуля, я буду считать ПЛОХИМИ и сильно их за это ругать.

2Денис Кириенко Спасибо за информацию о ликвидации федеральных апелляционных комиссий. Мои худшие опасения подтверждаются. И, конечно, мы будем очень осторожными и не будем разрешать использовать школьникам те версии и языки, которые могут вызвать непонимание проверяющих.
Денис Кириенко ( Пользователь )
Цитата (Андрей Сидоров, 30.01.2010, 00:33) <{POST_SNAPBACK}>
Кстати, а "новые, лучше продуманные" задачи С4 - это не те, что в новом сборнике Якушкин-Ушаков? Там же косяки минимум в трех задачах из десяти! 


1. Цитируете точно. "новые, лучше продуманные" - не мои слова.

2. Не знаю, надо смотреть. Скорее всего, нет. Задачи открытого сегмента 2009 года были опубликованы в одном из сборников, но я точно не помню, в каком именно.

3. Естественно, задачи, которые войдут в ЕГЭ в 2010 году не опубликованы нигде.
Андрей Сидоров ( Пользователь )
Ликвидация федеральных апелляционных комиссий - это, конечно, круто. Теперь надо запретить все языки, кроме QBasic, поскольку в школах (в наших местах) дают только его, прости Господи...
Александр Чернов ( Пользователь )
Цитата (Михалкович Станислав, 30.01.2010, 00:36) <{POST_SNAPBACK}>
Давайте я отвечу без иронии. И - прошу меня понять. Я учу ИТ-шников, не олимпиадников. Этот мир прагматичен. Я прошу их анализировать стандартные и пиковые условия, в которых работает задача. Если в 99 случаях из 100 вводится маленькая последовательность, я буду настаивать на понятном способе, который быстро пишется, понятен при прочтении, легко модифицируется. Если в 99 случаях из 100 последовательность - длинная, я буду просить их придумать по возможности оптимальное решение.


Извините, меня очень настораживают такие высказывания. Вот Вы уже сделали предположения о задаче ("данные вводятся с клавиатуры и поэтому имеют небольшой размер"), и оно оказалось неверным. Точно также и в реальной жизни очень часто априорные предположения о "стандартных и пиковых условиях, в которых работает задача" оказываются неверными. А 1%, или даже 0.001%, когда программа работает неудовлетворительно - для программирования почти всегда недопустимо.

Программа должна быть (в порядке важности):
1. Корректной.
2. Эффективной.
3. Понятной и легко модифицируемой.
Андрей Сидоров ( Пользователь )
Цитата (cher, 30.01.2010, 01:04) <{POST_SNAPBACK}>
Программа должна быть (в порядке важности):
1. Корректной.
2. Эффективной.
3. Понятной и легко модифицируемой.


Насчет первого согласен, а вот с порядком 2-3 пунктов во многих случаях не все так ясно. Иногда читабельность и легкость модификации может быть важней скорости. Иначе не распространился бы, например, тот же Ruby. И вообще, мы бы всё писали на ассемблере и в машинных кодах.
Станислав Михалкович ( Пользователь )
Цитата (cher, 30.01.2010, 01:04) <{POST_SNAPBACK}>
Извините, меня очень настораживают такие высказывания. Вот Вы уже сделали предположения о задаче ("данные вводятся с клавиатуры и поэтому имеют небольшой размер"), и оно оказалось неверным. Точно также и в реальной жизни очень часто априорные предположения о "стандартных и пиковых условиях, в которых работает задача" оказываются неверными. А 1%, или даже 0.001%, когда программа работает неудовлетворительно - для программирования почти всегда недопустимо.

Программа должна быть (в порядке важности):
1. Корректной.
2. Эффективной.
3. Понятной и легко модифицируемой.

Почему неверным? В ЕГЭ-решении они вводятся с клавиатуры. Не будете же Вы вводить миллион?
По поводу априорных предположений - их делают всегда. Если не делать, то трудно жить. А вот почему априорные основанные на интуиции предположения ОЧЕНЬ ЧАСТО оказываются неверными - я понять не могу.

По поводу 1% - это давайте разберемся. Насколько неэффективно работает программа? Насколько высока цена того, что программа работает неэффективно? Если в результате неправильной работы программы с вероятностью 0.01% рухнет мост - это одно. Если с вероятностью 1% программа будет работать в 30 раз менее эффективно, а в остальных случаях - так же или даже быстрее - это - другое. Что значит недопустимо? Вот, к примеру, сортировка бинарным деревом максимально эффективна в среднем и неэффективна если данные уже отсортированы. И что - это недопустимо? Нет, что-то здесь не так.

По поводу 2. и 3. понятие эффективности очень размыто, и в некоторых случаях я бы 2. и 3. переставил местами.

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

А применительно к нашей задаче - все-таки меня интересует, откуда вводятся данные.

Денис Кириенко ( Пользователь )
Цитата (Михалкович Станислав, 30.01.2010, 02:17) <{POST_SNAPBACK}>
Почему неверным? В ЕГЭ-решении они вводятся с клавиатуры. Не будете же Вы вводить миллион?


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

Цитата
А применительно к нашей задаче - все-таки меня интересует, откуда вводятся данные.


Откуда угодно, в этом задании не оценивается умение реализовать стандартный-файловый-оконный-сетевой ввод-вывод, школьник может написать такой ввод-вывод, какой наиболее ему удобен. Главное, что задан формат входных данных, а вот программа может получать эти данные как угодно - со стандартного ввода, из файла... Я видел решение задачи C4 на php (и оценил его в 3 балла - верное, но неэффективное), где данные программа получала по http-протоколу через метод POST - но это не имеет никакого отношения к алгоритму решения задачи. Тут, правда, возникает другая проблема - данные, переданные через метод POST автоматически сохраняются целиком в памяти, т.е. программа, получающая данные таким образом не может быть эффективной по критериям с одной стороны, а с другой стороны школьник может просто не владеть технологией потокового ввода-вывода данных, если он писал исключительно web-приложения на PHP и он просто может не понимать, в чем же может заключаться неэффективность алгоритма. Аналогично будет и с оконным вводом-выводом - данные, полученные через GUI будут автоматически сохранены целиком в памяти. Но это - 0,01 процента тонкостей, от которых вряд ли удастся избавиться полностью и на которые нужно смотреть в каждом конкретном случае.
Федор Ткачев ( Пользователь )
Предложу такие формулировки:

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

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

Ясность подразумевает читабельность и минималистичность (не количества литер, конечно).

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

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

Про решение на Руби можно сказать, что оно, конечно, неплохо, что юный программер к месту и правильно может вызвать, к примеру, сортировку. Но задачи такого типа, очевидно, подразумевают и проверку умения делать сортировку (если она по логике нужна). В этом смысле использование библиотеки язык/среды противоречит целям обучения и, соответственно, экзамена.
Разумеется, в обсуждаемом контексте общего школьного образования.
Станислав Михалкович ( Пользователь )
Цитата (Денис Кириенко, 30.01.2010, 02:30) <{POST_SNAPBACK}>
В ЕГЭ-решении они вводятся не с клавиатуры, а со стандартного устройства ввода.

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


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

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

Вот несколько программ.

0. Программа создания файла на миллион символов. (обязательно запустить в начале)
1. Программа ЕГЭ.
2. "Неэффективная", но понятная программа Андрея Сидорова
3. "Эффективная" программа Андрея Сидорова по мотивам решения ЕГЭ
4. Неэффективная", но понятная программа Андрея Сидорова с моей идеей пессимизации о подсчете максимума

(сразу предупрежу - в Опере и IE6 - не будет работать)

Вот мои данные:
0. Файл создается 700 мс.
1. Программа ЕГЭ - 850 мс.
2. "Неэффективная", но понятная программа Андрея Сидорова - 500 мс.
3. Эффективная" программа Андрея Сидорова по мотивам решения ЕГЭ - 400 мс.
4. Неэффективная", но понятная программа Андрея Сидорова с моей идеей пессимизации о подсчете максимума - 400 мс.

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

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

Кстати, без обид. Если здесь будет опубликовано решение на Обероне (возможно, с относительными замерами времени) - будет очень интересно. Заодно можно будет наглядно посмотреть на чистоту кода Оберона.
Федор Ткачев ( Пользователь )
Тут уже свидетельствовалось, что на задачках такого уровня Оберон практически не отличается от паскаля.

Воспользуюсь случаем и сообщу, что в связи с ЕГЭ вывел наружу в Блэкбоксе команду простой загрузки модуля, что позволяет держать программу в секции инициализации модуля, -- тогда MODULE практически не отличается от старой PROGRAM.
А посадка соотв. команд на соотв. клавишу делает схему работы на ЕГЭ-шном уровне (компиляция, выполнение) неотличимой от ТП и прочего старья.

Ссылки не открываются -- менять браузер (iRider) точно не буду. Потому что он удобней и быстрее всех мозилл.
Без обид: KISS.

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