Ответ на »сообщение 3255« (Руслан Богатырев)
___________________________

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

В отличие от участников мы уже знаем статистику сдачи и, ориентируясь по ней, можем косвенно выделить простые и сложные. Делается это так: берем замороженное табло (официальное никогда не публикуют, более того, даже команды-участники в полном варианте его не имеют -- форменное безобразие). Вот оно: http://icpc.baylor.edu/icpc/Finals/Scoreboard/default.htm

Заморожено оно после окончания 4-го часа (т.е. примерно в районе 4*60-240-й минуты). В столбце по каждой задаче (от A до J) напротив каждой команды указано количество попыток и через дробь -- минута, на которой была зафиксирована успешная попытка. В столбце Time указано суммарное время минут успешной сдачи + штрафных минут (по 20 за каждую неудачную попытку).

Сразу видно, что задачи E, H и J относятся к разряду "гробов" (есть такой жаргон в этой сфере). По ним к окончанию 4-го часа не было ни одной успешной попытки сдачи. "Гробы" (почти неразрешимые задачи в смысле длительности кодирования или сложности поиска идеи-ключа) в последние чемпионаты постоянно добавляются, чтобы жизнь медом не казалась. По задачкам E и H участники попыток сдачи даже не предпринимали, видимо классифицировав их как 100-процентные гробы. В результате чемпионы (Warsaw Univ.) за оставшийся час сдали еще какую-то из них (у Варшавы было 7 задач, в итоге стало 8). Смотрим сводную итоговую таблицу без детальной статистики: http://icpc.baylor.edu/icpc/Finals/scoreboard/Final/

Сопоставив время поляков на 4-м часу (1133) и финальный результат после 5-го часа (1405), приходим к выводу, что им добавили 1405-1133=272 мин. Поскольку в этих 272 мин. уже заложены 240 мин. первых четырех часов (относительно которых мы и делаем срез), то получаем разницу в 272-240=32 мин. Т.е. либо они с первой попытки сдали какую-то из задач-гробов на 32-й минуте 5-го часа, либо сдали ее на 12-й минуте того же последнего игрового часа со второй попытки (20 мин. штрафа). Судя по соотношению попыток и принятых решений (Total att/solv), они придерживались тактики "тихой паники" (18/7). Тогда как, например, новосибирцы и саратовцы шли размеренно: имели 9/5 и 8/5 соответственно (у МГУ "паника" была очень уж заметной -- 22/5, хотя могли и быть чисто технические проблемы).

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

Ответ на »сообщение 3254« (Geniepro)
___________________________

А нельзя ли проверять решения по очереди, а не все сразу? Ну типа как на том самом чемпионате? А то неизвестно, смогу ли я решить все эти задачки и захочет ли ещё какой хаскеллер решать их?

На чемпионате (если ничего не путаю) регламент таков, что задачи проверяются на контрольном наборе тестов специальной системой (Programming Contest Control System). Сама команда должна решить, будет ли она делать попытку сейчас или еще доработает решение. В случае каждой неудачной попытки сдать задачу команде начисляется 20 мин. штрафа (если задача в итоге так и не была принята, штраф за нее не начисляется). Они добавляются к сумме минут, на которых судьями была принята каждая из успешно решенных задач. Показания времени играют решающую роль при распределении мест между командами, решившими одинаковое число задач.

Напомню, что в финалах ACM ICPC требуется решить 10 задач за 5 часов. Это к вопросу о "шапкозакидательстве". Здесь соревнуются алгоритмисты. UI равно как и системная инфраструктура убраны вообще (хотя в TopCoder есть соответствующие "номинации", но там больше конкурс, а не спорт).
Конечно, даже "любители" из студенческих команд (по сравнению с профи на TopCoder) поднаторели в "щелкании" задачек такого плана и в специфике работы. И мы по сравнению с ними в этом плане просто начинающие.

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

Так что Руслан, следующий ход Ваш, ждём решений на Обероне, а я пока почитаю этот задачник дальше...

Сожалею, но, заварив кашу, я, как обычно, "умываю руки". Возможно, кто-то из сторонников Оберона возьмется хотя бы за пару-тройку задач. Займу нейтральную позицию, чтобы собрать решения и передать их экспертам. Дергать их по каждой задаче нереально. Так что если есть желание сопоставить Oberon и Haskell на этом наборе алгоритмических задач, предлагаю сначала выдвинуть решения, обсудить их, а потом коллективные варианты от каждой стороны передать экспертам. Думаю, можно даже пойти таким путем: распределить задачи (даже по языкам). А потом, узнав правильное решение (от экспертов), заоптимизировать его, переписав на другом языке. Вопросы контроля времени тут не стоят. Плюс одна из главных вещей -- поиск идеи -- тоже за скобками, ведь нас интересует не процесс мышления, а результат. Хотя, наверняка, язык и центральная его парадигма могут существенно влиять на скорость получения правильного результата. Кстати, а почему еще и Delphi к этому не подключить, раз мы в Королевстве это обсуждаем и тут немало спецов по этому языку?

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

Сравнение еще интересно и вот в каком плане: как известно, раньше на чемпионатах допускались решения на 4 языках -- Cи, C++, Java, Паскаль (C# пока вне игры по политическим соображения ген.спонсора -- IBM). Фиксировались эталонные системы программирования с минимумом стандартных настроек для каждого компьютера команды-участницы. Паскаль, на котором наши преимущественно писали, исключили из "элиты" по причине "моральной старости". Притом, что для контроля правильности язык как таковой не рассматривается; отслеживается лишь корректность поведения программы на наборе контрольных тестов для каждой задачи. Текст члены жюри будут изучать лишь в исключительных случаях, при подаче протестов.

Если вернуться к самому спортивному регламенту, то лично для меня очевидно, что если есть пять часов на размышление, три участника в команде и всего один компьютер в их распоряжении, то нужна соответствующая схема коллективной разработки в этом "экстремальном программировании". Нужно отдельно искать идеи-отмычки к задачам, отдельно готовить варианты, отдельно их кодировать (возможно, с предварительным стенографированием участником, "не рулящим" сейчас компьютером), отдельно проверять правильность (как идеи решения, так и кода). В этом случае о каком-то там проектировании системы классов, по-моему, речи быть не может. Равно как и об инфраструктуре обвязки решения. Это стадии другого уровня, не спортивного программирования. А вот операторное программирование (внутри того же Оберона или Delphi) или функциональное (внутри Haskell или иного ФЯ) -- вполне могут здесь посоперничать.

Ответ на »сообщение 3224« (Руслан Богатырев)
___________________________

Так и давайте приколимся. Вот текст задач чемпионата (PDF): http://icpc.baylor.edu/icpc/Finals/2007WorldFinalProblemSet.pdf

Как насчет того, чтобы подготовить решения на Haskell и выставить на всеобщий суд общественности?

Почему бы и нет? Первую задачку из этого конкурса я вроде решил и выложил в теме %url[Функциональное программирование]


Для контроля правильности готов взять на себя миссию связаться с нашими ведущими спецами по чемпионатам ACM и огласить их вердикт.

А нельзя ли проверять решения по очереди, а не все сразу? Ну типа как на том самом чемпионате? А то неизвестно, смогу ли я решить все эти задачки и захочет ли ещё какой хаскеллер решать их?


Кстати, было бы интересно услышать аргументы в защиту того, почему ту или иную задачу лучше решать на языке ФП, а не, например, на Обероне.

Кстати, да, было бы очень интересно сравнить решения на Хаскелле с решениями на Обероне и обсудить, какие решения лучше/проще/красивее и т.д...
Так что Руслан, следующий ход Ваш, ждём решений на Обероне, а я пока почитаю этот задачник дальше...

Ответ на »сообщение 3252« (AVC)
___________________________

Ответ на »сообщение 3171« (Jack Of Shadows)
Но из чтения SICP (на примере из раздела 3.1.2) у меня родилось подозрение, что (в чистом виде) ФП находится в некотором противоречии с модульностью (в смысле сокрытия информации, coupling/cohesion и т.п.).
Т.к. я очень ценю модульность, то меня это беспокоит.
Я про это и говорил несколько раньше...
Модульная архитектура построена на отношениях, связях между модулями, которые строятся динамически по определенным правилам, через те или иные разъемы, интерфейсы - шины сообщений, объектно-ориентированные хуки, инсталлируемые каталоги и т.п. Но для этого необходимо наличие состояния у модуля, т.е. меняющейся во времени информации о подключении его к тем или иным разъемам.
В том же Хацкеле модуль состояния не имеет. Т.е. он всегда один и тот же - каким был в момент написания/компиляции. Ни в какие связи кроме участия в статическом импорте другим модулем вступать он не может. Модульная архитектура невозможна, остается только модульная декомпозиция и упаковка.
Однако это весьма интересное направление для работы функциональщикам - сформировать декларативные конструкции для выстраивания межмодульных отношений.
А, возможно, и не декларативные - а сделать конструкции соединения модулей синхронными, императивными, но высокоуровневыми (без каких-либо присваиваний, все в жестких рамках, так сказать). Будет еще один четко выделенный островок синхронности в ФП акромя closures.

Ответ на »сообщение 3171« (Jack Of Shadows)
___________________________

Ответ на »сообщение 3170« (AVC)
___________________________

Недостатки ФП навскидку (эффективность и требования к рессурсам не рассматриваем, правильно ?)

1. Невозможность чистого ФП, приходится "опускаться" до императива.
2. Сравнительная (с ИЯ) сложность обучения.
3. Все недостатки императивного подхода (поскольку к нему ПРИХОДИТСЯ прибегать) ТАМ где к нему приходится прибегать.
4. Исторически сложившаяся бедность (по сравнению с mainstream языками) библиотеками и тулзами (средами)
5. Невозможность обеспечить индустрию достаточным количеством специалистов. При чем я не знаю вызвано ли это повышенной сложностью работы с ФП или же отсутствием необходимой инфраструктуры (повальное обучение, коммерческие среды и библиотеки) То есть лечится это со временем или нет.


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

Что касается ФП, то видно, что у этого подхода в ряде ситуаций есть заметные преимущества, связанные прежде всего с отсутствием побочных эффектов.
Но из чтения SICP (на примере из раздела 3.1.2) у меня родилось подозрение, что (в чистом виде) ФП находится в некотором противоречии с модульностью (в смысле сокрытия информации, coupling/cohesion и т.п.).
Т.к. я очень ценю модульность, то меня это беспокоит.

Ответ на »сообщение 3246« (info21)
___________________________
Ответ на »сообщение 3233« (Сергей Перовский)
___________________________

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

Лучше так спросить: в каких прикладных задачах отказ от использование механизмов модульности не будет приводить к заметонму оверхеду?
Ответ: в маленьких задачах -- по-грубому, до 500 строк.

Абажьите!
Имеется в виду количество строк относящихся ТОЛЬКО к предметной области?
А вообще мне сама постановка вопроса не симпатична...

Ответ на »сообщение 3245« (info21)
___________________________
Впервые за несколько лет соглашаюсь полностью с тем, что вы сказали...