Все комментарии викилогов

Материал из DISCOPAL
Перейти к: навигация, поиск

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

На 7 слайде, название "Линейная релаксация". Она же нелинейная, там произведение v стоит. Да и Вы на видео это сказали, 16 минута...


Пусть алгоритм A присваивает всем переменным значение 1. Тогда вероятность что скобка принимает значение 1, равна 7/8(благоприятные исходы, значения литералов 001, 010, 011, 100, 101, 110, 111; не благоприятный исход 000). Пусть в КНФ m скобок, тогда

Т.е. вероятностный приближенный алгоритм гарантирует точность 7/8

13 слайд, опечатка: должно быть имеет долю невыполненных дизъюнктов >= \epsilon

Нет определения класса APX

1) Пусть Боб выбрал кость А. Тогда Алиса выбирает кость В. Благоприятные для Алисы исходы: 2-1, 4-1, 9-1, 9-6, 9-8; неблагоприятные 2-6, 2-8, 4-6, 4-8. Все эти исходы равновероятны и других исходов быть не может, значит вероятность выигрыша Алисы равна

2) Пусть Боб выбрал кость B. Тогда Алиса выбирает кость C. Благоприятные для Алисы исходы: 3-2, 5-2, 5-4, 7-2, 7-4; неблагоприятные 3-4, 3-9, 5-9, 7-9. Все эти исходы равновероятны и других исходов быть не может, значит вероятность выигрыша Алисы равна

3) Пусть Боб выбрал кость C. Тогда Алиса выбирает кость A. Благоприятные для Алисы исходы: 6-3, 6-5, 8-3, 8-5, 8-7; неблагоприятные 1-3, 1-5, 1-7, 6-7. Все эти исходы равновероятны и других исходов быть не может, значит вероятность выигрыша Алисы равна

В любом из этих случаев вероятность выигрыша Алисы


8 слайд, как Вы вместо sol, должно быть Т, видео на 47:40 секунд. Вы просто забыли переименовать это значение

Выбираем произвольную вершину, красим ее в gthdsq цвет, помечаем;

for(все помеченные вершины) {
  for(все смежные вершины){
    if(вершина не покрашена) красим ее в другой цвет и помечаем
      else if (цвета совпадают) return покраски не существует
  }
  снимаем метку с вершины;}
return покраска графа

На 12 слайде, в комментарии что такое "size" написано, что это "счетчик выполняющих...". Однако на видео 2011 года, на 55 минуте, говорится, что это "счётчик обнуляющих КНФ наборов"


Пусть существует алгоритм А, выписывающий одну за другой все машины Тьюринга, которые не останавливаются, будучи запущенными на пустой ленте. Каждой МТ Х поставим в соответствие МТ Х0, которая запускается на пустой ленте и за первые шаги переходит в начальное состояние Х(если после этого запустить Х и Х0, они будут работать одинаково).

Возьмем произвольную МТ М, ей соответствует М0. Запускаем М и МТ, реализующую алгоритм А. Дальее возможны два исхода:

1) М остановится.

2) Алгоритмом А будет выписана М0. Значит, М0 не останавливается, и М не останавливается.

В результате для произвольной МТ М решена проблема остановки. ПРОТИВОРЕЧИЕ. Следовательно, алгоритма А не существует.

3 ячейки занимают счетчики левых скобок, правых скобок и их разность.

Тогда вы не понимаете, что такое ячейки в машине Тьюринга.

Действительно нехорошо, алфавит все таки конечный. Тогда под каждый счетчик - свою ленту, на ней число в двоичном виде.

Первое предложение надо поменять на "сведем нахождение MAX-CUT к нашей задаче".

Почему ничего не смогут сделать? В данном примере есть два цикла, которые пересекаются в А.

Я за него и не брался. Просто решил выполнить один пункт задачи.

На 91 странице в упражнении дерево "оставное"

Да, это уже исправлено. Но пишите такие замечания лучше при чтении книги PDF-комментами и аннотацией, либо в случае слайдов — на странице обсуждения книги или соотвествующих слайдов. А это вроде как обсуждение меня, не надо сюда писать.

Я проголосовал за вторник, в надежде что мне нужно приехать и получить автомат) А если учить и сдавать, то у нас 27го Случайные процессы - экзамен. а 31го Уравнения мат физики - экзамен, Вот УМФ нужно готовить минимум 3 дня, потому что там контрольная , которую завалить нельзя, потому единственный вариант, это во вторник, но он не лучший(

Вообще эта неделя как-то не очень для ещё одного экзамена, но мне больше подошла бы среда, которой тут нету. Проголосовала за вторник, но не уверена, что смогу приехать.

Итак, на неделе 27.05-31.05 выбран вторник, и мы будем там во вторник, для тех, кто соберется.

Теперь выбираем удобный день на следующую неделю.

Итак, на неделе 03.06-07.06 по голосованию победила пятница, но в пятницу Николай Николаевич увы, не сможет.

Поэтому так - на этой неделе предлагаем вторник, но только, если сейчас в комментариях запишется больше двух желающих.

Ждем подтверждения.

У нас 20-го ГОС по математике, поэтому 19 - это не самое удобное время. Во вторник нет возможности сдавать?

Меня на этой неделе вообще нет в Москве, попробуйте написать Николаю Николаевичу, может он сможет приехать во вторник (хотя не планировал, поэтому заявлена среда).

Можно сделать опрос про дни сдачи на следующей неделе?

В четверг у нас устный гос, поэтому в четверг не сможем. А в пятницу только часть группы может, так как у остальных пересдачи по экзаменам в МФТИ.

Насколько мы поняли, в пятницу у подавляющего большинства лекции весь день. В пятницу вебинар отменяется, будет на следующей неделе, не в пятницу.

Кто не смог посмотреть вживую - выложен конспект и видео вебинара (пока драфт, вечером улучшу).

Пожалуйста, проверьте, правильно ли проставлены баллы за задачи. Несколько моих задач помечены как решенные, но не добавлены баллы в таблицу - Полиномиальный в среднем алгоритм для SAT/Задачи/ex-sat-dynp-bad-data, Полиномиальный в среднем алгоритм для SAT/Задачи/ex-sat-dynp-good-data, MAX-SAT: вероятностное округление/Задачи/MAX-3ESAT (точнее баллы добавлены, но другому человеку в предыдущую строку в таблице).

У меня тоже вопрос - куда-то пропало мое решение задачи Формально об алгоритмах. Вычислительные модели/Задачи/ex-lost от 7 декабря. Оно не перенесено в "проблемы" и сама задача не перенесена в "решенные". Значит ли это, что задача зачтена?

Все учтено. Просто сейчас «Категория:Решения» скрыта (она собственно была три месяца открыта, можно было свободно смотреть решения задач предыдущим курсом), и вы перестаете видеть свое решение.

Задача не была перенесена в «Решеные» сразу, ибо там проверял несколько разных решений.

Еще у меня не добавлено баллов за задачу Формально об алгоритмах. Вычислительные модели/Задачи/ex-union-decideable-decideable, которую вы пометили как решенную.

Во время вебинара Вы перенесли мою задачу MAX-SAT: дерандомизация/Задачи/shell-game/Решение Cандуляну Любовь в категорию решенные задачи, но не учли это в таблице. Прошу учесть эту задачу.

А до скольки он примерно будет? Если я захочу опаздать, то на сколько можно?

Ну, лучше не опаздывать.

На сколько минут можно опоздать на экзамен? Просто у нашей группы в этот день с 10 до 11:30 другой экзамен на ИСПе и может он затянется.

Ну, после НГ приходите. К тому же 5я группа, в некотором смысле уже сталкивалась с схожим курсом (хотя в тот раз мы пыталась сделать упор на практику, и реализовать какие-нибудь живые проекты), и проблем со сдачей не будет.

Скорее у нас до часа будет сдача, по крайней мере так нам обещал преподаватель.

Два экзамена в один день — это в любом случае неправильно.

Здравствуйте, а можно как-нибудь записаться ещё? Я немного опоздал.

После НГ будет еще сдача. Слишком много народу — больше десятка — тоже неудобно.

А можно тоже записаться?

После НГ будет еще сдача. Слишком много народу — больше десятка — тоже неудобно (нам).

Это единственный вариант сдавать в январе? Может лучше перенести на 9 или другой рабочий день. Многие не в Москве и расчитывают возвращаться именно к рабочим дням.

Деканат просил сдать до 10 января. 9го я не могу. Дальше будет видно.

Т.е. сдавать будет можно и после 10го, только тогда придется озаботится «отрывными».

Если кто еще хочет сдавать — договаривайтесь с Николаем Николаевичем Кузюриным о времени, и берите в деканате отрывной.

А почему в пятницу? У нас же обычный базовый день - четверг. К тому же в пятницу у нас досрок по методам оптимизации.

Я предлагаю те дни, когда могу. Приедет Николай Николаевич — будут еще и другие. Важное — НЕ ЗАПИСЫВАЙТЕСЬ на те дни, когда вам не удобно. Вот вы сказали, что у вас — экзамен по оптимизации в пятницу, и при этом записались. Не надо этого делать.

Я таким образом пытаюсь понять, когда вам удобно.

Гм, ну я записался, т.к предпочитаю сначала сдать алгоритмы, и не идти на досрок, а сдавать опты во время обычного экзамена.

Хотя, все-таки я пойду на досрок и не поеду в пятницу. Поэтому в графе опроса да -1, в графе нет +1

Я дико извиняюсь, но завтра я точно не смогу приехать. А значит остается ровно 2 человека.

Я тоже дико извиняюсь, т.к. из-за личных дел завтра не получается приехать. Скажите, если прийти 3 июля, то насколько можно опоздать?

Ну, больше чем на час наверно не стоит.

Еще раз обращаю внимание — сдавать можно до конца экзаменационной сессии, спешки «любой ценой» быть не должно.

А со скольки и до скольки по времени будет приём? А то, что со второго числа у нас уже экзаменационная сессия, это никак не влияет? Я просто думал, что кто не сдал до лета, тот будет сдавать уже осенью.

  • «Сбор в 11:00 в 301, как обычно. »
  • Как пойдет. Но обычно небыстро, так что на этот день других сдач не планируйте.
  • Это экзамен, и разумеется, его можно сдавать до конца экзаменационной сессии. Просто мы шли вам навстречу, и предлагаем удобные вам даты.

Стас, вы обещали мне задачу на отл, можно получить ее ДО пятницы?

Я предлагал вам дополнительные задачи на дом для получения отличной оценки. Но вы за ними не обратились (Мои контакты опубликованы, ваши мне неизвестны и я не телепат).

Теперь вы проявились (хотя email и все такое на вашей страничке не указаны), и я предлагаю вам решить любые три задачи из Категория:P1401 (я постараюсь ее продолжать наполнять, может пригодится еще кому-нибудь для этих целей).

Скажите пожалуйста, до скольких вы будете в пятницу?

Не знаю, надеюсь недолго. Не рассчитывайте меня застать позже назначенного срока.

Ждал полтора часа, страйк записавшимся и неявившимся:


До конца субботы записывайтесь на вторник - если не наберется троих, отменяется, и возможно устроим сдачу в следующий четверг. Следите за объявлениями.

У нас 18ого устные урматы, очень много к ним готовить. А что если в четверг этой недели?

Николай Николаевич будет в понедельник или вторник. Может тогда на понедельник?

Во вторник прием будет. Будет Николай Николаевич и возможно Стас Фомин.

Меня не будет, поскольку очень мало народу едет.

Следующий раз будет в четверг, 26 июня, 11:00, записывайтесь. Или, если у вас столкновение с другим экзаменом — пишите сразу.

Итак, пять приемов дифференцированного зачета (в этом году этот курс оказалось оценивается зачетом) прошли, ведомости сданы, оставшиеся (Горелышев, Плетенец, Аришин…):

Вы же говорили, что сдавать можно до конца экзаменационной сессии.

Можно. Договаривайтесь с НН и сдавайте. В этом году курс оказался зачетом, ведомости деканат требует сейчас.

Будем считать, что отрезки заданы парами (a,b) - где числа есть соответственно начало и конец отрезка. Пусть дано n отрезков. за O(n*logn) сортируем отрезки сначала по a, затем по b. (будет два массива, отдельно друг от друга.) найдем множество точек I (принадлежность точки множеству I обозначим () = I) s=2 for i = 1 to n, : (если i = 1,b1=I  ; если b(i)>a(s) s++; если b(i)<= a(s) пометить b(s) И i+ = s ; s++ )


Суть алгоритма - конец отрезка уже помечен, если он больше начала другого отрезка - другой отрезок тоже помечен, идем до тех пор, пока не дойдем до того, что конец отрезка меньше начала следующего, далее помечаем конец этого самого найденного отрезка, а все остальные уже считаются помеченными - каждый отрезок просматривается 1 раз.


Сложность алгоритма - сортировка за O(nlogn) + пометка за линейное время = сложность O(nlogn)

из одного состояния по i символу можно перейти m+1 способами (можем остаться на месте). Всего символов n+1. Значит, для данного состояния необходимо задать по одному переходу через каждый символ - (m+1)^(n+1). столько же будет для всех остальных состояний, которых m+1 - (m+1)^(n+1)*...*(m+1)^(n+1)= (m+1)^((m+1)(n+1)) (две машины отличаются, если хотя бы в 1 состоянии по хотя бы 1 символу разный переход)

А тем, у кого отл(8) автоматом, нужно записываться?

Желающим получить отл(8) автоматом можно просто зачетку передать?

Пусть слово w = ab, a /in L1, b /in L2.

Пусть |w| = n. Разбиваем w на подслова разными способами, запускаем первые подслова на машине, принимающей L1, если L1 выдала ДА, запускаем второе подслово на L2.

Рано или поздно разобьем слово на ab, обе машины скажут ДА, слово примется. Если слово не лежит в конкантенации, значит перебрав все варианты разбиения

не получим L1=1 && L2=1 - делаем вывод, что слово не принадлежит конкантенации.

Конкантенация разрешима

Вход - набор объектов и характеристики рюкзака. Длина входа - количество предметов. Предметов n штук

По Участник:VasyukovaMarya/задача 7 → Очень круто. Но задача была сильно проще — «задача распознавания гамильтоновых графов (т.,е. графов, содержащих гамильтонов цикл) принадлежит NP». NP! Не NPC! Задача ставилась сильно проще! Но все равно, труд будет оплачен большими баллами!

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