Форум » Теория игр » [C3] Решение через дерево » Ответить

[C3] Решение через дерево

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

Ответов - 55, стр: 1 2 3 4 All

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

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

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


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

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

Поляков: Ion пишет: опишите пожалуйста, этот алгоритм более подробно и понятно Про динамическое программирование можно почитать в файле C3.doc или в главе нового учебника (там подробнее, но сложнее). Более подробно и понятно я описать, наверное, не смогу. :-) Если дерево автоматически доказывает отсутствие других решений, то как это решение можно не засчитать на 3 балла? Давайте подождем ответа разработчиков КИМ (будет на днях, опубликую здесь и на сайте).

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

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

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

Сидоров: Я не совсем уверен, что мой метод - это динамическое программирование. Попробуйте решить моим методом: 2 -> 33 1) +5 2) *4 Получится чистое дерево без повторяющихся узлов.

Поляков: Сидоров пишет: 2 -> 33 1) +5 2) *4 Получится чистое дерево без повторяющихся узлов. В таблице ДП тоже получаются только 0, 1 и 2. :-)

Сидоров: Поляков пишет: В таблице ДП тоже получаются только 0, 1 и 2. :-) Таблица получится шибко длинная, а дерево вот: [pre2] 33 - 28 - 23 - 18 - 13 - 8 - 3 | | 7 - 2 2 [/pre2]

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

Сидоров: Что лучше - такое дерево: [pre2] 33 - 28 - 23 - 18 - 13 - 8 - 3 | | 7 - 2 2 [/pre2] или такая таблица? [pre2] 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 [/pre2]

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



полная версия страницы