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

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

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

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

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

Доброго времени суток.

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

На дворе 2014 год, доля Android JellyBean перевалила за 60%, появились новые тренды в дизайне. В общем, случилось много всего интересного. Но синхронизация данных с сервером осталось неотъемлемой частью большинства приложений. Существует много способов реализации ее в приложении. Android предоставляет нам SyncAdapter Framework, который позволяет автоматизировать и координировать этот процесс и предоставляет множество плюшек в довесок.

Account

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

Краткое резюме преимуществ:

• Поддержка фоновых механизмов вроде SyncAdapter
• Стандартизация способа авторизации
• Поддержка различных токенов (прав доступа)
• Шаринг аккаунта с разграничением привилегий (возможность использовать один аккаунт для различных приложений, как это делает Google)

Шаги для получения плюшек:
1) Создание Authenticator'а
2) Создание Activity для логина
3) Создание сервиса для общения с нашим аккаунтом

Всем привет, хочу поведать хабру об одном необычном сетевом сервисе и процессе его разработки. Но сперва пару слов непосредственно обо мне — я прикладной программист MAXScript (это встроенный в 3ds max скриптовый язык), а 3ds max это один из популярнейших пакетов для создания разнообразной 3d-графики и в нем, естественно, есть такая штука как рендеринг, из-за которой собственно все ниженаписанное и делалось.

Идея

Начался процесс с одной идеи, которая пришла мне в голову совершенно внезапно поздней ночью 30 ноября 2010 года и вылилась на следующий день вот в такой пост на форуме 3dcenter.ru:

01/12/2010, 12:49
Пришла эта мысль в голову и не вылазит. Хочу обсудить с сообществом полезность и целесообразность. Основную часть технических подробностей пока опускаю, но сделать сие вполне реально либо в качестве плагина (SDK), либо даже скрипта (MAXScript).
Итак, смысл в том, чтобы бесплатно (или не очень) использовать чужие компы для рендера своих сцен. Есть система рейтинга, т.е. нельзя долго рендерить свое («качать»), но не рендерить чужое («раздавать»). Для тех, кто боится, что его сцены или текстуры будут использовать чужие нехорошие люди, предусмотрена защита — координаты всех объектов сцены изначально обнуляются, правильные координаты шифруются и передаются на рендер отдельным файлом, текстуры бьются на маленькие квадратики и собираются в одну тоже только перед рендером. Показ самой визуализации (VFB) можно отключить, т.е. человек даже не видит, что он рендерит. Аналогичные действия происходят и после рендера — изображение автоматически разбивается на кусочки (либо просто перемешиваются пиксели по какому-то закону) и собрать его правильно можно только на стороне автора сцены. Для альтруистов есть возможность отключения защиты, т.е. сцена с барахлом передается в свободном доступе. Защита может быть и другая, и вообще все что я пишу еще до конца не обдумано — только варианты.
…
Ну вот в общем как-то так, прошу не кидаться помидорами, и, если велосипед я не изобрел, то обсудим, насколько вообще жизнеспособна эта идея.

Play! и Lift, — эти два фреймворка являются олицетворением того, куда движется основной поток Scala веб-разработчиков. Воистину, попробуйте поискать на Stack Overflow фреймворки для Scala и вы поймете что я прав. Я верю, что процент здравомыслящих людей, которым надоели сложные комбайны, велик, поэтому расскажу про «другой» фреймворк Xitrum.

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

Впервые она появилась, когда еще никаких практических надобностей для больших сетей не было: в тридцатые годы XX века. На самом деле Штейнер начал ее изучать еще раньше, в XIX веке. Это была чисто геометрическая задача, практические приложения которой стали известны только несколько десятилетий спустя.

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



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

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

В предыдущих своих заметках я описал основу, на которой строятся lock-free структуры данных, и базовые алгоритмы управления временем жизни элементов lock-free структур данных. Это была прелюдия к описанию собственно lock-free контейнеров. Но далее я столкнулся с проблемой: как построить дальнейший рассказ? Просто описывать известные мне алгоритмы? Это довольно скучно: много [псевдо-]кода, обилие деталей, важных, конечно, но весьма специфических. В конце концов, это есть в опубликованных работах, на которые я даю ссылки, и в гораздо более подробном и строгом изложении. Мне же хотелось рассказать интересно об интересных вещах, показать пути развития подходов к конструированию конкурентных контейнеров.
Хорошо, — подумал я, — тогда метод изложения должен быть такой: берем какой-то тип контейнера — очередь, map, hash map, — и делаем обзор известных на сегодняшний день оригинальных алгоритмов для этого типа контейнера. С чего начать? И тут я вспомнил о самой простой структуре данных — о стеке.

Компания Freescale Semiconductor, известный производитель полупроводниковых чипов и микропроцессоров, представила преемника микросхемы Kinetis KL02, которой в прошлом году достался титул самого маленького микроконтроллера на архитектуре ARM. В ассортименте производителя новинка получила обозначение Kinetis KL03. Она на 15% меньше по сравнению с Kinetis KL02.

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

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

Сегодня, 21 февраля, в журнале «Science» была опубликована статья о принципиально новом способе создания искусственных мышц, на основе обычной рыболовной лески и других подобных полимерных нитей, вообще без использования дорогих или экзотических материалов наподобие углеродных нанотрубок, диоксида ванадия или металлических сплавов с памятью. Причём способ их изготовления совершенно тривиален и доступен в домашних условиях — леска скручивается под нагрузкой, пока не свернётся в спираль, а затем нагревается. При нагревании спираль сокращается, развивая достаточно большое усилие, при остывании удлиняется до исходных размеров.



Искусственное мышечное волокно из нейлона может сокращаться на 49% относительно начальной длины и поднимать вес, в сто раз больший, чем человеческие мышечные волокна такой же толщины и длины. Его удельная механическая мощность достигает 5,3 киловатт на килограмм — это сравнимо с реактивными двигателями самолётов и самыми совершенными современными электродвигателями.

Рады сообщить, что в издательстве «Питер» вышел перевод новой книги Леонарда Сасскинда и Джорджа Грабовски — «Теоретический минимум» (ориг: The Theoretical Minimum: What You Need to Know to Start Doing Physics).

В Америке эта книга, несмотря на свой формат лекций по физике и классической механике, неожиданно стала настоящим бестселлером, а The Wall Street Journal вообще признал ее «Книгой 2013 года». В России книга вышла в издательстве «Питер» при поддержке гуманитарного фонда «Династия», цель которого — содействовать изданию лучших современных научно-популярных книг в области естественных и гуманитарных наук.



Мы уже издавали одну книгу Сасскинда на русском — «Битву при черной дыре» (пост о ней был на Хабре) — но «Теоретический минимум» по формату и содержанию кардинально от нее отличается.

В данной статье мы рассмотрим 10 анти-паттернов навигации в Android, которые допускают многие новички (и не только) в создании интерфейсов Android-приложений.

Целью статьи является ознакомление с наиболее распространенными подводными камнями в работе с сервисом нотификаций от Google.
Источником послужила очень полезная, на мой взгляд, статья Keeping Google Cloud Messaging For Android Working Reliably от разработчиков Pushbullet — удобного приложения для синхронизации нотификаций между Android устройствами и браузером Chrome.

Здравствуй, Хабр!

Компания «Октодон», в лице её основателя, Алексея Лысенко (то есть меня), приветствует тебя.
Наша команда с 2010 года занимается разработкой дикой, но симпатичной физической клавиатуры, которая призвана сделать работу с текстом на карманных устройствах (читай, смартфонах), такой же приятной, как на ноутбуке. За три года мы прошли путь длиной в пять итераций протипа, обросли полезным программным обеспечением, и в этом году собираемся, наконец, вывести наш проект на Kickstarter.

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





А теперь всё по порядку.
История переносит нас назад, в 2005 год, когда мир ещё не знал iPhone…

Эта статья – продолжение истории о возникновении мобильной клавиатуры Октодон.
Начало истории: Октодон: Какой должна быть удобная клавиатура для смартфонов.

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

Совсем недавно стала доступна публичная версия мессенджер Tox.
(Теперь кнопка загрузить на сайте наконец-то активная)

Напомню, что Tox — децентрализованный мессенджер который создается для будущей замены Skype, основные цели проекта:
— Полностью открытый исходный код
— Децентрализованная работа
— Отсутствия закладок и прослушек
— Отсутствие рекламы

Coursera объявила о запуске десяти специализаций. Теперь можно не просто получить verified certificate за предмет, а взяв определенный набор курсов и получив сертификат за каждый из них, в результате стать обладателем сертификата об окончании специализации. В нее входят от 3 до 9 курсов плюс итоговый проект. За проект предполагается такая же оплата как и за verified certificate — $49.

В данный момент в списке специализаций:

Data Science?
Mobile Cloud Computing with Android

Эта статья навеяна топиком «Как и насколько быстро вы считаете в уме на элементарном уровне?» и призвана распространить приёмы С.А. Рачинского для устного счёта.
Рачинский был замечательным педагогом, преподававшим в сельских школах в XIX веке и показавшим на собственном опыте, что развить навык быстрого устного счёта можно. Для его учеников не было особой проблемой посчитать подобный пример в уме:

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

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

Интересный факт: Оказывается существует целое движение — OpenCourseWare, которое началось в 1999 году в Германии, когда один из университетов разместил видео своих лекций онлайн. Вскоре и други университеты подхватили инциативу и сейчас OpenCourseWare — это достаточно популярная штука, которая представляет из себя курсы и бесплатные учебные материалы, созданные в университетах и распространяющиеся через интернет.
Как правило ресурсы OCW не требуют регистрации и не предлагают никаких сертификатов о прохождении. Все обучение — в качестве self-improvement.

Под катом список бесплатных онлайн-курсов и уроков от лучших учебных заведений

В моём детстве был такой замечательный фильм, как «Газонокосильщик». Тогда мне было всё равно на сюжет, на какой-то смысл, заложенный автором. Но фильм мне очень нравился и манил одной вещью — виртуальной реальностью. Те несколько сцен, в которых герои погружались внутрь виртуального мира, — это то, ради чего стоило его смотреть. Мне хотелось испытать всё то, что испытывали они. Полёт внутри виртуальной реальности — то, что запомнилось навсегда.

Шло время и вот я уже вырос. Фильм забылся, но потаённое желание окунуться в виртуальную реальность осталось. И однажды я увидел проект Oculus Rift. Он приковал моё внимание на некоторое время, но ненадолго. Ведь очки Oculus ещё в разработке и получить их не так просто. Но это дало толчок. Голова начала копаться в прошлом, доставая то самое потаённое желание наружу, и искать пути решения.