Открытие весеннего семестра 2010-го года в Computer Science клубе состоится в воскресенье, 31-го января. В 12-00 будет проведено орг. собрание, на котором будет рассказано об истории создания клуба, предстоящих курсах, кафедре математических и информационных технологий АФТУ РАН, дипломах о дополнительном образовании, Академии современного программирования, международных студенческих школах по Computer Science, физико-математическом клубе при ПОМИ, а также Школе Microsoft по структурам данных и алгоритмам, которая пройдёт в Санкт-Петербурге с 8-го по 14-е августа. После собрания Андрей Гольдберг (Microsoft Research) прочтёт лекцию о нахождении кратчайших путей в графе (аннотация приведена ниже, доклад будет на русском).

Курсы весеннего семестра 2010-го года

• Highway Dimension and Provably Efficient Shortest Path Algorithms (1 пара)
  Андрей Гольдберг, Microsoft Research
• Десятая проблема Гильберта. Решение и применения в информатике (10 пар)
  Юрий Владимирович Матиясевич, ПОМИ РАН
• Виртуализация и виртуальные машины (12 пар)
  Н. Иготти, Sun Microsystems
• Введение в бионформатику (10 пар)
  Михаил Капущевский, European Bioinformatics Institute
• Тестирование на основе моделей (3 пары)
  Виктор Кулямин, ИСП РАН
• Дополнительные главы теории паросочетаний (5 пар)
  Максим Бабенко, МГУ
• Алгоритмы на графах и обработка изображений (3 пары)
  Виктор Лемпицкий, University of Oxford
• Современные методы автоматической формальной верификации аппаратного обеспечения (2 пары)
  Арист Александрович Кожевников, ПОМИ РАН
• а также курсы профессоров Университета Лугано (информация появится позже)

Андрей Гольдберг (Microsoft Research), Highway Dimension and Provably Efficient Shortest Path Algorithms

Аннотация. Computing driving directions has motivated many shortest path heuristics that answer queries on continental scale networks, with tens of millions of intersections, in real time, and with very low storage overhead. We give the first theoretical analysis of several underlying algorithms on a non-trivial class of networks. To do this, we introduce the notion of highway dimension. Our analysis works for networks with low highway dimension and gives a unified explanation of good performance for several seemingly different algorithms.

О лекторе. Andrew Goldberg is a Principal Researcher at Microsoft Research – Silicon Valley. His research interests include design, analysis, and experimental evaluation of algorithms, data structures, algorithm engineering, and computational game theory. Goldberg received his Ph.D. degree in Computer Science from M.I.T. in 1987. He also holds a B.S. degree from M.I.T. and an M.S. degree from U.C. Berkeley. Before joining Microsoft, he worked for Stanford University, NEC Research Institute, and InterTrust STAR Lab. His graph algorithms are taught in computer science and operations research classes and their implementations are widely used in industry and academia. Goldberg received a number of awards, including the NSF Presidential Young Investigator Award, the ONR Young Investigator Award, and the Mathematical Programming Society A.W. Tucker Prize. He is an ACM Fellow.

О клубе

Computer Science клуб при ПОМИ РАН создан в сентябре 2007-го года при поддержке Антона Лиходедова,на сегодняшний день поддержку клубу оказывают Антон Лиходедов (Deutsche Bank) и Юрий Богданов (Уралкалий).Основная цель клуба — предоставить возможность студентам Санкт-Петербурга получить образование в области Theoretical Computer Science.Лекции читают петербургские и иностранные преподаватели по субботам и воскресеньям в ПОМИ РАН (Фонтанка, 27). По основным курсам проводятся экзамены, оценки за которые могут быть зачтены формально. Вход на лекции свободный.Дополнительная информация о клубе(расписание занятий, описание курсов, слайды и видеозаписи лекций, информация о преподавателях) доступна с сайта клуба:http://logic.pdmi.ras.ru/~infclub.

Ссылки: сайт клуба, расписание, RSS новостей, трансляция новостей в ЖЖ, группа вконтакте, встреча вконтакте, Google-группа, Google-календарь.