Лекция Михаила Тихомирова

Cегодня, в Актовом зале МФТИ, с 18:30 до 20:00, пройдёт лекция в рамках межкафедрального семинара кафедры дискретной математики «Графы-экспандеры и их применения».
Лекцию проведет научный сотрудник кафедры дискретной математики Физтех-школы ПМИ, тренер ЦРИТО, методист Зимней компьютерной школы Михаил Тихомиров.

Рассказ будет посвящён графам-экспандерам, их свойствам и применениям. В широком смысле (мульти)граф является экспандером, если любая его небольшая область имеет сравнительно большую окрестность. На лекции обсудят непосредственные применения экспандеров в таких задачах, как построение эффективных сетей и самоисправляющих кодов и «экономия» случайных битов в рандомизированных алгоритмах. Кроме этого, речь пойдет про связь расширительной величины графа с его спектральными характеристиками и случайные блуждания в экспандерах.

Поделиться в социальных сетях: