Эдсгер В. Дейкстра (Edsger Wybe Dijkstra, 1930 — 2002) — один из создателей современного программирования. Он входил в состав команды, написавшей компилятор с языка ALGOL 60. Знаменитая статья Дейкстры «О вреде оператора GO TO» (Go To Statement Considered Harmful), опубликованная в марте 1968 года, положила начало структурному подходу к программированию.

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

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

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

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

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

В PDF-е автор алгоритма привдит более детализированное описание алгоритма и имплементацию на java.

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

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

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

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

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

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

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

 

Добрый день!

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


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

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

Под катом перечень курсов и несколько вопросов касательно вебинаров.

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

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

За это время мы с Владимиром Федоровичем подготовили вариант статьи, чтобы отправить его коллегам-ученым и попутно реализовали эталонную реализацию этого алгоритма на Java.

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

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

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

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

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

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

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

gist.github.com/791064

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

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

Чтобы не переписывать здесь еще раз статью, предлагаю в обсуждении задавать вопросы, которые требуют дополнительных разъяснений.

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

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

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

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

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

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

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

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

Каждую такую тройку <M, ⊗, e> мы и будем торжественно называть моноидом. Зафиксируем это знание в коде:

public interface IMonoid<T> {
    T Zero { get; }
    T Append(T a, T b);
}

Больше примеров моноидов, а также где мы их, собственно, применять будем, лежит под катом.

Весенний семестр в 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

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

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?

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

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

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

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