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

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

Короткая ссылка: 2011-10-13

Тема

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

Скайп-логи

[15:17:14] Дорн Юрий Владимирович [student]: Заказчик в среднем некомпетентен, так что купит в среднем:)
[15:17:27] Максим Р [student]: нумерация страниц 10/20 и 7/20 - это норм?
[15:17:31] Максим Р [student]: )
[15:17:41] Kirill Pavlov [student]: перекомпилировать надо
[15:17:45 | Изменены 15:17:52] Kirill Pavlov [student]: mindmap
[15:22:11] Alexander (Suslik)  [student]: m - константа?
[15:23:55] Alexander (Suslik)  [student]: разве это не ограничивает круг поиска подмножеств для влобного перебора?
[15:23:58] Дорн Юрий Владимирович [student]: а есть ли какая-нибудь мера, согласно которой мера таких, вычернкутых матриц, мала?
[15:24:21] Дорн Юрий Владимирович [student]: ну т.е. можно ли сказать что да, обычно все хорошо
[15:24:30] Максим Р [student]: это ты к "почти всем" ведешь, Юрий?
[15:24:35] Дорн Юрий Владимирович [student]: да
[15:26:42] Максим Р [student]: скайп есть, экран видно
[15:26:45] Дорн Юрий Владимирович [student]: попробуйте сменить страницу
[15:26:45] Дмитрий Черников [student]: да
[15:26:50] Дорн Юрий Владимирович [student]: нам тоже написали
[15:26:56] Дмитрий Черников [student]: не меняется
[15:26:57] Kirill Pavlov [student]: нет
[15:26:57] Дорн Юрий Владимирович [student]: все по старому
[15:26:58] Максим Р [student]: страница та же
[15:27:21] Alexander (Suslik)  [student]: вероятность - (1-p) ^ L?
[15:27:43] Дмитрий Черников [student]: видно
[15:28:12] ustas [student]: 1 -
[15:28:14] Alexander (Suslik)  [student]: 1-
[15:28:16] Дорн Юрий Владимирович [student]: 1-
[15:28:20 | Изменены 15:28:31] Kirill Pavlov [student]: 1 - (1-p)^L
[15:28:37] Дмитрий Черников [student]: перемножить
[15:28:47] ustas [student]: (1 -  )^m
[15:28:47] Дорн Юрий Владимирович [student]: м*
[15:28:50] Alexander (Suslik)  [student]: физтех, ёпте
[15:28:53] Дорн Юрий Владимирович [student]: )
[15:30:38 | Изменены 15:30:52] Alexander (Suslik)  [student]: под суммой не должно быть L * P( -L-)
[15:30:54] Kirill Pavlov [student]: это любовь
[15:31:03] Дмитрий Черников [student]: ))
[15:31:14] Alexander (Suslik)  [student]: минусы не читать
[15:31:31] Alexander (Suslik)  [student]: всё, понял
[15:31:56] Alexander (Suslik)  [student]: именно
[15:34:58] Максим Р [student]: мы тут
[15:35:10] Дорн Юрий Владимирович [student]: разложили (1-п), потом вернулись к тем ограничениям
[15:35:44] Kirill Pavlov [student]: я понял
[15:35:59] Kirill Pavlov [student]: то, что в скобках меньше m^(1-delta)
[15:36:10] Kirill Pavlov [student]: нужно подставить и прологарифмировать
[15:36:14] Kirill Pavlov [student]: и все получиться.
[15:37:14] Kirill Pavlov [student]: логарифмы сократятся
[15:37:17] Максим Р [student]: да
[15:37:21] ustas [student]: кул
[15:37:36] Kirill Pavlov [student]: будет m^(-(1-\delta))
[15:38:19] ustas [student]: понятно
[15:38:20] Alexander (Suslik)  [student]: да нормально
[15:38:21] Суворикова Александра [student]: не надо
[15:38:22] Максим Р [student]: не стоит писать
[15:39:44 | Изменены 15:40:15] Kirill Pavlov [student]: Неравенство Чебышева
[15:39:45] Дорн Юрий Владимирович [student]: шум
[15:39:50] Дорн Юрий Владимирович [student]: выключите микрофон
[15:39:52] ustas [student]: потому, что есть еще вероятность P(X(l0)<1)
[15:39:55] Дорн Юрий Владимирович [student]: не Вы6)
[15:39:58] Kirill Pavlov [student]: в знаменателе дисперсия < 1
[15:39:59] ustas [student]: и она тоже входит в матожидание
[15:41:19] ustas [student]: ага
[15:41:21] Kirill Pavlov [student]: pong
[15:44:22] Дмитрий Черников [student]: тут
[15:44:23] Kirill Pavlov [student]: я тут
[15:44:24] Дорн Юрий Владимирович [student]: пока все норм
[15:44:26] Максим Р [student]: слышно
[15:44:26] Суворикова Александра [student]: тут
[15:44:27] Alexander (Suslik)  [student]: у меня всё ок
[15:44:27] Фаворская Алена [student]: кто то вышел
[15:44:45] Максим Р [student]: мб, вам кто-то звонил?..
[15:44:53] ustas [student]: а мне кажется, что кто-то зашел
[15:44:59] ustas [student]: было 10, стало 11
[15:44:59] Фаворская Алена [student]: эт кто-то один отключился или подключился
[15:45:54] ustas [student]: да
[15:45:54] Дмитрий Черников [student]: да
[15:45:56] Максим Р [student]: +
[15:46:01] Alexander (Suslik)  [student]: ++
[15:46:06] Суворикова Александра [student]: +
[15:48:47] Фаворская Алена [student]: дополнение?
[15:49:03] ustas [student]: 1= веоятность, что есть непокрытый элемент, + вероятность, что такого элемента нет
[15:49:03] Alexander (Suslik)  [student]: так нас интересует, чтобы непокрытых элементов не было
[15:49:13] Фаворская Алена [student]: дополнение события
[15:49:14] Фаворская Алена [student]: вот
[15:51:46] Фаворская Алена [student]: а куда o(1) делось?
[15:51:59] Фаворская Алена [student]: ну ноль
[15:52:36] Фаворская Алена [student]: 1+дельта - дельта квадрат и тд что то типа этого
[15:52:48] Фаворская Алена [student]: и этот дельта (1 + -...) = епсилон
[15:53:39] ustas [student]: а можно еще раз вкратце пройтись по слайдам и повторить общую идею?
[15:54:54] ustas [student]: ок
[15:55:08] ustas [student]: спасибо
[15:55:54] Alexander (Suslik)  [student]: фектически мы подогнали условие таким образом, чтобы наше решение для него подошло?
[15:56:17] Фаворская Алена [student]: ну... оно ж достаточно общий случай
[15:56:51] Alexander (Suslik)  [student]: вот тут был как раз вопрос
[15:56:57 | Изменены 15:57:07] Alexander (Suslik)  [student]: по второму пределу
[15:57:01] Дорн Юрий Владимирович [student]: а мы ему: тогда мы с вами не работаем!
[15:57:31] Alexander (Suslik)  [student]: можно пояснить его смысл ещё раз?
[15:58:02] Максим Р [student]: когда очень мало множеств
[15:58:59] Alexander (Suslik)  [student]: ясно, спасибо
[15:59:07] Дорн Юрий Владимирович [student]: Ну кстати да, если у нас зафиксировано n строк, то у нас порядка 2^n матриц подходящих, а все остальные не подходят
[16:00:49] Alexander (Suslik)  [student]: вопросов нет
[16:00:49] Дмитрий Черников [student]: нет
[16:00:50] Kirill Pavlov [student]: нет
[16:00:51] Максим Р [student]: нет
[16:00:51] ustas [student]: нету
[16:00:56] Дорн Юрий Владимирович [student]: Удачи!
[16:00:58] Дмитрий Черников [student]: до свиданья
[16:01:00] Суворикова Александра [student]: досвидания
[16:01:00] ustas [student]: до свидания
[16:01:04] Максим Р [student]: ок
[16:01:09] Alexander (Suslik)  [student]: счастливо
[16:01:09] Фаворская Алена [student]: тоже в четверг?
[16:01:09] Максим Р [student]: до свидания
[16:01:12] Фаворская Алена [student]: до свиданья!
[16:01:12] Kirill Pavlov [student]: всего хорошего
[16:01:14] Фаворская Алена [student]: спасибо!

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

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

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