Курс лекций «Эффективные алгоритмы»/Лекции осеннего семестра 2011/2011-09-29
Материал из DISCOPAL
Короткая ссылка: 2011-09-29
Содержание
Темы
Видео
Проблемы
Не успел нарисовать поясняющую геометрию вероятностей картинку, плюс в алгоритме на слайдах была ошибка — спешите исправить и сделать правильный алгоритм.
Интересное
Удалось придумать, как пришить и логи скайп-переговоров к лекции. Но предыдущие лекции не «проиграли» — я пришью скайп-переговоры и к ним, после чего их можно будет удалить со страничек (если кого-то это беспокоит).
Скайп-логи
[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]: до свидания
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.