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

Эта лекция посвящена удивительному повороту истории, когда конечные поля (поля Галуа), прежде незнакомые даже многим профессиональным математикам, стали вдруг востребованы инженерами, и тому, как это изменило наше знание теории конечных полей и родственных объектов.



Для начала подумаем, как рассадить на n–мерном кубе максимальное число Sp(n) пауков так, чтобы они не дрались. У паука n лап — по одной на каждое ребро, при этом длина лапы равна длине ребра куба. Драка начинается, если два паука дотянулись до одной и той же вершины. Можем ли мы добиться совершенного расположения: чтобы на каждой вершине было по пауку?

Это первая часть статьи, посвященной такому языковому механизму Java 5+ как аннотации. Она имеет вводный характер и рассчитана на Junior разработчиков или тех, кто только приступает к изучению языка.

Я занимаюсь онлайн обучением Java и опубликую часть учебных материалов в рамках переработки курса Java Core.

Также я веду курс «Scala for Java Developers» на платформе для онлайн-образования udemy.com (аналог Coursera/EdX).

Мой метод обучения состоит в том, что я

1. строю усложняющуюся последовательность примеров
2. объясняю возможные варианты применения
3. объясняю логику двигавшую авторами (по мере возможности)
4. даю большое количество тестов (50-100) всесторонне проверяющее понимание и демонстрирующих различные комбинации
5. даю лабораторные для самостоятельной работы

Данная статье следует пунктам #1 (последовательность примеров) и #2(варианты применения).

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

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

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

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

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

Java еще не умерла — и люди начинают это понимать.

Добро пожаловать в ведение по Java 8. Этот материал шаг за шагом познакомит вас со всеми новыми фичами языка. Вы научитесь использовать методы интерфейсов по умолчанию (default interface methods), лямбда-выражения (lambda expressions), ссылки на методы (method references) и повторяемые аннотации (repeatable annotations). Все это будет сопровождаться короткими и простыми примерами кода. В конце статьи вы познакомитесь с наиболее свежими изменениями в API, касающихся потоков, функциональных интерфейсов, расширений для ассоциативных массивов, а также с изменениями в API работы с датами.

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

В предыдущей части мы показали как может выглядеть распределенная память. Основная идея заключается в том, что общий волновой идентификатор может объединить нейроны, которые своей активностью формируют запоминаемую картину. Чтобы воспроизвести конкретное событие достаточно запустить по коре соответствующий идентификатор воспоминания. Его распространение восстановит ту же картину активности, что была на коре на момент фиксации этого воспоминания. Но главный вопрос — это как нам получить требуемый идентификатор? Ассоциативность памяти подразумевает, что по набору признаков мы можем отобрать события, в описании которых присутствовали эти признаки. То есть должен существовать нейронный механизм, который позволит по описанию в определенных признаках, получить идентификатор подходящего под эти признаки воспоминания.

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

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

Сообществу Angular требуются свежие туториалы и учебники с простыми примерами на последних версиях библиотек. Правила, которые работали в Angular v0.X, уже не все действуют, в чём легко убедиться, а хочется разобрать что-то более сложное, чем фильтр из учебника на сайте и TODO-лист из примеров реализации (как, например, найденный для v1.0.3: jsfiddle.net/dakra/U3pVM ). Когда такие примеры покажутся слишком простыми, хочется посмотреть на развитие постановки задачи и приближенное к реальности приложение с некоторым оформлением стилей.

Предлагается вниманию пример приложения — работы с телефонной книгой в 2 списках: основного и «spam». Каждый из списков подвержен фильтрации (ну это — самое простое и встроенное в фреймворк), редактированию элементов, добавлению новых и удалению имеющихся. Одним кликом переносятся элементы из одного списка в другой, а подсветки элементов сделаны в стиле Bootstrap v.3.

История

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

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

И наконец, в один прекрасный день вы решили: “Сделаем это!”. И вот вы уже пытаетесь разобраться как реализовать бизнес-логику своего приложения, ту киллер-фичу, которая будет двигать продукт вперед. У вас есть идея как это сделать, и вы знаете, что способны на это. И вот вы говорите: “Готово! Работает!” У вас есть успешный прототип! Осталось только упаковать его в веб приложение.

“Окей, сделаем сайт,” говорите вы.

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

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

“Я перегружен”, говорите вы и чувствуете себя перегруженным. Энергия уже не та, что была в начале. Вы пытаетесь собраться с мыслями, но работы слишком много. Прототип медленно блекнет и умирает.

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



Полный код редактора доступен на гитхабе. Готовый редактор можно установить из магазина приложений Chrome.

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

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

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

Для тех, кому интересно как у меня это получилось, добро пожаловать под кат.

Данная статья была написана 21 января 2014 участником проекта HTML5Rocks, Алексом Данило. Хочу отметить, что это мой первый перевод на Хабре, поэтому к минусам я готов, к критике еще больше. По всем проблемам и недочетам старайтесь писать мне лично, я буду оперативно исправлять. Оригинал на английском.

Высокая производительность веб-приложений является ключевым моментом для конечного пользователя. Так как веб-приложения становятся всё более и более сложными, понимание управления производительностью является убедительным навыком программиста. За последние пару лет появилось множество новых API в браузере, позволяющих следить за производительностью сети, временем загрузки и т.д. но ни одно из них не позволяет достаточно гибко и детально определить, что же именно “тормозит” ваше приложение. Для этого и есть User Timing API, которое предоставляет механизм для вашего приложения, позволяющий определить, на что и когда расходуется время.

В предыдущей части были освещены общедоступные вопросы, касающиеся SAT и P-NP: история проблемы, интуитивные определения классов и задач, указаны основные приложения SAT и основные последствия, в случаи решения P ?= NP (там же можно найти достаточное число ссылок на различный материал для самостоятельного изучения тематики).

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



картинка из статьи Boolean Satisfiability: From Theoretical Hardness to Practical Success (Communications of ACM)

В этой статье я продолжу знакомить хабрасообщество с техниками, обеспечивающими написание lock-free контейнеров, попутно рекламируя (надеюсь, не слишком навязчиво) свою библиотеку libcds.

Речь пойдет об ещё одной технике безопасного освобождения памяти для lock-free контейнеров — RCU. Эта техника существенно отличается от рассмотренных ранее алгоритмов a la Hazard Pointer.

Read – Copy Update (RCU) – техника синхронизации, предназначенная для «почти read-only», то есть редко изменяемых, структур данных. Типичными примерами такой структуры являются map и set – в них большинство операций является поиском, то есть чтением данных. Считается, что для типичного map'а более 90% вызываемых операций — это поиск по ключу, поэтому важно, чтобы операция поиска была наиболее быстрой; синхронизация поиска в принципе не нужна — читатели при отсутствии писателей могут работать параллельно. RCU обеспечивает наименьшие накладные расходы как раз для read-операций.

Откуда взялось название Read – Copy Update? Первоначально идея была очень проста: есть некоторая редко изменяемая структура данных. Если нам требуется изменить её, то мы делаем её копию и производим изменение — добавление или удаление данных — именно в копии. При этом параллельные читатели работают с первоначальной, не измененной структурой. В некоторый безопасный момент времени, когда нет читателей, мы можем подменить структуру данных на измененную копию. В результате все последующие читатели будут видеть изменения, произведенные писателем.

Вот надумал написать обзор библиотек с помощью которых легко и удобно писать приложения под Android.
Список вырисовывается такой:

• Android Annotations
• Groundy
• Retrofit
• AnnotatedSQL
• Android db-commons

Если заинтересованны прошу под кат.

Здравствуйте, уважаемые хабралюди!
Последние несколько месяцев, в свободное время, я занимался разработкой клона знаменитой игры Pacman для ОС Android. Как это было, и что из этого вышло я хочу рассказать.

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

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

Здравствуйте, коллеги.
Хочу рассказать о SFINAE, интересном и очень полезном (к сожалению*) механизме языка C++, который, однако, может представляться неподготовленному человеку весьма мозгоразрывающим. В действительности принцип его использования достаточно прост и ясен, будучи сформулирован в виде нескольких чётких положений. Эта заметка рассчитана на читателей, обладающих базовыми знаниями о шаблонах в C++ и знакомых, хотя бы шапочно, с C++11.
* Почему к сожалению? Хотя использование SFINAE — интересный и красивый приём, переросший в широко используемую идиому языка, гораздо лучше было бы иметь средства, явно описывающие работу с типами.

Для разработки приложений под ОС Android, Google предоставляет два пакета разработки: SDK и NDK. Про SDK существует много статей, книжек, а так же хорошие guidelines от Google. Но про NDK даже сам Google мало что пишет. А из стоящих книг я бы выделил только одну, Cinar O. — Pro Android C++ with the NDK – 2012.

Эта статья ориентирована на тех, кто ещё не знаком (или мало знаком) с Android NDK и хотел бы укрепить свои знания. Внимание я уделю JNI, так как мне кажется начинать нужно именно с этого интерфейса. Так же, в конце рассмотрим небольшой пример с двумя функциями записи и чтения файла. Кто не любит много текста, тот может посмотреть видео версию.

В данной статье мы попытаемся разобраться с Dependency Injection в Android (и не только) на примере набирающей популярность open source библиотеки Dagger
И так, что же такое Dependency Injection? Согласно википедии, это design pattern, позволяющий динамически описывать зависимости в коде, разделяя бизнес-логику на более мелкие блоки. Это удобно в первую очередь тем, что впоследствии можно эти самые блоки подменять тестовыми, тем самым ограничивая зону тестирования.

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

Рассмотрим упрощенную (до псевдокода) версию Twitter клиента.

Как и договаривались в первой части статьи, в этой мы будем рассматривать инструменты для изменения стандартного поведения Activity Stack.

Вся теория по сегодняшей теме присутствует на developer.android.com/guide/topics/manifest/activity-element.html, я буду кое-где на неё ссылаться, а мы постараемся разобраться как оно работает на деле и выяснить, в каких ситуациях это можно использовать в реальной жизни.