Computer Science Center (образовательный проект ШАД Яндекса, компании JetBrains и Сomputer Science клуба при ПОМИ РАН) продолжает регистрацию на бесплатные массовые открытые онлайн-курсы (MOOC) по основам программирования.

Как мы уже писали, с 15 сентября 2014 года можно будет пройти следующие онлайн-курсы:
1. Алгоритмы и структуры данных (А.С. Куликов)
2. Введение в архитектуру ЭВМ. Элементы операционных систем (К.В. Кринкин)
3. Программирование на языке C++ (А.В. Смаль)

В данном посте пойдёт речь о том, как CS центр использовал онлайн-курс по Алгоритмам и структурам данных в качестве одного из этапов приёмной кампании в 2014 году.

Computer Science Center (образовательный проект ШАД Яндекса, компании JetBrains и Сomputer Science клуба при ПОМИ РАН), открывает запись на массовые открытые онлайн-курсы (MOOC) по основам программирования.

С 15 сентября 2014 года можно будет пройти следующие онлайн-курсы, подготовленные преподавателями CS центра:

1. Алгоритмы и структуры данных (А.С. Куликов)
2. Введение в архитектуру ЭВМ. Элементы операционных систем (К.В. Кринкин)
3. Программирование на языке C++ (А.В. Смаль)

Данные три курса являются «джентльменским набором» начинающего программиста, преподаются на русском языке и бесплатны для всех желающих. Преподаватели при подготовке курса пользовались опытом чтения одноименных дисциплин в CS центре и Академическом университете. Записаться на курсы можно на сайте CS центра. Для освоения курсов слушателям достаточно владеть школьной программой по математике, информатике, физике.

Для создания и размещения онлайн-курсов СS Center использовал образовательный плеер Stepic. Проект Stepic существует с 2013 года и выделяется среди других образовательных платформ возможностями для автоматической проверки задач на программирование, например, безопасное исполнение пользовательского кода в песочнице (C++, Java, Python, Haskell, Octave), а также генерация и проверка рандомизированных датасетов. Cистема проверки задач Stepic была использована в ряде курсов на платформе Coursera, включая курсы от Калифорнийского университета в Сан-Диего и НИУ «Высшая школа экономики».

Так как онлайн-курсы продолжают захватывать планету, а в России этот процесс идет весьма медленно, мы решили внести свой вклад в популяризацию онлайн-образования среди русскоязычных преподавателей и провести конкурс на создание открытых курсов и учебных материалов с использованием некоммерческой платформы Stepic.

Мы сделали небольшой анализ существующих возможностей получить поддержку для создания открытого интернет-курса на русском языке и пришли к выводу, что вариантов совсем немного. Получить грант на эти цели можно от Благотворительного фонда В. Потанина (но только при условии, что вы – преподаватель магистратуры), свои внутренние бюджеты на развитие дистанционного обучения есть у ряда университетов (например, у НИУ ИТМО, СПбГПУ, НИУ ВШЭ, СПбГУ, МФТИ), некоторые платформы покрывают часть расходов на создание курсов (например, «Лекториум»). Возможно, есть и другие варианты, добавляйте в комментариях, если знаете.

Комбинаторика в старших классах школы, как правило, ограничивается текстовыми задачами, в которых нужно применить одну из трёх известных формул — для числа сочетаний, перестановок или размещений. В институтских курсах по дискретной математике рассказывают и о более сложных комбинаторных объектах — скобочных последовательностях, деревьях, графах… При этом, как правило, ставят задачу вычислить количество объектов данного типа для некоторого параметра n, например количество деревьев на n вершинах. Узнав количество объектов для фиксированного n, можно задаться и более сложным вопросом: как все эти объекты за разумное время предъявить? Алгоритмы, решающие подобного рода задачи, называются алгоритмами комбинаторной генерации. Таким алгоритмам, например, посвящена первая глава четвёртого тома «Искусства программирования» Дональда Кнута. Кнут очень подробно рассматривает алгоритмы генерации всех кортежей, разбиений числа, деревьев и других структур. Придумать какой-нибудь алгоритм, работающий умеренно быстро, для каждой из этих задач несложно, но с дальнейшей оптимизацией могут возникнуть серьёзные проблемы.

В процессе написания магистерской диссертации, защищённой в Академическом университете, мне потребовалось изучить и применить один из алгоритмов комбинаторной генерации, подходящий для особого класса задач. Это генерация структур, на которых дополнительно введено некоторое отношение эквивалентности. Чтобы было понятно, о чём идёт речь, я приведу простой пример. Давайте попробуем сгенерировать все триангуляции шестиугольника. Получится что-нибудь такое:



Написать алгоритм, который вернёт все такие триангуляции, довольно несложно. Например, сгодится такая процедура: фиксируем какое-нибудь ребро (пусть это будет ребро 1-6), после чего в цикле перебираем вершины, не являющиеся его концами. На текущей вершине и фиксированном ребре строим треугольник, а оставшиеся после этого две области триангулируем рекурсивно. Если присмотреться к получающимся в результате работы этого алгоритма триангуляциям, то можно заметить, что многие из них почти одинаковы и отличаются лишь тем, как расставлены пометки (номера) вершин. Поэтому, полезно было бы придумать алгоритм, который будет генерировать так называемые непомеченные триангуляции — те, что изображены на следующем рисунке:

В этом году в московском офисе Яндекса пройдёт юбилейная 25-я конференция Combinatorial Pattern Matching — главное в мире событие в области алгоритмов на строках.

Конференция начнётся с открытых лекций известных ученых, являющихся отцами-основателями серии конференций и внёсшими огромный вклад в область алгоритмов на строках:

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

Что будет в этой статье

Продолжаем цикл статей о создании файловой системы в ядре Linux, основанный на материалах курса ОС в Академическом университете .

В прошлый раз мы настроили окружение, которое понадобится нам, чтобы знакомится с ядром. Затем мы взглянули на загружаемые модули ядра и написали простой «Hello, World!». Ну и наконец, мы написали простую и бесполезную файловую систему. Пришло время продолжить.

Главная цель этой статьи научить файловую систему читать с диска. Пока она будет читать только служебную информацию (суперблок и индексные узлы), так что пользоваться ей все еще довольно трудно.

Почему так мало? Дело в том, что в этом посте нам потребуется определить структуру нашей файловой системы — то как она будет хранится на диске. Кроме того мы столкнемся с парой интересных моментов, таких как SLAB и RCU. Все это потребует некоторых объяснений — много слов и мало кода, так что пост и так будет довольно объемным.

Данная статья составлена преподавателем Академического университета Валерием Исаевым по материалам практики по курсу функционального программирования.

Полагаю, ни для кого не секрет, что написание многопоточных приложений связано с целым рядом проблем, отсутствующих при разработке однопоточных программ.
Одна из проблем заключается в тестировании приложения.
Мы не можем контролировать порядок, в котором выполняются операции, следовательно, не поддается контролю и результат выполнения программы. Даже если мы получим ошибку, наступить на те же грабли второй раз будет не так-то просто.
Хочу предложить небольшой рецепт того, как можно протестировать многопоточное приложение.
Из ингредиентов нам понадобятся: haskell, QuickCheck, немного монад, соль/перец по вкусу.

Рад сообщить, что вышел перевод отличнейшего учебника Дасгупты, Пападимитриу, Вазирани «Алгоритмы», над которым я работал последние несколько лет. В книге многие алгоритмы объяснены гораздо короче и проще, чем в других учебниках: с одной стороны, без излишнего формализа, с другой — без потери математической строгости. Откройте книгу на каком-нибудь известном вам алгоритме и убедитесь в этом. =)

В общем, угощайтесь: печатный вариант перевода, электронный вариант перевода (PDF), печатный вариант оригинала, электронный вариант оригинала (PDF).

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

В этом посте мы порассуждаем о том, какой должна быть магистерская диссертация computer science.

Магистерские диссертации: плохие и хорошие

Успешное обучение в магистратуре неизбежно заканчивается защитой магистерской диссертации.
Давайте обсудим, чем хорошая магистерская диссертация отличается от плохой.

На нашей кафедре защищают два типа магистерских диссертаций: теоретические (теоретическая информатика и биоинформатика) и прикладные (разработка ПО).

Для кого эта статья

Данная статья составлена по материалам практики по курсу операционных систем в Академическом университете . Материал готовился для студентов, и ничего сложного здесь не будет, достаточно базового знания командной строки, языка C, Makefile и общих теоретических знаний о файловых системах.

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

Мы уже писали о том, что одним из результатов обучения в университете (с нашей точки зрения) должна быть широта знаний. Сегодня мы публикуем пост одного из наших выпускников, который решил сменить направление работы после университета, и попробуем посмотреть, что из этого получилось.

Computer Science центр объявил от открытии набора на 2014-2016/2017 учебные годы. В связи с этим очень хотелось бы узнать мнение общественности о том, какой формат дополнительного образования наиболее интересен и нужно ли оно вообще.

Существует несколько основных форматов дополнительного образования:

Теоретическая информатика — одно из направлений обучения на кафедре Математических и информационные технологий Академического университета. Нас часто спрашивают, чем занимается теоретическая информатика. Теоретическая информатика — активно развивающееся научное направление, включающее в себя как фундаментальные области: алгоритмы, сложность вычислений, криптография, теория информации, теория кодирования, алгоритмическая теория игр, так и более прикладные: искусственный интеллект, машинное обучение, семантика языков программирования, верификация, автоматическое доказательство теорем и многое другое. Эту статью мы посвятим обзору лишь небольшого сюжета, а именно расскажем о необычных подходах к понятию доказательства, которые рассматривает теоретическая информатика.



Чтобы объяснить, о какого рода доказательствах пойдет речь, рассмотрим пример: есть компьютерная программа, авторы которой утверждают, что программа делает что-то определенное (конкретные примеры будут чуть позже). Программу можно запустить и получить ответ. А как можно удостовериться, что программа делает то, что должна делать? Хорошо бы, если кроме ответа программа выдавала бы доказательство того, что этот ответ правильный.

Рассмотрим более конкретный пример: мы хотим иметь программу, которая в двудольном графе находит паросочетание максимального размера вместе с доказательством его максимальности.



Напомним, что граф называется двудольным, если его вершины можно покрасить в два цвета так, что ребра графа соединяют вершины разных цветов. Паросочетанием в графе называется такое множество ребер, что никакие два из них не имеют общего конца. Множество вершин графа называется покрывающим, если каждое ребро графа имеет как минимум один конец в этом множестве. Теорема Кенига гласит, что в двудольном графе размер максимального паросочетания совпадает с размером минимального покрывающего множества. Таким образом, чтобы доказать, что паросочетание является максимальным, можно предъявить, покрывающее множество, размер которого совпадает с размером данного паросочетания. Действительно, это покрывающее множество будет минимальным, поскольку каждое покрывающее множество обязано покрыть хотя бы один конец каждого ребра этого паросочетания. Например, в графе на рисунке паросочетание (M1, G3), (M2, G2), (M4,G1) будет максимальным, поскольку есть покрывающее множество размера 3, которое состоит из G2, G3 и M4. Отметим, что проверить такое доказательство гораздо проще, чем вычислять максимальное паросочетание: достаточно проверить, что размер паросочетания совпадает с размером покрывающего множества и проверить, что все ребра покрыты.

Рассмотрим еще один пример, допустим нам нужна программа, которая проверяет систему нестрогих линейных неравенств с рациональными коэффициентами на совместность (напомним, что система неравенств называется совместной, если можно подобрать такие значения переменных, что все неравенства выполняются).



Как можно доказать правильность результата? Если система совместна, то доказательством совместности может стать решение этой системы (нетрудно доказать, что если у такой системы есть решение, то есть и рациональное решение, т.е. его можно записать). А как доказать, что система несовместна? Оказывается, что это сделать можно с помощью леммы Фаркаша, которая утверждает, что если система нестрогих линейных неравенств несовместна, то можно сложить эти неравенства с неотрицательными коэффициентами и получить противоречивое неравенство 0≥1. Например, система на рисунке несовместна, и если сложить первое уравнение с коэффициентом 1, второе с коэффициентом 2, а третье с коэффициентом 1, то получится 0≥1. Доказательством несовместности будет как раз набор неотрицательных коэффициентов.

В этой статье мы поговорим о том, нужны ли доказательства, или проверка доказательства всегда не проще, чем самостоятельное решение задачи. (В примере про максимальное паросочетание мы не доказали, что не существует алгоритма, решающего задачу за то же время, сколько занимает проверка доказательства.) Если мы не ограничиваем размер доказательства, то окажется, что доказательства нужны, а если будем требовать, чтобы доказательства были короткими, то вопрос о нужности доказательств эквивалентен важнейшему открытому вопросу о равенстве классов P и NP. Потом мы поговорим об интерактивных доказательствах (доказательства в диалоге). Обсудим криптографические доказательства, которые не разглашают лишнюю информацию, кроме верности доказываемого утверждения. И закончим обсуждением вероятностно проверяемых доказательств и знаменитой PCP-теоремы, которая используется для доказательства трудности приближения оптимизационных задач.

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

Перед прочтением статьи рекомендую посмотреть посты про splay-деревья (1) и деревья по неявному ключу (2, 3, 4)

Динамические деревья (link/cut trees) мало освещены в русскоязычном интернете. Я нашел только краткое описание на алголисте. Тем не менее эта структура данных очень интересна. Она находится на стыке двух областей: потоки и динамические графы.

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

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

Перед тем, как нырнуть под кат, попробуйте решить следующую задачу. Дан взвешенный граф в виде последовательности ребер. По последовательности можно пройти только один раз. Требуется посчитать минимальное покрывающее дерево, используя памяти и времени. По прочтении статьи вы поймете, как легко и просто можно решить эту задачу, используя динамические деревья.

Когда я оканчивал школу, мой учитель информатики на последнем уроке говорил следующие слова: «Чем дольше вы будете учиться и чем позже начнете работать, тем на большую зарплату вы сможете рассчитывать». С тех пор много воды утекло, и я успел несколько раз изменить собственное мнение по этому поводу, но в свете последних постов о проблемах образования в IT хотелось бы еще раз обсудить эту тему.

Компаниям, как правило, нужны программисты двух типов. Одни — «рабочие руки», т.е. те, кто умеет хорошо выполнять порученное им задание, и вторые — «рабочие мозги», т.е. те, кто может генерировать новые идеи, предлагать новые подходы, разрабатывать новые направления.
Что касается первой категории, то для того, чтобы в ней работать действительно может хватить пары курсов института и книжек перед сном. Со второй категорией все сложнее… Дело в том, что специалисты этого уровня должны иметь знания шире, чем это требуется для их непосредственной работы.
Вот о том, как готовить специалистов второй категории и хочется поговорить сегодня. И начать с азов — с бакалавриата.

Продолжаем рассказывать о нашем опыте построения «самой лучшей магистратуры по Computer Science» =) и интересоваться мнением IT-сообщества. Напомню, что нашей целью было создать магистратуру с сильной программой, в которой не было бы «лишних» курсов. И благодаря сотрудничеству с Академией Современного Программирования и лабораторией математической логики Санкт-Петербургского отделения математического института им. В.А. Стеклова РАН у нас это успешно получилось сделать.

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

В этом посте мы обсудим, чему нужно учить в магистратуре по Computer Science.

Сбалансированное дерево поиска является фундаментом для многих современных алгоритмов. На страницах книг по Computer Science вы найдете описания красно-черных, AVL-, B- и многих других сбалансированных деревьев. Но является ли перманентная сбалансированность тем Святым Граалем, за которым следует гоняться?

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

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

C тех пор, как я опубликовал первую обзорную статью о биоинформатике, прошел уже почти год. Хотелось бы писать чаще, но как раз биоинформатика отвлекаться и не дает. В предыдущей статье была упомянута задача сборки генома, а также Лаборатория алгоритмической биологии (СПбАУ РАН), в которой ей занимаются. Как уже было сказано, над этой задачей работают во многих университетах мира давно и достаточно успешно. Однако для сборки генома биологи получают огромное количество различных типов данных, каждый из которых имеет свои особенности. Около пяти лет назад появилась технология MDA, открывшая большие возможности в области изучения бактерий. В результате появился тип данных, для которого потребовался новый геномный сборщик. Через несколько лет он был разработан, и не в Стэнфорде или Массачусетсе, а в Санкт-Петербурге, в молодом Академическом университете. Но обо всем по порядку.

Я хочу описать историю одного заносчивого и самовлюбленного студента Академического Университета, коим я, конечно, не являюсь, но хорошо представляю его мысли и переживания. Будем называть этого студента, например, Шурик. На момент поступления Шурика в Академический Университет (АУ), согласно его программистскому резюме, он уже был экспертом в области алгоритмов. Он мастерски владел алгоритмом поиска в глубину, знал несколько методов сортировки массивов, и имел представление о двоичном поиске. Естественно, курс алгоритмов его не интересовал совершенно, да и вообще, мало чему можно научить программиста с пятилетним опытом. Программа теоретической информатики АУ его заинтересовала тем, что в темах по известным ему предметам было слишком много неизвестных ему слов. Но это же Питер, там они и бордюр то странным словом называют, вероятно, и для поиска в глубину красивых слов понавыдумывали. Он тщательно изучил слайды и видеозаписи курсов. Оказалось, что существует какая-то там информатика, которой Шурик не владеет в совершенстве. Шурик собрал книги, носки и пять лет опыта, и отправился в Питер на собеседование. Там он встретил людей, которые могут научить чему-то даже программиста с таким опытом. Это все рушило Шурикову картину мира, в которой знание информатики измерялось количеством написанных классов на C#.
Во время учëбы в магистратуре Шурик занимался исследованиями в области схемной сложности и области экспоненциальных алгоритмов. Это действительно очень интересно и, что не менее важно, полезно для поступления в аспирантуру.
На данный момент Шурик является счастливым аспирантом New York University, использует слово «поребрик», и с глубокой благодарностью вспоминает Академический Университет. А кафедра математических и информационных технологий АУ и сейчас ведет набор новых магистрантов, в частности, по направлению «теоретическая информатика».
Сейчас я передаю слово Шурику, который и расскажет об одном своëм исследовании.

Кафедра математических и информационных технологий Санкт-Петербургского Академического университета РАН создана в 2008 году. В этом году ей исполняется 5 лет. Настало время подвести промежуточные итоги и поделиться опытом с сообществом.

Мы уже несколько раз писали об этом на хабре. Правда раньше мы ограничивались сухими объявлениями.

Зачем мы решили открыть кафедру?