Сложность вычислений ФПМИ
Відкрити в Telegram
1 105
Підписники
Немає даних24 години
+17 днів
+130 днів
Архів дописів
Наконец готова дорешка по к/р 1. Дедлайн 5 января. Upd: в файле была ошибка, он заменён, задачи поменялись, так что скачайте новую версию
Ещё завтра открывается мой курс по сложности вычислений на платформе "Открытое образование": https://openedu.ru/course/mipt/COMPLEX/ В основном это подмножество того, что мы здесь проходим, но, может быть, какие-то вещи изложены более структурированно и с подготовленными картинками. Например, там записан разбор задачи о квадратичной сложности проверки на палиндром для одноленточной машины. Так что сдавать его там было бы странно, а послушать отдельные фрагменты может быть полезно.
https://drive.google.com/file/d/1v-96l40Dfva6CZmVUuOk3n8gWtYcuFs_/view?usp=sharing - запись лекции 11.11
Во вторник, 10 ноября, в 18:30 на межкафедральном семинаре пройдёт интересный доклад Рене Андреасовича ван Беверна про историю открытия алгоритма Кристофидеса. Краткий анонс:
Одним из самых фундаментальных результатов в области комбинаторной оптимизации является полиномиальный 3/2-приближённый алгоритм для метрической задачи коммивояжёра. Он был представлен Никосом Кристофидесом в 1976 г. и хорошо известен под названием «алгоритм Кристофидеса». В последнее время некоторые авторы стали называть его «алгоритмом Кристофидеса-Сердюкова», утверждая, что он был опубликован независимо в СССР в 1978 г. В докладе будет рассказано об историческом контексте, в котором произошло параллельное и почти одновременное открытие ставшего всемирно известным алгоритма.
Полные тезисы в приложенном файле.
Ссылка для подключения: https://zoom.us/j/98824014290?pwd=V2FPaVRWYWI5MFRJVzVlcTd0RStoQT09
Идентификатор конференции: 988 2401 4290
Код доступа: 022474
