Обсуждение:Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве — различия между версиями
| Строка 5: | Строка 5: | ||
: {{tick | ticked=1}} Не надо писать «Псевдокод на ''C++''», так как это не с++. Просто «Псевдокод» | : {{tick | ticked=1}} Не надо писать «Псевдокод на ''C++''», так как это не с++. Просто «Псевдокод» | ||
: {{tick | ticked=1}} Псевдокод надо оформить в виде функции, которая принимает граф в каком-либо его виде, а возвращает максимальный вес паросочетания. Тут же только dfs, и даже неясно, из какой вершины его запускать(видимо, из произвольной, но всё же). | : {{tick | ticked=1}} Псевдокод надо оформить в виде функции, которая принимает граф в каком-либо его виде, а возвращает максимальный вес паросочетания. Тут же только dfs, и даже неясно, из какой вершины его запускать(видимо, из произвольной, но всё же). | ||
| − | : {{tick}} Раз упомянул про алгоритм Куна, добавь ссылку на него, он есть в конспектах дискретки второго курса. И на паросочетание добавь. | + | : {{tick | ticked=1}} Раз упомянул про алгоритм Куна, добавь ссылку на него, он есть в конспектах дискретки второго курса. И на паросочетание добавь. |
| − | : {{tick}} еще не хватает категорий | + | : {{tick | ticked=1}} еще не хватает категорий |
| − | : {{tick}} « работает за время <tex>O \left ( \sum_{x=1}^n \limits \left ( Ch \left ( x \right ) \right )^k \right )</tex> для вершины x.». Странно, для вершины x, а вершину x мы перебираем в суммировании. Как-то странно. А еще тут нет модуля, тебе же нужна мощность множества Ch. | + | : {{tick | ticked=1}} « работает за время <tex>O \left ( \sum_{x=1}^n \limits \left ( Ch \left ( x \right ) \right )^k \right )</tex> для вершины x.». Странно, для вершины x, а вершину x мы перебираем в суммировании. Как-то странно. А еще тут нет модуля, тебе же нужна мощность множества Ch. |
| − | : {{tick}} Ch(x) — не множество потомков, а множество сыновей, наверное. Мне кажется, это разные вещи. | + | : {{tick | ticked=1}} Ch(x) — не множество потомков, а множество сыновей, наверное. Мне кажется, это разные вещи. |
| − | : {{tick}} br'ы убирай, для этого есть двойной перевод строки. | + | : {{tick | ticked=1}} br'ы убирай, для этого есть двойной перевод строки. |
== Замечания АС == | == Замечания АС == | ||
: {{tick | ticked=1}} Определение - множество ребер чего? Надеюсь, графа ;) | : {{tick | ticked=1}} Определение - множество ребер чего? Надеюсь, графа ;) | ||
| − | : {{tick}} Опять сразу "заведём массивы a, b и c размерностью n" без формулировки принципов оптимальности | + | : {{tick | ticked=1}} Опять сразу "заведём массивы a, b и c размерностью n" без формулировки принципов оптимальности |
Как следствие, дальнейшие рассуждения выглядят безосновательными. | Как следствие, дальнейшие рассуждения выглядят безосновательными. | ||
: {{tick}} А второй раздел с места в карьер начинается утверждением, им и заканчивается. Возникает естественный вопрос: "и что?" | : {{tick}} А второй раздел с места в карьер начинается утверждением, им и заканчивается. Возникает естественный вопрос: "и что?" | ||
:: И зачем шаблон убрал, все равно это не изменило бы замечания АС, а форматирование ухудшилось. | :: И зачем шаблон убрал, все равно это не изменило бы замечания АС, а форматирование ухудшилось. | ||
| − | : {{tick}} Про утверждение: "алгоритм динамического программирования" - а другой алгоритм не будет так работать, будет дольше? | + | : {{tick | ticked=1}} Про утверждение: "алгоритм динамического программирования" - а другой алгоритм не будет так работать, будет дольше? |
Текущая версия на 07:59, 29 февраля 2012
- ☑ Написать код алгоритма.
- ☑ Почитать внимательно правила оформления псевдокода, особенно насчёт фигурных скобок и именований переменных
- ☑ Зачем вводить странную конструкцию типа «переберем блаблабла», можно же написать что-то типа «for w in adjList[v]»? И предка лучше передавать в рекурсии явно, а то непонятно, как без цветов вершин в обходе мы вообще можем узнать, что было предком. --Дмитрий Герасимов 15:26, 27 ноября 2011 (MSK)
- ☑ Не надо писать «Псевдокод на C++», так как это не с++. Просто «Псевдокод»
- ☑ Псевдокод надо оформить в виде функции, которая принимает граф в каком-либо его виде, а возвращает максимальный вес паросочетания. Тут же только dfs, и даже неясно, из какой вершины его запускать(видимо, из произвольной, но всё же).
- ☑ Раз упомянул про алгоритм Куна, добавь ссылку на него, он есть в конспектах дискретки второго курса. И на паросочетание добавь.
- ☑ еще не хватает категорий
- ☑ « работает за время для вершины x.». Странно, для вершины x, а вершину x мы перебираем в суммировании. Как-то странно. А еще тут нет модуля, тебе же нужна мощность множества Ch.
- ☑ Ch(x) — не множество потомков, а множество сыновей, наверное. Мне кажется, это разные вещи.
- ☑ br'ы убирай, для этого есть двойной перевод строки.
Замечания АС
- ☑ Определение - множество ребер чего? Надеюсь, графа ;)
- ☑ Опять сразу "заведём массивы a, b и c размерностью n" без формулировки принципов оптимальности
Как следствие, дальнейшие рассуждения выглядят безосновательными.
- ☐ А второй раздел с места в карьер начинается утверждением, им и заканчивается. Возникает естественный вопрос: "и что?"
- И зачем шаблон убрал, все равно это не изменило бы замечания АС, а форматирование ухудшилось.
- ☑ Про утверждение: "алгоритм динамического программирования" - а другой алгоритм не будет так работать, будет дольше?
