Занятия в осеннем семестре в 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

Осенью Академический университет и Computer Science Center запускают годовую образовательную программу по основам программирования (code.stepic.org). Программа запускается на платформе онлайн-обучения Stepic. При успешном завершении программы студентам будет выдан диплом о профессиональной переподготовке от Академического университета.

Осенью Академический университет и Computer Science Center запускают годовую образовательную программу по основам программирования (code.stepic.org). Программа запускается на платформе онлайн-обучения Stepic. При успешном завершении программы студентам будет выдан диплом о профессиональной переподготовке от Академического университета.

Небольшая предыстория. Этот пост я написал для двух целей. Во-первых, обкатать конвертор разметки Markdown + в хабрачитаемый вид. Во-вторых, рассказать об интересной задаче из data streaming. К концу написания, я обнаружил пост про LogLog четырехлетней давности. На мою удачу автор предыдущего поста делал упор на реализацию. Я же, полагаясь на , расскажу больше о математике.

Давайте представим, что у нас есть роутер. Через роутер проходит много пакетов по разным адресам. Нам интересно получить статистику, как много адресов задействовано в коммуникации. Есть пара проблем.

• Пакетов так много, что запомнить их все нельзя. Сказать ушедшему пакету «Вернись! Я все прощу,» — тоже.
• Всех возможных адресов . Столько памяти на роутере нет.

Задача. Есть последовательность целых чисел , все числа принимают значения от до . Требуется в один проход посчитать количество различных чисел, используя памяти.

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

В прошлом году в Санкт-Петербургском академическом университете открылся бакалавриат (А), готовящий студентов по информатике с дальнейшей специализацией по теоретической информатике, разработке программного обеспечения или биоинформатике.

В этом году в Санкт-Петербургском государственном университете открывается бакалавриат (Ч) по математике и теоретической информатике.

Поскольку я принимал участие в создании обеих этих программ, коллеги настойчиво рекомендуют мне объясниться. (Зовут меня Эдуард Гирш, и я работаю в лаборатории математической логики ПОМИ РАН.)

Привет, уважаемые участники сообщества!

В Санкт-Петербурге на днях снова выпал снег, и для летнего вдохновения расскажем о мероприятии, проходившем в июле 2014 года. А именно – летней школе по биоинформатике, организованной Институтом биоинформатики и СПбАУ РАН при поддержке СПбГУ. Про первую школу на Хабре писали тут и тут.

В этой статье речь пойдет об интересном эксперименте — учебно-научных проектах в рамках школы: начиная от идеи и заканчивая тем, что же получилось в итоге.

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

Сегодня хочу поделиться с Вами двумя задачами с этих семинаров.

Задача 1. На прямой даны n отрезков, нужно выбрать максимальное по размеру подмножество непересекающихся.

Задача 2. На окружности даны n дуг (отрезков), нужно выбрать максимальное по размеру подмножество непересекающихся.

Каждый университет сталкивается с тем, что на некоторые темы в городе невозможно найти преподавателя, который бы являлся в этой теме специалистом. Один из вариантов решить эту проблему состоит в том, чтобы поручить подготовить курс на эту тему какому-нибудь из имеющихся преподавателей, который не является специалистом в этой области. Мы в Акадеическом университете стараемся пойти другим путем — пригласить специалиста для чтения курса. В прошлом году мы поучаствовали в конкурсе фонда Династия “приглашенный профессор”. Мы подали две заявки и обе выиграли, а также два наших преподавателя были приглашены в Уральский и Казанский федеральные университеты. В сентябре 2014 года Александр Охотин из университета Турку прочитал курс Формальные грамматики. А 18 марта начнет читать курс “Комбинаторика слов и ее приложения” профессор Уральского федерального университета Арсений Михайлович Шур. Мы приняли решение сделать этот курс полностью открытым для всех и провести его в рамках Computer Science клуба, нашего постоянного партнера.

Арсений Михайлович — активный исследователь в области комбинаторики слов, поэтому курс обещает быть очень интересным. Первое занятие состоится в среду 18 марта в 18-30 в Мраморном зале ПОМИ РАН (Санкт-Петербург, наб. реки Фонтанки д. 27), вход свободный, регистрация не требуется.

Подробное описание курса и расписание: тут.

Краткое описание курса

В начале каждого семестра студенты магистерской программы кафедры МиИТ Академического университета (СПб) и представители компаний-партнеров собираются вместе. Представители рассказывают о проектах, над которыми можно будет работать, а студенты выбирают их.

В одном из проектов, сделанных в Parallels Labs, наш студент исследовал возможность реализации виртуального Hardware Security Module (HSM). В результате он добавил свою реализацию VHSM в open-source проект OpenVZ. Подробнее о его решении читайте под катом.

Около шестнадцати лет назад вышла первая версия Hotspot – реализация JVM, впоследствии ставшая стандартной виртуальной машиной, поставляемой в комплекте JRE от Sun.

Основным отличием этой реализации стал JIT-компилятор, благодаря которому заявления про медленную Джаву во-многих случаях стали совсем несостоятельными.
Сейчас почти все интерпретируемые платформы, такие как CLR, Python, Ruby, Perl, и даже замечательный язык программирования R, обзавелись своими реализациями JIT-трансляторов.

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

Таким образом вам может быть интересно под катом, если:

• Вы принципиально не понимаете, что такое JIT-компилятор, или у вас есть легкое непонимание, чем такой подход существенно лучше интерпретации.
• Вы хотели бы написать простой JIT для своего интерпретируемого языка.
• Вы преподаете курс «Языки программирования и компиляторы», и не против сделать практическое задание для студентов еще интересней.
• Вам интересно, как нарисована эта картинка.

Мы рады объявить об открытии набора в магистратуру на 2015-2017 учебные годы.



Магистратура Академического университета существует с 2008 года. Всё это время мы прикладываем очень много усилий, чтобы поддерживать в нашем университете благоприятную образовательную среду: подбираем качественные и интересные курсы, приглашаем в качестве преподавателей известных ученых и ведущих разработчиков, развиваем партнерские отношения с известными IT-компаниями, создаём удобную для студентов инфраструктуру.

Мы рады объявить об открытии набора в магистратуру на 2015-2017 учебные годы.


Магистратура Академического университета существует с 2008 года. Всё это время мы прикладываем очень много усилий, чтобы поддерживать в нашем университете благоприятную образовательную среду: подбираем качественные и интересные курсы, приглашаем в качестве преподавателей известных ученых и ведущих разработчиков, развиваем партнерские отношения с известными IT-компаниями, создаём удобную для студентов инфраструктуру.

Часто на собеседованиях в магистратуру СПбАУ или CS центр ребята затрудняются ответить на вопросы об элементарных понятиях как из классической, так и из дискретной математики. А эти знания требуются для освоения курсов алгоритмов, машинного обучения и прочих Computer Science дисциплин. Чтобы облегчить подготовку, Академический университет совместно с Computer Science Center этой весной запускают два онлайн-курса:

1. Ликбез по дискретной математике. Преподаватель — А.В. Омельченко (СПбАУ РАН).
2. Введение в математический анализ. Преподаватель — А.И. Храбров (СПбГУ, СПбАУ РАН, CS центр).

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

Курсы размещены на дружественной платформе Stepic.

Часто на собеседованиях в магистратуру СПбАУ или CS центр ребята затрудняются ответить на вопросы об элементарных понятиях как из классической, так и из дискретной математики. А эти знания требуются для освоения курсов алгоритмов, машинного обучения и прочих Computer Science дисциплин. Чтобы облегчить подготовку, Академический университет совместно с Computer Science Center этой весной запускают два онлайн-курса:

1. Ликбез по дискретной математике. Преподаватель — А.В. Омельченко (СПбАУ РАН).
2. Введение в математический анализ. Преподаватель — А.И. Храбров (СПбГУ, СПбАУ РАН, CS центр).

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

Курсы размещены на дружественной платформе Stepic.

Магистратура Академического университета готовит специалистов в сфере IT уже 7 лет. И из года в год мы сталкиваемся с недостаточной подготовленностью поступивших по профильным для нас курсам. Как следствие, нам приходится преподавать в магистратуре базовые (бакалаврские) курсы. Поэтому вполне закономерно, что мы пришли к идее открыть свой собственный бакалавриат.

В результате кропотливой работы была создана и аккредитована программа обучения бакалавров, и летом 2014 года состоялся первый набор. В этой связи хочется поделиться с вами опытом приема и — недолгого пока — обучения вчерашних школьников, одаренных в области математики и информатики, а также узнать ваше мнение о путях дальнейшего усовершенствования образовательного процесса.

Магистратура Академического университета готовит специалистов в сфере IT уже 7 лет. И из года в год мы сталкиваемся с недостаточной подготовленностью поступивших по профильным для нас курсам. Как следствие, нам приходится преподавать в магистратуре базовые (бакалаврские) курсы. Поэтому вполне закономерно, что мы пришли к идее открыть свой собственный бакалавриат.

В результате кропотливой работы была создана и аккредитована программа обучения бакалавров, и летом 2014 года состоялся первый набор. В этой связи хочется поделиться с вами опытом приема и — недолгого пока — обучения вчерашних школьников, одаренных в области математики и информатики, а также узнать ваше мнение о путях дальнейшего усовершенствования образовательного процесса.

Академический университет поощряет и спонсирует участие студентов в мероприятиях научно-образовательного характера. В частности, довольно часто наши студенты участвуют в международных студенческих школах. Участие в студенческой школе позволяет не только узнать об актуальном состоянии науки и технологий, но и вживую пообщаться с ведущими исследователями и завести связи в сообществе. Кроме того, на некоторых школах студентам предоставляется возможность сделать доклад (на т.н. student session) о том, чем он в данный момент занимается (например, о своей магистерской работе). Это очень полезно, особенно, если студент хочет в дальшейшем заниматься исследованиями. Вполне возможно, что на такой школе студент определится с дальнейшими направлениями исследований или даже найдёт научного руководителя.



Если вы сами хотите поучаствовать в подобной студенческой школе, то советую заглянуть на сайт Computer Science клуба, на котором поддерживается список международных студенческих школ.

В качестве примера, публикуем отчёт нашего студента Кирилла Елагина о поездке на Estonian Winter School in Computer Science в 2014 г. Эта школа проходит в Эстонии каждый год и наши студенты регулярно её посещают.

Идея вводного курса по работе с Linux возникла у нас с коллегами довольно давно. Я с 2011 года занимаюсь биоинформатикой в Лаборатории алгоритмической биологии СПбАУ РАН (тут и тут мой напарник писал про то, чем мы занимаемся). Сразу нужно сказать, что работа биоинформатика без Linux практически невозможна, поскольку большинство биоинформатических программ созданы именно под эту операционную систему и работают только на ней.



В силу того, что это область на стыке наук, мы постоянно общаемся с биологами. Биологам же сейчас приходится работать с очень большими объемами данных, поэтому умение использовать Linux, оптимальную для подобных задач операционную систему, становится необходимым навыком. На самом деле, речь не только об умении обращаться с Linux, а в целом о компьютерной грамотности: какие существуют правила работы на сервере, как загружать и эффективно хранить файлы с данными, какие программы запускать для их обработки и как это сделать и т.д. — все те вещи, которые как упрощают и ускоряют вашу работу, так и значительно облегчают совместную деятельность с коллегам. Несмотря на то, что разобраться с Linux можно и самостоятельно, почитав умные книжки и сайты, для людей из не технической среды это часто вызывает определенные сложности и многие сдаются на начальных этапах освоения этой ОС (например, на знакомстве с командной строкой).

На основе нашего опыта я и мой коллега Андрей Пржибельский (@andrewprzh) изначально собирались провести несколько занятий для биологов по компьютерной грамотности. А потом эта идея выросла в трехнедельный открытый онлайн-курс (MOOC) Института биоинформатики на русском языке, который позже был сужен до именно введения в Linux, как отправной точки, — поскольку вместить все в три недели оказалось очень и очень трудно. Курс уже начался и оказался достаточно популярен (на данный момент на него записалось более пяти тысяч человек), но первый дедлайн по заданиям — 24 ноября, поэтому еще можно присоединиться без потери баллов или просто изучать курс в свободном режиме (все материалы останутся открытыми).

Думаю, что многие читатели Хабра уже слышали о биоинформатике, возможно даже непосредственно о задаче сборки генома. Множество людей по всем миру занято написанием геномных ассемблеров — программ, интерпретирующих сырые данные машин для секвенирования и выдающих в результате последовательность ДНК изучаемого организма. Однако, в большинстве случаев, геном целиком «из коробки» получить не удается. В этой статье я постараюсь объяснить, почему же геном нельзя собрать одним щелчком мыши и опишу процесс его «финиширования» — пожалуй, самый трудоемкий этап во всей сборке, порой длящийся несколько лет.

Также, я расскажу, как мы иногда можем существенно облегчить этот процесс, используя уже собранные геномы близкородственных организмов. Этой задачей я занимался в рамках написания своей магистерской диссертации в Санкт-Петербургском Академическом Университете, а обучение проходило совместно с Институтом Биоинформатики. Поскольку получившийся алгоритм достаточно специфичен, я начну с описания проблемы в целом, дам обзор некоторых «хардварных» методов ее решения, а затем немного расскажу о том, что же получилось у меня.

На этой неделе я начал читать бакалаврам Академического университета базовый курс по алгоритмам. Начинал я совсем с основ, и чтобы тем, кто с базовыми алгоритмами уже знаком, было чем заняться, я в начале пары сформулировал две, наверное, самые свои любимые задачки по алгоритмам. Давайте и с вами ими поделюсь. Решение одной из них даже под катом подробно расскажу. Но не отказывайте себе в удовольствии и не заглядывайте сразу под кат, а попытайтесь решить задачи самостоятельно. Обещаю, что у обеих задач есть достаточно простые решения, не подразумевающие никаких специальных знаний по алгоритмам. Это, конечно, не означает, что эти решения просто найти, но после пары один из студентов подошёл и рассказал правильное решение первой задачи. =) Если же вам интересно посмотреть на начало курса или порешать больше разных задач — приходите к нам на (бесплатный) онлайн-курс, который начнётся 15 сентября.

Задача 1. Дан массив A длины (n+1), содержащий натуральные числа от 1 до n. Найти любой повторяющийся элемент за время O(n), не изменяя массив и не используя дополнительной памяти.

Сразу поясню. В условии не говорится, что каждое число от 1 до n встречается в массиве, поэтому повторяющихся элементов там может быть сколько угодно (если бы все числа входили по разу, а одно — дважды, то задача была бы гораздо проще). Ограничение на использование дополнительной памяти означает, что нельзя заводить дополнительный массив линейной длины, но можно заводить переменные.

Задача 2. Дана матрица nxn, содержащая попарно различные натуральные числа. Требуется найти в ней локальный минимум за время O(n).

Локальным минимумом матрицы называется элемент, который меньше всех своих четырёх соседей (или трёх, если этот элемент лежит на границе; или двух, если это угловой элемент). Обратите внимание, что от нас требуется линейное по n время, хотя в матрице квадратичное по n число элементов. Поэтому мы предполагаем, что матрица уже считана в память. И нам нужно найти в ней локальный минимум, обратившись лишь к линейному количеству её ячеек.

Под катом — решение первой задачи. Ещё раз призываю вас заглядывать под кат только после того, как порешаете задачу. По второй задаче могу какую-нибудь подсказку сказать.