Курс лекций «Эффективные алгоритмы»/Лекции осеннего семестра 2011/2011-09-22

Ссылки сюда (1) →

Короткая ссылка: 2011-09-22

Темы

• Динамическое программирование для задачи о рюкзаке
• Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке

---

Проблемы

Участвующие в лекции парни куда-то разбежались.

Скайп-логи

[22.09.2011 16:05:51] *** Conference call ***
[22.09.2011 16:06:27] Фаворская Алена [student]: я тут
[22.09.2011 16:06:38] Игорь Литвинов [student]: добавившиеся, не забывайте микрофоны отключать
[22.09.2011 16:07:17] Игорь Литвинов [student]: да
[22.09.2011 16:07:19] Владимир Игнатьев [student]: Да
[22.09.2011 16:08:07] Фаворская Алена [student]: да
[22.09.2011 16:08:10] Владимир Игнатьев [student]: да
[22.09.2011 16:08:10] Фаворская Алена [student]: все отлично
[22.09.2011 16:08:12] Рубен... [students]: да
[22.09.2011 16:08:22] Фаворская Алена [student]: Саша?
[22.09.2011 16:08:34] Фаворская Алена [student]: а трубочка рядом с ней почему-то....
[22.09.2011 16:08:41] Владимир Игнатьев [student]: перезапустить скайп)) что делать)
[22.09.2011 16:11:37] ustas [student]: жадный алгоритм
[22.09.2011 16:12:00] Фаворская Алена [student]: может как систему уравнений?
[22.09.2011 16:12:20] Фаворская Алена [student]: а, да...
[22.09.2011 16:13:25] Владимир Игнатьев [student]: веса упорядочены?
[22.09.2011 16:13:38] Владимир Игнатьев [student]: тогда перебор
[22.09.2011 16:14:42] Фаворская Алена [student]: все комбинации...
[22.09.2011 16:14:44] Фаворская Алена [student]: и проверка
[22.09.2011 16:14:54] Фаворская Алена [student]: я люблю перебирать)
[22.09.2011 16:15:26] Фаворская Алена [student]: ну, да... с упорядочненными весами можно пеберитать более по умному
[22.09.2011 16:15:52] Фаворская Алена [student]: 2^n комбинаций
[22.09.2011 16:16:21] Фаворская Алена [student]: долго
[22.09.2011 16:17:51] Суворикова Александра [student]: питон это прекрасно )
[22.09.2011 16:18:27] Фаворская Алена [student]: да
[22.09.2011 16:19:19] Владимир Игнатьев [student]: У нас был Дин прог
[22.09.2011 16:23:07] Владимир Игнатьев [student]: есть же ответ))
[22.09.2011 16:23:16] Игорь Литвинов [student]: )
[22.09.2011 16:24:27] Игорь Литвинов [student]: псевдо
[22.09.2011 16:24:28] Фаворская Алена [student]: нет
[22.09.2011 16:24:38] Фаворская Алена [student]: на прошлом слайде было написано)
[22.09.2011 16:24:46] Игорь Литвинов [student]: rly?
[22.09.2011 16:24:46] Фаворская Алена [student]: вроде
[22.09.2011 16:24:56] Фаворская Алена [student]: а, ну ладно
[22.09.2011 16:25:51] Фаворская Алена [student]: размер а
[22.09.2011 16:25:52] Фаворская Алена [student]: ?
[22.09.2011 16:26:26] Фаворская Алена [student]: [22 сентября 2011 г. 16:19] Владимир Игнатьев [student]:

<<< У нас был Дин прогвот еще
[22.09.2011 16:26:35] Фаворская Алена [student]: еще человек
[22.09.2011 16:27:13] Фаворская Алена [student]: размер а и б?
[22.09.2011 16:27:42] Фаворская Алена [student]: N, B?
[22.09.2011 16:27:56] Фаворская Алена [student]: ну... сложить?
[22.09.2011 16:28:01] Фаворская Алена [student]: не знаю
[22.09.2011 16:28:02] Суворикова Александра [student]: N+1
[22.09.2011 16:28:27] Фаворская Алена [student]: указатель на массив... и чиселко
[22.09.2011 16:28:41] Фаворская Алена [student]: ну...)
[22.09.2011 16:29:10] Фаворская Алена [student]: (N+1)*size
[22.09.2011 16:29:18] Фаворская Алена [student]: размер числа
[22.09.2011 16:29:38] Фаворская Алена [student]: количество знаков
[22.09.2011 16:29:59] Фаворская Алена [student]: так тогда.. неограничено
[22.09.2011 16:30:05] Фаворская Алена [student]: зависит от того какие числа
[22.09.2011 16:30:31] Фаворская Алена [student]: так размер предметов-чисел не известен
[22.09.2011 16:30:35] Фаворская Алена [student]: или считается что меньш?
[22.09.2011 16:30:38] Фаворская Алена [student]: аа...
[22.09.2011 16:30:42] Фаворская Алена [student]: в битах надо?
[22.09.2011 16:30:49] Фаворская Алена [student]: ну тогда B*(N+1)
[22.09.2011 16:31:13] Фаворская Алена [student]: а массив и само B
[22.09.2011 16:32:13] Фаворская Алена [student]: размер B * (N+1)
[22.09.2011 16:32:17] Фаворская Алена [student]: вот
[22.09.2011 16:32:25] Фаворская Алена [student]: размер B, а не И
[22.09.2011 16:32:27] Фаворская Алена [student]: ой
[22.09.2011 16:32:29] Фаворская Алена [student]: а не Б
[22.09.2011 16:33:06] Фаворская Алена [student]: логарифм B?
[22.09.2011 16:33:22] Фаворская Алена [student]: lnB*(N+1)
[22.09.2011 16:33:51] Фаворская Алена [student]: ну это на констату - если не натуральный
[22.09.2011 16:34:07] Фаворская Алена [student]: ну да да
[22.09.2011 16:35:11] Фаворская Алена [student]: кто есть?
[22.09.2011 16:35:16] Суворикова Александра [student]: z
[22.09.2011 16:35:18] Суворикова Александра [student]: я
[22.09.2011 16:36:37] Фаворская Алена [student]: казалось бы.. нет принципиальной разницы. и наверное нет.
[22.09.2011 16:36:54] Суворикова Александра [student]: )))
[22.09.2011 16:36:56] Фаворская Алена [student]: даже так)
[22.09.2011 16:37:01] Фаворская Алена [student]: тогда придется поразмыслить
[22.09.2011 16:38:14] Фаворская Алена [student]: а почему N^2?
[22.09.2011 16:38:25] Фаворская Алена [student]: аа...
[22.09.2011 16:38:59 | Edited 16:39:07] Фаворская Алена [student]: тогда вместо lnB мы сможем ограничить ln(N^2)
[22.09.2011 16:39:30] Фаворская Алена [student]: размер входных данных теперь другой
[22.09.2011 16:39:45] Фаворская Алена [student]: ну он теперь N^2 ограничен
[22.09.2011 16:39:49] Фаворская Алена [student]: а не B
[22.09.2011 16:40:05] Фаворская Алена [student]: в квадрате
[22.09.2011 16:40:08] Фаворская Алена [student]: а нуда
[22.09.2011 16:40:40] Фаворская Алена [student]: наверное можно даже как-то специально "умный" перебор построить
[22.09.2011 16:40:45] Фаворская Алена [student]: с учетмо n^2
[22.09.2011 16:41:10] Фаворская Алена [student]: сложность его?
[22.09.2011 16:41:58] Фаворская Алена [student]: да.. для балланса
[22.09.2011 16:42:34] Фаворская Алена [student]: 2N^2?...
[22.09.2011 16:43:13] Суворикова Александра [student]: n^4
[22.09.2011 16:43:14] Фаворская Алена [student]: куб
[22.09.2011 16:43:44] Суворикова Александра [student]: а блин их n )
[22.09.2011 16:45:23] Фаворская Алена [student]: да
[22.09.2011 16:46:04] Суворикова Александра [student]: да
[22.09.2011 16:46:04] Фаворская Алена [student]: примерно
[22.09.2011 16:46:06] Суворикова Александра [student]: словарик!
[22.09.2011 16:47:22] Суворикова Александра [student]: solution?
[22.09.2011 16:47:38] Фаворская Алена [student]: добавляем если не такой, меньше, или больше цена..
[22.09.2011 16:48:15] Фаворская Алена [student]: скобки стоят.
[22.09.2011 16:48:27] Фаворская Алена [student]: да, поэтому это сравнение сначала
[22.09.2011 16:48:59] Фаворская Алена [student]: с большим весом его замещает
[22.09.2011 16:49:00] Суворикова Александра [student]: почему тогда не сделать ключами веса?
[22.09.2011 16:49:12] Суворикова Александра [student]: ога
[22.09.2011 16:49:13] Суворикова Александра [student]: ок
[22.09.2011 16:50:40] Фаворская Алена [student]: а как же цена?
[22.09.2011 16:51:30] Фаворская Алена [student]: к набору еще один предмет добавили7
[22.09.2011 16:51:33] Суворикова Александра [student]: ага
[22.09.2011 16:52:27] Фаворская Алена [student]: цикл зациклиться может?
[22.09.2011 16:53:02] Суворикова Александра [student]: не модифицурой массив, пока просматриваешь его
[22.09.2011 16:53:04] Суворикова Александра [student]: как-то так
[22.09.2011 16:53:36] Фаворская Алена [student]: можно было бы наверное как-то иначе организовать цилк
[22.09.2011 16:53:44] Фаворская Алена [student]: но наверное предложенное решение оптимально
[22.09.2011 16:56:39] Фаворская Алена [student]: сам
[22.09.2011 16:57:37] Суворикова Александра [student]: lf
[22.09.2011 16:57:38] Фаворская Алена [student]: да
[22.09.2011 16:57:43] Суворикова Александра [student]: да
[22.09.2011 16:57:48] Фаворская Алена [student]: это да с другой расскадкой
[22.09.2011 16:57:58] Фаворская Алена [student]: )
[22.09.2011 16:59:59] Суворикова Александра [student]: чтобы все наборы были с разными весами?
[22.09.2011 17:01:39] Фаворская Алена [student]: но оптимизируем то по цене
[22.09.2011 17:03:44] Фаворская Алена [student]: да вроде понятно
[22.09.2011 17:03:49] Суворикова Александра [student]: все понятно
[22.09.2011 17:06:00] Фаворская Алена [student]: а чем же может быть ограничена цена....
[22.09.2011 17:07:01] Фаворская Алена [student]: f**N
[22.09.2011 17:08:20] Суворикова Александра [student]: обожемой
[22.09.2011 17:10:21] Суворикова Александра [student]: pareto
[22.09.2011 17:10:42] Фаворская Алена [student]: почему?
[22.09.2011 17:10:50] Суворикова Александра [student]: упорядочить можно?
[22.09.2011 17:11:17] Суворикова Александра [student]: тоесть у вас отсротированный список7
[22.09.2011 17:11:27] Фаворская Алена [student]: наверное функция отбора сортирует
[22.09.2011 17:11:42] Суворикова Александра [student]: да там можно просто sort cсделать
[22.09.2011 17:12:20] Суворикова Александра [student]: )))
[22.09.2011 17:15:30] Суворикова Александра [student]: дааа
[22.09.2011 17:15:31] Фаворская Алена [student]: да
[22.09.2011 17:26:51] Фаворская Алена [student]: а зачем 1?
[22.09.2011 17:26:55] Суворикова Александра [student]: просто 2
[22.09.2011 17:26:56] Суворикова Александра [student]: *1
[22.09.2011 17:26:57] Суворикова Александра [student]: ))))
[22.09.2011 17:27:18] Фаворская Алена [student]: неет... зачем 1 округлять? что это даст?
[22.09.2011 17:27:57] Суворикова Александра [student]: 1 -если элемент входит в набор, а если 0 - то не входит
[22.09.2011 17:28:36] Фаворская Алена [student]: да, я поняла
[22.09.2011 17:29:12] Фаворская Алена [student]: ну да... больше чем 0.9 не потеряме
[22.09.2011 17:29:21] Суворикова Александра [student]: ну это понятно, что там ограничение скейл
[22.09.2011 17:29:53] Суворикова Александра [student]: даа
[22.09.2011 17:30:47] Фаворская Алена [student]: ну выберем скейл как функцию епсилон
[22.09.2011 17:31:45] Фаворская Алена [student]: а как же быть... от f* зависит....
[22.09.2011 17:31:51] Фаворская Алена [student]: там вроде машина едет)
[22.09.2011 17:31:59] Фаворская Алена [student]: у ва
[22.09.2011 17:32:00] Фаворская Алена [student]: с
[22.09.2011 17:32:02] Фаворская Алена [student]: раньше
[22.09.2011 17:32:38] Фаворская Алена [student]: оценить как то
[22.09.2011 17:32:41] Фаворская Алена [student]: с запасом
[22.09.2011 17:32:54] Фаворская Алена [student]: n*max
[22.09.2011 17:33:01] Фаворская Алена [student]: эти нет)
[22.09.2011 17:33:11] Фаворская Алена [student]: а, нижняя...
[22.09.2011 17:33:25] Фаворская Алена [student]: да,...
[22.09.2011 17:33:53] Фаворская Алена [student]: ну на минимум
[22.09.2011 17:33:59] Фаворская Алена [student]: n*min
[22.09.2011 17:34:12] Фаворская Алена [student]: .... не n
[22.09.2011 17:34:22] Фаворская Алена [student]: да
[22.09.2011 17:34:27] Фаворская Алена [student]: просто минимум
[22.09.2011 17:34:33] Фаворская Алена [student]: и минимум по весу
[22.09.2011 17:34:43] Фаворская Алена [student]: ну...
[22.09.2011 17:35:18] Суворикова Александра [student]: я промолчу )
[22.09.2011 17:35:35] Суворикова Александра [student]: Макс сказал, что он не писал
[22.09.2011 17:35:39] Суворикова Александра [student]: это косяк скайпа
[22.09.2011 17:35:40] Фаворская Алена [student]: мне тоже не было видно
[22.09.2011 17:35:45] Фаворская Алена [student]: что он писал
[22.09.2011 17:35:55] Суворикова Александра [student]: у них там на работ дедлайн
[22.09.2011 17:35:56] Суворикова Александра [student]: какой-то
[22.09.2011 17:35:57] Фаворская Алена [student]: время неудобное7?....
[22.09.2011 17:36:26] Фаворская Алена [student]: кроме минимума минимума... ничего пока не придумывается
[22.09.2011 17:36:34] Фаворская Алена [student]: ну минимум по весу и по цене
[22.09.2011 17:36:43] Суворикова Александра [student]: ну надо взять
[22.09.2011 17:36:45] Суворикова Александра [student]: самый дорогой
[22.09.2011 17:36:47] Фаворская Алена [student]: а..
[22.09.2011 17:36:57] Фаворская Алена [student]: да, согласан
[22.09.2011 17:40:11] Суворикова Александра [student]: понятно
[22.09.2011 17:40:13] Фаворская Алена [student]: понятно
[22.09.2011 17:40:51] Фаворская Алена [student]: осортировать?
[22.09.2011 17:41:05] Суворикова Александра [student]: зато из предыдущей лекции :)
[22.09.2011 17:41:07] Фаворская Алена [student]: по некой функции от веса и цены
[22.09.2011 17:41:13] Фаворская Алена [student]: отсортировать по ней
[22.09.2011 17:41:26] Фаворская Алена [student]: жадный был
[22.09.2011 17:41:41] Фаворская Алена [student]: 2?
[22.09.2011 17:42:50] Фаворская Алена [student]: для оценки?
[22.09.2011 17:43:58] Фаворская Алена [student]: ясно
[22.09.2011 17:44:26] Суворикова Александра [student]: дада
[22.09.2011 17:46:14] Maxim Panov [student]: дедлайн не при чем
[22.09.2011 17:46:21] Maxim Panov [student]: мне в принципе неудбно с работы
[22.09.2011 17:46:38] Maxim Panov [student]: я и так на работе всего 3 дня в неделю и не готов тратить это время на лекцию
[22.09.2011 17:47:16] Суворикова Александра [student]: эпсилон одинаковые
[22.09.2011 17:48:24] Фаворская Алена [student]: ну...
[22.09.2011 17:48:28] Фаворская Алена [student]: а что поделать..
[22.09.2011 17:49:30] Maxim Panov [student]: что поделать - делать электронную пару или в пятницу, или в выходные, или вечером после 19.00
[22.09.2011 17:49:55] Фаворская Алена [student]: что-то сегодня была большая небольшая лекция
[22.09.2011 17:50:02] Суворикова Александра [student]: отличная лекция )
[22.09.2011 17:50:05] Фаворская Алена [student]: да, отличная
[22.09.2011 17:50:38] Фаворская Алена [student]: ну... мало человек
[22.09.2011 17:50:44] Maxim Panov [student]: я вам сейча обзавидуюсь ))
[22.09.2011 17:50:58] Maxim Panov [student]: кстати на нормальную пару наверно даже больше бы ходило
[22.09.2011 17:51:05] Serega (sympa) [student]: я слушал с удовольствием. не было возможности общаться в этот раз
[22.09.2011 17:51:13] Фаворская Алена [student]: потому что стационарное время и стационарный день.
[22.09.2011 17:51:13] Serega (sympa) [student]: звук классный, все ясно, спасибо)
[22.09.2011 17:53:21] Суворикова Александра [student]: спасибо :) досвидания
[22.09.2011 17:53:29] Фаворская Алена [student]: до свиданья, спасибо

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.