Прошел семинар лаборатории: "Эффективные алгоритмы для решения некоторых задач вычислительной геометрии и комбинаторной оптимизации"

Прошел семинар лаборатории теоретической информатики 28 ноября.

На семинаре выступил Каймаков Кирилл, аспирант, Нижний Новгород

На семинаре было рассказано, что, структуры данных играют ключевую роль в оптимизации алгоритмов, позволяя эффективно хранить и получать доступ к информации. Правильный выбор структуры данных может значительно сократить время выполнения алгоритма, особенно при обработке больших объемов данных. В докладе на основе эффективного использования структур данных и комбинирования алгоритмических приемов предлагаются несколько алгоритмов для решения некоторых задач комбинаторной оптимизации и вычислительной геометрии, улучшающих ранее известные решения. В частности, в некотором смысле улучшаются результаты Габоу-Бентли-Тарджана для вычисления минимального остовного дерева на точечных данных в l1-норме и Рамасвами-Орлина-Чакраварти для анализа чувствительности оптимальных решений в задаче о максиминном пути. Это доклад автора по подготовленной им кандидатской диссертации.

Запись семинара представлена ниже