Алгоритмы *

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



Лектор – Софья Геннадьевна Кисельгоф, младший научный сотрудник Международной научной лаборатории анализа и выбора решений НИУ ВШЭ. Преподаватель департамента математики экономического факультета. На факультете компьютерных наук читает курс Operations Research and Game Theory. Защитила кандидатскую диссертацию на тему «Обобщенные паросочетания при предпочтениях, не являющихся линейными порядками». Софья Геннадьевна проводила исследование механизма зачисления абитуриентов в российские вузы в результате которого была построена модель, описывающая поведения абитуриента при выборе вуза.

Под катом – подробная стенограмма лекции.

Привет, Хабр!
Большинство разработчиков знает, что такое Nested Sets, их сильные и слабые стороны. Сегодня я хочу представить на суд общественности реализацию модификации этой методики, которая частично решает недостатки оригинального алгоритма, правда имеет и свои отрицательные стороны.

Предлагаю читателям «Хабрахабра» перевод небольшой заметки «Organizational Skills Beat Algorithmic Wizardry» за авторством James Hague. Заметка показалась интересной и мне захотелось поделиться с аудиторией.

Много раз я читал о технических собеседованиях в крупнейшие компании и был очень рад, что не ищу работу программиста. Способность написать оригинальные реализации кучи или дерева. Головоломки с различными ограничениями. Задачи, на обсчёт которых потребуется десять миллиардов лет если вы не сможете правильно проанализировать и перефразировать требования. Моя первая реакция – как вообще им удаётся хоть кого-нибудь нанять?

Яндекс умеет подсказывать цвета по их названию и находить близкие к ним. Некоторое время назад эту подсказку (внутри себя мы называем такие штуки «колдунщиками») пришлось переделывать, чтобы она соответствовала виду поисковых результатов после их редизайна. И мы воспользовались этим поводом, чтобы поработать над ним всерьёз, — ведь оказалось, что расположить цвета линейно — очень нетривиальная задача.







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

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

Так говорит Арам Харроу (Aram Harrow), профессор физики Массачуссетского технологического в своей статье «Почему сейчас самое подходящее время для изучения квантовых вычислений».

Он считает, что с научной точки зрения энтропия не могла быть полностью изученной, пока технология парового двигателя не дала толчок к развитию термодинамики. Квантовые вычисления появились из-за потребности имитировать квантовую механику на компьютере. Так и алгоритмы человеческого разума могут быть изучены с появлением нейронных сетей. Энтропия используется во многих областях: например, при смарт кропе, в кодировании видео и изображений; в статистике.

Всем привет! Сегодня я бы хотел рассказать о рендеринге, который не имеет отношения к компьютерным играм, анимационным фильмам или промышленным системам проектирования. Речь пойдет о движке для рендеринга карт в реальном времени для проекта MAPS.ME. В данном посте я опишу общие принципы работы движка и некоторые грабли, на которые мы наступили (и те, которые успешно обошли). Если вы занимаетесь рендерингом больших объемов данных, в особенности картографического характера, наш опыт, надеюсь, будет полезен в ваших проектах или, по крайней мере, любопытен. Всех заинтересовавшихся прошу под кат.

Здравствуйте, меня зовут Дмитрий Карловский и я… очень стар. Годы уже не те, чтобы с лёгкостью разбираться в хитросплетениях мудрёных интерфейсов. Хочется чего-то относительно простого, но и достаточно мощного, чтобы не чувствовать себя калекой, который еле-еле пишет простейшую программу.

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

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

Далее вы узнаете, как я избавился от геморроя путём смены городского минивена на спортивный велосипед :-)

Почему формальное определение цвета то ли есть, то ли нет, и связано ли это с тем, что его дал тот самый Шрёдингер? Что имел в виду Вейнберг, когда назвал свою революционную статью «Геометрия цветов»? Почему у цветового треугольника два угла, хотя интуитивно кажется, что должен быть один? Почему обычный детский рисунок показывает, что у автора всё в порядке с цветовосприятием, и зачем художник-академист всю жизнь учится его отключать? Почему в цветовом пространстве находятся кластеры, но они не находятся? Почему любая женщина знает о явлении метамерии окрасок, а ученые всё время забывают? Сколько должно быть цветовых каналов у хорошего фотоаппарата? А у монитора? А почему ответ разный? А красок у принтера?

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



Лектор — Дмитрий Николаев, заведующий сектором зрительных систем в Институте проблем передачи информации им. А.А. Харкевича РАН. Кандидат физико-математических наук, защитил диссертацию на тему «Алгоритмы цветовой сегментации, применимые в условиях сложного освещения сцены».

Как-то на собеседовании мне задали вопрос: какая реализация списка выполнит вставку в середину быстрее: ArrayList или LinkedList? С первого взгляда вопрос простой — нужно посчитать алгоритмическую сложность каждого варианта и сравнить их.

Перевод поста Джона Маклуна (Jon McLoone) "10 Tips for Writing Fast Mathematica Code".
Выражаю огромную благодарность Кириллу Гузенко KirillGuzenko за помощь в переводе.

---

Пост Джона Маклуна рассказывает о распространенных приемах ускорения кода, написанного на языке Wolfram Language. Для тех, кто заинтересуется этим вопросом мы рекомендуем ознакомиться с видео «Оптимизация кода в Wolfram Mathematica», из которого вы подробно и на множестве интересных примеров узнаете о приемах оптимизации кода, как рассмотренных в статье (но более детально), так и других.

---

Когда люди говорят мне, что Mathematica недостаточно быстро работает, обычно я прошу посмотреть код и часто обнаруживаю, что проблема не в производительности Mathematica, а в её не оптимальном использовании. Я хотел бы поделиться списком тех вещей, на которые я обращаю внимание в первую очередь при попытке оптимизировать код в Mathematica.

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

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

У большинства вычислительных программных систем нет такого понятия, как точная арифметика — для них 1/3 это то же самое, что и 0,33333333333333. Это различие может играть большую роль, когда вы сталкиваетесь со сложными и неустойчивыми задачами, однако для большинства задач числа с плавающей точкой вполне удовлетворяют нуждам, и что важно — вычисления с ними проходят значительно быстрее. В Mathematica любое число с точкой и с менее чем 16 цифрами автоматически обрабатывается с машинной точностью, потому всегда следует использовать десятичную точку, если в данной задаче скорость важнее точности (например, ввести треть как 1./3.). Вот простой пример, где работа с числами с плавающей точкой проходит почти в 50,6 раза быстрее, чем при работе с точными числами, которые лишь затем будут переведены в числа с плавающей точкой. И в этом случае получается такой же результат.

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

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

Здравствуйте все!

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

Мы предположили, что и в сфере изучения алгоритмов для распределенных систем краткость — сестра таланта, поэтому проработка книги Уона Фоккинка «Распределенные алгоритмы. Понятный подход» является перспективным и благодарным делом, пусть даже объем книги — всего 248 страниц.



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

Всем привет!

В этой статье я расскажу про то, как мы делали автономную машинку на базе нашей ОС Embox, которая детектирует изменение типа поверхности, по которой едет.

Так случилось, что в Новый Год у меня в руках оказалась китайская машинка на радиоуправлении. К сожалению, она не ездила. Чека из магазина у меня не было (машинка была подарком), да и, честно говоря, хотелось её разобрать и посмотреть на элементы схемы. Обычным способом схему было не достать, нужно было выпаивать. Пожалуй, в тот самый момент, когда я взялся за паяльник, я и понял, что вернуть машинку в магазин уже точно не получится. Короче говоря, всю зиму на моём подоконнике так и пылились запчасти, пока однажды мне на глаза не попалась статья от NASA про обнаружение разладки в марсоходе.

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

Хочу в очередной раз затронуть метод реализации умножения Карацубы с использованием возможностей стандарта C++11. Данный алгоритм неоднократно рассматривался здесь («Умножение длинных чисел методом Карацубы», «Алгоритм Карацубы для умножения двух чисел»), но видимо из-за того, что я не умею их готовить, первый вариант не работал с числами разной длины, а второй делает не совсем то, что было нужно.

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

Лето — время вступительных экзаменов. Прямо сейчас завершается отбор в Школу анализа данных Яндекса — идут собеседования для тех, кто уже сдал экзамен. В ШАД преподают машинное обучение, компьютерное зрение, анализ текстов на естественном языке и другие направления современной Computer Science. Два года студенты изучают предметы, которые обычно не входят в университетские программы, хотя пользуются огромным спросом как в науке, так и в индустрии. Учиться можно не только в Москве — у Школы открыты филиалы в Екатеринбурге, Минске, Киеве, Новосибирске, Санкт-Петербурге. Есть и заочное отделение, на котором можно обучаться, смотря видеолекции и переписываясь с преподавателями московской Школы по почте.

Но для того, чтобы поступить в ШАД, нужно успешно пройти три этапа — заполнить анкету на сайте, сдать вступительный экзамен и прийти на собеседование. Ежегодно в ШАД поступают старшекурсники, выпускники и аспиранты МГУ, МФТИ, ВШЭ, ИТМО, СПбГУ, УрФУ, НГУ и не все они справляются с нашими испытаниями. В этом году мы получили анкеты от 3500 человек, 1000 из которых была допущена к экзамену, и только 350 сдали его успешно.

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

Задание	1	2	3	4	5	6	7	8
Решило	57%	68%	40%	35%	29%	12%	20%	6%

Но для начала хотелось бы объяснить, что мы проверяем экзаменом и как подходим к его составлению. В самые первые годы существования ШАД письменного экзамена не было, так как заявок было ещё немного, и со всеми, кто прошёл онлайн-тестирование, получалось поговорить лично. Но зато и собеседования были дольше; некоторые выпускники вспоминают, как с ними беседовали по шесть часов, предлагая много сложных задач. Потом поступающих стало больше – и в 2012 году появился письменный экзамен.

^{Капитан Немо у штурвала «Наутилуса»}

Индексы — один из самых мощных инструментов в реляционных базах данных. Мы используем их, когда нужно быстро найти какие-то значения, когда объединяем базы данных, когда нужно ускорить работу SQL-операторов и т.д. Но что представляют собой индексы? И как они помогают ускорять поиск по БД? Для ответа на эти вопросы я изучил исходный код PostgreSQL, отследив, как происходит поиск индекса для простого строкового значения. Я ожидал найти сложные алгоритмы и эффективные структуры данных. И нашёл.

Здесь я расскажу о том, как устроены индексы и как они работают. Однако я не ожидал, что в их основе лежит информатика. В понимании подноготной индексов также помогли комментарии в коде, объясняющие не только как работает Postgres, но и почему он так работает.

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



Лекцию в марте прошлого года прочитал на факультете компьютерных наук Ростислав Яворский, доцент департамента анализа данных и искусственного интеллекта. На факультете Ростислав Эдуардович ведет курсы «Введение в программирование», «Компьютерная алгебра», «Неклассические логики и представление знаний».

В этой статье речь пойдет о самом простом в реализации алгоритме генерации «идеального» лабиринта и его применении для поиска пути.

Мы рассмотрим алгоритм, основанный на бэктрекинге, позволяющий создавать лабиринты без циклов, имеющие единственный путь между двумя точками. Алгоритм не самый быстрый, довольно требователен к ресурсам, по сравнению с алгоритмом Эйлера или Крускала, но очень прост в реализации и позволяет создавать ветвистые лабиринты с очень длинными тупиковыми ответвлениями.

Заинтересовавшихся — прошу под кат.

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

Недавно Google на своем блоге опубликовали интересный способ использования нейронных сетей, распознающих картинки. Далее свободный перевод публикации.

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