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

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

Есть ли все это в университетских курсах? Конечно есть. Однако к законам Ома/Кирхгофа мы получаем термодинамику и теорию поля; помимо операций с матрицами и векторами приходится разбираться с Жордановыми формами; в программировании изучать полиморфизм — темы, которые не всегда нужны для решения простой практической задачи.

Университетское обучение экстенсивно — учащийся идет широким фронтом и зачастую не видит смысла и практической значимости знаний, которые получает. Мы решили перевернуть парадигму университетского обучения STEM (от слов Science, Technology, Engineering, Math) и сделать такую программу, которая опирается на связность знаний, допуская наращивание полноты в будущем, то есть подразумевает интенсивное освоение предметов.

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

Я занимаюсь программированием уже 15 лет. Но в последнее время при разработке не принято думать об эффективности, простоте и совершенстве: вплоть до того, что мне становится грустно за свою карьеру и за IT-отрасль в целом.

Для примера, современные автомобили работают, скажем, на 98% от того, что физически позволяет нынешняя конструкция двигателя. Современная архитектура использует точно рассчитанное количество материала, чтобы выполнять свою функцию и оставаться в безопасности в данных условиях. Все самолёты сошлись к оптимальному размеру/форме/нагрузке и в основном выглядят одинаково.

Только в программном обеспечении считается нормальным, если программа работает на уровне 1% или даже 0,01% от возможной производительности. Ни у кого вроде нет возражений.

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

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

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

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

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

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

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

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

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, включая курсы от Калифорнийского университета в Сан-Диего и НИУ «Высшая школа экономики».

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

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



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

Утро понедельника? Отличное время вспомнить, что хорошего уже успело случиться, чтобы начать неделю с добрых новостей!

Осенью 2013-го мы затеяли Kotlin Challenge — соревнование по программированию для тех, кто был готов попробовать Kotlin, новый язык программирования для платформы Java. Записались несколько сотен человек, осенью прошли заочные тренировочные туры и четвертьфиналы, в феврале 2014-го — полуфинал, и наконец…

На Хабре несколько месяцев назад обсуждалось, что нет идеального трекера — такого, чтобы он подошел хорошо и разработчику, и заказчику. В частности, упоминалось, что трекеру нужен help desk. В YouTrack начиная с версии 5.1 он есть, и сегодня мы расскажем, как его настраивать.

Перед ответом на вопрос «как» полезно понять, зачем. Типичный сценарий выбора YouTrack состоит в том, что вы решаете, какой баг-трекер взять для нового проекта, или легко ли включить требуемую функциональность в существующем. Тогда возможность буквально за пять минут добавить help desk в трекер склонит чашу весов в пользу YouTrack, если проект предполагает общение пользователей со службой поддержки.

Прежде всего, help desk должен иметь привычный интерфейс. Нет, мы (пока) не научили YouTrack отвечать красивым голосом на телефонные звонки. Однако и привыкать к веб-интерфейсу вашим пользователям незачем: в YouTrack можно просто писать письма. У вас на сайте написано, что писать в поддержку надо по адресу support@your-brilliant-app.com? Отлично, YouTrack может вынимать письма из этого ящика и делать из них заявки, видимые вашим разработчикам.

Хотя YouTrack — не бесплатное решение, вы можете сэкономить. Дело в том, что лицензия на YouTrack покупается на определенное количество разработчиков (до 10 — бесплатно). Разработчики работают с YouTrack с помощью веб-интерфейса.

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

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

Делаем себе свой YouTrack

Для теста я сделал себе экземпляр YouTrack в облаке. Если в проекте не требуется регистрировать больше 10 разработчиков, то можно взять бесплатный вариант.

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

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

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

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

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

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

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

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

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

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

Тема высшего образования очень популярна на хабре. Есть много статей о том, как плохо у нас, и как хорошо за рубежом. Сегодня я бы хотел рассказать вам, как я искал высшее образование в России. И нашёл.