Курс лекций «Эффективные алгоритмы»/Лекции осеннего семестра 2011/2011-09-22
Материал из DISCOPAL
< Курс лекций «Эффективные алгоритмы» | Лекции осеннего семестра 2011(перенаправлено с «2011-09-22»)
Короткая ссылка: 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]: до свиданья, спасибо
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.