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

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

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

Тема

• Полиномиальный в среднем алгоритм для SAT

Проблемы

Сначала была попытка Skype через WiFi — падал.

Скайп-логи

[2011-09-25 18:51:16] Фаворская Алена [student]: да
[2011-09-25 18:51:29] Фаворская Алена [student]: да
[2011-09-25 18:51:30] Kirill Pavlov [student]: да
[2011-09-25 18:51:30] Владимир Игнатьев [student]: да
[2011-09-25 18:51:33] ustas [student]: ага
[2011-09-25 18:51:39] Владимир Игнатьев [student]: -1
[2011-09-25 18:51:41] Kirill Pavlov [student]: 3-выполнимость
[2011-09-25 18:51:45] Фаворская Алена [student]: -1
[2011-09-25 18:51:49] max: -1
[2011-09-25 18:51:51] ustas [student]: почему 3?
[2011-09-25 18:52:02] ustas [student]: просто выполнимость
[2011-09-25 18:52:14] Максим Р [student]: адддд
[2011-09-25 18:52:36] *** Call ended, duration 01:54 ***
[2011-09-25 18:52:45] Фаворская Алена [student]: отвалились
[2011-09-25 18:52:46] Владимир Игнатьев [student]: Отваливается((
[2011-09-25 18:52:50] Максим Р [student]: печаль
[2011-09-25 18:52:59] Фаворская Алена [student]: может попробуем все же прорваться?
[2011-09-25 18:53:12] Фаворская Алена [student]: вайфай плох...
[2011-09-25 18:53:16] Владимир Игнатьев [student]: 3 попытки
[2011-09-25 18:53:25] Владимир Игнатьев [student]: даем?
[2011-09-25 18:54:40] *** Conference call ***
[2011-09-25 18:54:44] Максим Р [student]: а мб инет по проводу?
[2011-09-25 18:55:32] Kirill Pavlov [student]: тут
[2011-09-25 18:55:32] Максим Р [student]: тут
[2011-09-25 18:55:34] ustas [student]: тута
[2011-09-25 18:55:39] Максим Р [student]: слышно
[2011-09-25 18:55:43] ustas [student]: хорошо
[2011-09-25 18:56:14] Kirill Pavlov [student]: я.онлайн
[2011-09-25 18:57:22] Максим Р [student]: среднее по чему?
[2011-09-25 18:58:05] Фаворская Алена [student]: по входным данным
[2011-09-25 18:58:25] Фаворская Алена [student]: я каким то образом пропустила самое начало...
[2011-09-25 18:58:51] Фаворская Алена [student]: что не лезет?
[2011-09-25 19:00:40] Kirill Pavlov [student]: eps ~ 1/C
[2011-09-25 19:00:49] Максим Р [student]: не всегда
[2011-09-25 19:00:55] Максим Р [student]: как мне кажется
[2011-09-25 19:01:44] Фаворская Алена [student]: первое?
[2011-09-25 19:01:45] Максим Р [student]: второе шире
[2011-09-25 19:01:48] Kirill Pavlov [student]: второе включает первое
[2011-09-25 19:01:52] Фаворская Алена [student]: а, да согласна
[2011-09-25 19:01:53] max: мат ожидание от экспоненты не равно експоненте от матожидания
[2011-09-25 19:01:58] Владимир Игнатьев [student]: второе
[2011-09-25 19:02:04] ustas [student]: первое
[2011-09-25 19:02:07] Kirill Pavlov [student]: зачем, мы видим все, нет?
[2011-09-25 19:02:17] Фаворская Алена [student]: а нельзя ли сделать так чтобы презентация закрывала часть экрана?
[2011-09-25 19:02:45] Kirill Pavlov [student]: у себя можно сделать
[2011-09-25 19:02:50] Фаворская Алена [student]: ну да
[2011-09-25 19:02:55] Kirill Pavlov [student]: каждый браузер сожмет и скайп вставит.
[2011-09-25 19:02:57] Фаворская Алена [student]: вопрос идет о видео для отсутствющих
[2011-09-25 19:03:24] Максим Р [student]: так ответили уже все )
[2011-09-25 19:03:29] Максим Р [student]: второе щире
[2011-09-25 19:03:30] Фаворская Алена [student]: второе.
[2011-09-25 19:03:47] Фаворская Алена [student]: у вас скайп почему-то новые ответы не отображает
[2011-09-25 19:03:54] max: второе
[2011-09-25 19:04:00] Максим Р [student]: делэй большой скайпа
[2011-09-25 19:04:01] Фаворская Алена [student]: он нас не видит
[2011-09-25 19:04:09] Фаворская Алена [student]: а уже видите
[2011-09-25 19:04:18] Фаворская Алена [student]: мы ответили что второе
[2011-09-25 19:04:18] Максим Р [student]: delay
[2011-09-25 19:06:38] Владимир Игнатьев [student]: Надо же функцию)
[2011-09-25 19:07:39] Kirill Pavlov [student]: есть матожидание, нет дисперсии
[2011-09-25 19:08:28] Максим Р [student]: я даю шанс другим
[2011-09-25 19:08:30] Максим Р [student]: пока )
[2011-09-25 19:08:47] ustas [student]: такой великодушный Макс)
[2011-09-25 19:08:57] Максим Р [student]: алгоритм работать должен ровно 2^n на всех входах. тогда E (T) = 1,  E (T^2) = 2^n
[2011-09-25 19:09:12] Максим Р [student]: там степень
[2011-09-25 19:09:28] Максим Р [student]: ок, поняд
[2011-09-25 19:09:58] Максим Р [student]: тогда на одном 2^n, на остальных 0
[2011-09-25 19:10:20] ustas [student]: конечно проходили
[2011-09-25 19:11:16] Максим Р [student]: тогда, мб, на остальных n?
[2011-09-25 19:12:39] ustas [student]: да, понятно
[2011-09-25 19:12:52] Фаворская Алена [student]: да
[2011-09-25 19:13:12] ustas [student]: Стас, а можно скайп подвинуть?
[2011-09-25 19:13:50] Kirill Pavlov [student]: второе шире
[2011-09-25 19:13:51] Фаворская Алена [student]: 2
[2011-09-25 19:13:54] ustas [student]: 2
[2011-09-25 19:13:57] max: 2
[2011-09-25 19:16:21] Kirill Pavlov [student]: отбор признаков сводится
[2011-09-25 19:16:30] Kirill Pavlov [student]: алгоритмы вычисления оценок
[2011-09-25 19:17:12] Kirill Pavlov [student]: сводить конъюнкцию с минимальной и перебор
[2011-09-25 19:18:27] Kirill Pavlov [student]: это пример использования
[2011-09-25 19:18:44] Kirill Pavlov [student]: где решение SAT применяется.
[2011-09-25 19:19:54] Фаворская Алена [student]: отвалились?
[2011-09-25 19:19:57] Kirill Pavlov [student]: нет
[2011-09-25 19:19:59] Фаворская Алена [student]: только я
[2011-09-25 19:20:02] Serega (sympa) [student]: и я
[2011-09-25 19:20:05] ustas [student]: не только
[2011-09-25 19:20:09] Serega (sympa) [student]: второй раз
яя
[2011-09-25 19:20:11] Владимир Игнатьев [student]: и я
[2011-09-25 19:20:14] Фаворская Алена [student]: да и я второй
[2011-09-25 19:20:22] ustas [student]: кое-кто отвалился
[2011-09-25 19:20:29] ustas [student]: таких много
[2011-09-25 19:20:31] Владимир Игнатьев [student]: 3-ий раз
[2011-09-25 19:21:10] Kirill Pavlov [student]: это в tikz нарисовано?
[2011-09-25 19:21:35] Максим Р [student]: надо все же чтоб Стас видел чат, иначе обратной связи совсем нет.
[2011-09-25 19:21:49] Фаворская Алена [student]: а у него нынче один разве экран?
[2011-09-25 19:21:53] Максим Р [student]: видимо
[2011-09-25 19:22:05] Фаворская Алена [student]: по моему просто запись идет с одного
[2011-09-25 19:22:27] Kirill Pavlov [student]: невыполнима = 0 на всех наборах.
[2011-09-25 19:22:37] Kirill Pavlov [student]: на одном = нетождественна
[2011-09-25 19:22:53] Максим Р [student]: +1
[2011-09-25 19:24:41] Владимир Игнатьев [student]: И это лучше полного перебора еще раз?
[2011-09-25 19:24:57] Фаворская Алена [student]: ну мы как бы "упростили"
[2011-09-25 19:25:21] Владимир Игнатьев [student]: план понятен)
[2011-09-25 19:30:26] Kirill Pavlov [student]: понятно
[2011-09-25 19:30:27] Фаворская Алена [student]: да
[2011-09-25 19:30:28] ustas [student]: да
[2011-09-25 19:30:29] Владимир Игнатьев [student]: да
[2011-09-25 19:30:32] Serega (sympa) [student]: да, вполне\
[2011-09-25 19:31:29] Serega (sympa) [student]: dc ;/
[2011-09-25 19:31:39] Serega (sympa) [student]: обрыв
[2011-09-25 19:34:09] Фаворская Алена [student]: то есть для примера 4?
[2011-09-25 19:34:25] Kirill Pavlov [student]: равенство только в случае независимового множества.
[2011-09-25 19:34:54] Фаворская Алена [student]: в формуле для нарисованного примера 4
[2011-09-25 19:35:42] Владимир Игнатьев [student]: переодически отваливаюсь(
[2011-09-25 19:35:48] Kirill Pavlov [student]: это майкрософт виноват. Как купили так и сломали )
[2011-09-25 19:37:27] Фаворская Алена [student]: я
[2011-09-25 19:37:30] Фаворская Алена [student]: по скайпу
[2011-09-25 19:37:30] Владимир Игнатьев [student]: по скайпу
[2011-09-25 19:37:34] Владимир Игнатьев [student]: ага
[2011-09-25 19:37:45] Kirill Pavlov [student]: я не отваливаюсь
[2011-09-25 19:37:53] Kirill Pavlov [student]: сижу через вайфай
[2011-09-25 19:38:25] Kirill Pavlov [student]: нет
[2011-09-25 19:38:26] Владимир Игнатьев [student]: нетт))
[2011-09-25 19:38:32] Фаворская Алена [student]: вас слышно
[2011-09-25 19:39:06] Дмитрий Черников [student]: норм
[2011-09-25 19:39:26] Kirill Pavlov [student]: это понятно
[2011-09-25 19:39:30] Фаворская Алена [student]: да понятно
[2011-09-25 19:43:44] Дмитрий Черников [student]: кто то микрофон не выключил?
[2011-09-25 19:43:50] Дмитрий Черников [student]: какие то странные звуки идут
[2011-09-25 19:43:56] Максим Р [student]: с того света )
[2011-09-25 19:44:09] Дмитрий Черников [student]: будто кто то в варкрафт играет
[2011-09-25 19:44:20] Дмитрий Черников [student]: слышит кто еще?\
[2011-09-25 19:44:24] ustas [student]: ага
[2011-09-25 19:44:30] Максим Р [student]: serega speaking
[2011-09-25 19:44:35] max: да
[2011-09-25 19:44:49] Serega (sympa) [student]: видюшку рядом смотрели
[2011-09-25 19:44:50] Serega (sympa) [student]: сорри
[2011-09-25 19:44:50] Фаворская Алена [student]: было было
[2011-09-25 19:44:54] Фаворская Алена [student]: аа...
[2011-09-25 19:44:54] Serega (sympa) [student]: выключил
[2011-09-25 19:45:02] Фаворская Алена [student]: да, спасибо, стало тихо
[2011-09-25 19:45:14] max: видяшку или микрофон?
[2011-09-25 19:45:18] Serega (sympa) [student]: просто после каждого дисконнекта нужно выключать заного
[2011-09-25 19:45:23] Максим Р [student]: 'nj lf
[2011-09-25 19:45:25] Максим Р [student]: это да
[2011-09-25 19:48:15] Kirill Pavlov [student]: зависимое
[2011-09-25 19:49:09] max: как определяется size?
[2011-09-25 19:49:22] Kirill Pavlov [student]: зачем добавлять к С3 С0? Уже же проверялм, что С0 несовместима
[2011-09-25 19:49:24] Дмитрий Черников [student]: да, что такое сайз?
[2011-09-25 19:50:00] Kirill Pavlov [student]: 2:т - колво скобок
[2011-09-25 19:50:18] Дмитрий Черников [student]: слышим
[2011-09-25 19:50:18] Максим Р [student]: да слышно
[2011-09-25 19:50:23 | Edited 19:50:39] Kirill Pavlov [student]: size = 2^{n - кол-во независимых}
[2011-09-25 19:50:34] Дмитрий Черников [student]: ясн
[2011-09-25 19:50:42] ustas [student]: не похоже на 2:2
[2011-09-25 19:50:51] ustas [student]: 2^n
[2011-09-25 19:51:08] Kirill Pavlov [student]: n = 4 в примере
[2011-09-25 19:51:25] ustas [student]: а в примере на слайде size = 12
[2011-09-25 19:51:53 | Removed 19:52:03] Kirill Pavlov [student]: This message has been removed.
[2011-09-25 19:52:24] Kirill Pavlov [student]: 2^4 - 4 = 12
[2011-09-25 19:52:33] Kirill Pavlov [student]: для слоя k=1
[2011-09-25 19:52:37] ustas [student]: да, это ясно
[2011-09-25 19:53:13] Kirill Pavlov [student]: хотя нет
[2011-09-25 19:54:01] Kirill Pavlov [student]: замер литералов 4 так? все переменные встречаются.
[2011-09-25 19:54:30] Фаворская Алена [student]: 2+2+4+4?
[2011-09-25 19:56:43] Kirill Pavlov [student]: для быстрой работы алгоритма слои не должны плодиться.
[2011-09-25 19:57:04] Kirill Pavlov [student]: да, хочется, чтоб при малых k процесс заканчивался.
[2011-09-25 19:57:19] Kirill Pavlov [student]: пример помог
[2011-09-25 19:57:21] Фаворская Алена [student]: да
[2011-09-25 19:57:24] Дмитрий Черников [student]: да
[2011-09-25 19:57:27] ustas [student]: вроде понятно
[2011-09-25 19:57:59] Kirill Pavlov [student]: скобки в квадрате
[2011-09-25 19:58:17] Kirill Pavlov [student]: при переходе на следующих уровень все со всеми надо проверить.
[2011-09-25 19:58:58] Kirill Pavlov [student]: 1 - долго из-зи maxN_k
[2011-09-25 19:59:47] Kirill Pavlov [student]: x1&x2&x3 и т.д. для экспоненты
[2011-09-25 20:00:00] Kirill Pavlov [student]: все конъюнкции одноэлементные
[2011-09-25 20:00:31] Kirill Pavlov [student]: чтоб O(e) нужно невыполнимый пример
[2011-09-25 20:00:41] Фаворская Алена [student]: это скайп шалит
[2011-09-25 20:00:46] Фаворская Алена [student]: там формула должна быть
[2011-09-25 20:00:54] Фаворская Алена [student]: там е в скобочке
[2011-09-25 20:00:59] Фаворская Алена [student]: (е)
[2011-09-25 20:01:01 | Edited 20:01:10] Максим Р [student]: я вижу ( m )
[2011-09-25 20:01:03] Фаворская Алена [student]: о(е)
[2011-09-25 20:01:07] Фаворская Алена [student]: ой О(е)
[2011-09-25 20:01:10] Фаворская Алена [student]: это он написла
[2011-09-25 20:01:14] Фаворская Алена [student]: вместо письма
[2011-09-25 20:01:35] Фаворская Алена [student]: O(e) ==[20:01:56] Алена: О(е)
[2011-09-25 20:01:45] Kirill Pavlov [student]: О (  m  )
[2011-09-25 20:01:50] Kirill Pavlov [student]: это скайп шалит
[2011-09-25 20:02:02] Фаворская Алена [student]: а у меня письмо - е...
[2011-09-25 20:02:04] Фаворская Алена [student]: от м понятно
[2011-09-25 20:02:17] Дмитрий Черников [student]: ну одна скобка если
[2011-09-25 20:02:34] Максим Р [student]: мб, одно множество со всеми литералами, остальные - одноэлементные?
[2011-09-25 20:02:44] Фаворская Алена [student]: дополнения?
[2011-09-25 20:03:01] Kirill Pavlov [student]: x1notx_2 & x_2notx_3
[2011-09-25 20:03:04] Kirill Pavlov [student]: и т.д.
[2011-09-25 20:03:09] Kirill Pavlov [student]: т.е. по парам
[2011-09-25 20:03:59] Фаворская Алена [student]: совпадение в скобке
[2011-09-25 20:04:34] Фаворская Алена [student]: а пример так чтобы были зависимые и было быстро? есть ли?
[2011-09-25 20:04:37] Serega (sympa) [student]: ага
[2011-09-25 20:04:37] Дмитрий Черников [student]: да
[2011-09-25 20:04:41] Фаворская Алена [student]: чтобы не зависимые
[2011-09-25 20:04:44] Фаворская Алена [student]: НЕ зависимые
[2011-09-25 20:04:55] Kirill Pavlov [student]: x1 not x_1 & x2 not x_2
[2011-09-25 20:04:55] Фаворская Алена [student]: а пример чтобы были НЕ зависимые и так же быстро?
[2011-09-25 20:06:06] Фаворская Алена [student]: а, да понятно. невыполнимость выполнимость не коррелирует
[2011-09-25 20:06:25] Максим Р [student]: да
[2011-09-25 20:06:26] max: да
[2011-09-25 20:06:29 | Edited 20:06:35] Kirill Pavlov [student]: понятно
[2011-09-25 20:06:30] Дмитрий Черников [student]: ясно
[2011-09-25 20:06:31] Фаворская Алена [student]: да
[2011-09-25 20:06:31] Serega (sympa) [student]: дада)
[2011-09-25 20:09:08] Максим Р [student]: все поотпадали
[2011-09-25 20:09:10] Дмитрий Черников [student]: все отвалалсь?
[2011-09-25 20:09:14] Фаворская Алена [student]: я уже снова тут
[2011-09-25 20:09:14] ustas [student]: да вроде нет
[2011-09-25 20:09:18] max: тут
[2011-09-25 20:09:20] Kirill Pavlov [student]: pong
[2011-09-25 20:09:22] Дмитрий Черников [student]: понг)
[2011-09-25 20:09:24 | Edited 20:10:29] Максим Р [student]: было 3 пару секунд назад
[2011-09-25 20:09:28] Serega (sympa) [student]: быстро подключились)
[2011-09-25 20:09:29] Фаворская Алена [student]: было было
[2011-09-25 20:14:13] Фаворская Алена [student]: понятно
[2011-09-25 20:14:35] max: да
[2011-09-25 20:14:37] Максим Р [student]: а тут неравенства разве нестрогие? p > 0 ведь и k >= 1
[2011-09-25 20:14:39] Kirill Pavlov [student]: pong
[2011-09-25 20:14:43] Дмитрий Черников [student]: понг
[2011-09-25 20:14:45] Максим Р [student]: понг
[2011-09-25 20:14:49] ustas [student]: понг
[2011-09-25 20:16:05] Дмитрий Черников [student]: если 1 подставить будут все равны
[2011-09-25 20:16:07] Дмитрий Черников [student]: норм
[2011-09-25 20:16:14] Дмитрий Черников [student]: в п
[2011-09-25 20:16:17] Фаворская Алена [student]: p=1
[2011-09-25 20:16:25] Фаворская Алена [student]: поэтому нестрогое
[2011-09-25 20:16:33] Дмитрий Черников [student]: знач нестрогие
[2011-09-25 20:16:34] Фаворская Алена [student]: уже проверили
[2011-09-25 20:16:36] Фаворская Алена [student]: да
[2011-09-25 20:21:59] Фаворская Алена [student]: то есть эта формула просто из док-ва?
[2011-09-25 20:23:49] Максим Р [student]: что-то задач на сайте не видно
[2011-09-25 20:24:21] Дмитрий Черников [student]: лучше по одной
[2011-09-25 20:24:32] Serega (sympa) [student]: там есть тесты "перед экзаменом"
[2011-09-25 20:24:33] Kirill Pavlov [student]: Задачки на чем угодно прогать надо?
[2011-09-25 20:24:36] Serega (sympa) [student]: рендомные каждый раз
[2011-09-25 20:24:46] Фаворская Алена [student]: там математические задачи
[2011-09-25 20:24:51] Дмитрий Черников [student]: мы хотим прогать!)
[2011-09-25 20:24:55] Фаворская Алена [student]: ну...
[2011-09-25 20:25:59] Максим Р [student]: там только одна
[2011-09-25 20:28:40] Kirill Pavlov [student]: субтитры )
[2011-09-25 20:28:48] Максим Р [student]: по timestamp )
[2011-09-25 20:28:51] Kirill Pavlov [student]: можно вставить из скайпа
[2011-09-25 20:28:55] Kirill Pavlov [student]: да, на питоне!
[2011-09-25 20:29:05] Дмитрий Черников [student]: нееееет
[2011-09-25 20:29:12] Дмитрий Черников [student]: хотя не критично
[2011-09-25 20:29:13] Максим Р [student]: так это может быть первой задачей: как писать сабы
[2011-09-25 20:29:30] Максим Р [student]: special for Dima )
[2011-09-25 20:29:59] Фаворская Алена [student]: да, Саша куда-то делась
[2011-09-25 20:30:12] ustas [student]: в прошлый раз я был на работе
[2011-09-25 20:30:14] Фаворская Алена [student]: да ладно, хорошо вышло
[2011-09-25 20:30:17] Фаворская Алена [student]: хоть и отваливалось
[2011-09-25 20:30:28] Фаворская Алена [student]: люди отваливались
[2011-09-25 20:30:35] Фаворская Алена [student]: да ничего страшного
[2011-09-25 20:30:37] Serega (sympa) [student]: да это не сильно мешает
[2011-09-25 20:30:37] Serega (sympa) [student]: не страшно
[2011-09-25 20:30:44] Фаворская Алена [student]: быстро замечаешь что звук пропал и снова присоединяешься
[2011-09-25 20:32:26] ustas [student]: а когда в следующий раз будет лекция?
[2011-09-25 20:32:53 | Edited 20:33:00] Фаворская Алена [student]: спасибо
[2011-09-25 20:32:59] Kirill Pavlov [student]: adios amigos

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

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

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