Чему равно самое большое число, которое можно составить из этих пяти карточек? И как написать программу, которая быстро найдёт ответ, получив на вход сто таких карточек?
Саша Куликов @alexanderskulikov
Исследователь, автор курсов по алгоритмам
Собеседование по алгоритмам: задача Иосифа Флавия
2 min
Review
На следующем собеседовании по алгоритмам вам может попасться алгоритмическая задача, основанная на легенде об Иосифе Флавии: стоящие по кругу n мятежников начинают убивать каждого k-го из оставшихся в живых; нужно написать программу, которая получает на вход числа n и k и за время O(n) находит номер последнего оставшегося в живых мятежника. Сможете написать такую программу за тридцать минут? В этой статье мы подробно разберём решение задачи.
Интерактивный учебник для подготовки к алгоритмической секции собеседования
2 min
Собеседования в крупные IT-компании почти всегда содержат алгоритмическую секцию — даже если вы собеседуетесь на позицию, в работе на которой алгоритмы возникать вряд ли будут. Ниже мы приводим пример задачи, с которой вы можете столкнуться на вашем следующем интервью. Мы расскажем, как эта задача решается, но мы настоятельно рекомендуем вам читать решение только после того, как вы попробуете решить задачу самостоятельно: во-первых, это отличная тренировка; во-вторых, вы лучше запомните решение, если придумаете его сами (не отказывайте себе в этом удовольствии!); в-третьих, даже если вы подумаете над задачей, но не решите её, время не будет потеряно: прочитав потом решение, вы лучше его поймёте и оцените его красоту.
Специализация по спортивному программированию на Курсере
1 min
Исследовательской лабораторией им. П. Л. Чебышева при СПбГУ готовится онлайн-специализация по спортивному программированию на платформе Coursera. В первом курсе специализации даётся мягкое введение в мир спортивного программирования, в последующих четырёх курсах даются углубленные знания по вычислительной геометрии, алгоритмах на графах, числовым алгоритмам, алгоритмам на строках. В специализации будет много задач, максимально похожих на задачи с соревнований. Для самых сложных задач каждой недели будут даваться разборы. Лекции в специализации читаются как профессорами-математиками, так и тренерами СПбГУ и участниками недавних финалов чемпионата мира по программированию (ACM ICPC): Н. А. Вавилов, К. В. Вяткина, С. В. Копелиович, А. С. Куликов, А. Е. Логунов, А. С. Лопатин, А. С. Охотин, В. А. Петров, Ф. В. Петров, К. А. Симонов. Программу помогал составлять Е. Ф. Суворов, задачи — А. А. Толстиков.
Бакалавриат СПбГУ
2 min
К успешно существующему три года при поддержке компании Газпром нефть бакалавриату «Математика» в Санкт-Петербургском государственном университете добавляются потоки «Математика, алгоритмы и анализ данных» и «Современное программирование» при поддержке компаний JetBrains и Яндекс. Планируемая численность:
- “Математика”, “Математика, алгоритмы и анализ данных”: суммарно 50 бюджетных + 18 бесплатных внебюджетных мест (обучение оплачено Яндексом);
- “Современное программирование”: 25 мест.
Преимущества образования
Сильные математические курсы
Математические курсы читаются преподавателями и научными сотрудниками Исследовательской лаборатории им. П.Л. Чебышева (научный руководитель лаборатории — лауреат премии Филдса С. К. Смирнов).
Сильные технологические курсы
Программистские курсы будут читаться разработчиками ведущих IT-компаний, в частности, JetBrains и Яндекс. Соответственно, будут даваться актуальные востребованные индустрией знания.
Международная студенческая школа Recent Advances in Algorithms: Санкт-Петербург, 22–26 мая 2017
1 min
22–26 мая в Санкт-Петербургском отделении Математического института Стеклова РАН пройдёт международная студенческая школа «Recent Advances in Algorithms». Цель школы — познакомить студентов и аспирантов с недавними прорывами в разных областях алгоритмов: от таких классических областей, как потоки в графах и длиннейшие пути в графах, до таких сравнительно недавно возникших областей, как алгоритмы обработки потоковых данных и алгоритмы для многомерных данных. Лекции будут читаться учёными, активно развивающими соответствующие области. Каждый мини-курс начнётся со введения в область и постепенно дойдёт до текущего положения дел в данной области.
К участию приглашаются студенты, аспиранты и молодые исследователи.
Поиск кратчайших путей в дорожных сетях: от теории к реализации
1 min
В ближайшую субботу Виталий Осипов (Технологический институт Карлсруэ) начнёт читать в Computer Science клубе в Санкт-Петербурге курс по алгоритмам поиска кратчайших путей в графах. В ходе курса будут изучаться и реализовываться алгоритмы, используемые миллионами людей в таких сервисах, как Google/Bing/Yandex карты. Как всегда, вход свободный, регистрация не требуется, приглашаются все желающие.
» Страница курса на сайте CS клуба
Первая лекция: суббота, 5 ноября, 17:20
Место: Математический институт Стеклова, Санкт-Петербург, Фонтанка 27, Мраморный зал (второй этаж)
Две международные конференции в Санкт-Петербурге в июне: Experimental Algorithms и Computer Science in Russia
1 min
Летом в Математическом институте Стеклова (ПОМИ) пройдут две международные конференции: 15th International Symposium on Experimental Algorithms (SEA 2016, 5–8 июня) и 11th International Computer Science Symposium in Russia (CSR 2016, 9–13 июня). Программы конференций уже доступны на страницах конференций. Будет куча интересных докладов. Ниже приведён список приглашённых докладов. Для местных участников установлен минимальный орг. взнос. Если вы хотите принять участие, но оплатить орг. взнос у вас возможности нет, напишите мне — мы что-нибудь придумаем.
Онлайн-курс «Введение в теоретическую информатику» от Александра Ханьевича Шеня
1 min
Категорически приглашаем всех желающих на онлайн-курс «Введение в теоретическую информатику» Александра Ханьевича Шеня, подготовленный совместно с Computer Science центром и платформой Stepic. Курс начнётся 24 февраля.
Александр Ханьевич — автор многих популярных книг по математике и программированию. Многие его книги и брошюры можно бесплатно скачать с сайта издательства МЦНМО: например, «Программирование: теоремы и задачи» (Шень, 2004), «Лекции по математической логике и теории алгоритмов» (Верещагин, Шень, 2012), «Классические и квантовые вычисления» (Китаев, Шень, Вялый, 1999). Под его редакцией вышел перевод первого издания классического учебника «Алгоритмы: построение и анализ» (Кормен, Лейзерсон, Ривеста, 1990), а также недавнего учебника «Алгоритмы» (Дасгупта, Пападимитриу, Вазирани, 2006).
В общем, у Александра Ханьевича огромный опыт чтения лекций как школьникам, так и студентам и аспирантам. Рассказывает он очень увлекательно и понятно. В онлайн-курсе он даст обзор различных направлений Theoretical Computer Science: криптография, инварианты циклов, вычислимость, переборные задачи, игры, коды, интерактивные доказательства и многое другое (всего в курсе восемнадцать глав!). В курсе будет много задач — как простых (закрепляющих изученный материал), так и более сложных, над которыми придётся поломать голову и тем, кто уже был знаком с теорией.
Будем рады видеть вас среди слушателей онлайн-курса!
stepic.org/104
Александр Ханьевич — автор многих популярных книг по математике и программированию. Многие его книги и брошюры можно бесплатно скачать с сайта издательства МЦНМО: например, «Программирование: теоремы и задачи» (Шень, 2004), «Лекции по математической логике и теории алгоритмов» (Верещагин, Шень, 2012), «Классические и квантовые вычисления» (Китаев, Шень, Вялый, 1999). Под его редакцией вышел перевод первого издания классического учебника «Алгоритмы: построение и анализ» (Кормен, Лейзерсон, Ривеста, 1990), а также недавнего учебника «Алгоритмы» (Дасгупта, Пападимитриу, Вазирани, 2006).
В общем, у Александра Ханьевича огромный опыт чтения лекций как школьникам, так и студентам и аспирантам. Рассказывает он очень увлекательно и понятно. В онлайн-курсе он даст обзор различных направлений Theoretical Computer Science: криптография, инварианты циклов, вычислимость, переборные задачи, игры, коды, интерактивные доказательства и многое другое (всего в курсе восемнадцать глав!). В курсе будет много задач — как простых (закрепляющих изученный материал), так и более сложных, над которыми придётся поломать голову и тем, кто уже был знаком с теорией.
Будем рады видеть вас среди слушателей онлайн-курса!
stepic.org/104
Открытая лекция: задача выполнимости булевых формул
1 min
(Скриншот из презентации: slideplayer.com/slide/3238789)
Приглашаем всех на открытую лекцию Computer Science центра, посвященную задаче выполнимости булевых формул — одной из самых известных и важных алгоритмических задач. Лекция пройдёт в рамках встречи со слушателями онлайн-курса «Алгоритмы: теория и практика. Методы». Время и место проведения: 25 декабря, 19:00, БЦ Таймс (г. Санкт-Петербург, ул. Кантемировская 2А, 4 этаж). Участие бесплатное, но требуется регистрация: goo.gl/IiNvV8
Задача выполнимости — каноническая трудная задача, по которой проводится огромное количество исследований: как практических, так и теоретических. В частности, этой задаче посвящена ежегодная международная конференция. Каждый год проходят соревнования программ для данной задачи (так называемых сат-солверов). Такие программы активно используются во многих прикладных областях. Буквально несколько месяцев назад Дональд Кнут дописал том 4B монографии «Искусство программирования», треть которого посвящена задаче выполнимости.
Алгоритмы: теория и практика. Методы
2 min
Tutorial
В ноябре мы запускаем онлайн-курс «Алгоритмы: теория и практика. Методы» от Computer Science центра. Курс бесплатный, приглашаются все желающие. В курсе будут подробно разобраны базовые алгоритмические методы: жадные алгоритмы, метод «разделяй и властвуй», динамическое программирование. Для всех алгоритмов будут математически строго доказаны корректность и оценки на время работы. Мы постарались изложить материал так, чтобы были понятны и сами алгоритмы, и то, как можно было бы догадаться до их основных идей. Помимо теоретических основ, будут рассказаны тонкости реализации алгоритмов на языках программирования C++, Java и Python. В частности, будет рассказано, какие есть общие практики написания кода, позволяющие минимизировать вероятность ошибки, как писать и тестировать код, где стоит использовать стандартные методы, а не изобретать колесо.
Мы тщательно подобрали задачи для закрепления материала. Большинство алгоритмов, которые вы узнаете, вам нужно будет запрограммировать. Это лучший способ убедиться, что вы разобрались во всех деталях. Решая такие задачи, вы получите ценный опыт написания и отладки эффективных и надёжных программ. Задачи на программирование помогут вам почувствовать разницу между плохим (медленным) и хорошим (быстрым) алгоритмом. Вас также ждут тесты (где нужно выбрать правильные ответы из предложенных) и теоретические задачи (в них нужно доказать математическое утверждение). Наконец, в курсе есть также задачи повышенной сложности — менее стандартные задачи, которые не являются обязательными для прохождения курса. Получить удовольствие от решения этих задач смогут и те, кто уже знаком с базовыми алгоритмами.
Курсы осеннего семестра 2015 в Computer Science клубе
1 min
Занятия в осеннем семестре в Computer Science клубе начнутся уже на первой неделе сентября! Как всегда, все лекции клуба открыты, регистрация не требуется. Приглашаются все желающие. Список курсов и подробное расписание ищите на сайте клуба: compsciclub.ru
2 сентября в 18:00 Иван Близнец начнёт читать курс по параметризованным алгоритмам. Данная область изучает сложность алгоритмов в зависимости не только от размера входных данных, но и от различных дополнительных параметров. За последнее десятилетие в этой области появилось много новых красивых результатов. Курс будет читаться по недавней книге «Parameterized Algorithms», выпущенной в 2015 году М. Цыганом, Ф. Фоминым, Л. Коваликом, Д. Марксом, М. Филипчуком, М. Филипчуком и С. Саурабом: link.springer.com/book/10.1007%2F978-3-319-21275-3
Предварительное расписание курса (может поменяться! следите за новостями и заходите на страницу расписания): среда, 18:00.
Страница курса:
compsciclub.ru/courses/parameterizedalgorithms
Две красивые задачи по алгоритмам
4 min
Tutorial
На этой неделе я начал читать бакалаврам Академического университета базовый курс по алгоритмам. Начинал я совсем с основ, и чтобы тем, кто с базовыми алгоритмами уже знаком, было чем заняться, я в начале пары сформулировал две, наверное, самые свои любимые задачки по алгоритмам. Давайте и с вами ими поделюсь. Решение одной из них даже под катом подробно расскажу. Но не отказывайте себе в удовольствии и не заглядывайте сразу под кат, а попытайтесь решить задачи самостоятельно. Обещаю, что у обеих задач есть достаточно простые решения, не подразумевающие никаких специальных знаний по алгоритмам. Это, конечно, не означает, что эти решения просто найти, но после пары один из студентов подошёл и рассказал правильное решение первой задачи. =) Если же вам интересно посмотреть на начало курса или порешать больше разных задач — приходите к нам на (бесплатный) онлайн-курс, который начнётся 15 сентября.
Сразу поясню. В условии не говорится, что каждое число от 1 до n встречается в массиве, поэтому повторяющихся элементов там может быть сколько угодно (если бы все числа входили по разу, а одно — дважды, то задача была бы гораздо проще). Ограничение на использование дополнительной памяти означает, что нельзя заводить дополнительный массив линейной длины, но можно заводить переменные.
Локальным минимумом матрицы называется элемент, который меньше всех своих четырёх соседей (или трёх, если этот элемент лежит на границе; или двух, если это угловой элемент). Обратите внимание, что от нас требуется линейное по n время, хотя в матрице квадратичное по n число элементов. Поэтому мы предполагаем, что матрица уже считана в память. И нам нужно найти в ней локальный минимум, обратившись лишь к линейному количеству её ячеек.
Под катом — решение первой задачи. Ещё раз призываю вас заглядывать под кат только после того, как порешаете задачу. По второй задаче могу какую-нибудь подсказку сказать.
Задача 1. Дан массив A длины (n+1), содержащий натуральные числа от 1 до n. Найти любой повторяющийся элемент за время O(n), не изменяя массив и не используя дополнительной памяти.
Сразу поясню. В условии не говорится, что каждое число от 1 до n встречается в массиве, поэтому повторяющихся элементов там может быть сколько угодно (если бы все числа входили по разу, а одно — дважды, то задача была бы гораздо проще). Ограничение на использование дополнительной памяти означает, что нельзя заводить дополнительный массив линейной длины, но можно заводить переменные.
Задача 2. Дана матрица nxn, содержащая попарно различные натуральные числа. Требуется найти в ней локальный минимум за время O(n).
Локальным минимумом матрицы называется элемент, который меньше всех своих четырёх соседей (или трёх, если этот элемент лежит на границе; или двух, если это угловой элемент). Обратите внимание, что от нас требуется линейное по n время, хотя в матрице квадратичное по n число элементов. Поэтому мы предполагаем, что матрица уже считана в память. И нам нужно найти в ней локальный минимум, обратившись лишь к линейному количеству её ячеек.
Под катом — решение первой задачи. Ещё раз призываю вас заглядывать под кат только после того, как порешаете задачу. По второй задаче могу какую-нибудь подсказку сказать.
Конференция по алгоритмам на строках
1 min
В этом году в московском офисе Яндекса пройдёт юбилейная 25-я конференция Combinatorial Pattern Matching — главное в мире событие в области алгоритмов на строках.
Конференция начнётся с открытых лекций известных ученых, являющихся отцами-основателями серии конференций и внёсшими огромный вклад в область алгоритмов на строках:
Конференция начнётся с открытых лекций известных ученых, являющихся отцами-основателями серии конференций и внёсшими огромный вклад в область алгоритмов на строках:
- Альберто Апостолико (см., например, учебники и труды конференций на амазоне)
- Максим Крошмор (опять книги на амазоне)
- Юджин Майерс (один из авторов суффиксных массивов и BLAST-а, см. википедию).
Перевод учебника по алгоритмам
1 min
Рад сообщить, что вышел перевод отличнейшего учебника Дасгупты, Пападимитриу, Вазирани «Алгоритмы», над которым я работал последние несколько лет. В книге многие алгоритмы объяснены гораздо короче и проще, чем в других учебниках: с одной стороны, без излишнего формализа, с другой — без потери математической строгости. Откройте книгу на каком-нибудь известном вам алгоритме и убедитесь в этом. =)
В общем, угощайтесь: печатный вариант перевода, электронный вариант перевода (PDF), печатный вариант оригинала, электронный вариант оригинала (PDF).
Псевдокод на русском
1 min
Коллеги, нужен ваш совет. Мы сейчас занимаемся переводом отличного учебника Dasgupta, Papadimitriou, Vazirani. Algorithms. McGraw-Hill. 2006 на русский язык. Так вот, хочется услышать ваше мнение на тему того, как в русских учебниках по алгоритмам должен быть оформлен псевдокод: выделять ключевые слова? переводить ключевые слова на русский? помечать конец блока ключевым словом? (Опрос — снизу). Несколько потенциальных способов оформления приведены ниже. Буду благодарен за любые советы/замечания.
Международная студенческая школа CSEDays по алгоритмам и теории сложности
2 min
С 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 лет. И это далеко не единственный его результат. Ещё, например, он показал, как найти максимальный разрез в графе быстрее полного перебора с неожиданным и элегантным использованием быстрого умножения матриц. |
Уменьшена экспонента умножения матриц
2 min
Новости из мира науки: матрицы размера 
теперь умеют умножать за 
. Другими словами, доказано, что 
, где 
— экспонента умножения матриц. Доказала это совсем недавно Вирджиния Василевска-Вильямс, улучшив тем самым оценку 
, полученную Копперсмитом и Виноградом в 1987 году. Я напишу про важность этого алгоритма совсем немножко. Тем, кому интересно узнать побольше, предлагается почитать посты Скотта Ааронсона, Ричарда Липтона и Билла Гасарша.
Итак, многие теоретические верхние оценки на время работы алгоритмов используют экспоненту умножения матриц. В частности, много алгоритмов на графах эксплуатируют данную идею: если A — матрица смежности графа, то
— количество (не обязательно простых!) путей длины k между вершинами i и j. Эта простая идея позволяет за время 
проверить, есть ли в графе треугольник (3-клика): нужно возвести матрицу смежности в куб (для этого потребуется два умножения матриц) и посмотреть на диагональ. Отметим, что речь здесь именно о теоретических оценках, поскольку продвинутые алгоритмы умножения матриц хоть и обгоняют асимптотически простой кубический алгоритм, но на практике дают ускорение только на огромных размерах матриц.
Ещё несколько примеров:
теперь умеют умножать за . Другими словами, доказано, что , где — экспонента умножения матриц. Доказала это совсем недавно Вирджиния Василевска-Вильямс, улучшив тем самым оценку , полученную Копперсмитом и Виноградом в 1987 году. Я напишу про важность этого алгоритма совсем немножко. Тем, кому интересно узнать побольше, предлагается почитать посты Скотта Ааронсона, Ричарда Липтона и Билла Гасарша.Итак, многие теоретические верхние оценки на время работы алгоритмов используют экспоненту умножения матриц. В частности, много алгоритмов на графах эксплуатируют данную идею: если A — матрица смежности графа, то
— количество (не обязательно простых!) путей длины k между вершинами i и j. Эта простая идея позволяет за время проверить, есть ли в графе треугольник (3-клика): нужно возвести матрицу смежности в куб (для этого потребуется два умножения матриц) и посмотреть на диагональ. Отметим, что речь здесь именно о теоретических оценках, поскольку продвинутые алгоритмы умножения матриц хоть и обгоняют асимптотически простой кубический алгоритм, но на практике дают ускорение только на огромных размерах матриц.Ещё несколько примеров:
Алгоритмы: поиск химических соединений, задача ранжирования и анализ геномов
1 min
Первого мая в Computer Science клубе при ПОМИ РАН состоятся три интересные лекции. Лекции можно послушать вживую в ПОМИ РАН (Санкт-Петербург, наб. р. Фонтанки, д. 27; вход свободный, никакой предварительной регистрации не требуется) или же по трансляции, организуемой проектом Лекториум.
В 11:15 Михаил Рыбалкин (ПОМИ РАН и GGA Software Services) расскажет о подструктурном поиске химических соединений в базах даных. В 13:00 Игорь Куралёнок (СПбГУ и Яндекс) сделает доклад о практическом применении методов машинного обучения. Наконец, в 14:35 Максим Алексеев (University of South Carolina) расскажет о комбинаторных задачах и алгоритмах сравнительного анализа геномов.
Летняя школа по программной инженерии и верификации
2 min
Этим летом (с 17 по 27 июля 2011 года) Microsoft Research, совместно с НИУ ВШЭ и ИСП РАН, организует международную Летнюю Школу, посвященную вопросам программной инженерии и верификации программного обеспечения. В числе спонсоров и партнеров Школы — компании Intel, Google, Лаборатория Касперского, а также IEEE Computer Society.
Директором Школы является сэр Тони Хоар (Tony Hoare) — ученый с мировым именем, лауреат премии Тьюринга. В качестве лекторов в школе будут выступать широко известные ученые и другие профессора из ведущих университетов США и Европы.
К участию приглашаются заинтересованные и активные студенты старших курсов, аспиранты, и молодые ученые из России, СНГ, а также стран центральной Европы и Скандинавии.
Если Вы заинтересованы, то спешите зарегистрироваться: Вы можете подать официальную заявку и документы до 1 мая включительно.
Подробности — под катом, в нашей группе и на официальном сайте.