Below are the 20 most recent journal entries recorded in Maxim Babenko's LiveJournal:

[ << Previous 20 ]

Tuesday, December 14th, 2010
2:33 pm	Про лекции Андрея Гольдберга и немного про ISAAC Все вы, конечно, уже знаете про то, что Андрей Гольдберг, один из живых классиков theoretical computer science, будет читать весной в ШАДе спецкурс. Но если вдруг еще не знаете, то посмотрите пост Ильи Разенштейна, где можно найти всю необходимую информацию. Илья, кстати, будет teaching assistant-ом по этому курсу, так что лицо он вполне официальное :) От себя, как лица неофициального, добавлю одно важное замечание: количество место ограничено. Мы хотим, чтобы на занятия ходило не более 30 человек. При большом числе читать лекции и вести семинары на порядок труднее, а контакт с аудиторией трудно реализуем. Сейчас у нас уже больше 30 заявок. Это означает, что будет конкурс, пусть не такой, как на MIDAS, но все же. Поэтому пишите про себя побольше хорошего. Комбинации ФИО+email нам не достаточно, чтобы понять, как вы прекрасны. Если, конечно, вас не зовут, например, Robert Tarjan ;) Тем временем, я приехал и зарегистрировался сегодня на ISAAC 2010, где в четверг нужно будет делать доклад. Из впечатлений пока -- бессмысленно длинный перелет с двумя пересадками, а также удивительно настроенный интернет. В аэропорту Пекина просят деньги за wi-fi, честно перенаправляя все http на страницу биллинга. При этом https, rdp и ssh открыты. Сложно понять китайцев :) Корейцев, впрочем, тоже нелегко. В номере еле ловится некий wifi, который (сюрприз) хочет денег. А еще в стене есть настоящий RJ-45, в котором дают всё то же самое, только на хорошей скорости и бесплатно. Идея возить с собой патч-корд оказалась не такой уж безумной. Ваня: если ты читаешь это -- я помню про Итальяно. Если он действительно тут появится (все же он член PC, так что гарантии нет), то попробую спросить у него про жизнерадостные алгоритмы. (9 Comments |Comment on this)
Tuesday, March 30th, 2010
9:25 pm	Спецсеминар по алгоритмам Всем заинтересованным напоминаю, что на следующем заседании спецсеминара 6 апреля выступит Григорий Кучеров (CNRS LIlle, Лаборатория Понселе) с докладом "Техника затравок для нахождения схожих участков в символьных последовательностях". Затем, 13 апреля у нас в гостях Александр Тискин (University of Warwick) с докладом "Приближенное решение метрической задачи о коммивояжере". Более подробную информацию об этих, а также предстоящих докладах можно найти здесь. Приходите! :) (19 Comments |Comment on this)
Tuesday, March 2nd, 2010
10:37 pm	Ване П., по мотивам сегодняшней дискуссии про bing и perfect hash Надеюсь, что те гипотетические товарищи, писавшие bing, были чуть умнее их коллег ;) Current Mood: working (12 Comments |Comment on this)
Sunday, December 20th, 2009
6:10 pm	Летняя школа по алгоритмам Хочу пригласить всех желающих попробовать принять участие в летней школе, посвященной быстрым алгоритмам и задачам комбинаторной оптимизации Microsoft Data Structures and Algorithms School August 08-14, 2010, St. Petersburg, Russia Всю необходимую информацию вы можете найти на домашней странице школы. Заявку нужно подать не позднее 22 февраля 2010 года. (9 Comments |Comment on this)
Sunday, September 13th, 2009
5:45 pm	Пользуясь случаем, хочу сделать объявление про спецкурс, который собираюсь читать в наступившем семестре. На раз этот планируется годовой курс про теорию потоков. Рассказывать предполагается с нуля, так что никаких предварительных знаний не потребуется. Занятия будут проходить на 5-й паре по пятницам начиная с 18 сентября, ауд. 1327. Приходите :) ( Под катом -- список тем первого семестра ) Current Mood: calm (33 Comments |Comment on this)
Thursday, July 30th, 2009
9:08 am	С 1 по 14 августа буду в Хорватии. Если что-то срочное, пишите SMS. Почту постараюсь не читать. Всем привет ;) Current Mood: busy (Comment on this)
Saturday, June 6th, 2009
2:40 pm	Пушкин Рассказывают, что литературный мир отмечает сегодня 210-летие со дня рождения нашего выдающегося поэта. Никогда бы не подумал ранее, что тоже примкну к отмечающим, хотя и слегка по иному поводу. Поздравляю всех причастных, сочувствовавших и помогавших :) Тем временем, пора в отпуск. (4 Comments |Comment on this)
Saturday, April 11th, 2009
1:30 pm	Мы тут подумали немного с Игнатом Колесниченко и Ильей Разенштейном (ilyaraz) и посчитали, что вот такую задачу умеем решать за O(E + V log V): Задан ненаправленный граф и 6 различных терминалов: s1, s2, s3, t1, t2, t3. Нужно провести три не пересекающихся по ребрами пути: из s1 в t1, из s2 в t2 и из s3 в t3. При этом степени всех терминалов нечетные, а остальных вершин четные. Хочется быстрее :) Может кто-нибудь что-нибудь придумает? Чтобы почувствовать, что дает условие на степени, можно начать с задачи, где всего две пары терминалов, и понять, что задачи там как таковой нет. Update: всем спасибо, с помощью некоторого трюка с инкрементальной достижимостью задача решилась за линейное время. Заодно нашлась интересная ссылка для случая 2 пар и безо всякой эйлеровости: http://www.springerlink.com/content/efw5mb2rfhj75pcm/ (Comment on this)
Tuesday, March 24th, 2009
11:45 pm	Завтра утром улетаю в Ханты-Мансийск. Вернусь в понедельник вечером. Вероятно, почту читать буду, но в случае надобности лучше звонить. Всем привет. (10 Comments |Comment on this)
Saturday, March 21st, 2009
12:55 pm	Друзья, Никто из вас случайно не собирается в Питер в ближайшее время? Одному хорошему человеку нужно передать туда записанную болванку. Естественно, забирающая сторона встретит у поезда. Заранее спасибо. (15 Comments |Comment on this)
Thursday, March 5th, 2009
9:53 pm	Бывает, что приходит в жизни момент, когда нужно забросить сомнения и сделать что-то неожиданное и слегка невозможное. Сделать для того, чтобы чуть лучше узнать себя. Сделать это для кого-то близкого, заранее понимая, каков будет итог. Завтра утром нас ждет трасса М10 и, похоже, в ее плену мы проведем как минимум день. Всем друзьям из Питера неожиданный привет, я еду к вам :) В субботу-воскресение надеюсь оказаться в вашей теплой компании и побывать на кораблике. А уже в понедельник обратный путь домой. Такие вот планы :) P.S. Дорогие слушатели спецкурса по пятницам! Как вы, наверное, поняли, завтрашнее занятие не состоится. Буду очень признателен, если повесите соответствующее объявление на кафедре. Я, увы, это сделать уже не успеваю. (13 Comments |Comment on this)
Saturday, February 28th, 2009
11:07 am	Инкрементальный топологический порядок Известна такая простая, на первый взгляд, задача: в исходно пустой направленный граф последовательно добавляют дуги. После каждого запроса на добавление требуется перестроить в текущем графе топологический порядок, либо предъявить цикл. Совсем недавно на ISAAC 2008 в Австралии слушал приглашенную лекцию Tarjan-а на эту тему. Если кратко суммировать результаты, которые он упомянул, то получается следующее: 1) O(V) времени на каждую добавляемую дугу несложно получить с помощью некоторого инкрементального DFS 2) O(E^{1/2}) достичь также можно, но потребуются не вполне тривиальные структуры данных плюс bidirected search И вот сюрприз, оказывается, задачу можно решить за время O(V^2 log V) на все E добавлений. Соответствующая статья принята на SODA 2009, а текст доступен здесь. Внимательно пока не изучал, но судя по всему там что-то вполне понимаемое. Приятно осознавать, что даже в таких фундаментальных задачах все еще возможны прорывы. История творится на наших глазах, между прочим ;) P.S. Кстати, дорогие питерские друзья, я к вам обещался с лекцией в ПОМИ. Рассказать как раз хотелось про данную задачу. Теперь материала прибавилось. (18 Comments |Comment on this)
Wednesday, September 10th, 2008
3:51 pm	Объявления В осеннем семестре 2008-2009 года я буду читать на мехмате спецкурс про приближенные алгоритмы. На нем будет рассказано о задачах из разнообразных разделов computer science (теория графов, строковые алгоритмы, булевы формулы, вычислительная геометрия), для которых не известно эффективного точного решения. Более того, для подавляющего большинства этих задач в предположении P != NP полиномиальных алгоритмов заведомо нет. Вот типичный (и весьма неполный) список таких проблем: минимальные целочисленные покрытия и максимальные целочисленные упаковки деревья Штейнера и задача коммивояжера максимальная выполнимость булевых формул кратчайшие общие надстроки максимальные разрезы в графах подсчет числа выполняющих наборов для булевых формул вычисление параметров надежности сетей кратчайшие целочисленные векторы в решетках Оказывается, что даже если точное решение в этих задачах и не может быть найдено эффективно, существуют алгоритмы, вычисляющие за полиномиальное время приближения к оптимуму с определенной гарантированной точностью. Именно их мы и рассмотрим на наших занятиях. Первое занятие состоится в пятницу 12 сентября в 16:45. Сбор в 16:40 у кафедры математической логики и теории алгоритмов (ауд. 1605). Приглашаются все желающие. Одновременно, у нас начинает работать спецсеминар по комбинаторной оптимизации и теории алгоритмов. Данный семинар ориентирован в первую очередь на младшекурсников. Его целью является познакомить слушателей с типичными методами, используемыми в комбинаторной оптимизации -- разделе математики, изучающим способы нахождения экстремумов функций, заданных на наборах комбинаторных объектов (перестановок, строк, последовательностей, путей, остовов, паросочетаний, покрытий и т.д.) Предварительный список тем: Примеры задач комбинаторной оптимизации Основные алгоритмы теории графов Динамическое программирование Линейное программирование, линейная двойственность Тотальная унимодулярность и тотальная двойственная целочисленность линейных систем Целочисленное программирование и полиэдральная комбинаторика Линейное программирование на конусе неотрицательно определенных матриц (semidefinite programming) Основные понятия теории матроидов Субмодулярные функции и полиматроиды Полиматроиодные пересечения Первое занятие состоится в пятницу 12 сентября в 18:30 в ауд. 1324. Приглашаются все желающие. (15 Comments |Comment on this)
Friday, September 5th, 2008
10:20 pm	Вы это уже наверняка видели, но если вдруг нет, то оно того стоит: (4 Comments |Comment on this)
Wednesday, September 3rd, 2008
8:45 pm	Поездки С 14 по 18 буду в Карлсруэ (Германия) на 16th Annual European Symposium on Algorithms рассказывать про мультипотоковый алгоритм. Спасибо всем, кто помог советами про оформление виз. Если кому-то что-то надо оттуда, то пишите. Про наклейки на клавиатуру помню :) А в середине декабря есть мысль съездить на недельку в Австралию и побывать на 19th International Symposium on Algorithm and Computation, куда приняли статью про weight scaling technique for minimum cost bibranching. На этот раз спасибо в основном Пете Митричеву, который внимательно прочитал драфт и нашел там массу непонятных мест. Осталось только найти добрых спонсоров, поскольку поездка обещает быть недешевой. Any ideas? (16 Comments |Comment on this)
8:30 pm	Эти забавные списки Многим из вас наверняка кажется, что связные списки -- это просто и даже почти банально. Тем, кто так не думает или вообще не понимает, о чем речь, читать дальше наверное будет не очень интересно. Основных разновидностей списков две: одно- и двусвязные. Считая, что у нас 32-битные адреса, в первом случае мы тратим 4 дополнительных байта на каждую вершину (указатель next), а во-втором случае -- 8 байт (указатели next и prev). Предположим, что у нас есть вполне практическая задача: нужен список, по которому можно ходить итераторами в обе стороны (bidirectional iterator), расходуя O(1) единиц времени на каждое перемещение. При этом итератор позволяет читать-писать значение, на которое он указывает, а также производить обычные операции Remove, Insert-Before, Insert-After. Как решить эту задачу? Очевидно, нужно использовать двусвязный список. Но представим себе, что памяти у нас совсем мало, зато есть такое дополнительное ограничение: easy: в любой момент по списку может гулять лишь один итератор; hard: в любой момент по списку может гулять произвольное количество итераторов, но стоит одному из них выполнить Remove, Insert-Before или Insert-After, как остальные тут же становятся невалидными. (Известное мне решение представляет собой некоторый не вполне переносимый hack. Например, хочется иметь flat memory model. А еще для C#/Java напрямую работать оно не будет.) Внимание, соцопрос: можно ли получить требуемое, затратив лишь 4 байта на каждую вершину и O(1) единиц времени на каждую операцию? ( Решение под катом ) (35 Comments |Comment on this)
Monday, July 7th, 2008
11:31 pm	Школа Яндекса, версия 2.0 Пока некоторые замечательные знакомые выходят замуж и женятся (привет ircha11 и programmer ;), мы посовещались и решили, что пора нам наоборот разделиться. Так что с этой осени в Школе Яндекса будет два факультета (отделения): A) анализа данных (которое возглавит Илья Борисович Мучник) и B) computer science (руководить которым будет Лена Бунина). (Все названия предварительные.) Первая основная цель -- поделить целевые аудитории слушателей. Вторая основная цель -- не пытаться объять необъятное в рамках одной общей программы, а выделить два направления. Отделение computer science будет больше ориентировано на мехмат, а также близкие по духу академические структуры. Мои курсы будут в обоих программах (как специальные для отделения A и основные -- для отделения B). Вот такие дела. Следите за новостями, информацию на официальном сайте мы скоро выложим ;) (30 Comments |Comment on this)
Sunday, May 25th, 2008
5:24 pm	ESA'08 Давно ничего не писал, поскольку повода не было. А вот теперь есть. Нашу с А.В. Карзановым статью про мультипотоковый алгоритм приняли на ESA'08 (16th Annual European Symposium on Algorithms). Собираюсь туда поехать в сентябре, если, конечно, отпустят :) В один из прошлых разов попытка съездить в Италию (на WEA 07) закончилась тем, что мне вежливо объяснили: подавать документы на визу надо за пару месяцев до начала, а не как я, за 30 дней :) Очень не хочется повторения этих приключений. Так что если вы недавно обращались за немецкой визой, то буду признателен любым наблюдениям. Спасибо! P.S. Текущий драфт работы, если вдруг кому-то это интересно, лежит здесь. Конечно, критика приветствуется. P.P.S. Последнее время чувствую как минимум три несовместных желания: 1) Бросить наконец преподавание и заняться наконец наукой. 2) Бросить наконец науку и заняться наконец работой 3) Бросить наконец работу и заняться (наконец?) нормальной жизнью. Но поскольку выбрать одно не получается, то приходится перебирать по циклу. (29 Comments |Comment on this)
Thursday, March 27th, 2008
8:24 pm	Дорогие друзья с 1 и 2 курса мехмата, Очереденая встреча с кафедрой математической логики и теории алгоритмов состоится завтра, 28 марта в 16:45. Где именно, правда, не ясно, поэтому стоит подходить к кафедре (ауд. 1605). Приходите :) (2 Comments |Comment on this)
Saturday, February 23rd, 2008
3:25 pm	Провел вчера первую консульацию по матлогике для двух групп мехмата. Две группы оказались представлены аж целыми 11 студентами (мальчики в меньшинстве). Мило, смахивает на спецкурс. Нас, конечно, поджидают разнообразные трудности, но проблемы нехватки места среди них точно не будет. Current Mood: working (14 Comments |Comment on this)