ЕГЭ по поэбеньтике

[lex_kravetski]

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

Comments

[son_0f_morning]

Какой смысл вообще в рамках одного предмета преподавать: "как правильно запустить excel двойным щелчком мыши" и "отдебажить в голове алгоритм, мутирующий строку, на 180+ символьном входе"?

[lex_kravetski]

Смысл, кстати, есть. Точнее, был бы при нормальной программе по IT. Поскольку, в частности, тот же самый Excel подразумевает плавное перетекание от кликов мышкой в написание микро-программ: сначала в виде комбинации функций в ячейках, потом на VBA для аналогичного вызова из ячеек, а потом на VBA для автоматизации процессов.

[ext_3342285]

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

[lex_kravetski]

Так не надо писать крестики-нолики при помощи формул. VBA там нужен для автоматизации заполнения таблиц и для программирования тех функций, которые в Excel не встроены.

[viktorpetrov]

Задачи на удивление адекватные и, что характерно, именно по информатике (а не по компьютерной грамотности или знанию конкретного языка). А Ваши комментарии немного удивляют. Например, в задаче предлагают найти число путей в ацикличном графе --- отличная задача на азы динамического программирования или метод "разделяй и властвуй" (который, впрочем, тут можно заменить и здравым смыслом, типа, если мы идем от вершины A до вершины B, то надо посмотреть на предпоследнюю вершину в пути С и заменить задачу на такую же, но с меньшим графом). Программисты, которые такой техникой не владеют, пишут потом индусский быдлокод, работающий за O(n!) там, где можно за O(n^2), причем тесты до n=10 проходят на ура. А Вы предлагаете перебирать все пути, это совсем другая задача. Думаю, Вы сами в состоянии на бумажке нарисовать граф, где ответом будет триллион --- предлагаете перебирать триллион путей?

[lex_kravetski]

> Например, в задаче предлагают найти число путей в ацикличном графе…

…вручную

> Программисты, которые такой техникой не владеют

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

> А Вы предлагаете перебирать все пути, это совсем другая задача.

Внезапно, задача перебора всех путей решается за то же время, за которое решается задача подсчёта всех путей древовидного направленного графа и имеет сложность сильно меньше, чем O(n^2). А именно O(n). Но для этого, конечно, надо уметь программировать.

> Задачи на удивление адекватные и, что характерно, именно по информатике

Всегда интересно посмотреть на закономерные результаты школьного обучения информатике.

[viktorpetrov]

В чем проблема вручную сложить 13 чисел? Тем более что большая часть сложений происходит с нулем.

Я не знаю, что имеется в виду под "древовидным", но в любом случае графы тех типов, которые на рисунке, к ним не относятся. Перечитайте мое исходное сообщение: не так уж сложно нарисовать граф с примерно 100 вершинами и ответом в виде триллиона путей. Вас не настораживает, что 100^2 сильно меньше триллиона? Насчет того, что можно подсчитать ответ (но никак не перебрать пути) быстрее, чем за O(n^2), я верю слабо, если нет дальнейших ограничений на число ребер. За O(n+m), где n --- число вершин, m --- число ребер, верю (в конце концов, задача похожа на топологическую сортировку).

[lex_kravetski]

> В чем проблема вручную сложить 13 чисел

[__const__]

Из неотмеченного безобразия: на Python обмен значениями можно (и нужно, для читаемости) производить без введения промежуточной переменной.
A[i], A[i-1] = A[i-1], A[i]
;)

[zagovor7]

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

[viktorpetrov]

Думаю, проще, "настоящий программист на Фортране может на любом языке написать программу на Фортране". Авторы стремились к единообразию, а в этом случае использование фич противопоказано.

[ext_5324538]

Лекс, в первом посте про стримы был пункт о началах программирования. Есть надежда на появления такого стрима?

[lex_kravetski]

Ну он чо-то не много голосов собрал. Поэтому когда-то.

[ext_3259374]

нда. вопросы конечно странные. хотя как правило в школе все дается в отрыве от практического применения. Информатика тут видимо не исключение.

+честно говоря, я не очень представляю как отвечать на вопрос о графах. предполагается написать программу, или вот так буквально написать сколько путей? их вручную посчитать можно даже не зная алгоритма - тут помоему и так все очевидно.

[viktorpetrov]

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

[ext_3259374]

в задаче никак не предполагается, что человек знает или в состоянии придумать алгоритм. Граф достаточно простой. Можно посчитать вручную, а потом написать что-то вроде

print N

и все. задача решена.

Это вероятно не сочтут за правильное решение, но по факту оно именно таким и будет

[viktorpetrov]

Конкретно в данной задаче ответ 40. Насчитать вручную перебором 40 объектов и не обсчитаться --- задача для человека довольно сложная. Другое дело, если он догадался хотя бы до 10*4, но тогда он и к алгоритму близок.

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