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

== Темы ==
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]

== Видео ==

{{vimeoembed|29878996|720|404}}

== Проблемы ==
Не успел нарисовать поясняющую геометрию вероятностей картинку, плюс в алгоритме на слайдах была ошибка — спешите исправить и сделать правильный алгоритм.

== Интересное ==
Удалось придумать, как пришить и логи скайп-переговоров к лекции.
Но предыдущие лекции не «проиграли» — я пришью скайп-переговоры и к ним, после чего их можно будет удалить со страничек (если кого-то это беспокоит).

== Скайп-логи ==

<pre>
[13:35:55] Фаворская Алена [student]: видим да
[13:35:57] Фаворская Алена [student]: все в порядке
[13:36:03] ustas [student]: сейчас лучше
[13:39:23] ustas [student]: ага
[13:39:23] Фаворская Алена [student]: да
[13:39:27] Максим Р [student]: да
[13:39:29] Суворикова Александра [student]: да, а если стоимость не больше но вес меньше?
[13:39:41] ustas [student]: то это не паретто оптимум
[13:39:50] Суворикова Александра [student]: а чем плох такой варинт-то?
[13:39:54] Фаворская Алена [student]: стоимость такая же а вес меньше?
[13:39:59] ustas [student]: а зачем он нам?
[13:40:09] Суворикова Александра [student]: он будет меньше весить но стоить столько же...
[13:40:31] Суворикова Александра [student]: Саша, а не Алёна
[13:40:32] Фаворская Алена [student]: ну на него надо заменить потому что можно будет потом добавить
[13:40:33] Суворикова Александра [student]: но это не важно )
[13:40:58] Владимир Игнатьев [student]: ок
[13:41:00] Фаворская Алена [student]: да
[13:41:02] ustas [student]: да
[13:41:05] Юрий Горшенин [student]: y
[13:43:30] Фаворская Алена [student]: он и есть решение
[13:43:33] Суворикова Александра [student]: потому что отсортированно
[13:43:33] Фаворская Алена [student]: потому чт ост дешевле
[13:43:40] ustas [student]: последний нам и нужен после сортировки
[13:45:22] Максим Р [student]: откуда 9/7?
[13:45:37] Фаворская Алена [student]: она не учитывает когда цена та же
[13:45:41] Фаворская Алена [student]: забывает этот случай
[13:46:13] Фаворская Алена [student]: а кстати... если есть 2 итоговых набора
[13:46:15] Фаворская Алена [student]: с одной ценой
[13:46:21] Фаворская Алена [student]: но разным весом, но оба допустимых
[13:46:25] Фаворская Алена [student]: оба равноценные решения?
[13:46:25] Суворикова Александра [student]: вот, это то о чем я говорила же
[13:46:38] Фаворская Алена [student]: про сортировку ясно как с ними обойтись
[13:46:49] Фаворская Алена [student]: а вот будут ли оба одинаковыми равноценными решениями...
[13:46:53] Суворикова Александра [student]: но алгоритм выберет более тяжелый видимо
[13:46:59] Фаворская Алена [student]: парето - нет
[13:47:01] Фаворская Алена [student]: остальные не факт
[13:47:46] Юрий Горшенин [student]: слияние видимо за O(|paretoSet|) а не за n?
[13:47:53] Фаворская Алена [student]: а у меня был вопрос!
[13:47:59] Фаворская Алена [student]: [13:46] Фаворская Алена [student]:

<<< а кстати... если есть 2 итоговых набора
с одной ценой
но разным весом, но оба допустимых
оба равноценные решения?
[13:48:54] Суворикова Александра [student]: блин
[13:49:00] Фаворская Алена [student]: ясно
[13:49:00] Суворикова Александра [student]: а почему я как В/Алёна у вас отображаюст?
[13:49:06] Суворикова Александра [student]: я Саша :(
[13:49:11] Фаворская Алена [student]: т.е. если программа найдет более тяжелое - все равно верно
[13:49:16] Суворикова Александра [student]: а ок
[13:49:21] Суворикова Александра [student]: я не вижу Алёну :(
[13:49:23] Суворикова Александра [student]: извините
[13:49:39] Фаворская Алена [student]: а ты у меня отображаешься по твоему логину, а не по имени
[13:49:43] Фаворская Алена [student]: хотя все прошлые разы было имя
[13:50:01] Суворикова Александра [student]: аааа :)
[13:50:04] Суворикова Александра [student]: привет!
[13:50:22] Фаворская Алена [student]: можно будет контактами поменяться... тогда нверное этот глюк исчезнет
[13:54:29] Фаворская Алена [student]: парето?
[13:55:11] Суворикова Александра [student]: :D
[13:55:12] Максим Р [student]: 3?
[13:55:13] Юрий Горшенин [student]: here
[13:55:15] ustas [student]: 3
[13:55:17] Юрий Горшенин [student]: 3
[13:55:18] Владимир Игнатьев [student]: 3
[13:55:32] Фаворская Алена [student]: думаю
[13:55:35] Фаворская Алена [student]: не 3
[13:55:37] Фаворская Алена [student]: )
[13:55:39] Максим Р [student]: XD
[13:55:48] Фаворская Алена [student]: 1 для каждого веса ведь
[13:55:58] Фаворская Алена [student]: ну по добавлению предмета
[13:56:01] Фаворская Алена [student]: не знаю как объяснить
[13:56:08] Фаворская Алена [student]: так вес не дан!
[13:56:26] Фаворская Алена [student]: мы же не знаем когда один заменит другой!
[13:56:37] Владимир Игнатьев [student]: желтые и белые
[13:57:09] ustas [student]: вообще наборов 6
[13:57:13] Максим Р [student]: 1
[13:57:16] Юрий Горшенин [student]: А пустой?
[13:57:20] Фаворская Алена [student]: 7
[13:57:25] Фаворская Алена [student]: он нарисован
[13:57:27] Фаворская Алена [student]: )
[13:57:30] Юрий Горшенин [student]: ))
[13:57:31] ustas [student]: )
[13:57:32] Фаворская Алена [student]: но у него нет площади
[13:57:36] Фаворская Алена [student]: поэтому он не раскрашен
[13:57:44] Фаворская Алена [student]: 4 значит
[13:57:45] Суворикова Александра [student]: 4
[13:58:52] Максим Р [student]: так u и k - это индексы подмножеств, а не веса ведь?
[14:02:11] Максим Р [student]: да
[14:02:12] Юрий Горшенин [student]: да
[14:02:14] Владимир Игнатьев [student]: да
[14:02:15] Фаворская Алена [student]: да
[14:03:07] Юрий Горшенин [student]: От нуля до еденицы а предметов n
[14:03:07] Максим Р [student]: величины от 0 до 1
[14:04:07] Фаворская Алена [student]: потому что они должны друг от  друга отличаться
[14:04:11] Фаворская Алена [student]: на эту дельту
[14:05:02] Максим Р [student]: когда вес пропорционален стоимости?
[14:05:05] Фаворская Алена [student]: да
[14:05:08] Фаворская Алена [student]: нет?
[14:05:14] Максим Р [student]: нет - это плохой пример
[14:05:16] Фаворская Алена [student]: когда вес пропорционален стоимости нам плохо
[14:05:19] Фаворская Алена [student]: да?
[14:05:40] Фаворская Алена [student]: ну тогда и будут все парето
[14:09:25] Фаворская Алена [student]: не больше 19)
[14:09:28] Фаворская Алена [student]: слайдов
[14:09:31] Суворикова Александра [student]: ну да
[14:09:31] Фаворская Алена [student]: ну 1 то видна
[14:09:32] ustas [student]: да
[14:09:41] ustas [student]: а может под 100
[14:09:42] Фаворская Алена [student]: а почему1...
[14:09:45] Суворикова Александра [student]: или может быть порядка 100
[14:10:07] Максим Р [student]: дзита
[14:12:07] Максим Р [student]: да
[14:12:07] Владимир Игнатьев [student]: да
[14:12:08] Юрий Горшенин [student]: да
[14:12:08] Фаворская Алена [student]: да
[14:12:09] ustas [student]: ага
[14:15:42] Суворикова Александра [student]: да
[14:16:27] Максим Р [student]: 0
[14:16:37] Фаворская Алена [student]: невозможно
[14:17:22] Фаворская Алена [student]: а х точно меньше епсилон?
[14:17:40] Фаворская Алена [student]: а да все виж
[14:18:17] Максим Р [student]: да
[14:18:18] Суворикова Александра [student]: да
[14:18:18] Юрий Горшенин [student]: да
[14:18:19] Фаворская Алена [student]: да
[14:18:19] ustas [student]: да
[14:18:21] Владимир Игнатьев [student]: ок
[14:25:21] Владимир Игнатьев [student]: в чем идея?
[14:27:09] Владимир Игнатьев [student]: почему тогда вероятность увеличится?
[14:27:40] Юрий Горшенин [student]: Неравенство ослабляется
[14:28:02] Владимир Игнатьев [student]: да
[14:28:14] Владимир Игнатьев [student]: спасибо
[14:29:47] Фаворская Алена [student]: тут но думаю
[14:31:07] Дорн Юрий Владимирович [students]: Да, извините!
[14:31:07] Юрий Горшенин [student]: парето набор это delta > 0. Дельта не мала это delta >= eps * eps
[14:31:08] Дорн Юрий Владимирович [students]: :)
[14:31:33] Фаворская Алена [student]: ясно
[14:34:28] Владимир Игнатьев [student]: Это стас отвалился или я?_
[14:34:51] ustas [student]: надо будет с картинкой еще повозиться
[14:35:07] ustas [student]: ну я о том же
[14:35:36] *** Conference call ***
[14:35:44] Фаворская Алена [student]: я тут
[14:35:47] Дорн Юрий Владимирович [students]: тут
[14:36:04] Владимир Игнатьев [student]: камбэк?
[14:36:31] Максим Р [student]: звук есть?
[14:36:33] Максим Р [student]: я не слышу
[14:36:35] Юрий Горшенин [student]: +1
[14:36:36] Суворикова Александра [student]: есть
[14:36:42] Фаворская Алена [student]: слышно
[14:36:44] Владимир Игнатьев [student]: есть
[14:36:45] Дорн Юрий Владимирович [students]: слышно
[14:38:15] Максим Р [student]: все ок, разобрался.
[14:38:52] Владимир Игнатьев [student]: шикарно!) Даже Горбачев такого не рисовал)
[14:39:03] Суворикова Александра [student]: )))))
[14:39:12] Владимир Игнатьев [student]: Препод по теорверу)
[14:39:12] ustas [student]: Олег Геннадьевич
[14:40:49] Фаворская Алена [student]: формула?
[14:41:08] Юрий Горшенин [student]: Вероятности не больше 1
[14:41:09] Суворикова Александра [student]: ну p<1
[14:41:21] Суворикова Александра [student]: что значит даже?
[14:41:27] Юрий Горшенин [student]: )
[14:41:28] Суворикова Александра [student]: :(
[14:41:29] ustas [student]: )
[14:41:59] Фаворская Алена [student]: да
[14:42:01] Максим Р [student]: понг
[14:42:01] ustas [student]: ясно
[14:42:02] Владимир Игнатьев [student]: да
[14:42:03] Юрий Горшенин [student]: да
[14:42:14] Владимир Игнатьев [student]: Сашу обидели зачем?)
[14:42:33] *** Call ended, duration 05:01 ***
[14:44:04] *** Conference call ***
[14:44:15] Максим Р [student]: все ок
[14:44:16] Фаворская Алена [student]: слышно
[14:44:19] Дорн Юрий Владимирович [students]: все норм
[14:44:21] Фаворская Алена [student]: и у нас
[14:44:24] Фаворская Алена [student]: но слышно
[14:44:29] Фаворская Алена [student]: кто то 1 отвалился
[14:44:31] Фаворская Алена [student]: видимо
[14:45:31] Юрий Горшенин [student]: Ничего не слышно
[14:46:08] Фаворская Алена [student]: подключиться попробуй? или подключен но не слшыно?
[14:46:12] Юрий Горшенин [student]: Все ОК
[14:46:28] *** Call ended, duration 01:26 ***
[14:46:53] Юрий Горшенин [student]: Пустой набор? )
[14:47:01] Фаворская Алена [student]: да?
[14:47:06] Юрий Горшенин [student]: Слышу слышу
[14:48:48] Максим Р [student]: о, круто будет
[14:49:02] Владимир Игнатьев [student]: Дело хорошее)
[14:49:52] ustas [student]: next time?
[14:50:02] Владимир Игнатьев [student]: Кроме тех моментов, когда я отваливался) Спасибо!
[14:50:10] Суворикова Александра [student]: Спасибо )
[14:50:11] Фаворская Алена [student]: да, спасибо
[14:50:23] ustas [student]: я не смогу в выходные
[14:50:24] Максим Р [student]: спасибо
[14:50:25] Юрий Горшенин [student]: ок, спасибо
[14:50:35] Фаворская Алена [student]: до свиданья
[14:50:36] Максим Р [student]: до связи
[14:50:36] Владимир Игнатьев [student]: До свиданья
[14:50:37] ustas [student]: до свидания
</pre>