Оригинал взят у edwardahirsch в Магистратура СПбАУ РАН по информатике, биоинформатике и разработке ПО

Привет, дорогой журнальчик! Писать в тебя опять времени нет совсем, так что опять придётся обо всём понемножку.

Сборка генома

Это картинка из постера, который мы с Максом Алексеевым и Мишей Дворкиным представляли на ISMB 2011. Она должна дать представление о том, как принято собирать геном, даже тем, кто ничего об этом не знает. Да, вынужден признать, что на самой конференции я понял довольно мало. Учиться и учиться мне ещё.

Схемная сложность булевых функций

А это картинка из нашей с Женей Деменковым статьи про нижнюю оценку 3n-o(n) на схемную сложность. Такая же оценка в 1984 году была доказана Блюмом, и с тех пор улучшить её не удаётся никак.

Рассказать же мне здесь хочется не про саму оценку, а про то, как она доказалась. Года три примерно назад мы сообразили, что для получения этой оценки нужно построить булеву функцию, удовлетворяющую некоторому специальному условию (она не должна обращаться в константу ни на каком аффинном подпространстве достаточно большой размерности). Построить же такую функцию явно никак не получалось. Я периодически доставал на конференциях учёных мужей вопросами о том, где же её взять, но никто мне так и не помог. Отчаявшись, я решил спросить на cstheory.stackexchange — и мне тут же ответили, что такая функция была построена совсем недавно (но с абсолютно другой целью). Забавно, что я как-то угадал правильный момент, когда нужно спрашивать. В общем же случае, видимо, разумно спросить на форуме после пары безуспешных попыток найти ответ самому.

The 6th International Computer Science Symposium in Russia

Провели конференцию и провели очень хорошо, я считаю. Таможня вот пыталась подпортить общее впечатление, но мы её побороли.

Программа получилась довольно сильной. Особенно стоит отметить приглашённых докладчиков. Николаю Константиновичу Верещагину, председателю программного комитета, удалось пригласить очень сильных и известных исследователей. Видеозаписи и слайды их лекций доступны в разделе "Invited speakers" на сайте.

За помощь на всех этапах организации конференции хочу сказать огромное спасибо Сане Смалю. Благодарю также Ваню Близнеца, Сашу Головнёва, Женю Деменкова и Ваню Михайлина за помощь в проведении.

Вообще же, что-то я уже третье лето подряд что-нибудь организовываю. Не говоря уже о том, что и во время учебного года у меня организационной работы хватает. Стремительно превращаюсь в менеджеришку, в общем.

Computer Science Сenter
Набор в CS центр идёт полным ходом. Мы хотели успеть всех желающих отсобеседовать до 15 июля, но в последние несколько дней пришла такая гора заявок, что мы не успели. Не первый раз, в общем-то, отбираем студентов уже, и я знаю, что они, студенты, в последний момент любят всё делать, но всё равно неожиданно вышло. В общем, теперь будем пытаться до конца июля всех обработать. Поблагодарить же хочется Женю Смольникову, которая героически все эти заявки разбирает и отвечает на все вопросы поступающих.

Друзья мои, я сейчас в Японии. Вроде, собирался отдохнуть от менеджерства и преподавания, но на деле каждый день всё равно трачу кучу времени на клуб, CSR и студентов. Только делаю всё это теперь тупо за ноутом, от чего глаза ещё больше стали уставать. Но я стараюсь много гулять — погода к этому очень располагает (тут весна, оказывается!). А ещё я посмотрел кино и книжку прочитал, что тоже неплохо. И во всяких социальных сетях я стал чуть почаще появляться. Однако об этом позже, наверное, а сейчас хочется немножко про Японию рассказать. Будет, видимо, много картинок и мало текста.

( Read more... )

Журнал у меня уже почти окончательно превратился в блог новостей CS клуба. И я опять не могу удержаться. Простите мне, пожалуйста, эту мою слабость. Я чуть позже попробую ещё каких-нибудь своих мыслей написать (их ведь иногда пишут в журналы, да?), а пока всё-таки просто факты о клубе, сопровождающиеся фотографиями.

( Так вот... )

Не удержался и напишу всё же и в этом году ещё пост, ибо есть что сказать и спросить.

Microsoft Data Structures and Algorithms School
Школа прошла просто отлично! Все остались очень довольны — и студенты, и Андрей, и профессора. Боюсь, что время написать об этом подробно у меня вряд ли уже найдётся, так что просто смотрите сайт. И лучше это делать через неделю-две — я как раз фотографии и видеозаписи выложу. А пока ещё можно почитать рассказ о школе на сайте Microsoft Research.

Есть также некоторая предварительная информация о следующих школах. В следующем году школа будет, скорее всего, в Нижнем Новгороде и будет она по компьютерному зрению. А проводить её будет Антон Конушин, который как раз скоро будет в Питере. И я, конечно же, уже зазвал его к нам в клуб прочитать пару лекций. Так что заходите. А через раз школа будет по верификации, наверное, но про это говорить ещё рановато.

Новый сайт клуба
Да-да, слепил я новый сайт, и это, видимо, главный пункт моего поста. Скажите мне, пожалуйста, что он прекрасен, а то я всё лето с ним возился. Если серьёзно, то буду рад любым замечаниям/пожеланиям. Куда именно смотреть, здесь писать не буду — всё написано на сайте. Скажу лишь, что мне было лень выставлять правильную дату лекциям, когда я переносил их с одного сайта на другой. Поэтому сейчас в расписании куча лекций в августе. Пусть вас это не смущает.

Да, посоветуйте, пожалуйста, какой бы домен купить для сайта клуба. Я вот никогда не покупал и не очень понимаю, чем надо руководствоваться при выборе. csclub.ru занят злодеями, и что-то мне не хочется с ними общаться. Может быть, cslub.edu?

Очки
Посоветуйте ещё, пожалуйста, где правильно покупать очки. У меня вот, к сожалению, зрение ещё ухудшилось. И оправа что-то старая совсем уже. Ну и намылился я в магазин. Из десяти оправ, которые мне нравятся, мне почти все малы. То есть рожа у меня шире, чем надо, и очки еле налезают. Из каких-то дорогущих коллекций налезают чаще, конечно, но что-то не хочется больше десяти кусков отдавать за очки. Вот и что мне делать, а? Куда идти? Худеть у меня времени нет, очки нужны уже сейчас.

Друзья! Что-то совсем я запустил свой журнал. Полгода уже ничего не писал. В последнее время также очень мало читаю ленту и ридер и совсем забросил френдфид. Объясняется всё это тем, что у меня огромная куча дел и мне кажется, что у меня что-то получается, поэтому я с особым упорством всем этим и занимаюсь. И мне всё это действительно доставляет. Под катом я собираюсь рассказывать о том, что же произошло хорошего за последнее время, что я успел, что собираюсь делать и чем вообще я сейчас занимаюсь вместо того, чтобы сидеть в жж. Пунктов в списке будет много, поэтому писать буду ещё более сухо, чем обычно. Попробую, наверное, картинок вставить, чтобы хоть как-то оживить свой занудный текстик, но сомневаюсь, что это поможет. Пост, как обычно, будет интересен только моей маме. ( Мама, тыкай сюда, чтобы почитать дальше. )

Мы в воскресенье толпой едем в Прагу на Fall school of logic and complexity. Это, казалось бы, школа, но ездят туда далеко не только студенты. В этом году, например, туда поедет послушать профессор, который у нас недавно читал лекции. Я бы на этой школе в прошлом году. Главным лектором тогда был Стивен Кук (да-да, тот самый). Я, признаться, понял далеко не всё. В этом году за главного будет Ран Раз и рассказывать он будет довольно интересные вещи. Почти сразу после Праги мы ещё более крупной компанией рванём на Estonian theory days.

Итого, меня не будет с 20-го сентября по 4-е октября. До отъезда мне нужно переделать кучу дел. В частности, подготовить слайды к докладу в Эстонии. Я же вместо этого маюсь какой-то дурью. Сейчас вот, например, пост в жж пишу. А некоторое время назад я сам сделал японский кроссворд. Не без гордости представляю его вам, друзья. Круто, не правда ли? Если есть среди вас эксперты по японским кроссвордам, посоветуйте мне, пожалуйста, какое-нибудь солидное издание для моего творенья.

На открытии клуба сегодня настоящий аншлаг был. То ли благодаря посту на Хабре (спасибо, avsmal!), то ли благодаря тому, что в этот раз я не побрезговал хорошенько поспамить через контакт. Все стулья в Мраморном зале ПОМИ были заняты, некоторые стояли. Посмотрим, сколько из вас, ребята, доживёт до конца семестра. =)

Я сегодня прочитал две вводные лекции по алгоритмам для NP-трудных задач. Даже цель сегодняшних лекций на слайдах сформулировал: "Привести несколько красивых алгоритмов, не особо вдаваясь в определения и доказательства. Все формальности будут дальше в курсе." Просто моя следующая лекция будет нескоро, и к ней всё, что было сегодня, уже может вполне и забыться. Так что сегодня я пытался заинтересовать всех тематикой, продемонстрировав несколько элегантных подходов к решению NP-трудных задач. Хочется надеяться, что у меня получилось, хоть успел я и не всё. Слайды доступны со страницы курса. После моих двух пар yury_lifshits выступил на нашем семинаре с рассказом о двухсторонних рынках. Идеи Юра рассказывал совсем новые, даже не записанные ещё. Кусайте локти, если вас не было.

А ещё alf_kadett купил новую видеокамеру, пишущую на жёсткий диск. Спасибо, alf_kadett! И вообще, спасибо вам, Альф и Оля, за все наши клубные видеозаписи! (У меня, кстати, сегодня само по себе вылетело слово "Ольф", когда я рассказывал про то, как вы нам помогаете.)

А ещё мы сегодня всех угощали яблоками, заботливо выращенными и собранными edwardahirsch-ем к открытию осеннего семестра.

Открытие осеннего семестра 2009-го года в Computer Science клубе состоится в воскресенье, 13-го сентября. В 10-00 будет проведено орг. собрание, на котором будет рассказано об истории создания клуба, предстоящих курсах, стипендиях для студентов, Академическом университете РАН, дипломах о дополнительном образовании, Академии современного программирования, международных студенческих школах по Computer Science, а также школе по теории сложности, проведённой этим летом коллективом клуба. После собрания будут прочитаны две вступительные лекции по алгоритмам для NP-трудных задач и проведено заседание семинара, на котором выступит Юрий Лифшиц.

Курсы осеннего семестра 2009-го года
Алгоритмы для NP-трудных задач (А. Куликов, ПОМИ РАН)
Математические основы Computer Science (Д. Ицыксон, ПОМИ РАН)
Криптографические протоколы (С. Николенко, ПОМИ РАН)
Формальные языки и синтаксический анализ (А. Охотин, University of Turku)
Computer Science семинар

О клубе. Computer Science клуб при ПОМИ РАН создан в сентябре 2007-го года при поддержке Антона Лиходедова, на сегодняшний день поддержку клубу оказывают Антон Лиходедов (Deutsche Bank) и Юрий Богданов (Уралкалий). Основная цель клуба — предоставить возможность студентам Санкт-Петербурга получить образование в области Theoretical Computer Science. Лекции читают петербургские и иностранные преподаватели по субботам и воскресеньям в ПОМИ РАН (Фонтанка, 27). По основным курсам проводятся экзамены, оценки за которые могут быть зачтены формально. Вход на лекции свободный. Дополнительная информация о клубе (расписание занятий, описание курсов, слайды лекций, информация о преподавателях) доступна с сайта клуба: http://logic.pdmi.ras.ru/~infclub.

Ссылки: сайт клуба, расписание, RSS новостей, трансляция новостей в ЖЖ, группа вконтакте, встреча вконтакте, Google-группа, Google-календарь, объявление для печати.

Как многие из вас уже знают, я недавно организовывал международную студенческую школу по теории сложности в Санкт-Петербурге — NoNA Summer School on Complexity Theory. К настоящему моменту я уже успел поучаствовать в примерно двадцати международных школах и конференциях. Соответственно, у меня уже сложились какие-то представления о том, какой должна быть офигенная школа. Именно такой я школу и пытался организовать — и именно такой, на мой (и не только) взгляд, она получилась. Под катом я рассказываю о своих этих представлениях и о том, что у нас получилось, и сопровождаю все это фотографиями. ( Итак... )