Сложность вычислений ФПМИ
Open in Telegram
764
Subscribers
No data24 hours
No data7 days
No data30 days
Posts Archive
Ещё завтра открывается мой курс по сложности вычислений на платформе "Открытое образование": https://openedu.ru/course/mipt/COMPLEX/ В основном это подмножество того, что мы здесь проходим, но, может быть, какие-то вещи изложены более структурированно и с подготовленными картинками. Например, там записан разбор задачи о квадратичной сложности проверки на палиндром для одноленточной машины. Так что сдавать его там было бы странно, а послушать отдельные фрагменты может быть полезно.
Во вторник, 10 ноября, в 18:30 на межкафедральном семинаре пройдёт интересный доклад Рене Андреасовича ван Беверна про историю открытия алгоритма Кристофидеса. Краткий анонс:
Одним из самых фундаментальных результатов в области комбинаторной оптимизации является полиномиальный 3/2-приближённый алгоритм для метрической задачи коммивояжёра. Он был представлен Никосом Кристофидесом в 1976 г. и хорошо известен под названием «алгоритм Кристофидеса». В последнее время некоторые авторы стали называть его «алгоритмом Кристофидеса-Сердюкова», утверждая, что он был опубликован независимо в СССР в 1978 г. В докладе будет рассказано об историческом контексте, в котором произошло параллельное и почти одновременное открытие ставшего всемирно известным алгоритма.
Полные тезисы в приложенном файле.
Ссылка для подключения: https://zoom.us/j/98824014290?pwd=V2FPaVRWYWI5MFRJVzVlcTd0RStoQT09
Идентификатор конференции: 988 2401 4290
Код доступа: 022474
