Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Динамическое программирование  (Прочитано 14640 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Olegator
Команда клуба

ru
Offline Offline
Пол: Мужской

« : 30-10-2005 03:17 » 

1. Читаю статью http://club.shelek.ru/viewart.php?id=131 и не понимаю почему она в разделе для начинающих? Вроде такая не простая. Её бы в "Направления и технологии". Или даже к статьям Alf-а про рекурсию. Как раз выйдет как пример применения рекурсии.

2. И в одном месте я сомневаюсь на счёт правильности написания.
Цитата
дана последовательность из n матриц (А1, А2, …, Аn) заданных размеров (матрица i имеет размеры pi-1 x pi)
Почему pi-1 x pi. Что это за p. Может имеется ввиду i-1 x i? Т.е. каждая текущая матрица больше предыдущей на 1 строку и на 1 столбец.

3. И может индексы выделять квадратными скобками. А то я в некоторых местах не сразу понял, что имеется ввиду.
Например:
Цитата
Обозначим через Аi..j матрицу, являющуюся произведением матриц АiAi+1…Aj
Переделать так.
Цитата
Обозначим через A[i+1]…A[j]
« Последнее редактирование: 30-10-2005 16:55 от Olegator » Записан
Olegator
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #1 : 30-10-2005 15:58 » 

Или p это коэффициент который задаёт начальную матрицу. И тогда надо писать p*(i-1) x p*i.
Записан
Olegator
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #2 : 31-10-2005 01:52 » 

Это что плохая статья? Никто не читал чтоли?
Записан
Alf
Гость
« Ответ #3 : 31-10-2005 07:55 » 

2. И в одном месте я сомневаюсь на счёт правильности написания.
Цитата
дана последовательность из n матриц (А1, А2, …, Аn) заданных размеров (матрица i имеет размеры pi-1 x pi)
Почему pi-1 x pi. Что это за p. Может имеется ввиду i-1 x i? Т.е. каждая текущая матрица больше предыдущей на 1 строку и на 1 столбец.

Сумбурность изложения материала, помноженная на неряшливость оформления, и является причиной твоих затруднений. Я считаю, что приведенный тобой пример должен выглядеть так:

Цитата
дана последовательность из n матриц (А1, А2, …, Аn) заданных размеров (матрица с номером i имеет размеры pi-1 * pi)

Так больше похоже на правду?
Записан
VaN
Интересующийся

ua
Offline Offline

« Ответ #4 : 31-10-2005 12:17 » 

гхм... сумбурность изложения - это может быть, не спорю. Но неряшливое оформление не ко мне - я делал в .chm, а то, что в хтмл, как я понял - лишь для препросмотра... В .chm индексы проставлены нормально вроде...
Записан
Olegator
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #5 : 31-10-2005 22:10 » 

Условие перемножения матриц: Чтобы перемножить две матрицы надо, чтобы количество строк первой матрицы совпадали с количеством столбцов второй матрицы. Или наоборот.
Конечно то что
Цитата
дана последовательность из n матриц (А1, А2, …, Аn) заданных размеров (матрица с номером i имеет размеры pi-1 * pi)
Так больше похоже на правду?
исходит из дальнейшего оформления.
Но всё-таки моё предположение больше подходит под «Условие перемножения матриц».
Хотя может я ошибаюсь. А запись
Цитата
pi-1 * pi)
по моему не имеет смысла.
Записан
Olegator
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #6 : 31-10-2005 22:43 » 

Хотя матрицы могут быть такими:
3x4 * 4x12 *12x5
И тогда я не прав.
Записан
Olegator
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #7 : 31-10-2005 22:52 » 

А всё я понял. Действительно так и должно выглядеть.
pi-1 * pi
Тогда как раз соблюдается условие перемножения матриц.
« Последнее редактирование: 31-10-2005 22:54 от Olegator » Записан
Alf
Гость
« Ответ #8 : 31-10-2005 23:09 » 

Молодец. А я только собрался было расписывать произведение матриц.

В данном случае pi - это количество столбцов матрицы с номером i, а pi-1 - количество столбцов матрицы с номером i-1, которое равно числу строк матрицы с номером i (иначе произведение не имеет смысла).

Вопрос, откуда брать значение pi-1 при i=1 (при том, что матрицы пронумерованы с 1), лучше задай автору, раз уж он сюда заглядывает.
Записан
VaN
Интересующийся

ua
Offline Offline

« Ответ #9 : 01-11-2005 10:27 » 

Ну если формализировать данную фразу до конца, то нужно сказать, что при i=1 задача не требует никаких действий. При i>1 (i натуральное) p[i-1] * p

ЗЫ. Автор писал это давно и сам сознает несовершенство изложения  Здесь была моя ладья...
Записан
VaN
Интересующийся

ua
Offline Offline

« Ответ #10 : 04-11-2005 16:20 » 

только что пришло в голову, что я неверно истолковал вопрос...  Молчу
Матрицы-то пронумерованы с нуля, но вот массив их размерностей - с единицы. Все равно размеров будет на единицу больше, чем матриц. Так какая разница - (n+1)-й размер вводить или 0-й?
Записан
Olegator
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #11 : 12-12-2005 23:18 » 

Нашёл какие-то лекции по динамическому программированию. Там где была эта ссылка, было написано, что очень хорошие лекции.
Отсюда _http://algolist.manual.ru/forum/showflat.php/Cat/0/Number/6099/an/0/page/0 Правда незнаю можно ли такие ссылки давать? Получается реклама другого форума.

Только расширение какое-то непонятное. *.ps. Не знаю чем открыть.
Вот прямая ссылка _http://neerc.ifmo.ru/~pavlov/dpl.ps
« Последнее редактирование: 12-12-2005 23:21 от Olegator » Записан
Alf
Гость
« Ответ #12 : 12-12-2005 23:44 » 

Это файл в формате PostScript. Я открыл его Adobe Acrobat, там внутри лекции по информатике.

Само содержимое не особенно понравилось - галопом по европам. На все алгебраические структуры отведено менее страницы. Группы - 3 строчки, абелевы группы - 3 строчки, поля - 3 строчки... Тем, кто это и так знает, это не нужно, а тому, кто не знает, бесполезно совершенно - не разберешься. Можно только выучить, как попугаю, не понимая.
Записан
Olegator
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #13 : 12-12-2005 23:49 » 

Группы, абелевы группы, поля
Это теория групп. Ты всё это знаешь? Зачем она нужна эта теория групп? Всё хотел изучить.

И на счёт динамического программирования. Зачем оно нужно? Для оптимизации? Ты вроде тогда ещё говорил, что это всё не нужно.
Записан
VaN
Интересующийся

ua
Offline Offline

« Ответ #14 : 28-12-2005 15:47 » 

По высшей алгебре вообще и теории групп в частности, неплохие, имхо, материалы лежат по этим ссылкам:
http://www.mccme.ru/ium/ancient/algf92.html
http://www.mccme.ru/ium/ancient/alg1s93.html

Тоже достаточно коротко, но понять общий смысл можно. Для более детального изучения, конечно, нужна специальная литература. По теории групп это, к примеру, М. Холл "Теория групп", Курош "Высшая алгебра". С ходу больше не вспомню, но при если нужно - могу посмотреть.
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines