Pull to refresh

Летняя студенческая школа по теории сложности вычислений

Образовательные проекты JetBrains corporate blog Algorithms *Mathematics *

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

Список курсов:

— Схемная сложность булевых функций (Александр Куликов)
— Высокоточные оценки сложности (Иван Михайлин)
— Сложность доказательств (Дмитрий Соколов)
— Формульная сложность и гипотеза KRW (Александр Смаль)

Программа школы и условия отбора

Приглашаем участвовать изучающих математику студентов старших курсов бакалавриата или специалитета, магистрантов, аспирантов и молодых исследователей. Центр предоставляет участникам проезд, проживание и питание. Для заявки вам понадобится рекомендательное письмо научного руководителя, а также самостоятельно решить задачи по теме научной школы. Прием заявок открыт до 4 июля.

Читать далее
Total votes 5: ↑5 and ↓0 +5
Views 1.1K
Comments 3

Международная конференция Computer Science Symposium in Russia (CSR 2011)

Образовательные проекты JetBrains corporate blog

С 14 по 18 июня 2011 года в Санкт-Петербурге пройдёт 6-я Международная конференция Computer Science Symposium in Russia (CSR 2011). Темы конференции включают в себя алгоритмы и структуры данных, комбинаторную оптимизацию, теорию сложности вычислений, криптографию, комбинаторику, формальные языки и автоматы и др. Крайний срок подачи статей — 6 декабря 2010 года. Подробности на сайте конференции: http://logic.pdmi.ras.ru/csr2011
Ниже приведён список приглашённых докладчиков конференции.
Читать дальше →
Total votes 28: ↑26 and ↓2 +24
Views 977
Comments 6

Почему я не верю в простые алгоритмы для NP-полных задач

Algorithms *
На днях в этом блоге было опубликовано открытое письмо учёным по поводу предполагаемого полиномиального алгоритма для задачи 3-SAT. Обсуждение в том топике ещё далеко не закрыто и говорить о том, что в алгориме найдены ошибки пока преждевременно, но мне хочется написать почему «граждане учёные» не выстраиваются в очередь чтобы поскорее проверить это доказательство.

Примерно полгода назад, в августе 2010-го была опубликована попытка доказать что P≠NP. Тогда один математик-блогер, Скотт Оронсон, чтобы не казаться голословным в своём недоверии к этому доказательству поставил свой дом на то, что доказательство окажется ошибочным. Пожалуй, я ничего не потеряю если последую (с меньшим размахом) его примеру и поставлю на то, что нынешний алгоритм неправилен свой автомобиль (Auris 2008-го года выпуска).

По-моему, Оронсон немного рисковал. Винод Деолаликар, автор того доказательства — относительно известный математик, задача P≠NP входит в область его компетенции, и само доказательство использовало несколько принципиально новых идей, дающих надежду на то, что с помощью них удастся обойти трудности, с которыми сталкивались те кто пытался доказать этот факт до него. С нынешним доказательством ситуация немного иная.
Читать дальше →
Total votes 79: ↑58 and ↓21 +37
Views 11K
Comments 73

Еще немного про P и NP

Algorithms *
Sandbox
image

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

Чтобы проиллюстрировать центральную роль этого понятия, можно вообразить пять различных возможных миров (возможных — потому что еще не доказано, что они нереальны, и наш может оказаться любым из них) и посмотреть как условия в них будут влиять на информатику и жизнь вообще.
Читать дальше →
Total votes 99: ↑91 and ↓8 +83
Views 27K
Comments 23

Доказано, что игра Super Mario является NP-полной задачей

Game development *Algorithms *


Анализ вычислительной сложности пяти классических игр для Nintendo показал, что среди них есть NP-полные задачи, то есть которые решаются за полиномиальное время на так называемых недетерминированных машинах Тьюринга. Проще говоря, это математически очень сложные задачи, сравнимые с задачей коммивояжёра или проблемой раскраски графа.

Учёные проанализировали следующие игры: Mario, Donkey Kong, Legend of Zelda, Metroid и Pokemon. Как выяснилось, ко всем играм серий Mario и Donkey Kong применимо определение о NP-полноте. Отдельные игры других серий принадлежат к классу NP, а некоторые игры — к классу PSPACE.
Читать дальше →
Total votes 72: ↑54 and ↓18 +36
Views 7.3K
Comments 34

Магистратура по теоретической информатике, Академический Университет (РАН)

Образовательные проекты JetBrains corporate blog Algorithms *
image

В Санкт-Петербурге есть замечательное место, где из программистов делают ученых — теоретиков Computer Science. Это Академический Университет Российской Академии Наук (АУ РАН).

На тот момент, когда я поступила на Теоретическое Отделение кафедры Математических и Информационных Технологий АУ, отделение имело только один выпуск, состоящий из двух человек. Сейчас Академический Университет уже заработал себя прекрасное имя. Его выпускники работают в ведущих компаниях города, он принимает студентов из других городов, обеспечивая их жильем, а платное отделение стоит всего-навсего 10 тыс. рублей в семестр.

Но я хочу рассказать, на своем примере, какие интересные и глубокие проблемы можно исследовать и сколько интересного узнать, если вы станете студентом теоретического отделения.
Читать дальше →
Total votes 68: ↑57 and ↓11 +46
Views 5.5K
Comments 55

Теория сложности на простых примерах

Popular science
Sandbox
Задайтесь вопросом «ГДЕ?». Где находится центр управления движением галактик или поведением циклона? Где та сила, что объединяет атомы в сложные соединения, те в свою очередь — в цепочки белков, и порождает такие устойчивые и сложные явления как биологическая жизнь, разум, социум.

Под зонтиком теории сложности объединены разнообразные модели, которые описывают, как без центрального контроля из взаимодействия простых начальных элементов, подчиняющихся простым правилам, образуются явления более высокого порядка, обладающие сложно предсказуемым поведением и непредвиденными, но устойчивыми, свойствами.
Статья не предлагает готовых ответов о смысле жизни, сквозит грубыми нестрогими аналогиями, но при этом имеет дерзкую цель расширить кругозор читателя, опираясь на его воображение и некоторые математические факты.
приглашаю под кат
Total votes 83: ↑78 and ↓5 +73
Views 11K
Comments 53

Международная студенческая школа CSEDays по алгоритмам и теории сложности

Algorithms *Mathematics *
С 29 июня по 1 июля 2013 г. в Екатеринбурге пройдёт международная студенческая школа CSEDays по алгоритмам и теории сложности. Список преподавателей получился очень внушительным, давайте я о них здесь буквально в двух словах расскажу.
Константин Макарычев (Microsoft Research)
Молодой, но уже очень успешный учёный. Специалист по приближённым алгоритмам и Unique games conjecture (гипотезе, из которой выводятся результаты о неприближаемости для многих NP-трудных задач).
Александр Шень (Montpellier Laboratory of Informatics, Robotics, and Microelectronics и ИППИ РАН)
Наверное, не нуждается в представлении. Специалист в области теории сложности.Автор многих замечательных учебников — таких, например, как «Программирование: теоремы и задачи». Также является редактором перевода (и, на самом деле, главным переводчиком) первого издания классического учебника Кормена, Лейзерсона, Ривеста «Алгоритмы: построение и анализ».
Mario Szegedy (Rutgers University)
Дважды лауреат Премии Гёделя, присуждающейся ежегодно за выдающиеся статьи в области theoretical computer science. Первый раз — за вклад в доказательство PCP-теоремы (вероятностно проверяемых доказательств) и её применение к результатам о неприближаемости, второй — за работы в области streaming algorithms.
Ryan Williams (Stanford University)
Тоже молодая звезда. Его недавний результат о том, что класс NEXP не содержится в классе ACC0, называют одним из самых значительных достижений в области схемной сложности за последние 20 лет. И это далеко не единственный его результат. Ещё, например, он показал, как найти максимальный разрез в графе быстрее полного перебора с неожиданным и элегантным использованием быстрого умножения матриц.
В общем, очень-преочень рекомендую.
Читать дальше →
Total votes 54: ↑45 and ↓9 +36
Views 8.4K
Comments 23

Что такое Кеневин и немного о конференции Lean Kanban Russia

ScrumTrek corporate blog
Давно ли вы меняли свою работу? Если да, то возможно с вами или с вашими коллегами случалась такая ситуация — при переходе из одной компании в другую вы начинаете видеть те же самые проблемы, и пытаетесь, основываясь на предыдущем опыте, принимать решения, но в этом случае это только усугубляло ситуацию. Мало того, вы начинаете искать причины в том, что люди недостаточно хорошо работают и все получится, просто нужно подождать или еще что-нибудь. Короче, несмотря на всё окружение и сигналы свято верите, что вы правы. Ведь это кажется контр-логично – не доверять своему опыту. Это называется «Ловушка Эксперта» — вы становитесь заложником своего опыта, вам кажется что все просто и вы принимаете неподходящие решения, порой приводящие к глубокому кризису в управлении.

Например: была у меня такая история со знакомым. Он успешный проектный менеджер, который с успехом сделал несколько проектов, используя Scrum. Все было отлично — масштабирование работало отлично, заказчик был доволен, качество на высоте, команды на подъеме, релиз, планы и velocity стабильны и предсказуемы, в общем, все отлично. И тут его приглашают в другую крупную российскую компанию, и он видит там бардак, и первая его реакция – «так, Всем Scrum!»
А ситуация, конечно, по уровню беспорядка не сильно отличается от предыдущей, если только масштабом, а вот по специфике работы и взаимодействию людей – отличается, и результаты «Всем Scrumовской» политики, конечно, помогают, но не долго. Дальше начинается вой «Scrum ваш не работает» – и нашего, до недавнего времени, успешного менеджера уже намереваются уволить.

Что делать?

Выходит так, что мы должны уметь принимать решение и понимать, когда наш опыт это плюс и его стоит использовать, а бывает что минус и это только мешает нам принять подходящее контексту решение.
Именно по этому я хочу вам рассказать про фреймворк Cynefin/«Кеневин». Это один из основных методов компании Cognitive Edge, который позволяет руководителям взглянуть на вещи с новых точек зрения, усвоить сложные понятия, и решать реальные проблемы. Использование фреймворка «Кеневин» может помочь руководителям ощутить, в какой ситуации они находятся, так что они могут не только принять лучшие решения, но и избежать проблем, которые возникают, когда их стандартный стиль управления заставляет делать ошибки.

Проще говоря, Кеневин и Sensemaking (еще оно модное слово :)) вообще – нещадно разбивают все концепции General Management'a, которые преподаются на всеми любимых MBA программах или других курсах классического менеджмента. Хотите, чтобы ваша компания имела Бизнес Гибкость не только на уровне команды или IT-подразделения, а развивалась как Сложная Адаптивная Система, устойчивая к разному роду неопределенности? А неопределенности сейчас предостаточно на всех уровнях управления.
Почитать больше про Кеневин
Total votes 13: ↑11 and ↓2 +9
Views 14K
Comments 2

Universal Memcomputing Machines как альтернатива Машине Тьюринга

Algorithms *Mathematics *
Sandbox
Данную статью можно считать вольным переводом (хотя скорее попыткой разобраться) данной статьи. И да, написанна она скорее для математиков, нежели для широкой аудитории.

Небольшой спойлер: в начале это казалось мне какой-то магией, но потом я понял подвох…

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

Вообще говоря, есть другие модели — Недетерминированная машина Тьюринга, Квантовые машины Тьюринга. Однако они (пока) являются только абстрактными моделями, не реализуемые на практике.

Полгода назад в Science Advances вышла интересная статья с моделью вычислений, которая существенно отличается от МТ и которую вполне возможно реализовать на практике (собственно статья и была о том, как они посчитали задачу SSP на реальном железе).

И да. Самое интересное в этой модели то, что, по заверению авторов, в ней можно решать (некоторые) задачи из класса NP полных задач за полином времени и памяти.
Читать дальше →
Total votes 26: ↑26 and ↓0 +26
Views 16K
Comments 9

Курсы Computer Science клуба, весна 2017, часть вторая

Образовательные проекты JetBrains corporate blog Algorithms *Mathematics *Machine learning *

Продолжаем выкладывать видеозаписи курсов Computer Science клуба при ПОМИ РАН. Первая часть здесь. В этой подборке четыре курса: «Коммуникационная сложность», «Экспандеры и их применения», «Машинный перевод» и «Избранные главы теории потоков».
Читать дальше →
Total votes 11: ↑11 and ↓0 +11
Views 4.9K
Comments 2

Новая заявка на решение задачи P vs. NP

Образовательные проекты JetBrains corporate blog Algorithms *Mathematics *
На днях Норберт Блюм опубликовал на архиве препринт с названием «A Solution of the P versus NP Problem». Таким образом Блюм претендует на решение одной из задач тысячелетия, за которую кроме почестей полагается 1 миллион долларов. В данной статье я собрал небольшое резюме об этом.
Читать дальше →
Total votes 68: ↑68 and ↓0 +68
Views 26K
Comments 76

10 лет Computer Science клубу

Образовательные проекты JetBrains corporate blog C++ *Algorithms *Mathematics *Kotlin *


В этом году Computer Science клубу в Санкт-Петербурге исполняется 10 лет. С 2007 года в клубе проходят открытые лекции и курсы, где любой желающий может познакомиться с классическими результатами, современным положением дел и открытыми задачами в различных областях computer science. Вход на все лекции свободный, регистрация не требуется. Слайды и видеозаписи всех прошедших лекций доступны с сайта клуба.


Поздравить клуб с юбилеем приедут сотрудники следующих организаций: Академический университет, Математический институт Стеклова в Санкт-Петербурге, Санкт-Петербургский государственный университет, Яндекс, JetBrains, Montpellier University, Northwestern University, Toyota Technological Institute at Chicago, University of Bergen, University of California at San Diego, Yahoo Research. Они прочитают мини-курсы по следующим темам.


Читать дальше →
Total votes 16: ↑16 and ↓0 +16
Views 4K
Comments 2

Курсы Computer Science клуба в 2021 году: верификация, фотограмметрия, статистика, логика, теория игр и другие

Образовательные проекты JetBrains corporate blog Algorithms *Image processing *Mathematics *Statistics in IT

Все курсы Computer Science клуба в 2021 году проходили в онлайн режиме. Мы собрали для вас подборку видеозаписей лекций, которые выложены на нашем youtube канале.

Читать далее
Total votes 14: ↑14 and ↓0 +14
Views 4.2K
Comments 0

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

Cryptography *Mathematics *Popular science
Translation

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

Была лишь одна небольшая проблема: на самом деле, пятью годами ранее её взломал немецкий пехотный офицер Фридрих Касиски, описав решение в книге, привлёкшей на тот момент мало внимания.

Криптографы играли в эти «кошки-мышки», создавая и взламывая шифры, ещё с тех пор, как люди впервые начали передавать секретную информацию. «Тысячи лет люди пытались найти ответ на вопрос: сможем ли мы разорвать этот круг?», — рассказывает криптограф Рафаэль Пасс из Cornell Tech и Корнеллского университета.

Пять десятилетий назад криптографы сделали широкий шаг в этом направлении. Они продемонстрировали, что можно создавать доказуемо защищённые шифры, если есть доступ к единственному ингредиенту — односторонней функции, которую легко вычислить, но сложно обратить. С тех пор исследователи придумали широкий спектр вариантов односторонних функций, от одиночных операций, основанных на умножении, до более сложных геометрических или логарифмических процедур.
Читать дальше →
Total votes 68: ↑68 and ↓0 +68
Views 25K
Comments 46