Отправлено: 24.01.12 19:12. Заголовок: [C3] Решение через дерево

Вопрос:

цитата:

Здравствуйте! Есть вопрос по заданию С3: "У исполнителя Увеличитель две команды,которым присвоены номера: 1. прибавь 1; 2. умножь на 4. Сколько есть программ,которые число 1 преобразуют в число 32? Ответ обоснуйте. " Так вот, решаю это задание всегда "деревом" возможных решений,получается быстро и наглядно. Но на пробном ЕГЭ в школе учительница поставила 0 баллов и сказала что это неправильно, и, ссылаясь на правильное решение "Таблицей" с Вашего сайта, закончила разговор...=( Прошу рассудить, и сказать, имеет ли право на жизнь решение "деревом" задания С3...

В ответ на ваш вопрос приведу выдержку из критериев оценки из опубликованного демо-варианта:

цитата:

"В частности, оценка в 2 балла выставляется в случае, если просто перечислены все правильные программы и не доказано отсутствие других программ, кроме приведенных."

Так что ваше решение (если, конечно, получен правильный ответ) попадает целиком под этот пункт, то есть за решение с помощью дерева (перечислением) должны поставить 2 балла.

Ответ М.А. Ройтберга:

цитата:

Здравствуй, ….! Мне проще обращаться на «ты», если что – извини(те) ). Начну с конца. Никогда нельзя быть уверенным, что известны все правильные решения (в смысле – все рассуждения, приводящие к правильному решению). Вот правильный ответ может быть известен и может быть доказано, что других ответов нет. Таким образом, наличие определенного решения (например, «Таблицей»), само по себе не означает, что какое-то другое рассуждение (например, «деревом возможных решений» ) неправильное. Но является ли решение правильным, нельзя узнать, не увидев самого решения. Если оно приводит к неправильному ответу, - значит, точно неправильное. Но даже правильный ответ не гарантирует правильности решения. Более того. Может быть, решение (которое имелось в виду) было правильным, но при записи не были разобраны какие-то варианты. Построение дерева возможностей как раз часто и приводит к подобным ошибкам (а таблица от них защищает). Вывод. Если хочешь, пришли мне свое решение, я посмотрю и отвечу, правильное ли оно. Напоследок – несколько вопросов/замечаний. 1. Разобрался ли ты в решении «Таблицей»? В нем полезно разобраться независимо от ЕГЭ. Если не разобрался – напиши, что непонятно. 2. Даже, если твое решение правильное, сдавая экзамен, стоит помнить, что экзаменатор – человек. И, значит, (при прочих равных условиях) – писать то решение, в котором экзаменатору будет легче разобраться. В данном случае, - это, видимо, решение «Таблицей». 3. Ты пишешь: «Так вот, решаю это задание всегда "деревом" возможных решений, получается быстро и наглядно» Насчет «наглядно» - возможно, а насчет «быстро» - сомневаюсь. Я вот сделал ошибку при построении дерева. Если бы не знал правильный ответ (быстро заполнил таблицу), - пропустил бы. Успехов!

 Отправлено: 31.01.12 22:49. Заголовок: У той формы записи, ..

У той формы записи, которя в ответах демоварианта, у моих учеников помутнение в глазах и мозгу. А "карту", где нарисовано, какими способами дойти от большего числа к меньшему, они сразу понимают.

 Отправлено: 01.02.12 20:26. Заголовок: Я, честно говоря, то..

Я, честно говоря, тоже не могу понять, почему построение дерева не устраивает - разве при этом автоматически не доказывается, что других решений нет?

 Отправлено: 01.02.12 20:45. Заголовок: Ion пишет: Я, честно..

Ion пишет:

цитата:

Я, честно говоря, тоже не могу понять, почему построение дерева не устраивает - разве при этом автоматически не доказывается, что других решений нет?

Насколько я понимаю, есть две причины:
1) дерево - для ручного подсчёта, а информатика всё-таки занимается автоматической обработкой информации; решение таблицей (динамическое программирование) очень просто алгоритмизируется;
2) при большом числе программ (см. задачи 6-10 из файла C3.doc) дерево рисовать замучаетесь.

 Отправлено: 01.02.12 21:11. Заголовок: Держу пари, что в ре..

Держу пари, что в реале трехоперационных задач не будет, и не будет задач с количеством ответов больше 100. Подсчеты в них слишком громоздки даже для табличного метода.

 Отправлено: 02.02.12 13:04. Заголовок: решение таблицей (ди..

цитата:

решение таблицей (динамическое программирование) очень просто алгоритмизируется

Константин, если Вам не трудно, опишите пожалуйста, этот алгоритм более подробно и понятно. Или скажите, где можно более подробно про это прочитать. Я готовлюсь к экзамену самостоятельно и не совсем его понимаю. :(

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

 Отправлено: 02.02.12 13:56. Заголовок: Ion пишет: опишите п..

Ion пишет:

цитата:

опишите пожалуйста, этот алгоритм более подробно и понятно

Про динамическое программирование можно почитать в файле C3.doc или в главе нового учебника (там подробнее, но сложнее). Более подробно и понятно я описать, наверное, не смогу. :-)

цитата:

Если дерево автоматически доказывает отсутствие других решений, то как это решение можно не засчитать на 3 балла?

Давайте подождем ответа разработчиков КИМ (будет на днях, опубликую здесь и на сайте).

 Отправлено: 03.02.12 13:32. Заголовок: Уважаемые коллеги-уч..

Уважаемые коллеги-учителя!
Разработчиков КИМ ЕГЭ-2012 интересуют ваши предложения по оценке решений C3, полученных с помощью построения полного дерева, без динамического программирования. Если эта тема вас интересует, напишите, какие решения вы оценили бы на 3 балла, 2 балла, 1 балл. К предложениям можно приложить файлы с образцами соответствующих решений.
Сейчас есть реальная возможность принять участие в формировании критериев оценивания!

 Отправлено: 03.02.12 18:18. Заголовок: Поляков пишет: Уваж..

Поляков пишет:

цитата:

Уважаемые коллеги-учителя! Разработчиков КИМ ЕГЭ-2012 интересуют ваши предложения по оценке решений C3, полученных с помощью построения полного дерева, без динамического программирования. Если эта тема вас интересует, напишите, какие решения вы оценили бы на 3 балла, 2 балла, 1 балл. К предложениям можно приложить файлы с образцами соответствующих решений. Сейчас есть реальная возможность принять участие в формировании критериев оценивания!

Свой метод решения я оцениваю на 3 балла!

 Отправлено: 03.02.12 18:22. Заголовок: Сидоров пишет: Свой ..

Сидоров пишет:

цитата:

Свой метод решения я оцениваю на 3 балла!

Дело не в методе. Дело в том, что должно обязательно присутствовать в ЗАПИСИ решения, для того, чтобы его можно было оценить в 1, 2 или 3 балла. Кстати, ваш метод - это динамическое программирование, поэтому он идет "вне конкурса". :-) Речь о построении полного дерева.

 Отправлено: 03.02.12 18:30. Заголовок: Я не совсем уверен, ..

Я не совсем уверен, что мой метод - это динамическое программирование. Попробуйте решить моим методом:

2 -> 33
1) +5
2) *4

Получится чистое дерево без повторяющихся узлов.

 Отправлено: 03.02.12 18:38. Заголовок: Сидоров пишет: 2 -&..

Сидоров пишет:

цитата:

2 -> 33 1) +5 2) *4 Получится чистое дерево без повторяющихся узлов.

В таблице ДП тоже получаются только 0, 1 и 2. :-)

 Отправлено: 03.02.12 19:05. Заголовок: Поляков пишет: В та..

Поляков пишет:

цитата:

В таблице ДП тоже получаются только 0, 1 и 2. :-)

Таблица получится шибко длинная, а дерево вот:

 
 33 - 28 - 23 - 18 - 13 - 8 - 3 
       |                  | 
       7 - 2              2 
 

 Отправлено: 03.02.12 19:27. Заголовок: Сидоров пишет: Я не ..

Сидоров пишет:

цитата:

Я не совсем уверен, что мой метод - это динамическое программирование.

Зря. Динамическое программирование состоит в том, что мы учитываем уже готовые результаты предыдущих шагов, не вычисляя из заново. Вы делаете то же самое. А как оформить - дело второе.

 Отправлено: 03.02.12 19:36. Заголовок: Что лучше - такое де..

Что лучше - такое дерево:

 
 33 - 28 - 23 - 18 - 13 - 8 - 3 
       |                  | 
       7 - 2              2 
 

или такая таблица?

 
  2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 
  1 0 0 0 0 1 1 0  0  0  1  1  0  0  0  1  1  0  0  0  1  1  0  0  0  1  2  0  0  0  2  2 
 

 Отправлено: 03.02.12 20:39. Заголовок: Сидоров пишет: Что л..

Сидоров пишет:

цитата:

Что лучше - такое дерево: ... или такая таблица?

Здесь перемешаны два совершенно разных вопроса. Ответы на них такие:
1. Ваш метод - это фактически динамическое программирование.
2. Запись «обратным деревом» в данном случае удобнее для человека (при ручном решении), использование таблицы удобнее при алгоритмизации (при машинном решении).