Сложность вычислений ФПМИ
Ir al canal en Telegram
764
Suscriptores
Sin datos24 horas
Sin datos7 días
Sin datos30 días
Archivo de publicaciones
Ещё завтра открывается мой курс по сложности вычислений на платформе "Открытое образование": https://openedu.ru/course/mipt/COMPLEX/ В основном это подмножество того, что мы здесь проходим, но, может быть, какие-то вещи изложены более структурированно и с подготовленными картинками. Например, там записан разбор задачи о квадратичной сложности проверки на палиндром для одноленточной машины. Так что сдавать его там было бы странно, а послушать отдельные фрагменты может быть полезно.
Во вторник, 10 ноября, в 18:30 на межкафедральном семинаре пройдёт интересный доклад Рене Андреасовича ван Беверна про историю открытия алгоритма Кристофидеса. Краткий анонс:
Одним из самых фундаментальных результатов в области комбинаторной оптимизации является полиномиальный 3/2-приближённый алгоритм для метрической задачи коммивояжёра. Он был представлен Никосом Кристофидесом в 1976 г. и хорошо известен под названием «алгоритм Кристофидеса». В последнее время некоторые авторы стали называть его «алгоритмом Кристофидеса-Сердюкова», утверждая, что он был опубликован независимо в СССР в 1978 г. В докладе будет рассказано об историческом контексте, в котором произошло параллельное и почти одновременное открытие ставшего всемирно известным алгоритма.
Полные тезисы в приложенном файле.
Ссылка для подключения: https://zoom.us/j/98824014290?pwd=V2FPaVRWYWI5MFRJVzVlcTd0RStoQT09
Идентификатор конференции: 988 2401 4290
Код доступа: 022474
