Обсуждение:Задача о порядке перемножения матриц — различия между версиями
GosuGDR (обсуждение | вклад) м |
|||
| (не показано 12 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
| + | : {{tick | ticked=1}} Стоит переименовать статью из «Задачи о перемножении матриц» в «Задачу о порядке перемножения матриц» --[[Участник:GosuGDR|GosuGDR]] 09:38, 12 декабря 2011 (MSK) | ||
: {{tick | ticked=1}} «На самом деле задача заключается не в нахождении результата перемножения, а в нахождении нужного порядка этого перемножения.» — ну это очевидно, здесь надо написать что произведение матриц ассоциативно и то что в «Постановке задачи» переместить в шапку даюы пояснить, в чем собственно состоит задача. | : {{tick | ticked=1}} «На самом деле задача заключается не в нахождении результата перемножения, а в нахождении нужного порядка этого перемножения.» — ну это очевидно, здесь надо написать что произведение матриц ассоциативно и то что в «Постановке задачи» переместить в шапку даюы пояснить, в чем собственно состоит задача. | ||
| − | : {{tick}} Рассчитать асимптотику брутфорса. Сделать разделы «Решение перебором» и «Решение динамическим программированием» | + | : {{tick | ticked=1}} Рассчитать асимптотику брутфорса. Сделать разделы «Решение перебором» и «Решение динамическим программированием» |
:: Не done, я всё ещё не вижу какой-то оценки, кроме слов «экспоненциально» | :: Не done, я всё ещё не вижу какой-то оценки, кроме слов «экспоненциально» | ||
::: Check it again, pls --[[Участник:GosuGDR|GosuGDR]] 04:27, 12 декабря 2011 (MSK) | ::: Check it again, pls --[[Участник:GosuGDR|GosuGDR]] 04:27, 12 декабря 2011 (MSK) | ||
| + | :::: Есть точная оценка на количество правильных скобочных последовательностей — так и добавь её сюда. И ты начал считать асимптотику в шапке — делай это в разделе про перебор. | ||
| + | ::::: Ок, уже почти. А теперь раскрой число Каталана — не все помнят, чему они равны. И в одном месте таки осталось 2^n. А ещё C_n — время только на перебор последовательностей, а тебе на каждом шаге ещё надо посчитать произведение n чисел, плэтому n * C_n.--[[Участник:Dgerasimov|Дмитрий Герасимов]] 08:47, 12 декабря 2011 (MSK) | ||
| + | :::::: Раскрыл, лол --[[Участник:GosuGDR|GosuGDR]] 09:28, 12 декабря 2011 (MSK) | ||
| + | ::::::: Мда, можно было бы и написать точную формулу для него чтобы не лезть в википедию хотя бы в одном месте. А ещё в одном месте у тебя просто C_n а не n * C_n. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 20:17, 12 декабря 2011 (MSK) | ||
| + | :::::::: Зачем в этой статье рассматривать материал, который косвенно относиться к теме?? --[[Участник:GosuGDR|GosuGDR]] 01:17, 13 декабря 2011 (MSK) | ||
: {{tick | ticked=1}} Не надо писать про решение без мемоизации, итак очевидно что её надо делать в динамике. Сразу пиши что будем запоминать. | : {{tick | ticked=1}} Не надо писать про решение без мемоизации, итак очевидно что её надо делать в динамике. Сразу пиши что будем запоминать. | ||
| − | : {{tick}} Используй тег tex. И надо писать O(n) в техе полностью, а не только n. | + | : {{tick | ticked=1}} Используй тег tex. И надо писать O(n) в техе полностью, а не только n. |
:: Заюзал, как в статье вики, на которую лежит ссылка в «псевдосправке» --[[Участник:GosuGDR|GosuGDR]] 04:27, 12 декабря 2011 (MSK) | :: Заюзал, как в статье вики, на которую лежит ссылка в «псевдосправке» --[[Участник:GosuGDR|GosuGDR]] 04:27, 12 декабря 2011 (MSK) | ||
| − | : {{tick}} «поскольку существует всего n^2/2 матриц» — каких матриц? Здесь надо сказать «подотрезков», видимо. | + | ::: В статье примеры использования TeX в общем. У нас же надо использовать '''тег''' tex, а не math. |
| + | : {{tick | ticked=1}} «поскольку существует всего 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) | ||
:: Почему у тебя динамика — массив, а размеры матрица — вектор, надо придерживаться чего-то более-менее одного. | :: Почему у тебя динамика — массив, а размеры матрица — вектор, надо придерживаться чего-то более-менее одного. | ||
| Строка 29: | Строка 37: | ||
: {{tick| ticked=1}} Объединить разделы "Ссылки" и "литература", и нормально оформить --[[Участник:GosuGDR|GosuGDR]] 11:45, 10 декабря 2011 (MSK) | : {{tick| ticked=1}} Объединить разделы "Ссылки" и "литература", и нормально оформить --[[Участник:GosuGDR|GosuGDR]] 11:45, 10 декабря 2011 (MSK) | ||
--[[Участник:Dgerasimov|Дмитрий Герасимов]] 21:18, 10 декабря 2011 (MSK) | --[[Участник:Dgerasimov|Дмитрий Герасимов]] 21:18, 10 декабря 2011 (MSK) | ||
| + | |||
| + | ---- | ||
| + | |||
| + | "Какая мощная дискуссия в обсуждении ;) Почему в других конспектах такой нет? | ||
| + | {{tick}} Не понял принцип перечисления вариантов ""(ABC)D = (AB)(CD) = A(BCD) = A(BC)D = ."" | ||
| + | : Check it, please | ||
| + | :: Я тоже непонял, как ты расставляешь скобки. Напиши просто что умножение матриц ассоциативно, а это выкинь нафиг. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 09:18, 29 февраля 2012 (GST) | ||
| + | {{tick}} Опять дискуссии с читателем ""Сначала, давайте определимся, что мы хотим узнать минимальное количество операций (или минимальную стоимость), необходимых для перемножения матриц."" Я мысленно поставил точку после слова ""узнать"" и получилось забавно. | ||
| + | : Check it, please | ||
| + | :: Выкинь все «давайте», «мы хотим», риторические вопросы и прочее. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 09:18, 29 февраля 2012 (GST) | ||
| + | {{tick | ticked=1}} Зафига здесь вообще про перебор всех вариантов, да еще и с ужасными оценками? | ||
| + | : Check it, please | ||
| + | |||
| + | Вообще, акцент сделан не на том. На чем надо делать акцент в статьях про ДП? | ||
| + | Надо сформулировать подзадачи, доказать оптимальность для подзадач, указать рекуррентный переход и начальные условия. А детали реализации не так и важны с точки зрения конспекта по отдельным задачам. Там где дело в них, там надо, конечно, про них написать. Но эта статья написана не про то, про что хотелось бы. | ||
| + | |||
| + | Итого: про перебор выкинуть. Сформулировать подзадачи, принцип оптимальности (для подотрезков), написать рекуррентность и начальные условия. | ||
| + | Мемоизацию выделить в отдельную статью и там уже подробно написать про то, что это такое и как это применять для решения задач с помощью ДП" | ||
Текущая версия на 08:18, 29 февраля 2012
- ☑ Стоит переименовать статью из «Задачи о перемножении матриц» в «Задачу о порядке перемножения матриц» --GosuGDR 09:38, 12 декабря 2011 (MSK)
- ☑ «На самом деле задача заключается не в нахождении результата перемножения, а в нахождении нужного порядка этого перемножения.» — ну это очевидно, здесь надо написать что произведение матриц ассоциативно и то что в «Постановке задачи» переместить в шапку даюы пояснить, в чем собственно состоит задача.
- ☑ Рассчитать асимптотику брутфорса. Сделать разделы «Решение перебором» и «Решение динамическим программированием»
- Не done, я всё ещё не вижу какой-то оценки, кроме слов «экспоненциально»
- Check it again, pls --GosuGDR 04:27, 12 декабря 2011 (MSK)
- Есть точная оценка на количество правильных скобочных последовательностей — так и добавь её сюда. И ты начал считать асимптотику в шапке — делай это в разделе про перебор.
- Ок, уже почти. А теперь раскрой число Каталана — не все помнят, чему они равны. И в одном месте таки осталось 2^n. А ещё C_n — время только на перебор последовательностей, а тебе на каждом шаге ещё надо посчитать произведение n чисел, плэтому n * C_n.--Дмитрий Герасимов 08:47, 12 декабря 2011 (MSK)
- Раскрыл, лол --GosuGDR 09:28, 12 декабря 2011 (MSK)
- Мда, можно было бы и написать точную формулу для него чтобы не лезть в википедию хотя бы в одном месте. А ещё в одном месте у тебя просто C_n а не n * C_n. --Дмитрий Герасимов 20:17, 12 декабря 2011 (MSK)
- Зачем в этой статье рассматривать материал, который косвенно относиться к теме?? --GosuGDR 01:17, 13 декабря 2011 (MSK)
- Мда, можно было бы и написать точную формулу для него чтобы не лезть в википедию хотя бы в одном месте. А ещё в одном месте у тебя просто C_n а не n * C_n. --Дмитрий Герасимов 20:17, 12 декабря 2011 (MSK)
- Раскрыл, лол --GosuGDR 09:28, 12 декабря 2011 (MSK)
- Ок, уже почти. А теперь раскрой число Каталана — не все помнят, чему они равны. И в одном месте таки осталось 2^n. А ещё C_n — время только на перебор последовательностей, а тебе на каждом шаге ещё надо посчитать произведение n чисел, плэтому n * C_n.--Дмитрий Герасимов 08:47, 12 декабря 2011 (MSK)
- Есть точная оценка на количество правильных скобочных последовательностей — так и добавь её сюда. И ты начал считать асимптотику в шапке — делай это в разделе про перебор.
- Check it again, pls --GosuGDR 04:27, 12 декабря 2011 (MSK)
- Не done, я всё ещё не вижу какой-то оценки, кроме слов «экспоненциально»
- ☑ Не надо писать про решение без мемоизации, итак очевидно что её надо делать в динамике. Сразу пиши что будем запоминать.
- ☑ Используй тег tex. И надо писать O(n) в техе полностью, а не только n.
- Заюзал, как в статье вики, на которую лежит ссылка в «псевдосправке» --GosuGDR 04:27, 12 декабря 2011 (MSK)
- В статье примеры использования TeX в общем. У нас же надо использовать тег tex, а не math.
- Заюзал, как в статье вики, на которую лежит ссылка в «псевдосправке» --GosuGDR 04:27, 12 декабря 2011 (MSK)
- ☑ «поскольку существует всего n^2/2 матриц» — каких матриц? Здесь надо сказать «подотрезков», видимо.
- Done --GosuGDR 07:08, 11 декабря 2011 (MSK)
- «около n^2/2 подотрезков — как-то не очень, их можно рассчитать точно, либо просто писать O(n^2) подотрезков.
- Поправил. проверь ещё раз. --GosuGDR 04:27, 12 декабря 2011 (MSK)
- Плохо говорить около O(что-то там), так как это оценка асимптотическая. Убери «около»
- Поправил. проверь ещё раз. --GosuGDR 04:27, 12 декабря 2011 (MSK)
- ☑ Написать про восстановление ответа
- Написано о способе восстановления. Написать в псевдокоде? --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)
"Какая мощная дискуссия в обсуждении ;) Почему в других конспектах такой нет? ☐ Не понял принцип перечисления вариантов ""(ABC)D = (AB)(CD) = A(BCD) = A(BC)D = .""
- Check it, please
- Я тоже непонял, как ты расставляешь скобки. Напиши просто что умножение матриц ассоциативно, а это выкинь нафиг. --Дмитрий Герасимов 09:18, 29 февраля 2012 (GST)
☐ Опять дискуссии с читателем ""Сначала, давайте определимся, что мы хотим узнать минимальное количество операций (или минимальную стоимость), необходимых для перемножения матриц."" Я мысленно поставил точку после слова ""узнать"" и получилось забавно.
- Check it, please
- Выкинь все «давайте», «мы хотим», риторические вопросы и прочее. --Дмитрий Герасимов 09:18, 29 февраля 2012 (GST)
☑ Зафига здесь вообще про перебор всех вариантов, да еще и с ужасными оценками?
- Check it, please
Вообще, акцент сделан не на том. На чем надо делать акцент в статьях про ДП? Надо сформулировать подзадачи, доказать оптимальность для подзадач, указать рекуррентный переход и начальные условия. А детали реализации не так и важны с точки зрения конспекта по отдельным задачам. Там где дело в них, там надо, конечно, про них написать. Но эта статья написана не про то, про что хотелось бы.
Итого: про перебор выкинуть. Сформулировать подзадачи, принцип оптимальности (для подотрезков), написать рекуррентность и начальные условия. Мемоизацию выделить в отдельную статью и там уже подробно написать про то, что это такое и как это применять для решения задач с помощью ДП"
