Computer Science семинар

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

1. Роевой интеллект и управление (Н. Иготти)
(22.02.2009 - 16:15)

Небольшой обзор современных исследований в области роевого интеллекта и самоорганизации. Рассматриваются специфические свойства самоорганизующихся групп, позволяющие решать им совместные задачи и применение таких подходов для решения современных вычислительных задач (сортировка, ant programming, particle swarm optimization).
2. Суперполиномиальная нижняя оценка для монотонных формул (Александр Куликов)
(15.03.2009 - 16:20)

Доказательство нижних оценок на размер схем, вычисляющих булевы функции, является одной из самых известных и трудных задач Theoretical Computer Science. Несложно показать, что количество функций от n переменных сильно больше количества схем, имеющих полиномиальный от n размер, из чего следует, что большинство функций вычисляются только схемами экспоненциального размера. Несмотря на это, лучшая известная на данный момент нижняя оценка на схемную сложность есть 3n. Суперполиномиальные нижние оценки, однако, были доказаны для ограниченных схем: Й. Хастад привёл пример функции, не вычислимой схемами полиномиального размера константной глубины, А. А. Разборов доказал суперполиномиальную нижнюю оценку для монотонных схем. В данном докладе мы приведём элегантное доказательство А. А. Разборова суперполиномиальной нижней оценки для монотонных формул (в формулах, в отличие от схем, выходная степень каждого гейта равна единице). Данное доказательство опирается на теорему Карчмера–Вигдерсона, связывающую глубину схем с коммуникационной сложностью некоторой игры, а также использует некоторые свойства графов Пэли.
3. Agent–based (агент–ориентированное) моделирование (Иван Гниломёдов)
(17.08.2010 - 16:20)

Это класс вычислительных моделей в которых рассматривается совокупность обособленных агентов. «Совокупность» так как агенты действуют и взаимодействуют внутри какой–то общей жизненной среды. «Обособленность» проявляется в том, что каждый агент обладает ограниченными знаниями об окружающем мире. У каждого агента есть определённая жизненная цель, в процессе взаимодействия агенты могут самообучаться. Предполагается, что поведение агента не оптимально, напротив, задаётся набором достаточно простых правил. Однако несмотря на простоту каждого агента, система может демонстрировать весьма интересное поведение. Применение: agent–based модели применяются как для имитирования гуманистических (исследования в области экономики, социологии…), так и для моделирования технических систем. Примеры тем исследования: supply chain optimization (оптимизация поставок ресурсов), моделирование потребительского поведения, моделирование распределённых вычислений, workforce management (управление трудовыми ресурсами), моделирование пробок (транспортных). В конце будет сказана пара слов о бакалаврской работе докладчика. В работе рассматривалась экономическая модель, в которой процесс производства каждого агента представлен в виде конечного автомата. Подобное представление позволяет удобно описывать отношения между товарами и ресурсами производства (товары и ресурсы могут производиться друг из друга, быть взаимозаменяемыми и взаимодополняемыми).
4. Синтаксис предметно–ориентированных языков: композитные языки и диалекты (Андрей Бреслав)
(17.08.2010 - 16:25)

Предметно–ориентированные (или доменно–специфичные, DSL) языки — одна из популярных идей в мире высокоуровневого программирования. Идея проста: для того, чтобы решать часто встречающиеся в какой–то конкретной области задачи, проще создать маленький новый язык, чем писать громоздкие конструкции на языке общего назначения (представьте себе программирование баз данных на Java без SQL). При реализации этой идеи возникают новые технические задачи: многие языки похожи друг на друга, и мы не хотим создавать каждый из них с нуля, однако технология разработки языков в этом смысле развита довольно плохо. Будет рассказано о подходах к решению этих проблем, которые разрабатываются докладчиком в последнее время. В частности, будет рассказано о фундаментальных инструментах повторного использования — шаблонах и аспектах — и их обобщении на произвольные структурированные данные и о технике, позволяющей быстро создавать диалекты уже существущего языка.
5. Использование структурированных данных в информационном поиске (Юрий Лифшиц)
(17.08.2010 - 16:25)

Классические алгоритмы интернет поиска наиболее эффективны для нахождения ключевых слов в текстовых документах. В последние годы в интернете растет доля и влияние струтурированной иформации: социальный граф, профили товаров, описание событий, положение предметов в пространстве. В первой части доклада будет представлена общая картина: как структурированные данные публикуются, какие есть экономические механизмы сбора данных и как структурированные данные могут улучшить интернет поиск. Во второй части, будет количественно описана роль структурированной информации в современном использовании интернета. Анализ основан на данных поисковых логов Yahoo! Search и интернет навигации пользользователей Yahoo! Toolbar.
6. Оптимальные укладки графов в пространстве (Сергей Вельдер)
(17.08.2010 - 16:25)

Задачи реализации и рисования графа на плоскости и в пространстве находят много важных применений. Визуализация, построение логических схем и кодов требуют строить укладки графов, удовлетворяющие некоторому изобразительному соглашению, а также эстетическим и другим оптимизационным ограничениям. Этот раздел теории графов хорошо исследован; большинство алгоритмических задач, которые в нём проявляются, NP–полны. Данный доклад предназначен для введения в эту область; в нём рассматривается основное ограничение — минимизация объёма вложения (без самопересечений; вершины графа реализуются шариками фиксированного радиуса, а рёбра — криволинейными проволоками фиксированной толщины). В докладе будет рассказано о классических (для плоскости и трёхмерного пространства) и новых (для пространства любой размерности) результатах, связанных с этой задачей, а также об их предпосылках, в том числе биологических и комбинаторных. Будет обозначена связь объёма вложения с вычислительной сложностью некоторых алгоритмов для задачи SAT. Эта связь приводит к рассмотрению регулярных графов. В докладе формулируется следующий результат. Верхняя и нижняя оценка на минимальный объём вложения n–вершинного d–регулярного графа в k–мерное пространство в худшем и среднем случаях имеет порядок n^(k/(k–1)). Нижняя оценка верна для комбинаторных экспандеров особого типа. Такими экспандерами являются почти все графы. Часть теорем будет доказана.
7. Автоматизация доказательства NP–полноты некоторых двумерных задач (Михаил Дворкин)
(17.08.2010 - 16:25)

Доказательство NP–полноты некоторой задачи L в большинстве случаев представляет собой сведение какой–нибудь известной NP–полной задачи к задаче L. Например, можно «выразить на языке задачи L» провода, передающие логические значения, и логические элементы. Тогда задача SAT сводится к L. Именно так доказывают NP–полноту задач на клетчатом поле («Сапер», «Какуро», замощение тримино и др.) При этом во всех известных работах соответствующие элементы (логические операции, скрещивание проводов) создаются вручную, и это нетривиальная творческая задача. Предлагаемый подход — автоматическое построение этих элементов. Для этого используется модифицированное динамическое программирование по профилю: метадинамическое программирование. Предлагаемый подход позволяет автоматизировать процесс доказательства NP–полноты задач на клетчатом поле. В частности, была доказана NP–полнота задачи 4–CROSS SUM, что ранее являлось открытым вопросом.
8. Применение практики к теории (Григорий Ярославцев)
(17.08.2010 - 16:25)

Каким образом прогресс в области вычислительной техники может помочь теории сложности и теории алгоритмов? Будет дан краткий обзор существующих работ, которые использовали вычислительную технику для решения задач в теории вычислительной сложности и в теории алгоритмов. Будет неформально описано, как программы для решения задачи линейного программирования могут быть использованы для улучшения нижних оценок для задачи выполнимости. Также будет рассказано о программе исследований для развития нашего понимания схемной сложности. Доклад основан на статье Райана Вильямса “Applying Practice to Theory”. Также будет рассказано о нахождении эффективных булевых схем с использованием SAT–солверов, то есть о реализации программы, предложенной в этой статье.
9. What we can solve with a sublinear number of samples (Sofya Raskhodnikova)
(17.08.2010 - 16:25)

Suppose we are given a list of numbers and we wish to determine whether it is sorted. That problem obviously requires reading the entire list. But Ergun, Kannan, Kumar, Rubinfeld and Viswanathan showed in 1998 that if we know in advance that our list is either sorted or far from sorted, we can perform the test by examining only a small portion of the list. Testing if a list is sorted is thus an example of a task that can be performed with a small number of samples into the input. As data of all types gets easier to obtain and cheaper to store, datasets are becoming increasingly large, and we are faced with a need to perform computational tasks on massive datasets. Can we still compute something useful about a dataset when reading all of it is prohibitively expensive? In other words, what can we solve with a sublinear number of samples from the input? This is the main question addressed by the newly emerging area, called Sublinear Algorithms. In this talk, we will give a few examples of specific problems that can be solved with a sublinear number of samples, starting with the sorting example and moving on to simple properties of images, edit distance between strings, and approximating compressibility of a string. We will also explain a framework called “property testing” that was defined by Rubinfeld and Sudan in 1996 to formalize the kind of approximation that sublinear algorithms are good at. We will present a partial classification of what can and cannot be solved in that model when an algorithm can query the input only in a sublinear number of places.
10. Pinning Down “Privacy” in Statistical Databases (Adam Smith)
(17.08.2010 - 16:25)

Consider an agency holding a large database of sensitive personal information (perhaps medical records, census survey answers, or web search records). The agency would like to discover and publicly release global characteristics of the data (say, to inform policy and business decisions) while protecting the privacy of individuals' records. This problem is known variously as “statistical disclosure control”, “privacy–preserving data mining” or simply “database privacy”. In this talk, we describe “differential privacy”, a notion which emerged from a recent line of work in theoretical computer science that seeks to formulate and satisfy rigorous definitions of privacy for such statistical databases. We also sketch some basic techniques for achieving differential privacy.
11. Динамика двусторонних рынков (Юрий Лифшиц)
(17.08.2010 - 16:30)

Представьте себе, что у вас есть несколько рыночных площадей. На каждую из них каждые выходные приходит сколько–то покупателей и сколько–то продацов. Со временем, продавцы догадываются, что лучше торговать на рынке с самым большим количеством покупателей. Одновременно, покупатели постепенно перебираются на площадь с самым большим количеством продавцов. Этот процесс называют сетевым эффектом. Такая же картина наблюдается на сайтах знакомств, сайтах о работе, социальных сетях. Мы рассмотрим два вопроса: как предсказывать развитие двусторонних рынков во времени и как инвестировать усилия в развитие площадки: когда сделать скидку продавцам, а когда — покупателям? Для ответа на первый вопрос мы изучим модель основанную на стохастических дифференциальных уравнениях. В рамках инвестиционного анализа мы рассмотрим интересную геометрическую интерпретацию кривых сетевого эффекта. В конце доклада будут также представлены результаты измерений ряда дву–сторонних рынков в сети интернет.
Голосов пока нет
Share |