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

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

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

Темы

• Жадный алгоритм в задачах о покрытии
• Жадный алгоритм в задаче о рюкзаке

---

Проблемы

Сначала несколько раз отваливался скайп. Потом он проработал 1:15:00 без сбоев. Возможно проблема в Wi-Fi сети ИСПРАН.

Скайп-логи

[14:37:23] Фаворская Алена [student]: да, слайды видно
[14:37:31] Фаворская Алена [student]: да скайп не видим
[14:38:16] Maxim Panov [student]: видно
[14:38:35] Constantine [students]: кто?
[14:38:37] Суворикова Александра [student]: кто?
[14:38:40] Фаворская Алена [student]: а нам продолжает быть слышно
[14:38:42] Constantine [students]: звук есть
[14:38:42] Максим Р [student]: слышно вас
[14:38:43] Суворикова Александра [student]: нет, мы тут
[14:38:45] Фаворская Алена [student]: это может кто-то ушел?
[14:42:00] Фаворская Алена [student]: мы тут
[14:42:00] ustas [student]: ага
[14:42:01] Дорн Юрий Владимирович [students]: все отл
[14:42:02] Суворикова Александра [student]: да
[14:42:02] Фаворская Алена [student]: все отлично
[14:42:03] Фаворская Алена [student]: все слышно
[14:42:08] Игорь Литвинов [student]: тут
[14:42:52] Фаворская Алена [student]: примерно помним
[14:46:46] Фаворская Алена [student]: видим
[14:46:49] ustas [student]: дада
[14:47:13] Максим Р [student]: 3
[14:47:18] ustas [student]: +1
[14:47:20] Фаворская Алена [student]: самое длинное
[14:47:59] Фаворская Алена [student]: самое близкое и самое длинное
[14:48:07] Суворикова Александра [student]: да
[14:48:08] Максим Р [student]: да
[14:48:08] Дорн Юрий Владимирович [students]: да
[14:48:09] Фаворская Алена [student]: а нет, покрывающее
[14:48:12] ustas [student]: ага
[14:48:13] Фаворская Алена [student]: крестик да видим
[14:48:19] Максим Р [student]: 4 снизу
[14:49:01] Фаворская Алена [student]: а здесь нет других решений
[14:49:04] Фаворская Алена [student]: или я ошибаюсь?
[14:50:34] Фаворская Алена [student]: я верю что такое можно сделать.
[14:51:27] Максим Р [student]: каждый второй элемент взять
[14:51:39] Дорн Юрий Владимирович [students]: одно длинное по центру
[14:51:42] Дорн Юрий Владимирович [students]: без концов
[14:52:37] Фаворская Алена [student]: по той же схеме
[14:52:43] Фаворская Алена [student]: с увеличивающимся от центра размером
[14:52:49] *** Call ended, duration 19:33 ***
[14:52:55] Фаворская Алена [student]: звук пропал
[14:52:56] Дорн Юрий Владимирович [students]: отвалились
[14:52:58] *** Conference call ***
[14:53:03] Фаворская Алена [student]: пошло вроде
[14:53:39] Дорн Юрий Владимирович [students]: скорее всего все же падает интернет
[14:54:26] Суворикова Александра [student]: да
[14:54:28] Фаворская Алена [student]: да
[14:54:29] Максим Р [student]: да
[14:54:30] Рубен... [students]: да
[14:55:12] Максим Р [student]: ustas в ИСПе сейчас
[14:56:01] *** Call ended, duration 03:01 ***
[14:56:07] Фаворская Алена [student]: пропали
[14:56:07] Дорн Юрий Владимирович [students]: упали
[14:56:09] *** Conference call ***
[14:56:41] Фаворская Алена [student]: а с версиями скайпов всех участников никак не может быть связано?
[14:56:54] Дорн Юрий Владимирович [students]: нет
[14:56:56] Фаворская Алена [student]: у меня очень старая
[14:57:04] Фаворская Алена [student]: а, тогда здорово, если нет
[14:59:56] Фаворская Алена [student]: а какая это презентация из выложенных на сайте7
[15:00:55] Фаворская Алена [student]: спасибо, думаю найду. просто она не вторая.
[15:02:00] Фаворская Алена [student]: просто я хотела перед лекцией просмотреть.
[15:02:05] Фаворская Алена [student]: почему-то иногда пропадает звук
[15:02:08] Фаворская Алена [student]: ненадолго
[15:03:09] Фаворская Алена [student]: обмануть самым худшим способом?
[15:03:18] Фаворская Алена [student]: мне кжается это из за микрофона - со звуком
[15:03:30] Фаворская Алена [student]: обычно все прекрасно
[15:04:33] Фаворская Алена [student]: еще один почти как зеленый?
[15:04:44] Дорн Юрий Владимирович [students]: еще один зеленый только длиннее с концов
[15:04:47] Фаворская Алена [student]: да
[15:05:00] Максим Р [student]: по чуть больше чем половинки из остатков
[15:05:36] Фаворская Алена [student]: в одну сторону?
[15:05:38] Дорн Юрий Владимирович [students]: длиннее более чем на максимальная из непокрытых синих
[15:05:41] Дорн Юрий Владимирович [students]: в разную сторону
[15:05:56] Дорн Юрий Владимирович [students]: нет, тогда мы возьмем максимальный из синих
[15:06:04] Фаворская Алена [student]: а, да
[15:06:05] Дорн Юрий Владимирович [students]: в смысле если брать половинки
[15:06:47] Дорн Юрий Владимирович [students]: половинки не годятся, ведь он будет брать тот из синих, хвост у которого больше
[15:07:03] Фаворская Алена [student]: ясно
[15:07:08] *** Call ended, duration 10:57 ***
[15:07:11] Фаворская Алена [student]: пропали
[15:07:16] *** Conference call ***
[15:08:46] Дорн Юрий Владимирович [students]: если непокрытыми у синих остались отрезки длиной 2а и 2б, то от зеленого длина "добавки" будет (а+б), если ф не равно б, то либо 2а либо 2б больше, чем (а+б)
Разве жадина не выберет его?
[15:09:35] Фаворская Алена [student]: опыт других людей говорит что за 40 минут в скайпе связть не пропадает. правда их было трое всего.
[15:09:55] Максим Р [student]: Дорн: надо строить множества, в которых чуть больше(!), чем половинки
[15:10:02] Дорн Юрий Владимирович [students]: на третьей итерации может съесть левый отрезов
[15:10:06] Дорн Юрий Владимирович [students]: у них длина одинаковые
[15:10:10] Дорн Юрий Владимирович [students]: длины*
[15:10:48] Фаворская Алена [student]: ну может пример неккорректный
[15:10:55] Фаворская Алена [student]: можно же взять другой
[15:10:57] Фаворская Алена [student]: пример
[15:11:00] Фаворская Алена [student]: с тем же приинципом
[15:11:39] Фаворская Алена [student]: [15:09] Фаворская Алена [student]:

<<< опыт других людей говорит что за 40 минут в скайпе связть не пропадает. правда их было трое всего.
[15:11:43] Дорн Юрий Владимирович [students]: Надо брать чуть больше, не чем половинки, а чем максимальный из остатков
[15:11:53] Дорн Юрий Владимирович [students]: просто в разные стороны
[15:12:18] Дорн Юрий Владимирович [students]: Да, понятно
[15:12:18] Фаворская Алена [student]: ну да, худшая из возможностей
[15:12:24] Дорн Юрий Владимирович [students]: а гарантировать нельзя?
[15:12:36] Дорн Юрий Владимирович [students]: понятно:)
[15:12:39] Фаворская Алена [student]: звук вот толкьо что ненадолго пропал
[15:12:45] Фаворская Алена [student]: слово алгоритм как алгори
[15:12:48] Фаворская Алена [student]: это толкьо у меня7
[15:12:54] Фаворская Алена [student]: может быть
[15:13:02] Максим Р [student]: +1
[15:13:02] Фаворская Алена [student]: ну ничего страшного тогда
[15:13:05] Дорн Юрий Владимирович [students]: зависания есть
[15:13:08] Дорн Юрий Владимирович [students]: нестабильность сети
[15:13:12] Дорн Юрий Владимирович [students]: скайп терпит:)
[15:13:15] Максим Р [student]: так-то понятно из контекста )
[15:13:36] Фаворская Алена [student]: да
[15:14:12] Максим Р [student]: XD
[15:16:49 | Edited 15:18:56] Фаворская Алена [student]: ну к задано так чтобы было?
[15:19:37] Фаворская Алена [student]: не зависит от к?
[15:19:51] Максим Р [student]: k известно ведь
[15:20:00] Фаворская Алена [student]: результируящая оценка не зависит от к?
[15:20:31] Максим Р [student]:  зависимость в постановке задачи.
[15:20:48] Фаворская Алена [student]: понятно
[15:21:30] Максим Р [student]: хотя... решения будут разные, а ошибка реально не зависит. О_о
[15:21:41] Фаворская Алена [student]: ну.. я и удивилась.
[15:23:05] Фаворская Алена [student]: точная оценка вроде зависит от к. просто смотрим чему она больше либо равна снизу. судя по слайду.
[15:25:56] Дорн Юрий Владимирович [students]: центр
[15:25:59] Максим Р [student]: +1
[15:25:59] Суворикова Александра [student]: центр
[15:26:05] Фаворская Алена [student]: да
[15:26:33] Фаворская Алена [student]: вы не видели что мы пишем?
[15:26:36] Фаворская Алена [student]: странно....
[15:26:42] Фаворская Алена [student]: а мы думали мы не по той теме пишем
[15:26:47] Фаворская Алена [student]: * я думала
[15:26:54] Дорн Юрий Владимирович [students]: Генерал проспал свой полк:)
[15:27:52] Фаворская Алена [student]: это скайп виноват!!
[15:28:26] Дорн Юрий Владимирович [students]: 3
[15:28:28] Фаворская Алена [student]: три
[15:28:28] Суворикова Александра [student]: три
[15:28:40] Дорн Юрий Владимирович [students]: 8
[15:28:48] Дорн Юрий Владимирович [students]: упс:)
[15:30:45] Суворикова Александра [student]: ребра, выходящиие из одной вершины?
[15:32:52] Фаворская Алена [student]: скачали
[15:37:25] Дорн Юрий Владимирович [students]: Вопрос: Если есть мы и противник. Противник использует жадину. Мы расставляем обманки. Если противник берет обманку, мы получаем выигрышь а, если же угадывает, мы проигрываем б.
Есть ли оптимальное число обманок?

Стас Фомин 16:52, 16 September 2011 (MSD): Ну это отдельная задача, для каждой конкретной задачи. В нашем случае, в задачи о покрытии — есть верхняя граница качества алгоритма, и есть максимально плохой случай («оптимальное число обманок»). Тот плохой случай, который мы построили он «оптимален с точностью до константы», ибо там двоичный логарифм, а в оценке качества — натуральный. Но можно построить чуть более сложный пример, где будет натуральный логарифм обманок.

[15:39:13] Фаворская Алена [student]: а к записи лекций еще скайп-чат будет ли копироваться?
[15:39:23 | Edited 15:39:26] Фаворская Алена [student]: здорово
[15:39:52] Суворикова Александра [student]: 9
[15:40:08] Фаворская Алена [student]: а почему одни красные другие синие7
[15:40:13] Фаворская Алена [student]: кроме покрытия?
[15:43:21] Дорн Юрий Владимирович [students]: ошибка
[15:43:35] Фаворская Алена [student]: в чем ошибка?
[15:43:49] Фаворская Алена [student]: аа...
[15:43:58] Фаворская Алена [student]: да
[15:44:00] Фаворская Алена [student]: видим
[15:45:43] Фаворская Алена [student]: схватим все, да?
[15:45:59] Суворикова Александра [student]: кроме нижних
[15:46:10] Фаворская Алена [student]: по одной с каждого уровня
[15:46:30] Дорн Юрий Владимирович [students]: сидят внизу тихо:)
[15:46:36] Суворикова Александра [student]: ))) коварно
[15:47:25] Фаворская Алена [student]: давайте до конца
[15:47:25] Суворикова Александра [student]: а сколько человек осталось?
[15:47:31] Дорн Юрий Владимирович [students]: Если верить современной истории, Сталин был ленив:)
[15:49:44] Суворикова Александра [student]: да
[15:49:44] Суворикова Александра [student]: был
[15:49:56] Фаворская Алена [student]: у всех ли?
[15:50:03] Суворикова Александра [student]: ну у фупмов был )
[15:50:03] Фаворская Алена [student]: у меня не было. я вообще отстающая.
[15:50:04] Дорн Юрий Владимирович [students]: да
[15:51:57] Суворикова Александра [student]: это полезность
[15:52:00] Фаворская Алена [student]: полезоность да
[15:52:02] Суворикова Александра [student]: если переводить название
[15:52:05] Фаворская Алена [student]: странно...
[15:52:21] Фаворская Алена [student]: бесполезность тоже характеризует полезность
[15:52:31] Суворикова Александра [student]: 1 - бесполезность? ))))
[15:54:19] Фаворская Алена [student]: а почему стоимость 20 когда 10?
[15:54:24] Суворикова Александра [student]: вес 10
[15:54:25] Фаворская Алена [student]: ой
[15:54:26] Фаворская Алена [student]: вес
[15:54:27] Фаворская Алена [student]: вес
[15:54:30] Фаворская Алена [student]: я ошиблась
[15:54:36] Фаворская Алена [student]: я не права
[15:54:39] Фаворская Алена [student]: я с весом перепутала
[15:54:56] Фаворская Алена [student]: ограничение не на стоимость а на вес
[15:55:57] Суворикова Александра [student]: давать ему много дешевого товара?
[15:56:13] Фаворская Алена [student]: легкого дешевого товара?
[15:56:43] Фаворская Алена [student]: тогда дорогой и тяжелый
[15:56:46] Суворикова Александра [student]: ну за единицу стоимости
[15:56:48] Фаворская Алена [student]: очень дорогой и очень тяжелый
[15:56:49] Суворикова Александра [student]: дешевую
[15:56:51] Maxim Panov [student]: жалко, вас не слышу (( интересная тема
[15:56:54] Фаворская Алена [student]: и больше по массе не влезет
[15:57:03] Фаворская Алена [student]: он наушники забыл
[15:57:05] Максим Р [student]: у него ушей нет
[15:57:05] Фаворская Алена [student]: да7
[15:57:16] Фаворская Алена [student]: 100 10
[15:57:18] Максим Р [student]: в смысле наушников
[15:57:27] Фаворская Алена [student]: 1000 100
[15:57:30] Фаворская Алена [student]: ?
[15:57:41] Фаворская Алена [student]: 1000 100 и еще что то такого же рода
[15:57:50] Фаворская Алена [student]: чтобы общая сумма больше 1000
[15:57:59] Фаворская Алена [student]: у остаттка
[15:58:19] Суворикова Александра [student]: например такой вход (100 100), (99, 1) (99, 1) (99, 1)
[15:58:25] Фаворская Алена [student]: да
[15:58:33] Максим Р [student]: нее
[15:58:40] Максим Р [student]: 297
[15:58:41] Фаворская Алена [student]: другое отношение
[15:58:41] Дорн Юрий Владимирович [students]: дать один товар, настолько дорогой, что ниодин из оптимальных элементом не мог быть куплен на остаток. И дать ооочень много дешевой тяжелой мелочи
[15:58:45] Суворикова Александра [student]: не понятно
[15:58:52] Суворикова Александра [student]: почему вы не берете сразу самый орогой?
[15:59:31] Суворикова Александра [student]: чорт, и впрямь ) спасибо
[16:00:28] Дорн Юрий Владимирович [students]: После того, как он съел очень дорогой вариант, вариантов у него нет, кроме как есть те элементы, на которые хватит денег - они должны быть тяжелые.
[16:01:23] Дорн Юрий Владимирович [students]: (999, 1), (500, 2)
[16:01:35] Дорн Юрий Владимирович [students]: ой:)
[16:01:49] Фаворская Алена [student]: а это для рюкзака весом 2
[16:01:57] Дорн Юрий Владимирович [students]: (999, 99), (500, 50)
[16:02:00] Дорн Юрий Владимирович [students]: ой
[16:02:24] Фаворская Алена [student]: 999 50, 500 100
[16:02:45] Максим Р [student]: вес 1, стоимость k
вес 100, стоимость k*k
[16:02:58] Максим Р [student]: стоп
[16:03:10] Фаворская Алена [student]: от к долежн вес зависеть тоже
[16:15:16] Дорн Юрий Владимирович [students]: да
[16:15:17] Фаворская Алена [student]: да
[16:15:18] Максим Р [student]: дп
[16:15:19] Суворикова Александра [student]: да
[16:15:46] Суворикова Александра [student]: отлично )
[16:15:46] Дорн Юрий Владимирович [students]: офигенно!
[16:16:01] Фаворская Алена [student]: хорошо получилось
[16:16:22] Дорн Юрий Владимирович [students]: История скайпа также остается
[16:16:26] Максим Р [student]: хорошо
[16:16:30] Дорн Юрий Владимирович [students]: и доступна даже тем, кого небыло
[16:16:38] Дорн Юрий Владимирович [students]: но кто был в конференции
[16:16:47] Дорн Юрий Владимирович [students]: числился т.е.
[16:17:07] Фаворская Алена [student]: а когда копировать из скайпа - время видно
[16:17:17] Фаворская Алена [student]: время звонков тоже видно
[16:17:26] ustas [student]: а как тут отметиться?
[16:17:29] Фаворская Алена [student]: можно соотнести при желании
[16:17:51] Суворикова Александра [student]: интернет под рукой, опять же )
[16:18:05] ustas [student]: окай
[16:18:38] Дорн Юрий Владимирович [students]: а со временем-в это также?
[16:18:38] Фаворская Алена [student]: да, пожелание все же  что сегодня долго. могут на работе кого-то отвлечь.
[16:18:52] ustas [student]: да, меня тут много отвлекали
[16:19:00] Фаворская Алена [student]: да, было бы здорово разбивать на части
[16:19:07] Фаворская Алена [student]: так и усваивается материал легче.
[16:19:38] ustas [student]: мне близко) до вашего кабинета
[16:19:48] Фаворская Алена [student]: а кто где?
[16:19:51] Фаворская Алена [student]: я в Долгопрудном
[16:19:55] Максим Р [student]: зюзино
[16:20:01] Суворикова Александра [student]: спасибо Вам :)
[16:20:02] Фаворская Алена [student]: до свиданья.
[16:20:03] Дорн Юрий Владимирович [students]: Академическая
[16:20:06] Дорн Юрий Владимирович [students]: Спасибо!)
[16:20:06] Фаворская Алена [student]: Спасио вам
[16:20:09] Максим Р [student]: до свиданья
[16:20:12] Дорн Юрий Владимирович [students]: До свидания!

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

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

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