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

[ << Previous 20 ]

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). Вот такие дела. Следите за новостями, информацию на официальном сайте мы скоро выложим ;) (29 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) Бросить наконец работу и заняться (наконец?) нормальной жизнью. Но поскольку выбрать одно не получается, то приходится перебирать по циклу. (30 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)
Tuesday, February 12th, 2008
1:03 pm	Update: спецкурс про двунаправленные и кососимметрические графы Орг. собрание, а также первое занятие спецкурса состоятся в среду, 20 февраля на 5-й паре. Собираемся на кафедре математической логики (ауд. 1605 ГЗ). Важно: данное расписание не окончательное, 20 февраля мы обсудим выбор оптимального времени и места проведения. Поэтому даже если 5-я пара вам не подходит, то можно попробовать зайти в конце занятия и высказать свои пожелания о переносе. Приходите! =) (Comment on this)
Friday, February 8th, 2008
9:12 pm	А между тем... Нашу с Таней (my_attic) статью "Computing Longest Common Substrings Via Suffix Arrays" приняли на CSR 2008. Еще раз спасибо друзьям из Google, которые послушали мой рассказ и выдали массу ценных замечаний. Часть из них даже была учтена ;) P.S. Если открыть страницу с комментариями, то там можно найти Таню и поздравить её =) P.P.S. А ещё здесь можно поздравить Юру (est_lladon). (28 Comments |Comment on this)
Thursday, February 7th, 2008
2:59 pm	Спецкурс в весеннем семестре В наступающем весеннем семестре я буду читать на мехмате спецкурс "Введение в теорию двунаправленных и кососимметрических графов". ( Немного рекламы ) Расписание пока ещё не утверждено, но первое занятие состоится в отрезке 18-23 февраля. Если вы планируете ходить, то пожалуйста оставьте комментарий с указанием того, какие дни вам лучше всего подходят. Спасибо. (31 Comments |Comment on this)
Monday, January 21st, 2008
10:49 pm	Угадайка Задача рассказана andrewzta, за что ему большое спасибо: Как вам кажется, для любой ли функции f : R -> N найдётся четвёрка попарно различных вещественных чисел a, b, c, d, таких что: (i) f(a) = f(b) = f(c) = f(d) (ii) a + b = c + d Варианты ответа: a) Да, конечно! b) Нет, ну что вы! c) Фиг знает... Подумайте немного над этим несложным вопросом. Для самых нетерпеливых: правильный ответ скрывается под катом: ( Read more... ) (21 Comments |Comment on this)