Рубрика «теория сложности»

в 15:05, , рубрики: колмогоровская сложность, криптография, математика, Научно-популярное, односторонние функции, теория сложности
Исследователи выявили задачу, от которой зависит судьба современной криптографии - 1

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

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

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

Пять десятилетий назад криптографы сделали широкий шаг в этом направлении. Они продемонстрировали, что можно создавать доказуемо защищённые шифры, если есть доступ к единственному ингредиенту — односторонней функции, которую легко вычислить, но сложно обратить. С тех пор исследователи придумали широкий спектр вариантов односторонних функций, от одиночных операций, основанных на умножении, до более сложных геометрических или логарифмических процедур.
Читать полностью »

в 10:05, , рубрики: c++, computer science, kotlin, Алгоритмы, Блог компании СПБАУ, вычислительная геометрия, графы, искуственный интеллект, коды, математика, теория сложности

10 лет Computer Science клубу - 1

В этом году 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. Они прочитают мини-курсы по следующим темам.

Читать полностью »

в 8:10, , рубрики: complexity, p vs np problem, Алгоритмы, Блог компании СПБАУ, математика, теория, теория сложности, теория сложности вычислений

Новая заявка на решение задачи P vs. NP - 1
На днях Норберт Блюм опубликовал на архиве препринт с названием «A Solution of the P versus NP Problem». Таким образом Блюм претендует на решение одной из задач тысячелетия, за которую кроме почестей полагается 1 миллион долларов. В данной статье я собрал небольшое резюме об этом.
Читать полностью »

в 16:36, , рубрики: Алгоритмы, Блог компании СПБАУ, коммуникационная сложность, математика, машинное обучение, машинный перевод, потоки, теория графов, теория сложности, экспандеры, метки:
Курсы Computer Science клуба, весна 2017, часть вторая - 1

Продолжаем выкладывать видеозаписи курсов Computer Science клуба при ПОМИ РАН. Первая часть здесь. В этой подборке четыре курса: «Коммуникационная сложность», «Экспандеры и их применения», «Машинный перевод» и «Избранные главы теории потоков».
Читать полностью »

в 10:20, , рубрики: UMM, Universal Memcomputing Machines, Алгоритмы, математика, машина Тьюринга, нечем заняться на праздниках, теория сложности, метки: , , ,

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

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

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

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

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

И да. Самое интересное в этой модели то, что, по заверению авторов, в ней можно решать (некоторые) задачи из класса NP полных задач за полином времени и памяти.
Читать полностью »

в 12:09, , рубрики: Алгоритмы, математика, теория сложности, Учебный процесс в IT, метки: ,

С 29 июня по 1 июля 2013 г. в Екатеринбурге пройдёт международная студенческая школа CSEDays по алгоритмам и теории сложности. Список преподавателей получился очень внушительным, давайте я о них здесь буквально в двух словах расскажу.

Международная студенческая школа CSEDays по алгоритмам и теории сложности Константин Макарычев (Microsoft Research)
Молодой, но уже очень успешный учёный. Специалист по приближённым алгоритмам и Unique games conjecture (гипотезе, из которой выводятся результаты о неприближаемости для многих NP-трудных задач).
Международная студенческая школа CSEDays по алгоритмам и теории сложности Александр Шень (Montpellier Laboratory of Informatics, Robotics, and Microelectronics и ИППИ РАН)
Наверное, не нуждается в представлении. Специалист в области теории сложности.Автор многих замечательных учебников — таких, например, как «Программирование: теоремы и задачи». Также является редактором перевода (и, на самом деле, главным переводчиком) первого издания классического учебника Кормена, Лейзерсона, Ривеста «Алгоритмы: построение и анализ».
Международная студенческая школа CSEDays по алгоритмам и теории сложности Mario Szegedy (Rutgers University)
Дважды лауреат Премии Гёделя, присуждающейся ежегодно за выдающиеся статьи в области theoretical computer science. Первый раз — за вклад в доказательство PCP-теоремы(вероятностно проверяемых доказательств) и её применение к результатам о неприближаемости, второй — за работы в области streaming algorithms.
Международная студенческая школа CSEDays по алгоритмам и теории сложности Ryan Williams (Stanford University)
Тоже молодая звезда. Его недавний результат о том, что класс NEXP не содержится в классе ACC0,называют одним из самых значительных достижений в области схемной сложности за последние 20 лет. И это далеко не единственный его результат. Ещё, например, он показал, как найти максимальный разрез в графе быстрее полного перебора с неожиданным и элегантным использованием быстрого умножения матриц.

В общем, очень-преочень рекомендую. Читать полностью »

в 10:14, , рубрики: клеточные автоматы, Научно-популярное, Песочница, теория сложности, философия, метки: , ,

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

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

в 17:02, , рубрики: академический университет, Алгоритмы, АУ, магистратура, теоретическая информатика, теория сложности, метки: , , , ,

image

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

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

Но я хочу рассказать, на своем примере, какие интересные и глубокие проблемы можно исследовать и сколько интересного узнать, если вы станете студентом теоретического отделения.
Читать полностью »

в 20:56, , рубрики: game development, PSPACE, Super Mario, Алгоритмы, Игровые приставки, класс NP, теория сложности, метки: , , ,

Игра Super Mario признана NP полной задачей

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

Учёные проанализировали следующие игры: Mario, Donkey Kong, Legend of Zelda, Metroid и Pokemon. Как выяснилось, ко всем играм серий Mario и Donkey Kong применимо определение о NP-полноте. Кроме того, отдельные игры других серий принадлежат к классу NP, а некоторые игры из серии Zelda — к классу PSPACE.
Читать полностью »

в 20:56, , рубрики: game development, PSPACE, Super Mario, Алгоритмы, Игровые приставки, класс NP, теория сложности, метки: , , ,

Игра Super Mario определена как NP полная задача

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

Учёные проанализировали следующие игры: Mario, Donkey Kong, Legend of Zelda, Metroid и Pokemon. Как выяснилось, ко всем играм серий Mario и Donkey Kong применимо определение о NP-полноте. Отдельные игры других серий принадлежат к классу NP, а некоторые игры — к классу PSPACE.
Читать полностью »

12
Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js