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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 5: Строка 5:
 
: {{tick | ticked=1}} Не надо писать «Псевдокод на ''C++''», так как это не с++. Просто «Псевдокод»
 
: {{tick | ticked=1}} Не надо писать «Псевдокод на ''C++''», так как это не с++. Просто «Псевдокод»
 
: {{tick | ticked=1}} Псевдокод надо оформить в виде функции, которая принимает граф в каком-либо его виде, а возвращает максимальный вес паросочетания. Тут же только dfs, и даже неясно, из какой вершины его запускать(видимо, из произвольной, но всё же).
 
: {{tick | ticked=1}} Псевдокод надо оформить в виде функции, которая принимает граф в каком-либо его виде, а возвращает максимальный вес паросочетания. Тут же только dfs, и даже неясно, из какой вершины его запускать(видимо, из произвольной, но всё же).
: {{tick | ticked=1}} Раз упомянул про алгоритм Куна, добавь ссылку на него, он есть в конспектах дискретки второго курса. И на паросочетание добавь.  
+
: {{tick}} Раз упомянул про алгоритм Куна, добавь ссылку на него, он есть в конспектах дискретки второго курса. И на паросочетание добавь.  
: {{tick | ticked=1}} еще не хватает категорий
+
: {{tick}} еще не хватает категорий
: {{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}} « работает за время <tex>O \left ( \sum_{x=1}^n \limits \left ( Ch \left ( x \right ) \right )^k \right )</tex> для вершины x.». Странно, для вершины x, а вершину x мы перебираем в суммировании. Как-то странно. А еще тут нет модуля, тебе же нужна мощность множества Ch.
: {{tick | ticked=1}} Ch(x) — не множество потомков, а множество сыновей, наверное. Мне кажется, это разные вещи.
+
: {{tick}} Ch(x) — не множество потомков, а множество сыновей, наверное. Мне кажется, это разные вещи.
: {{tick | ticked=1}} br'ы убирай, для этого есть двойной перевод строки.
+
: {{tick}} br'ы убирай, для этого есть двойной перевод строки.
  
 
== Замечания АС ==
 
== Замечания АС ==
  
 
: {{tick | ticked=1}} Определение - множество ребер чего? Надеюсь, графа ;)
 
: {{tick | ticked=1}} Определение - множество ребер чего? Надеюсь, графа ;)
: {{tick | ticked=1}} Опять сразу "заведём массивы a, b и c размерностью n" без формулировки принципов оптимальности
+
: {{tick}} Опять сразу "заведём массивы a, b и c размерностью n" без формулировки принципов оптимальности
 
Как следствие, дальнейшие рассуждения выглядят безосновательными.
 
Как следствие, дальнейшие рассуждения выглядят безосновательными.
 
: {{tick}} А второй раздел с места в карьер начинается утверждением, им и заканчивается. Возникает естественный вопрос: "и что?"
 
: {{tick}} А второй раздел с места в карьер начинается утверждением, им и заканчивается. Возникает естественный вопрос: "и что?"
 
:: И зачем шаблон убрал, все равно это не изменило бы замечания АС, а форматирование ухудшилось.  
 
:: И зачем шаблон убрал, все равно это не изменило бы замечания АС, а форматирование ухудшилось.  
: {{tick | ticked=1}} Про утверждение: "алгоритм динамического программирования" - а другой алгоритм не будет так работать, будет дольше?
+
: {{tick}} Про утверждение: "алгоритм динамического программирования" - а другой алгоритм не будет так работать, будет дольше?

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: