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

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

Продолжаем тему "ЕГЭ по информатике"
Андрей Сидоров ( Пользователь )
 
Цитата (cher, 29.01.2010, 13:14) <{POST_SNAPBACK}>


Спасибо за пост, вот это уже разговор! :)

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

1) Не запоминаются в массивах входящие данные, если в этом нет необходимости;
2) Не содержится вложенных циклов, если можно обойтись без них
(напр, не используется сортировка для поиска минимумов-максимумов);
3) Не используются вещественные величины, если можно обойтись целыми;
4) Входящие данные считываются и просматриваются один раз.

Если эти требования не выполняются, снимается 1 балл.
Про порядок сложности алгоритма нет ни слова.Тем более нет ни слова про "скорость роста функции времени работы алгоритма от размера входных данных".
Представляю сцену - школьник приходит на апелляцию и спрашивает: за что штраф почему у меня снижен балл? А ему отвечают: вы превысили скорость роста функции времени работы алгоритма от размера входных данных. Езжайте Идите и больше не превышайте! 

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

(Кстати, а эффективность приведенного решения на Руби вы как оцениваете?) 
Александр Чернов ( Пользователь )
Цитата (Андрей Сидоров, 29.01.2010, 15:51) <{POST_SNAPBACK}>
Почитав критерии оценивания С4 в демовариантах последних лет, попробую выделить приведенные там критерии эффективности. 
Решение считается эффективным, если в программе:

1) Не запоминаются в массивах входящие данные, если в этом нет необходимости;
2) Не содержится вложенных циклов, если можно обойтись без них
(напр, не используется сортировка для поиска минимумов-максимумов);
3) Не используются вещественные величины, если можно обойтись целыми;
4) Входящие данные считываются и просматриваются один раз.

Если эти требования не выполняются, снимается 1 балл.
Про порядок сложности алгоритма нет ни слова.Тем более нет ни слова про "скорость роста функции времени работы алгоритма от размера входных данных".
Представляю сцену - школьник приходит на апелляцию и спрашивает: за что штраф почему у меня снижен балл? А ему отвечают: вы превысили скорость роста функции времени работы алгоритма от размера входных данных. Езжайте Идите и больше не превышайте! 


Если Вы спрашиваете, за что формально можно снять один балл, то ответ - за вложенный цикл в выводе. Это формально. А фактически - я написал выше.

Цитата (Андрей Сидоров, 29.01.2010, 15:51) <{POST_SNAPBACK}>
Нигде не указано, что переменные должны инициализироваться. Ошибкой считается лишь "неверная инициализация переменных", т.е. приводящая к ошибкам в вычислениях.


Отсутствие инициализации, вследствие которой переменная получает случайное неверное значение, это - неверная инициализация переменных, которая приводит к ошибкам в вычислениях.
Андрей Сидоров ( Пользователь )
Цитата (cher, 29.01.2010, 17:19) <{POST_SNAPBACK}>
Если Вы спрашиваете, за что формально можно снять один балл, то ответ - за вложенный цикл в выводе. Это формально. А фактически - я написал выше.
Отсутствие инициализации, вследствие которой переменная получает случайное неверное значение, это - неверная инициализация переменных, которая приводит к ошибкам в вычислениях.


1) Вложенных циклов циклов в моем решение ровно столько, же сколько в книжном. На паскале без вложенных циклов эту задачу просто невозможно решить. Требуем невозможного?

Если надо без вложенных циклов - см. решение на Руби, там циклов вообще нет, одни методы.


2) Каким образом переменная получит случайное значение, если в указанных при решении версиях языка (будь то Турбо Паскаль или PascalABC) переменные по умолчанию инициализируются нулями?

3) Эксперт при проверке имеет право руководствоваться только формальными критериями, а не своими "фактическими" представлениями о эффективности программ.

Александр Чернов ( Пользователь )
Цитата (Андрей Сидоров, 29.01.2010, 17:39) <{POST_SNAPBACK}>
1) Вложенных циклов циклов в моем решение ровно столько, же сколько в книжном. На паскале без вложенных циклов эту задачу просто невозможно решить. Требуем невозможного?


В критериях, любезно выписанных Вами выше, написано про вложенные циклы, "если они не являются необходимыми".

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

Цитата (Андрей Сидоров, 29.01.2010, 17:39) <{POST_SNAPBACK}>
2) Каким образом переменная получит случайное значение, если в указанных при решении версиях языка (будь то Турбо Паскаль или PascalABC) переменные по умолчанию инициализируются нулями?


В Турбо-паскале глобальные переменные по умолчанию не инициализируются.

Цитата (Андрей Сидоров, 29.01.2010, 17:39) <{POST_SNAPBACK}>
3) Эксперт при проверке имеет право руководствоваться только формальными критериями, а не своими "фактическими" представлениями о эффективности программ.


Еще раз. С формальной точки зрения здесь применимо правило об избыточных вложенных циклах.
Андрей Сидоров ( Пользователь )
Цитата (cher, 29.01.2010, 18:08) <{POST_SNAPBACK}>
В Турбо-паскале глобальные переменные по умолчанию не инициализируются.

Еще раз. С формальной точки зрения здесь применимо правило об избыточных вложенных циклах.

1) То есть, если правильно понимаю, вы утверждаете, что в Turbo Pascal 7.0 переменные по умолчанию инициализируются случайными величинами? Сомневаюсь, но рассмотрю ссылку на подтверждение этого  факта.


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

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

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

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

По поводу решения на Руби - я не специалист, не могу сказать ничего про эффективность. То, что оно вполне мне понятно, хотя я не программировал на Руби, о чем-то говорит. Не знаю, как там в Руби с ленивыми вычислениями, но такое ощущение, что все данные хранятся в памяти, потому не очень эффективно. Но парадигма - совершенно другая - функциональная я бы сказал. И - я не просто не знаю ответ, что будет, если проверяющий увидит такое решение.. Я очень бы хотел услышать от кого-то компетентного, а можно ли вообще приводить решение на Руби? такое решение?
Александр Чернов ( Пользователь )
Цитата (Андрей Сидоров, 29.01.2010, 18:45) <{POST_SNAPBACK}>
1) То есть, если правильно понимаю, вы утверждаете, что в Turbo Pascal 7.0 переменные по умолчанию инициализируются случайными величинами? Сомневаюсь, но рассмотрю ссылку на подтверждение этого  факта.


Если сомневаетесь, то проверьте. Установите себе Turbo Pascal и запустите тестовые программы.

Цитата (Андрей Сидоров, 29.01.2010, 18:45) <{POST_SNAPBACK}>
2) То есть, в решении из книги вложенный цикл не является избыточным, а в моем является? Я как-то потерял логическую нить ваших рассуждений.


Вы с какой целью интересуетесь? :) Вы хотите доказать, что ваше решение такое же эффективное? Это не так, ваше решение примерно в 27 раз медленнее авторского при большом количестве вводимых символов. Получите ли Вы за него полный балл? Я бы не поставил и указал формальную причину, по которой это можно сделать. За других говорить не буду.
Станислав Михалкович ( Пользователь )
Цитата (cher, 29.01.2010, 13:14) <{POST_SNAPBACK}>
Использование неинициализированных переменных - очень неприятная и очень частая для начинающих ошибка. Разные версии паскаля обрабатывают глобальные (статические) переменные по-разному. В некоторых версиях глобальные переменные не инициализируются нулем. Поэтому за отсутствие инициализации (а не за неявную инициализацию) можно и нужно балл снижать.

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


Да, я уже забыл это. Действительно - посмотрел стандарт Паскаля - и нигде этого не нашел. Частично беру слова назад. Но буду настаивать на следующем. Пусть ученик напишет версию языка. Например, Delphi. Любая. Всё. Вы уже не сможете ему снизить за это балл. Особенно, если он напишет в комментарии, что в Delphi глобальные переменные инициализируются нулями. По незнанию не инициализировать - одно, я согласен, но по знанию - другое.

Цитата (cher, 29.01.2010, 13:14) <{POST_SNAPBACK}>
Не стоит делать столь обобщающих утверждений.

В данной программе заметно желание обойтись минимумом выразительных средств языка. Более того, программа написана так, что она переписывается один-в-один на любой другой аналогичный язык программирования, будь то C, C++, Basic, Modula...
Поэтому не используются процедуры, не используются структуры (записи), массивы индексируются от нуля. И с учетом этого программа написана вполне хорошо. Возможно, это решение было переписано на паскаль с си.

Или Вы всерьез предполагаете, что авторы данного решения настолько не знают именно паскаля?

Да, я немного утрирую. Я не сомневаюсь в компетентности авторов. Я понимаю, ПОЧЕМУ они так пишут. Но - они вертятся в рамках выбранной ими системы ограничений - пишут на подмножестве всех языков. А для Паскаля таким подмножеством являются чрезвычайно древние версии. К счастью, не исходный виртовский Паскаль, но очень древние. Психологически они стимулируют школьников жить в старом мире. Это - плохо. Более того, они пугают школьников, что отход от этого стиля череват снижением оценки. В результате у школьника вырабатывается страх перед новым и - как следствие - неправильные ориентиры.

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

Цитата (cher, 29.01.2010, 13:14) <{POST_SNAPBACK}>
Процедуры не используются - см. выше.
Увы, но с сортировкой массива Вы не правы. Если сортируемые данные достаточно большие, "в любом приличном проекте" будут сортироваться либо индексы, либо указатели. Ожидать от учебной задачи использования структур или, тем более, указателей, как-то черезчур...

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


Цитата (cher, 29.01.2010, 13:14) <{POST_SNAPBACK}>
Конструкция такова, поскольку паскаль не позволяет просто вычитать символы один из другого. В функцию это оформлять вообще бессмысленно, так как по сути это одно вычитание. Вы предлагаете любое вычитание оформлять в отдельную функцию?

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

Цитата (cher, 29.01.2010, 13:14) <{POST_SNAPBACK}>
Зачем пытаться оптимизировать по мелочам неоптимальное решение? Вы в точности и занимаетесь преждевременной оптимизацией...

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


Цитата (cher, 29.01.2010, 13:14) <{POST_SNAPBACK}>
Единственно верного решения не бывает никогда. Но предложенное в качестве альтернативы решение было заведомо неоптимальным. Это решение имеет сложность порядка 2*N и никакие ваши мелкие оптимизации не понизят его сложность. В то время, как предложенное авторами решение имеет сложность порядка N. N - длина входа, то есть количество символов, поданных на вход программе.

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

Вообщем, я, несомненно, не спорю про неоптимальность при больших N.

Цитата (cher, 29.01.2010, 13:14) <{POST_SNAPBACK}>
А как сортировать массив из 26 элементов - вообще дело десятое. Хоть пузырьком, хоть вставками, хоть быстрой сортировкой...

Да. Если бы было написано Sort(a,26), я бы гораздо меньше критиковал программу. Кстати, не понял, почему Вы против Swap.


Цитата (cher, 29.01.2010, 13:14) <{POST_SNAPBACK}>
Из того, что решение объяснять проще и быстрее, не следуюет, что оно правильное с точки зрения критериев C4.

Например, наверное, проще всего вычислять числа Фибоначчи через рекурсию вида f(n - 1) + f(n - 2). Нужно ли объяснять, почему такое решение не эффективное?

Может, в C4 критерии - плохие или кто-то придумывает по ходу новые критерии?
Фибоначчи через рекурсию - это, несомненная, мерзость :)

Цитата (cher, 29.01.2010, 13:14) <{POST_SNAPBACK}>
Решения по необходимости ориентированы на некоторый минимальный язык, являющийся подмножеством всех паскалей, которые могут использоваться в школах. Надо объяснять почему?

Все авторы программ, приведенных в сборниках, более чем компетентные люди.


Вы знаете, мы тоже - заложники всего этого. Мы недавно написали книгу по ЕГЭ - наверняка не самую лучшую, но там - много разобранных задач и на C4 в частности. Мы - коллектив из четырех авторов, у каждого - более 20 лет педагогического опыта. И, конечно, мы инициализируем входные данные, не пользуемся процедурами и пишем на минимальном подмножестве Паскаля. От нас это потребовали чтобы книга раскупалась. Мы попытались немного ослабить маразм ситуации, но сути это не меняет. Мы - заложники ЕГЭ. Мы вертимся в его правилах. За пределами ЕГЭ эти правила никому не нужны и вредны.

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


Спасибо! А для уважаемого cher могу предложить такое решение, без ord-ов:

var 
   tmp1:word;
   c,k,tmp2: char;
   sym: array['a'..'z'] of char; //буква
   cnt: array['a'..'z'] of word; //счетчик буквы

begin

read(с);
while c<>'.' do
   begin
    sym[c]:=c;
    cnt[c]:=cnt[c]+1;
    read(с);
   end;

for c:='a' to 'y' do // сортировка
   for k:=c to 'z' do  
      if (cnt[c]>cnt[k])or // по возрастанию частоты
      (cnt[c]=cnt[k])and(sym[c]>sym[k]) then // по алфавиту
        begin
          tmp1:= cnt[c]; cnt[c] := cnt[k]; cnt[k] := tmp1;
          tmp2:= sym[c]; sym[c] := sym[k]; sym[k] := tmp2;  
        end;

//вывод
for c:='a' to 'z' do
   if cnt[c]>0 then write(sym[c]);  
end.


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


Я тут подумал - в чем-то тут вы правы. Если сознательно отклониться от Ruby Way, то можно считывать не строку целиком (gets), а брать, как в паскале, по символу за раз - как-то так: 

a=Hash.new(0)
until (c=STDIN.getc)=="." do  
    a[c]+=1 
end
a.sort_by{|sym,cnt|[cnt,sym]}.each{|sym,cnt| print sym}

Но мне так не нравится! :)

Цитата (, 29.01.2010, 21:52) <{POST_SNAPBACK}>
И - я не просто не знаю ответ, что будет, если проверяющий увидит такое решение.. Я очень бы хотел услышать от кого-то компетентного, а можно ли вообще приводить решение на Руби? такое решение?


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


Была ли издана эта книга? Можно ссылку?

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



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