Лекция
FPT-алгоритмы
Страница лекции на сайте Computer Science клуба
Курс о фундаментальных основах криптографии.
Нижние оценки для схем ограниченной глубины.
Арифметичность вычислимых функций. Арифметическая иерархия. m–сведения. Универсальные множества. Теоремы Тарского и Геделя.
Вероятностное округление для задачи о потоке в сетях с несколькими веществами.
Приближенные алгоритмы
Страница лекции на сайте Computer Science клуба
Языки вообще. Разбор естественных языков и языков программирования. Формальные языки и действия над ними. Понятие о регулярных выражениях и конечных автоматах.
Страница лекции на сайте Computer Science клуба
Содержание лекции
Криптография с открытым ключом I
Наибольшая возрастающая подпоследовательность, стоимость редактирования, рюкзак, перемножение нескольких матриц, кратчайшие пути, независимые множества в...
Задачи поиска. Классы P и NP. Сведения. NP–полные задачи. Не NP–полные задачи в классе NPP.
Конечное вероятностное пространство. Числа Рамсея. Монотонная схема для функции голосования. Теорема Эрдеша-Ко–Радо.
Приближенные алгоритмы
Страница лекции на сайте Computer Science клуба
Бесконтекстные грамматики. Примеры. Определение бесконтекстных грамматик через языковые уравнения и через перезапись. Ограничения бесконтекстных грамматик....
Страница лекции на сайте Computer Science клуба
Содержание лекции
Криптография с открытым ключом II.
Криптосистемы, основанные на частных случаях NP–трудных проблем. Коды, исправляющие ошибки. Линейные коды, коды Гоппы, NP–...
Наибольшая возрастающая подпоследовательность, стоимость редактирования, рюкзак, перемножение нескольких матриц, кратчайшие пути, независимые множества в...
Задачи поиска. Классы P и NP. Сведения. NP–полные задачи. Не NP–полные задачи в классе NPP.
Математическое ожидание. Линейность и принцип усреднения. Графы с большим количеством гамильтоновых путей. Независимое множество. Лемма о скрещивании. MAX-3–...
Приближенные алгоритмы
Страница лекции на сайте Computer Science клуба
Замкнутость бесконтекстных языков относительно объединения, сцепления, звёздочки, циклического сдвига и пересечения с регулярными языками. Доказательство...
Содержание лекции
Решётки в криптографии
Задача о выборе заявок, коды Хаффмена, покрытие множествами, вершинное покрытие, локальный поиск для задачи выполнимости.
Полиномиальная иерархия. Классы, ограниченные по времени и памяти. Иерархия по памяти. Иерархия по времени.
Математическое ожидание. Линейность и принцип усреднения. Графы с большим количеством гамильтоновых путей. Независимое множество. Лемма о скрещивании. MAX-3–...
Страницы
Конференция
Подумать только, прошло уже целых 20 лет со дня рождения самой популярной платформы, а она по прежнему не перестает удивлять теперь уже 9 миллионов...
Java-конференция Joker 2015 University Day
Санкт-Петербург, 18.10.2015
18–20 декабря 2017 года в Мраморном зале ПОМИ РАН прошла конференция, организованная сотрудниками ПОМИ РАН при поддержке компании Huawei. Основная цель...
CSR is an annual conference that intends to reflect the broad scope of international cooperation in computer science. In 2006-2009 the symposium consisted of...
На конференции рассказано о решениях от ГНУ/Линуксцентра на базе СПО для вашей организации:
Страница курса на сайте Computer Science клуба.
В силу различных причин, Java, как язык программирования, развивалась не очень динамично. Постепенно возникла необходимость в языке для JVM, в котором в первую...
Курс лекций
Экспандеры (расширяющие графы) являются мощным инструментом теоретической информатики и дискретной математики. По-видимому, эффективность экспандеров отчасти...
In this tutorial, I will review some of the work done in the distributed systems community on database replication, focusing on group communication–based...
Согласно одной притче, восточный властелин приказал двум своим мудрецам истолковать один из снов властелина.
В курсе будет рассказано о современном направлении в теории сложности - fine-grained complexity. В рамках этого направления ресурсы, необходимые для выполнения...