Computer Science семинар (осень 2011)

Общая информация
Семестросень 2011
Дата начала18.09.2011
Количество пар12
Язык курсарусский
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Privacy of profile based ad targeting (Александр Смаль, ПОМИ РАН)
(18.09.2011 - 15:35 - 17:10)

В 2010 году была показана практическая возможность использования таргетирования рекламных объявлений в социальных сетях с целью получения скрытой информации о пользователе. Можно показать, что при некоторых сильных предположениях о модели данных в профилях пользователей, можно гарантировать безопасность скрытых данный. В докладе будет расcказано о том, почему в отсутствии этих предположений таргетирование рекламы несовместимо с обеспечением безопасности скрытой информации пользователя. В конце доклада будет рассказано об интернатуре в Microsoft Research, где докладчик и занимался исследованиями по данной теме. http://www.lektorium.tv/lecture/?id=13371
2. Вычислительная сложность формальных грамматик (Александр Охотин, Университет Турку, Финляндия)
(25.09.2011 - 15:35 - 17:10)

Формальные грамматики — это прикладная логика, предназначеная для задания синтаксиса языков, Применение грамматик тесно связано с алгоритмами для распознавания тех или иных свойств языка — таких, как принадлежность данной строки языку, или непустота языка, заданного данной грамматикой. Разные семейства грамматик отличаются не только своими выразительными возможностями, но и вычислительной сложностью задач распознавания свойств. В докладе будут описаны известные разновидности формальных грамматик и дан обзор результатов о сложности основных задач для этих грамматик. http://www.lektorium.tv/lecture/?id=13380
3. Язык программирования Kotlin (Андрей Бреслав, JetBrains)
(02.10.2011 - 15:35 - 17:10)

Летом 2011 компания JetBrains объявила о разработке проекта Kotlin — статически типизированного ОО-языка программирования, компилируемого для платформы Java и предназначенного для использования промышленными разработчиками ПО. При разработке мы руководствуемся следующими требованиями к языку: он должен

  • быть совместим с Java “в обе стороны”: код на Java можно вызывать из кода на Kotlin, и наоборот;
  • компилироваться как минимум так же быстро как Java, это требование особенно важно для больших проектов;
  • быть безопаснее Java, то есть статически гарантировать отсутствие ошибок, типичных для программ на Java;
  • быть лаконичнее Java. Всем известны обвинения Java в излишней “церемониальности”: код на этом языке изобилует “само собой разумеющимися” конструкциями, загромождающими программы;
  • и, наконец, при сохранении необходимой выразительности, новый язык должен быть значительно проще Scala, нашего основного конкурента, поскольку сложность освоения — очень существенный фактор.

Как легко догадаться, интегрированная среда разработки (IDE) для нового языка создается параллельно с компилятором, “с первого дня”, так что пользователи даже самых ранних версий могут рассчитывать на достойную инструментальную поддержку.

Выход публичной бета-версии компилятора залпанирован на конец 2011 года. В настоящее время доступно описание языка, размещенное на странице проекта: http://jetbrains.com/kotlin.

В докладе будет представлен обзор дизайна языка и его основных возможностей. В частности, будут обсуждаться

  • система типов: отслеживание нулевых ссылок, автоматическое приведение типов, обобщенные типы и вариантность,
  • модель наследования,
  • внешние функции,
  • функции высших порядков,
  • создание DSL.

Предполагается знакомство аудитории с Java, C# или C++.

http://www.lektorium.tv/lecture/?id=13381
4. Выделение и сопоставление особых точек в обработке изображений (Александр Мордвинцев, СПбГУ ИТМО, НИИ НКТ)
(09.10.2011 - 15:35 - 17:10)

Развитие методов поиска и сопоставления устойчивых локальных особенностей изображения позволило добиться прогресса во многих задачах компьютерного зрения. Примерами таких задач являются:
  • сшивка панорам и аэрофотоснимков (image stitching);
  • восстановление трехмерной структуры сцены по снимкам с разных ракурсов (structure from motion);
  • поиск и распознавание объектов.
В докладе будет представлен обзор:
  • детекторов и дескрипторов особых точек (включая аффинно-инвариантные и адаптированные для приложений реального времени);
  • задач, решаемых при помощи сопоставления точеных особенностей.
http://www.lektorium.tv/lecture/?id=13429
5. Устойчивая реализация алгоритмов вычислительной геометрии (Антон Ковалев, Транзас, СПбГУ ИТМО)
(23.10.2011 - 15:35 - 17:10)

Хорошо описанный в предположении абсолютной точности всех вычислений алгоритм в некоторых случаях перестает работать из-за накапливающейся погрешности вычислений с плавающей точкой. В то же время нельзя заменить вычисления с плавающей точкой рациональной арифметикой(когда каждое число представляется в виде рациональной дроби с длинным числителем и длинным знаменателем) из соображений производительности.

Существует несколько известных приемов эффективной организации точных вычислений. Об одном из этих приемов, фильтрованном вычислении предикатов, и пойдет речь в данном докладе.

Список ключевых тем для обсуждения:

  • особенности арифметики с плавающей точкой;
  • подсчет погрешности арифметических выражений;
  • особенности организации интервальной арифметики (interval arithmetic);
  • арифметика произвольной точности на числах с плавающей точкой (adaptive precision floating-point arithmetic).

http://www.lektorium.tv/lecture/?id=13430
6. Практическое применение методов машинного обучения (Игорь Кураленок, Яндекс, СПбГУ)
(30.10.2011 - 15:35 - 17:10)

Доклад посвящен практическому применению методов машинного обучения для решения задач Яндекса. В частности большое внимание будет уделено проблеме ранжирования, современным стендам для исследования методов обучения ранжированию и перспективы дальнейшего развития данной области. Также, в контексте обучения будут поставлены рассмотрены проблемы шума в экспертных оценках, СЕО эффектах и тому подобных нюансах построения ранжирования для работы в реальных условиях. Для понимания лекции необходим начальный уровень знаний в области машинного обучения. http://www.lektorium.tv/lecture/?id=13431
7. Экпертный форум по компьютерным наукам (Николай Чабановский, ХэшКод)
(20.11.2011 - 14:35 - 15:35)

В 2010 году в России был открыт ХэшКод — первый сайт сети экспертных форумов вопросов и ответов. Востребованность сети обусловила рост количества тематических форумов. На повестке дня открытие форума по математическим, компьютерным наукам. Форумы характеризуются

  • качественной платформой,
  • отсутствием рекламы и спама,
  • сильной самоцензурой,
что позволяет создать виртуальное научное сообщество, где
  • происходит взаимное обучение,
  • темы являются мини-публикациями,
  • личный профиль как визитная карточка.

    В докладе будет представлен обзор основных особенностей системы, текущее состояние и прогнозы развития. У аудитории будет возможность принять прямое и непосредственное участие в развитии экспертного форума вопросов и ответов по математическим, компьютерным наукам.

    8. Безопасность веб-приложений: введение (Бен Лившиц, Microsoft Research)
    (04.12.2011 - 11:15 - 12:50)

    Лекция является введением в безопасность веб приложений. Рассматриваются распространенные типы уязвимостей в современных веб приложениях и способы обнаружения, предотвращения и борьбы с ними.
    9. Вредоносное программное обеспечение/Malware: введение (Бен Лившиц, Microsoft Research)
    (04.12.2011 - 13:00 - 14:35)

    Лекция является введением в тематику вредоносного программного обеспечения или malware. Будут обсуждаться вирусы и черви (worms), а также способы от защиты от них. Будет уделено особое внимание недавним результатам.
    10. Поиск совершенных паросочетаний в регулярных двудольных графах (Михаил Капралов, Стэнфорд)
    (11.12.2011 - 11:15 - 12:50)

    Задача поиска совершенного паросочетания в регулярном двудольном графе — классическая задача с приложеними к реберной раскраске, маршрутизации и задачам планирования, также связанная с задачей построения разложения Биркгофа-фон Неймана бистохастических матриц. В результате ряда улучшений в 2001 г. для этой задачи был получен алгоритм с линейным временем работы.

    В первой части доклада будет рассмотрена задача поиска совершенного паросочетания в регулярных двудольных графах за сублинейное время. Мы покажем, что использование вероятностных методов позволяет получить неожиданно эффективные алгоритмы для этой задачи. С другой стороны, мы покажем, что любому детерминированному алгоритму требуется как минимум линейное время.

    В второй части доклада будет рассмотрена следующая коммуникационная задача: Алиса знает граф $ G_A=(P, Q, E_A) $ , Боб знает граф $ G_B=(P, Q, E_B) $, где $ |P|=|Q|=n $. Алиса может послать Бобу сообщение $ m $, зависящее только от $ G_A $, после чего Боб должен выдать паросочетание $ M\subseteq 
E_A\cup E_B $. Минимальный размер сообщения, которое позволяет Бобу достичь $ 1-\e $ приближения максимального паросочетания в $ G_A\cup G_B $ — это коммуникационная сложность приближения паросочетания с одним раундом, которая также дает нижнюю оценку на однопроходную потоковую сложность приближения максимального паросочетания.

    В данной работе исследуется качество приближения, которое можно достичь при помощи сообщения (или памяти) размера $ \tilde O(n) $. Ранее для обеих задач было известно только приближение с коеффициентом $ 1/2 $.

    Мы опишем коммуникационный протокол со сложностью $ \tilde O(n) $, при помощи которого достигается приближение с коэффициентом $ 2/3 $, а также покажем, что существенно лучшее приближение имеет сложность $ n^{1+\Omega(1/\log\log n)} $.

    Данный коммуникационный протокол также позволяет получить детерминированный однопроходный потоковый алгоритм с памятью $ O(n) $, дающий приближение $ 1-1/e $ для случая, когда вершины на одной стороне графа появляются в потоке вместе со всеми инцидентными ребрами.

    Совместная работа с Ашишем Гоэлем и Сандживом Канна.

    11. Алгоритмы 3D-трэкинга и восстановления геометрии сцены (Роман Белов, СПбГУ)
    (11.12.2011 - 13:00 - 14:35)

    Восстановление траектории движения камеры является ключом к созданию современных визуальных эффектов. Будут рассмотрены основные коммерческие продукты и математические методы, лежащие в их основе.
    Ваша оценка: Пусто Средняя: 4 (4 голосов)
    Share |