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

☑ Написать код алгоритма.

☑ Почитать внимательно правила оформления псевдокода, особенно насчёт фигурных скобок и именований переменных

☑ Зачем вводить странную конструкцию типа «переберем блаблабла», можно же написать что-то типа «for w in adjList[v]»? И предка лучше передавать в рекурсии явно, а то непонятно, как без цветов вершин в обходе мы вообще можем узнать, что было предком. --Дмитрий Герасимов 15:26, 27 ноября 2011 (MSK)

☑ Не надо писать «Псевдокод на C++», так как это не с++. Просто «Псевдокод»

☑ Псевдокод надо оформить в виде функции, которая принимает граф в каком-либо его виде, а возвращает максимальный вес паросочетания. Тут же только dfs, и даже неясно, из какой вершины его запускать(видимо, из произвольной, но всё же).

☐ Раз упомянул про алгоритм Куна, добавь ссылку на него, он есть в конспектах дискретки второго курса. И на паросочетание добавь.

☐ еще не хватает категорий

☐ « работает за время [math]O \left ( \sum_{x=1}^n \limits \left ( Ch \left ( x \right ) \right )^k \right )[/math] для вершины x.». Странно, для вершины x, а вершину x мы перебираем в суммировании. Как-то странно. А еще тут нет модуля, тебе же нужна мощность множества Ch.

☐ Ch(x) — не множество потомков, а множество сыновей, наверное. Мне кажется, это разные вещи.

☐ br'ы убирай, для этого есть двойной перевод строки.

Замечания АС

☑ Определение - множество ребер чего? Надеюсь, графа ;)

☐ Опять сразу "заведём массивы a, b и c размерностью n" без формулировки принципов оптимальности

Как следствие, дальнейшие рассуждения выглядят безосновательными.

☐ А второй раздел с места в карьер начинается утверждением, им и заканчивается. Возникает естественный вопрос: "и что?"

И зачем шаблон убрал, все равно это не изменило бы замечания АС, а форматирование ухудшилось.

☐ Про утверждение: "алгоритм динамического программирования" - а другой алгоритм не будет так работать, будет дольше?