Обсуждение:Задача о порядке перемножения матриц — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 3: Строка 3:
 
:: Не done, я всё ещё не вижу какой-то оценки, кроме слов «экспоненциально»
 
:: Не done, я всё ещё не вижу какой-то оценки, кроме слов «экспоненциально»
 
::: Check it again, pls --[[Участник:GosuGDR|GosuGDR]] 04:27, 12 декабря 2011 (MSK)
 
::: Check it again, pls --[[Участник:GosuGDR|GosuGDR]] 04:27, 12 декабря 2011 (MSK)
 +
:::: Есть точная оценка на количество правильных скобочных последовательностей — так и добавь её сюда. И ты начал считать асимптотику в шапке — делай это в разделе про перебор.
 
: {{tick | ticked=1}} Не надо писать про решение без мемоизации, итак очевидно что её надо делать в динамике. Сразу пиши что будем запоминать.
 
: {{tick | ticked=1}} Не надо писать про решение без мемоизации, итак очевидно что её надо делать в динамике. Сразу пиши что будем запоминать.
 
: {{tick}} Используй тег tex. И надо писать O(n) в техе полностью, а не только n.
 
: {{tick}} Используй тег tex. И надо писать O(n) в техе полностью, а не только n.
 
:: Заюзал, как в статье вики, на которую лежит ссылка в «псевдосправке» --[[Участник:GosuGDR|GosuGDR]] 04:27, 12 декабря 2011 (MSK)
 
:: Заюзал, как в статье вики, на которую лежит ссылка в «псевдосправке» --[[Участник:GosuGDR|GosuGDR]] 04:27, 12 декабря 2011 (MSK)
 +
::: В статье примеры использования TeX в общем. У нас же надо использовать '''тег''' tex, а не math.
 
: {{tick}} «поскольку существует всего n^2/2 матриц» — каких матриц? Здесь надо сказать «подотрезков», видимо.
 
: {{tick}} «поскольку существует всего n^2/2 матриц» — каких матриц? Здесь надо сказать «подотрезков», видимо.
 
:: Done --[[Участник:GosuGDR|GosuGDR]] 07:08, 11 декабря 2011 (MSK)
 
:: Done --[[Участник:GosuGDR|GosuGDR]] 07:08, 11 декабря 2011 (MSK)
 
:: «около n^2/2 подотрезков — как-то не очень, их можно рассчитать точно, либо просто писать O(n^2) подотрезков.
 
:: «около n^2/2 подотрезков — как-то не очень, их можно рассчитать точно, либо просто писать O(n^2) подотрезков.
 
::: Поправил. проверь ещё раз. --[[Участник:GosuGDR|GosuGDR]] 04:27, 12 декабря 2011 (MSK)
 
::: Поправил. проверь ещё раз. --[[Участник:GosuGDR|GosuGDR]] 04:27, 12 декабря 2011 (MSK)
 +
:::: Плохо говорить около O(что-то там), так как это оценка асимптотическая. Убери  «около»
 
: {{tick | ticked=1}} Написать про восстановление ответа  
 
: {{tick | ticked=1}} Написать про восстановление ответа  
 
:: Написано о способе восстановления. Написать в псевдокоде? --[[Участник:GosuGDR|GosuGDR]] 14:33, 10 декабря 2011 (MSK)
 
:: Написано о способе восстановления. Написать в псевдокоде? --[[Участник:GosuGDR|GosuGDR]] 14:33, 10 декабря 2011 (MSK)
 
:: Не вижу, где о нём хоть что-то написано. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 21:18, 10 декабря 2011 (MSK)
 
:: Не вижу, где о нём хоть что-то написано. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 21:18, 10 декабря 2011 (MSK)
 
::: А теперь норм? --[[Участник:GosuGDR|GosuGDR]] 03:47, 12 декабря 2011 (MSK)
 
::: А теперь норм? --[[Участник:GosuGDR|GosuGDR]] 03:47, 12 декабря 2011 (MSK)
: {{tick}} Написать псевдокод --[[Участник:GosuGDR|GosuGDR]] 11:45, 10 декабря 2011 (MSK)
+
: {{tick | ticked=1}} Написать псевдокод --[[Участник:GosuGDR|GosuGDR]] 11:45, 10 декабря 2011 (MSK)
 
:: Замечания? --[[Участник:GosuGDR|GosuGDR]] 14:33, 10 декабря 2011 (MSK)
 
:: Замечания? --[[Участник:GosuGDR|GosuGDR]] 14:33, 10 декабря 2011 (MSK)
 
:: Почему у тебя динамика — массив, а размеры матрица — вектор, надо придерживаться чего-то более-менее одного.  
 
:: Почему у тебя динамика — массив, а размеры матрица — вектор, надо придерживаться чего-то более-менее одного.  

Версия 05:41, 12 декабря 2011

«На самом деле задача заключается не в нахождении результата перемножения, а в нахождении нужного порядка этого перемножения.» — ну это очевидно, здесь надо написать что произведение матриц ассоциативно и то что в «Постановке задачи» переместить в шапку даюы пояснить, в чем собственно состоит задача.
Рассчитать асимптотику брутфорса. Сделать разделы «Решение перебором» и «Решение динамическим программированием»
Не done, я всё ещё не вижу какой-то оценки, кроме слов «экспоненциально»
Check it again, pls --GosuGDR 04:27, 12 декабря 2011 (MSK)
Есть точная оценка на количество правильных скобочных последовательностей — так и добавь её сюда. И ты начал считать асимптотику в шапке — делай это в разделе про перебор.
Не надо писать про решение без мемоизации, итак очевидно что её надо делать в динамике. Сразу пиши что будем запоминать.
Используй тег tex. И надо писать O(n) в техе полностью, а не только n.
Заюзал, как в статье вики, на которую лежит ссылка в «псевдосправке» --GosuGDR 04:27, 12 декабря 2011 (MSK)
В статье примеры использования TeX в общем. У нас же надо использовать тег tex, а не math.
«поскольку существует всего n^2/2 матриц» — каких матриц? Здесь надо сказать «подотрезков», видимо.
Done --GosuGDR 07:08, 11 декабря 2011 (MSK)
«около n^2/2 подотрезков — как-то не очень, их можно рассчитать точно, либо просто писать O(n^2) подотрезков.
Поправил. проверь ещё раз. --GosuGDR 04:27, 12 декабря 2011 (MSK)
Плохо говорить около O(что-то там), так как это оценка асимптотическая. Убери «около»
Написать про восстановление ответа
Написано о способе восстановления. Написать в псевдокоде? --GosuGDR 14:33, 10 декабря 2011 (MSK)
Не вижу, где о нём хоть что-то написано. --Дмитрий Герасимов 21:18, 10 декабря 2011 (MSK)
А теперь норм? --GosuGDR 03:47, 12 декабря 2011 (MSK)
Написать псевдокод --GosuGDR 11:45, 10 декабря 2011 (MSK)
Замечания? --GosuGDR 14:33, 10 декабря 2011 (MSK)
Почему у тебя динамика — массив, а размеры матрица — вектор, надо придерживаться чего-то более-менее одного.
Потому что динамика на подотрезках…
Зачем пары? Пусть будет вектор каких-то матриц, у которых есть поля m и n — и пояснений не надо будет.
В классической формулировке задачи нам даются размеры матриц, а не их содержимое… Хранить размеры, на мой субъективный взгляд, удобно в парах…
Надо пояснить что -1 означает что значение динамики ещё не было посчитано. | Done --GosuGDR 07:03, 11 декабря 2011 (MSK)
Что за 1000 * 1000 * 1000 ? Пусть будет infinity, всем будет понятно. | Done --GosuGDR 07:03, 11 декабря 2011 (MSK)
  • Сделал все замечания, которые ты дал устно --GosuGDR 04:31, 12 декабря 2011 (MSK)
Раз m — двумерный массив, то и индексы у него должны быть как у двумерного массива.
После переписывания такой баги не замечено… --GosuGDR 14:33, 10 декабря 2011 (MSK)
везде используется малое n, а в асимптотике почему-то N.
После переписывания такой баги не замечено… --GosuGDR 14:33, 10 декабря 2011 (MSK)
Объединить разделы "Ссылки" и "литература", и нормально оформить --GosuGDR 11:45, 10 декабря 2011 (MSK)

--Дмитрий Герасимов 21:18, 10 декабря 2011 (MSK)