Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ)/Лекции весеннего семестра 2013 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показаны 4 промежуточные версии этого же участника)
Строка 4: Строка 4:
 
* [[Как смотреть многопоточное MKV-видео]]
 
* [[Как смотреть многопоточное MKV-видео]]
  
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv|1:23:00}}
+
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv|1:23:15}} — приближенные алгоритмы с гарантированной точностью, жадные алгоритмы в задаче о покрытии.
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-02-28-lectures.uncut.mkv|0:00:22}}
+
 
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-03-07-lectures.uncut.mkv|0:03:31}}
+
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv|2:12:00}} — временная и пространственная сложность алгоритмов.
 +
 
 +
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv|2:36:30}} — NP-полнота и сводимости.
 +
 
 +
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-02-28-lectures.uncut.mkv|0:00:22}} — недетерминированные машины Тьюринга, NTIME, NP-полнота, NP-полнота сапера
 +
 
 +
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-02-28-lectures.uncut.mkv|1:19:30}} — метрическая задача коммивояжера, алгоритм Кристофидеса.
 +
 
 +
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-03-07-lectures.uncut.mkv|0:03:31}} — вероятностная проверка тождеств.
 +
 
 +
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-03-07-lectures.uncut.mkv|0:37:40}} — вероятностное округление для MAX-SAT
  
  
 
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-03-13-lectures.uncut.mkv|0:03:59}} — криптография, 4 курс
 
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-03-13-lectures.uncut.mkv|0:03:59}} — криптография, 4 курс
  
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-03-14-lectures.uncut.mkv|0:01:10}}
+
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-03-14-lectures.uncut.mkv|0:01:10}} — Дерандомизация MAX-SAT
 +
 
 +
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-03-14-lectures.uncut.mkv|0:55:40}} — Вероятностные классы сложности сложности RP/ZPP.
  
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-03-20-lectures.uncut.mkv|2:02:34}}
+
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-03-20-lectures.uncut.mkv|2:02:34}} — Вероятностные классы сложности BPP
  
  
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-03-21-lectures.uncut.mkv|1:01:01}}
+
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-03-21-lectures.uncut.mkv|0:00:20}} — Полиномиальность в среднем, полиномиальный в среднем алгоритм для SAT.
  
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-03-28-lectures.uncut.mkv|1:08:28}}
+
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-03-28-lectures.uncut.mkv|0:00:30}} — Рюкзак. Жадный, квазиполиномиальный и PTAS-алгоритм
  
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-04-04-lectures.uncut.mkv|0:01:12}}
+
* {{VideoIspras|channels/ispras.ru/lectures/2013/2013-04-04-lectures.uncut.mkv|0:01:12}} — BPP, полиномиальная иерархия, схемная сложность.

Текущая версия на 05:45, 27 марта 2014


Записанное видео лекций Николая Николаевича Кузюрина и Стаса Фомина, за весенний семестр 2013 года.

  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv1:23:15 — приближенные алгоритмы с гарантированной точностью, жадные алгоритмы в задаче о покрытии.
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv2:12:00 — временная и пространственная сложность алгоритмов.
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv2:36:30 — NP-полнота и сводимости.
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-28-lectures.uncut.mkv0:00:22 — недетерминированные машины Тьюринга, NTIME, NP-полнота, NP-полнота сапера
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-28-lectures.uncut.mkv1:19:30 — метрическая задача коммивояжера, алгоритм Кристофидеса.
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-07-lectures.uncut.mkv0:03:31 — вероятностная проверка тождеств.
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-07-lectures.uncut.mkv0:37:40 — вероятностное округление для MAX-SAT


  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-13-lectures.uncut.mkv0:03:59 — криптография, 4 курс
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-14-lectures.uncut.mkv0:01:10 — Дерандомизация MAX-SAT
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-14-lectures.uncut.mkv0:55:40 — Вероятностные классы сложности сложности RP/ZPP.
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-20-lectures.uncut.mkv2:02:34 — Вероятностные классы сложности BPP


  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-21-lectures.uncut.mkv0:00:20 — Полиномиальность в среднем, полиномиальный в среднем алгоритм для SAT.
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-28-lectures.uncut.mkv0:00:30 — Рюкзак. Жадный, квазиполиномиальный и PTAS-алгоритм
  • http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-04-04-lectures.uncut.mkv0:01:12 — BPP, полиномиальная иерархия, схемная сложность.