Pull to refresh
  • by relevance
  • by date
  • by rating

Ozon Masters: прием заявок на набор 2021 года

Ozon Tech corporate blog Programming *Mathematics *Machine learning *Studying in IT

Открыт прием заявок на программу Ozon Masters.

Ozon Masters - это 2-х летняя образовательная программа в области Data Science и бизнес-аналитики.

Подробнее о программе, процессе обучения и порядке поступления рассказано под катом

Читать далее
Total votes 8: ↑8 and ↓0 +8
Views 2.8K
Comments 0

Архив Дейкстры

Lumber room
Эдсгер В. Дейкстра (Edsger Wybe Dijkstra, 1930 — 2002) — один из создателей современного программирования. Он входил в состав команды, написавшей компилятор с языка ALGOL 60. Знаменитая статья Дейкстры «О вреде оператора GO TO» (Go To Statement Considered Harmful), опубликованная в марте 1968 года, положила начало структурному подходу к программированию.
Читать дальше →
Total votes 17: ↑15 and ↓2 +13
Views 1.1K
Comments 7

Почему программистов не учат? Часть 2.

Studying in IT
Всем доброго времени суток. На мой предыдущий пост хабра-сообщество ответило почти полутысячей комментариев, что меня окончательно убедило в том, что проблема, которую я обозначил, действительно существует и близка многим. Чисто физически всем ответить у меня нет возможности, хотя очень многие комментарии достойны были реакции, и поэтому я решил написать продолжение.
Читать дальше →
Total votes 32: ↑23 and ↓9 +14
Views 677
Comments 23

Автоматическое дифференцирование

Abnormal programming *Mathematics *
imageВ программировании один из заветов — не дублировать функциональность. Иначе мы получаем код, в котором одни участки нетривиально зависят от других. При реализации части задач этому принципу легко следовать, но в других возникают проблемы: рассмотрим софт, который использует не очень хитрые математические алгоритмы, требующие работы с функциями и их производными.
Читать дальше →
Total votes 55: ↑43 and ↓12 +31
Views 9.8K
Comments 50

dual-pivot quicksort

Algorithms *
Улучшенный алгоритм quicksort: iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf

Краткое описание:
Обычный quicksort делит массив на два отрезка, выбрав случайный элемент P. Потом сортирует массив так, чтобы все элементы меньше P попали в первый отрезок, а остальные — во второй. Затем алгоритм рекурсивно повторяется на первом и на втором отрезках.

Dual-pivot quicksort делит массив на три отрезка, вместо двух. В результате количество операций перемещения элементов массива существенно сокращается.

В PDF-е автор алгоритма привдит более детализированное описание алгоритма и имплементацию на java.
Total votes 21: ↑13 and ↓8 +5
Views 8.8K
Comments 8

Открыт набор в школу Яндекса

IT-companies
Около недели назад Яндекс объявил о наборе на новый учебный год в свою школу. Обучение ведётся по двум направлениям: анализ данных и computer science. В качестве вступительного задания абитуриенту школы предлагается рассказать о себе и решить несколько несложных задачек по математическому анализу, теории вероятностей и программированию. Решения можно отправлять до 15 августа.

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

Обучение бесплатное, очно-заочное (вечернее), занятия проходят по вечерам, примерно с 18 до 20. Судя по отзывам моих знакомых, учиться интересно и местами даже сложно.

На сайте ничего не сказано о возрастном ограничении, так что дерзайте!

UPD: после заочной анкеты проводится очное собеседование, на котором вопросы могут быть сложнее. kronos о собеседовании.
Total votes 93: ↑82 and ↓11 +71
Views 4.2K
Comments 86

Магистерская программа по биоинформатике Санкт-Петербургского Академического университета (бывший АФТУ РАН)

Studying in IT
Повсеместный переход на Болонскую систему даёт студентам возможность сменить ВУЗ после получения диплома бакалавра. Однако немногие студенты задумываются об этом. Во многих ВУЗах магистерская программа очень «разрежена»: присутствует множество непрофильных курсов (философия, культурология и т.д.), профильных же очень мало, и для того, чтобы их сдать, достаточно просто появиться на экзамене/зачёте.

Тех, кто ещё сохранил желание учиться, а также интересуется биоинформатикой и имеет образование в области математики и/или информатики, кафедра математических и информационных технологий Академического университета приглашает в новую магистратуру по биоинформатике в Санкт-Петербурге.
Читать дальше →
Total votes 12: ↑11 and ↓1 +10
Views 2.2K
Comments 15

Опубликован весь архив Computer Science клуб при ПОМИ РАН

Лекториум corporate blog
Добрый день!

Как представитель проекта Лекториум рад сообщить — мы опубликовали весь архив Computer Science клуба.
Кроме того, почти год назад мы организовали запись всех лекций на хорошие камеры и микрофоны.
А в этом году планируем подключить вебинары.


Большинство лекций читается на русском языке. Все записи снабжены презентациями и описаниями.

UPD. Кратко. Старые лекции в плохом качестве, а новые с 2010 года с хорошим звуком и в 720p.
UPD 2 Расширили канал, видео грузится теперь без проблем.

Под катом перечень курсов и несколько вопросов касательно вебинаров.
Читать дальше →
Total votes 231: ↑227 and ↓4 +223
Views 5.5K
Comments 78

Международная конференция Computer Science Symposium in Russia (CSR 2011)

Образовательные проекты JetBrains corporate blog

С 14 по 18 июня 2011 года в Санкт-Петербурге пройдёт 6-я Международная конференция Computer Science Symposium in Russia (CSR 2011). Темы конференции включают в себя алгоритмы и структуры данных, комбинаторную оптимизацию, теорию сложности вычислений, криптографию, комбинаторику, формальные языки и автоматы и др. Крайний срок подачи статей — 6 декабря 2010 года. Подробности на сайте конференции: http://logic.pdmi.ras.ru/csr2011
Ниже приведён список приглашённых докладчиков конференции.
Читать дальше →
Total votes 28: ↑26 and ↓2 +24
Views 916
Comments 6

Открытое письмо ученым и эталонная реализация алгоритма Романова для NP-полной задачи 3-ВЫП

Algorithms *
С момента предыдущей публикации о полиномиальном алгоритме Романова для 3-ВЫП прошло 4,5 месяца.

За это время мы с Владимиром Федоровичем подготовили вариант статьи, чтобы отправить его коллегам-ученым и попутно реализовали эталонную реализацию этого алгоритма на Java.
Читать дальше →
Total votes 60: ↑52 and ↓8 +44
Views 8.7K
Comments 132

Почему я не верю в простые алгоритмы для NP-полных задач

Algorithms *
На днях в этом блоге было опубликовано открытое письмо учёным по поводу предполагаемого полиномиального алгоритма для задачи 3-SAT. Обсуждение в том топике ещё далеко не закрыто и говорить о том, что в алгориме найдены ошибки пока преждевременно, но мне хочется написать почему «граждане учёные» не выстраиваются в очередь чтобы поскорее проверить это доказательство.

Примерно полгода назад, в августе 2010-го была опубликована попытка доказать что P≠NP. Тогда один математик-блогер, Скотт Оронсон, чтобы не казаться голословным в своём недоверии к этому доказательству поставил свой дом на то, что доказательство окажется ошибочным. Пожалуй, я ничего не потеряю если последую (с меньшим размахом) его примеру и поставлю на то, что нынешний алгоритм неправилен свой автомобиль (Auris 2008-го года выпуска).

По-моему, Оронсон немного рисковал. Винод Деолаликар, автор того доказательства — относительно известный математик, задача P≠NP входит в область его компетенции, и само доказательство использовало несколько принципиально новых идей, дающих надежду на то, что с помощью них удастся обойти трудности, с которыми сталкивались те кто пытался доказать этот факт до него. С нынешним доказательством ситуация немного иная.
Читать дальше →
Total votes 79: ↑58 and ↓21 +37
Views 11K
Comments 73

Обсуждение работы алгоритма Романова на примере

Algorithms *
В продолжение вчерашнего обсуждения.

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

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

Unit-тест и подробный лог работы приложения я выложил здесь:

gist.github.com/791064

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

Как видно из лога работы, тест заканчивается ситуацией, когда на очередном шаге построения гиперструктуры базисный граф оказался пустым множеством, что согласно алгоритму означает, что формула не выполнима (пункт 2b внизу страницы 11 в тексте статьи).

Чтобы не переписывать здесь еще раз статью, предлагаю в обсуждении задавать вопросы, которые требуют дополнительных разъяснений.
Total votes 26: ↑21 and ↓5 +16
Views 2.5K
Comments 24

Моноиды и их приложения: моноидальные вычисления в деревьях

Algorithms *
Приветствую, Хабрахабр. Сегодня я хочу, в своём обычном стиле, устроить сообществу небольшой ликбез по структурам данных. Только на этот раз он будет гораздо более всеобъемлющ, а его применения и практичность — простираться далеко в самые разнообразные области программирования. Самые красивые применения, я, конечно же, покажу и опишу непосредственно в статье.

Нам понадобится капелька абстрактного мышления, знание какого-нибудь сбалансированного дерева поиска (например, описанного мною ранее декартова дерева), умение читать простой код на C#, и желание применить полученные знания.

Итак, на повестке сегодняшнего дня — моноиды и их основное применение для кеширования вычислений в деревьях.

Моноид как концепция


Представьте себе множество чего угодно, множество, состоящее из объектов, которыми мы собираемся манипулировать. Назовём его M. На этом множестве мы вводим бинарную операцию, то есть функцию, которая паре элементов множества ставит в соответствие новый элемент. Здесь и далее эту абстрактную операцию мы будем обозначать "⊗", и записывать выражения в инфиксной форме: если a и b — элементы множества, то c = ab — тоже какой-то элемент этого множества.

Например, рассмотрим все строки, существующие на свете. И рассмотрим операцию конкатенации строк, традиционно обозначаемую в математике "◦", а в большинстве языков программирования "+": "John""Doe" = "JohnDoe". Здесь множество M — строки, а "◦" выступает в качестве операции "⊗".
Или другой пример — функция fst, известная в функциональных языках при манипуляции с кортежами. Из двух своих аргументов она возвращает в качестве результата первый по порядку. Так, fst(5, 2) = 5; fst("foo", "bar") = "foo". Безразлично, на каком множестве рассматривать эту бинарную операцию, так что в вашей воле выбрать любое.

Далее мы на нашу операцию "⊗" накладываем ограничение ассоциативности. Это значит, что от неё требуется следующее: если с помощью "⊗" комбинируют последовательность объектов, то результат должен оставаться одинаковым вне зависимости от порядка применения "⊗". Более строго, для любых трёх объектов a, b и c должно иметь место:
(ab) ⊗ c = a ⊗ (bc)
Легко увидеть, что конкатенация строк ассоциативна: не важно, какое склеивание в последовательности строк выполнять раньше, а какое позже, в итоге все равно получится общая склейка всех строк в последовательности. То же касается и функции fst, ибо:
fst(fst(a, b), c) = a
fst(a, fst(b, c)) = a
Цепочка применений fst к последовательности в любом порядке всё равно выдаст её головной элемент.

И последнее, что мы потребуем: в множестве M по отношению к операции должен существовать нейтральный элемент, или единица операции. Это такой объект, который можно комбинировать с любым элементом множества, и это не изменит последний. Формально выражаясь, если e — нейтральный элемент, то для любого a из множества имеет место:
ae = ea = a
В примере со строками нейтральным элементом выступает пустая строка "": с какой стороны к какой строке её ни приклеивай, строка не поменяется. А вот fst в этом отношении нам устроит подлянку: нейтральный элемент для неё придумать невозможно. Ведь fst(e, a) = e всегда, и если ae, то свойство нейтральности мы теряем. Можно, конечно, рассмотреть fst на множестве из одного элемента, но кому такая скука нужна? :)

Каждую такую тройку <M, ⊗, e> мы и будем торжественно называть моноидом. Зафиксируем это знание в коде:
public interface IMonoid<T> {
    T Zero { get; }
    T Append(T a, T b);
}

Больше примеров моноидов, а также где мы их, собственно, применять будем, лежит под катом.
Читать дальше →
Total votes 127: ↑124 and ↓3 +121
Views 19K
Comments 27

Весенний семестр 2011 в Computer Science клубе в Санкт-Петербурге и Екатеринбурге

Algorithms *


Весенний семестр в Computer Science клубе будет довольно алгоритмическим.

Курсы


В. Л. Ерухимов
Компьютерное зрение и библиотека OpenCV
Санкт-Петербург
3 пары, начало: 20.02
Д. Н. Москвин
Системы типизации лямбда-исчисления
Санкт-Петербург
12 пар, начало: 27.02
Ф. Фомин
Параметризованные
алгоритмы

Санкт-Петербург
4 пары, начало: 19.03
М. Бабенко
Линейное программирование
Санкт-Петербург
10 пар, начало: 16.04
М. Н. Вялый
Квантовые алгоритмы: возможности и ограничения
Санкт-Петербург
10 пар, начало: 02.04
П. Браславский
Анализ поисковых запросов
Екатеринбург
3 пар, начало: 13.05
Д. С. Перевалов
Что может и не может компьютерное зрение с OpenCV
Екатеринбург
2 пары, начало: 17.02
М. Ю. Хачай
Теоретические основы распознавания образов
Екатеринбург
6 пар, начало: 03.03
А. М. Райгородский
Случайные графы и алгоритмы
Екатеринбург
6 пар, начало: 18.03
М. А. Ройтберг
Анализ символьных последовательностей
Екатеринбург
6 пар, начало: 21.04


Читать дальше →
Total votes 81: ↑71 and ↓10 +61
Views 1.1K
Comments 33

Evangelos Kranakis

Lumber room
image

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

Today we're talking with Evangelos Kranakis, PhD. Mathematician, computer scientist, received a B.Sc. (in Mathematics) from the University of Athens, Greece, in 1973 and a Ph.D. (in Mathematical Logic) from the University of Minnesota, USA, in 1980. Worked with mathematics Department of Purdue University, USA, mathematisches institut of the University of Heidelberg, Germany, Computer Science Department of Yale University, USA, Computer Science Department of the Universiteit van Amsterdam, Centrum voor Wiskunde en Informatica (CWI) in Amsterdam. Evangelos joined the faculty of the School of Computer Science of Carleton University in the Fall of 1991.

— Greece, Canada, USA, Germany, Netherlands
— Education system
— What is computer science?
— State of modern computer science and mathematics
— Why networking is important?
— Bioinformatics, genes. What do we know about DNA?
— Words of wisdom
— How to learn to understand mathematics?
— Is P=NP?
Total votes 14: ↑5 and ↓9 -4
Views 219
Comments 0

Набор в магистратуру Академического университета (Санкт-Петербург)

Образовательные проекты JetBrains corporate blog

Повсеместный переход на Болонскую систему даёт студентам возможность сменить ВУЗ после получения диплома бакалавра, однако не все студенты понимают, как это может изменить их жизнь. Во многих ВУЗах магистерская программа очень "разрежена": присутствует множество непрофильных курсов (философия, культурология и т.д.), профильных же очень мало, и для того, чтобы их сдать, достаточно просто появиться на экзамене/зачёте.

Тех, кто ещё сохранил желание учиться, кафедра математических и информационных технологий Санкт-Петербургского академического университета Российской академии наук приглашает в магистратуру для обучения по одной из трёх программ:
Читать дальше →
Total votes 44: ↑42 and ↓2 +40
Views 3.9K
Comments 82

Алгоритмы: поиск химических соединений, задача ранжирования и анализ геномов

Algorithms *


Первого мая в Computer Science клубе при ПОМИ РАН состоятся три интересные лекции. Лекции можно послушать вживую в ПОМИ РАН (Санкт-Петербург, наб. р. Фонтанки, д. 27; вход свободный, никакой предварительной регистрации не требуется) или же по трансляции, организуемой проектом Лекториум.

В 11:15 Михаил Рыбалкин (ПОМИ РАН и GGA Software Services) расскажет о подструктурном поиске химических соединений в базах даных. В 13:00 Игорь Куралёнок (СПбГУ и Яндекс) сделает доклад о практическом применении методов машинного обучения. Наконец, в 14:35 Максим Алексеев (University of South Carolina) расскажет о комбинаторных задачах и алгоритмах сравнительного анализа геномов.
Total votes 32: ↑32 and ↓0 +32
Views 1.7K
Comments 10

Первый набор в Computer Science Center (Санкт-Петербург)

Self Promo

Computer Science Center (Санкт-Петербург) объявляет о начале первого набора.

Computer Science Center — это совместная инициатива Академии современного программирования, Computer Science клуба при ПОМИ РАН и Школы анализа данных Яндекса. В центре желающие могут получить знания, востребованные современной наукой и рынком программирования.

Читать дальше →
Total votes 46: ↑41 and ↓5 +36
Views 1.9K
Comments 13

Экзоядро: архитектура операционной системы управления ресурсами на уровне приложений

Software
Привет, хабраюзер!
Сегодня я хочу тебя порадовать переводом части статьи за авторством Доусона Энглера, Франса Каашоека и Джеймса О'Тулла-младшего из лаборатории компьютерной науки M.I.T. (Dawson R. Engler, M. Frans Kaashoek, James O'Toole Jr., M.I.T. Laboratory of Computer Science) про экзоядерные операционные системы. Сама статья довольно объемная, так что переводить я ее буду по частям, если, конечно, вам будет интересно.
Читать дальше →
Total votes 57: ↑40 and ↓17 +23
Views 5.4K
Comments 16