Публикации

Let X_1, ... ,X_n be i.i.d. sample in R^p with zero mean and the covariance matrix S. The problem of recovering the projector onto the eigenspace of S from these observations naturally arises in many applications. Recent technique from [Koltchinskii and Lounici, 2015b] helps to study the asymptotic distribution of the distance in the Frobenius norm between the true projector P_r on the subspace of the r-th eigenvalue and its empirical counterpart \hat{P}_r in terms of the effective trace of S. This paper offers a bootstrap procedure for building sharp confidence sets for the true projector P_r from the given data. This procedure does not rely on the asymptotic distribution of || P_r - \hat{P}_r ||_2 and its moments, it applies for small or moderate sample size n and large dimension p. The main result states the validity of the proposed procedure for finite samples with an explicit error bound on the error of bootstrap approximation. This bound involves some new sharp results on Gaussian comparison and Gaussian anti-concentration in high dimension. Numeric results confirm a nice performance of the method in realistic examples. 

We derive tight non-asymptotic bounds for the Kolmogorov distance between the probabilities of two Gaussian elements to hit a ball in a Hilbert space. The key property of these bounds is that they are dimension-free and depend on the nuclear (Schatten-one) norm of the difference between the covariance operators of the elements and on the norm of the mean shift. The obtained bounds significantly improve the bound based on Pinsker's inequality via the Kullback-Leibler divergence. We also establish an anti-concentration bound for a squared norm of a non-centered Gaussian element in Hilbert space. The paper presents a number of examples motivating our results and applications of the obtained bounds to statistical inference and to high-dimensional CLT.

Книга содержит необходимые сведения из теории алгоритмов, теории графов, комбинаторики. Рассматриваются частично рекурсивные функции, машины Тьюринга, приводятся некоторые варианты алгоритмов (ассоциативные исчисления, системы подстановок, грамматики, продукции Поста, нормальные алгоритмы Маркова, операторные алгоритмы). Описываются основные типы графов (мультиграфы, псевдографы, эйлеровы графы, гамильтоновы графы, деревья, двудольные графы, паросочетания, сети Петри, планарные графы, транспортные сети). Приводятся некоторые часто используемые в практике алгоритмы на графах. Рассматриваются классические комбинаторные конфигурации и их производящие функции, рекуррентные последовательности. В основу книги положен многолетний опыт преподавания авторами дисциплины «Дискретная математика» на факультете бизнес-информатика, на факультете компьютерных наук Национального исследовательского университета Высшая школа экономики и на факультете автоматики и вычислительной техники Национального исследовательского университета  Московский энергетический институт. Книга предназначена для студентов бакалавриата, обучающихся по направлениям 09.03.01 «Информатика и вычислительная техника», 09.03.02 «Информационные системы и технологии», 09.03.03 «Прикладная информатика», 09.03.04 «Программная инженерия», а также для ИТ-специалистов и разработчиков программных продуктов.

В учебнике планируется отразить расширенное содержание курса «Дискретной математики», читающегося на первом курсе направления прикладной математики и информатики факультета компьютерных наук Высшей школы экономики. Сам курс при этом представляет собой собрание понятий, результатов и методов, которые являются частью базовой математической культуры и необходимы будущим математикам и программистам, но не входят в традиционно сложившиеся курсы начального математического цикла (анализ, алгебра, линейная алгебра). В этом состоит основная специфика учебника: здесь нет единой сквозной темы. Вместо этого книга состоит из отдельных в значительной степени независимых глав, каждая из которых отражает начальные сведения по одной из областей дискретной математики.

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

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

Изложение книги сопровождается задачами разного уровня сложности.

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

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

Профиль компетенции каждого сотрудника описан в виде вектора, в котором каждая координата описывает уровень его владения соответствующим навыком.

Вектор, описывающий профиль компетенций команды, получается в результате простого сложения профилей компетенций участников. Предложенная модель предполагает, что каждая задача требует определенного набора компетенций, и что список компетенций и уровень опыта являются критериями, на основе которых сотрудник принимает решение о присоединении к команде. Логика принятия решений на разных этапах формирования команды моделируется детерминированными булевозначными функциями. Очередность, в которой выбираются сотрудники для применения следующего шага алгоритма, реализуется вероятностно. Для калибровки профиля компетенций члена команды были использованы внутренние данные о квалификации сотрудников научно-технического центра «Газпромнефть НТЦ». Построенная модель является основой для дальнейших исследований процесса образования и функционирования проектных команд в научной среде, разработки методики оценки эффективности деятельности научных коллективов. Она позволяет прогнозировать потребность в кадрах с теми или иными компетенциями, планировать мероприятия по повышению квалификации сотрудников и укреплению связей в коллективе.