Сложность вычислений ФПМИ
前往频道在 Telegram
764
订阅者
无数据24 小时
无数据7 天
无数据30 天
帖子存档
Ещё завтра открывается мой курс по сложности вычислений на платформе "Открытое образование": https://openedu.ru/course/mipt/COMPLEX/ В основном это подмножество того, что мы здесь проходим, но, может быть, какие-то вещи изложены более структурированно и с подготовленными картинками. Например, там записан разбор задачи о квадратичной сложности проверки на палиндром для одноленточной машины. Так что сдавать его там было бы странно, а послушать отдельные фрагменты может быть полезно.
Во вторник, 10 ноября, в 18:30 на межкафедральном семинаре пройдёт интересный доклад Рене Андреасовича ван Беверна про историю открытия алгоритма Кристофидеса. Краткий анонс:
Одним из самых фундаментальных результатов в области комбинаторной оптимизации является полиномиальный 3/2-приближённый алгоритм для метрической задачи коммивояжёра. Он был представлен Никосом Кристофидесом в 1976 г. и хорошо известен под названием «алгоритм Кристофидеса». В последнее время некоторые авторы стали называть его «алгоритмом Кристофидеса-Сердюкова», утверждая, что он был опубликован независимо в СССР в 1978 г. В докладе будет рассказано об историческом контексте, в котором произошло параллельное и почти одновременное открытие ставшего всемирно известным алгоритма.
Полные тезисы в приложенном файле.
Ссылка для подключения: https://zoom.us/j/98824014290?pwd=V2FPaVRWYWI5MFRJVzVlcTd0RStoQT09
Идентификатор конференции: 988 2401 4290
Код доступа: 022474
