Курс лекций «Эффективные алгоритмы»/Лекции осеннего семестра 2011/2011-09-15
Материал из DISCOPAL
Короткая ссылка: 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]: До свидания!
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.