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

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

1. Синтаксический анализ для "встроенных" языков (Андрей Бреслав, кафедра Высшей математики СПбГУ ИТМО)
(27.02.2011 - 15:35 - 17:10)

Разрабатывая программы Java, Python, PHP и т.д., мы зачастую используем несколько языков одновременно: в нашем коде на языке общего назначения, например, Java, встечаются вкрапления других языков, например, регулярные выражения, пути в файловой системе и другие URI, SQL-запросы, тэги XML и HTML. Особенно часто это происходит при разработке вэб-приложений и приложений уровня предприятия, то есть при выполнении работы, в которой, по многим оценкам, занято большинство программистов на планете.

Как происходит взаимодействие программы на Java и кода на SQL или HTML? Очень часто "малый" язык используется внутри строковых литералов, например, при работе с базой данных с использованием стандартной библиотеки JDBC, SQL-запросы в программе на Java могут выглядеть так:

connection.prepareStatement("SELECT * FROM People" + whereClause);

Такой подход универсален: любой текстовый язык можно "встроить" в Java, заключив в двойные кавычки. Однако есть одна проблема: компилятор Java полностью игнорирует содержимое строковых литералов, и поэтому все ошибки (опечатки в именах, забытые скобки и т.д.) обнаруживаются только на стадии выполнения программы.

В докладе будет рассказано об алгоритмах, позволяющих статически (не запуская программу) гарантировать, что все строки в Java-программе, содержащие код на SQL или каком-то другом языке, не содержат синтаксических ошибок. Работа этих алгоритмов будет продемонстрирована примерах, заимствованных из реальных проектов. Также будут предложены возможные темы для бакалаврских и магистерских работ в данной области.

Работа выполнена в Университете Тарту и исследовательском центе STACC (Эстония) в соавторстве с А. Аннамаа и В. Вене.

Литература:
Обзорная статья по теме доклада: An interactive tool for analyzing embedded SQL queries, APLAS 2010, LNCS 6461, pp. 131-138, 2010. Препринт доступен без регистрации на домашней странице автора.

http://lektorium.tv/lecture/?id=13191
2. Вычислительная геометрия: иллюстрации (Кира Вадимовна Вяткина, Санкт-Петербургский государственный университет)
(06.03.2011 - 15:35 - 17:10)

В докладе будет рассмотрено несколько красивых алгоритмов вычислительной геометрии, на примере которых могут быть проиллюстрированы общие подходы, используемые в данной области. Цель доклада заключается в ознакомлении слушателей с некоторыми основными идеями и концепциями вычислительной геометрии; для понимания материала предварительных знаний не требуется. http://lektorium.tv/lecture/?id=13192
3. BrainStorm. Автоматизированная оптимизация аппаратно-программных архитектур (Андрей Бреслав, кафедра Высшей математики СПбГУ ИТМО)
(13.03.2011 - 15:35 - 17:10)

В докладе будут изложены результаты, полученные в ходе стажировки в Microsoft Research летом/осенью 2010 года под руководством Итана Джексона. Доклад посвящен применению технологий на основе SMT-солверов и машинного обучения к моделированию/автоматической разработке аппаратно-программных co-designs. В ходе стажировки моделировались планировщики ОС реального времени, протоколы передачи данных, драйверы и т.д., запускались полученные модели и собиралась статистика о том, насколько хорошо/плохо та или иная модель работает. Используя эту статистику, алгоритм машинного обучения определял, какие еще модели стоит попробовать. В результате удавалось среди огромного множества вариантов находить очень хорошие архитектуры, и, что самое интересное, автоматически определять, что именно делает их хорошими. http://lektorium.tv/lecture/?id=13193
4. Подструкурный поиск химических соединений в базах данных (Михаил Рыбалкин, ПОМИ РАН и GGA Software Services)
(01.05.2011 - 11:15 - 12:50)

Одной из задач в процессе разработки лекарств является задача поиска химических соединений, содержащих заданный фрагмент, в больших базах данных. Такие базы химических соединений содержат описание свойств, способы производства, результаты исследований, ссылки на статьи и другую связанную с данным веществом информацию. Сами молекулы задаются в виде своих структурных формул в виде помеченных графов. С формальной точки зрения задача поиска фрагмента химического соединения в другом соединении - это задача поиска изоморфного подграфа (subgraph isomorphism problem), которая является NP-полный. Обычно размер запроса (фрагмента молекулы) содержит не больше 20 вершин, а количество вершин в молекулах в базе около 100-200, и проверка наличия заданного фрагмента для конкретной молекулы занимает небольшое время (около 0.1-1 мс). Но количество молекул в современных базах данных достигает 40 млн., и поэтому явная проверка наличия изоморфного подграфа для каждого соединения в базе займет очень большое время. Для эффективного поиска используются различные критерии для отсеивания графов, которые заведомо не содержат заданный фрагмент. Одним из таких критериев является проверка на основе "битовых отпечатоков" (fingerprints), в которых каждый бит соответствует какому-либо свойству графа.
В докладе будет рассмотрены все промежуточные задачи и основные алгоритмы, которые позволяют производить быстрый поиск химических соединений, а именно:
1. Алгоритм VF2 для задачи поиска изоморфного подграфа [1] и его возможные улучшения
2. Способы построения и организации хранения "битовых отпечатков" молекул.
3. Метод реверсивного поиска [2] и его применение для перебора всех подграфов и поддеревьев определенного размера для заданного графа для построения битовых отпечатков.
В докладе также будет освещены некоторые альтернативные подходы к данной задаче.

Литература:
1. A (sub)graph isomorphism algorithm for matching large graphs; Cordella, L.P., Foggia, P., Sansone, C.,Vento, M., 2004
2. Reverse Search for Enumeration; David Avis, Komei Fukuda, 1993

http://www.lektorium.tv/lecture/?id=13291
5. Комбинаторные задачи и алгоритмы сравнительного анализа геномов (Максим Алексеев, University of South Carolina)
(01.05.2011 - 15:35 - 17:10)

Современные проекты по секвенированию геномов множества различных организмов дали толчок новым исследованиям в области сравнительного анализа геномов по разработке эффективных алгоритмов для получения важной информации о генетических и филогеномных вариациях. Одними из наиболее драматических эволюционных изменений в геномах являются перестройки геномов, перемешивающие генетический материал, и поэтому очень важно понимать их механизм и уметь восстанавливать последовательность таких эволюционных событий (т.н. эволюционную историю) между интересующими геномами. В этом обзорном докладе я опишу несколько наиболее спорных и жарко обсуждаемых вопросов в эволюционной биологии (модели эволюции хромосом, филогеномика млекопитающих, предсказание будущих перестроек генома человека) и сформулирую соответствующие им комбинаторные проблемы (анализ перестроек и точек излома геномов, реконструирование геномов предков). Я также расскажу о новых теоретических и алгоритмических результатах (2009-2011 годов) в решении этих проблем и их биологической интерпретации.
6. Оценки длины слов, имеющих заданный ранг относительно ДКА (Сергей Вельдер, кафедра компьютерных технологий СПбГУ ИТМО)
(15.05.2011 - 15:35 - 17:10)

Гипотеза Ж.-Э. Пэна и гипотеза о рангах дают верхние оценки на длину слов, имеющих ранг k относительно детерминировнного конечного автомата (ДКА) из n состояний. Эти верхние оценки можно выразить функцией от (n-k), не зависящей от самих величин n, k и от автомата. Точная верхняя оценка является функцией, перечислимой снизу путём перебора всех ДКА. Это означает, что если для каких-то n и k верхняя оценка не выполняется, то данный факт можно подтвердить предъявлением ДКА, который играет роль автоматически проверяемого сертификата. В докладе будут рассмотрены комбинаторные структуры, которые можно использовать в качестве автоматически проверяемых сертификатов для ситуации, когда верхняя оценка выполняется. Они позволяют установить перечислимость сверху точной верхней оценки на длину слов и, как следствие, машинно доказывать такие оценки для всех ДКА, а также определить время, достаточное для вычисления этих оценок.
7. Введение в задачи differential privacy (Григорий Ярославцев, Университет Штата Пеннсильвания)
(22.05.2011 - 15:35 - 17:10)

В докладе будет рассмотрено понятие "differential privacy", являющееся наиболее успешной попыткой теоретической формализации понятия "privacy". Данное понятие позвляет давать сильные теоретико-информационные гарантии "privacy" пользователям, чьи личные данные хранятся в базе данных, при условии, что над базой данных выполняются операции, сохраняющие "differential privacy". Поскольку гарантии являются теоретико-информационными, они действительны относительно произвольного противника, вне зависимости от его априорной информации.

Введение понятия "differential privacy" в работе Dwork, McSherry, Nissim и Smith (TCC, 2006) дало начало новой области теоретической информатики, посвященной изучению алгоритмов, сохраняющих "differential privacy". Мы рассмотрим некоторые современные темы и задачи в этой области. Особенное внимание будет уделено механизму "smooth sensitivity", введенному в работе Nissim, Raskhodnikova и Smith (STOC 2007) и его приложениям при анализе структуры графов с сохранением "privacy" (совместная работа докладчика с Behoora, Karwa, Raskhodnikova и Smith).

Ваша оценка: Пусто Средняя: 3 (4 голосов)
Share |
Семинар, Михаил Рыбалкин
Семинар
Семинар
Семинар, Макс Алексеев
Михаил Рыбалкин
Семинар
Семинар
Семинар, Макс Алексеев
Семинар
Семинар
Семинар
Семинар
Семинар