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

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

Введение

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

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

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

Привет, Хабр!

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

C годами у нас появилось много образовательных программ, которые мы поддерживаем (Computer Science Center, программа магистров при АУ РАН, Лаборатория JetBrains при Математико-механическом факультете СПбГУ и пр.) и много студентов, которые хотят пройти стажировку у нас. В результате этим летом мы провели масштабный проект летних практик.

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

Опубликовано ранее:
Часть 1
Часть 2

Логарифмы

Если вы знаете, что такое логарифмы, то можете спокойно пропустить этот раздел. Глава предназначается тем, кто незнаком с данным понятием или пользуется им настолько редко, что уже забыл что там к чему. Логарифмы важны, поскольку они очень часто встречаются при анализе сложности. Логарифм — это операция, которая при применении её к числу делает его гораздо меньше (подобно взятию квадратного корня). Итак, первая вещь, которую вы должны запомнить: логарифм возвращает число, меньшее, чем оригинал. На рисунке справа зелёный график — линейная функция f(n) = n, красный — f(n) = sqrt(n), а наименее быстро возрастающий — f(n) = log(n). Далее: подобно тому, как взятие квадратного корня является операцией, обратной возведению в квадрат, логарифм — обратная операция возведению чего-либо в степень.

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

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

Не так давно мой коллега опубликовал (читать тут) тест экстрим-камер iON Air Pro Wi-Fi и GoPro Hero3 White Edition. Сразу же замечу, что с его выводами я полностью согласен: право на жизнь имеют оба решения, но переплачивать за последнее при сопоставимом качестве съемки, когда на рынке есть куда лучше укомплектованное первое, особого смысла и нет. Камера от новичка нашего рынка – американской iON – меня заинтересовала, но тщательно тестировать то, что уже хорошенько погоняли до меня, было бы глупо.

Что же, прогулялся по официальному сайту iON и изучил ассортимент предлагаемых камер. Глаз сразу же зацепился за iON Air Pro 2 Wi-Fi: выглядит она практически так же, как iON Air Pro Wi-Fi, но вот по характеристикам немного обгоняет «младшую сестру». Тем интереснее будет ознакомиться с «двойкой».


iON Air Pro 2 Wi-Fi

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

До 28 октября я должен был принять решение, буду ли я работать в Amazon по окончанию стажировки. Оставалось совсем немного времени, но мой друг Дэниел убедил меня, что если я попробую попасть в Twitter, то как раз успею пройти все интервью. Я не смог устоять.

Сначала меня попросили решить пару вопросов с Codility, дав на все про все час времени. Вопросы попались средней интересности («является ли слово анаграммой палиндрома» и «посчитать количество седловых точек в двумерном массиве»). Я был не слишком уверен в получившихся решениях, но вскоре Джуди прислала мне письмо с приглашением на телефонное интервью в среду в 17:30.

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

В данном посте я расскажу о наиболее интересных командах, которые могут быть очень полезны при работе в консоли. Однозначных критериев определения какая команда лучше другой — нет, каждый сам для своих условий выбирает лучшее. Я решил построить список команд на основе наиболее рейтинговых приемов работы с консолью от commandlinefu.com, кладовой консольных команд. Результат выполнения одной из таких команд под Linux приведен на картинке. Если заинтересовало, прошу под кат.

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

Конечно, тема поднималась на хабре не раз и авторы статей действительно давали дельные советы, которые могли бы помочь защитить зрение пользователям ПК. Однако, в большинстве случаев, все они сводились к тому, что основное средство спасения — тот остров посреди океана — это упражнения для глаз в разных количествах и разных видов. Но давайте подойдем сейчас к другу/коллеге/соседу и спросим, стал ли он пользоваться этими упражнениями и насколько регулярно их выполняет? Лично я не уверен ни в положительном ответе, ни в систематическом выполнении этих упражнений.

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

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

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

Для начала терминология. Пентаграммой называют совокупность всех диагоналей пятиугольника, в случае гексаграммы — это уже не все диагонали, а только те, которые соединяют непротивоположные вершины шестиугольника. Во обоих случаях эти вершины идут через одну друг от друга. Например, если вершины пятиугольника перенумеровать (0, 1, 2, 3, 4), то пентаграмма — совокупность линий (0, 2), (1, 3), (2, 4), (3, 0), (4, 1). Гексаграмма (0, 1, 2, 3, 4, 5), соответственно, является совокупностью линий (0, 2), (1, 3), (2, 4), (3, 5), (4, 0), (5, 1). Нули в качестве начальной точки взяты не случайно и не как дань програмистскому мышлению, удобство этого обозначения я опишу ниже. Линии, образующие полиграмму, я буду называть ребрами. Вершинами полиграммы я буду называть вершины исходного полигона, а не все точки пересечения ребер.

Здесь нету примеров идеального кода, пяти шагов «как получить сертификат с вероятностью 100%, гарантия». Нету даже фотографий котиков :/

Не стоит преследовать цели, которые легко достичь. Стоит нацеливаться на то, что удается сделать с трудом, приложив немалые усилия — Альберт Эйнштейн

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

Краткий синопсис

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

P.S. Весьма «сухой язык», но вполне читабельно после университетской программы. По большей части определения парадоксов брались из Википедии (упрощённая формулировка и готовая TeX-разметка).

Введение

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

Следует начать с определения.

Что есть множество? Вопрос достаточно простой, ответ на него вполне интуитивен. Множество это некий набор элементов, представляемый единым объектом. Кантор в своей работе Beiträge zur Begründung der transfiniten Mengenlehre даёт определение: под «множеством» мы понимаем соединение в некое целое M определённых хорошо различимых предметов m нашего созерцания или нашего мышления (которые будут называться «элементами» множества M)[1]. Как видим, суть не изменилась, разница лишь в той части, которая зависит от мировоззрения определяющего. История же теории множеств как в логике так и в математике весьма противоречива. Фактически начало ей положил Кантор в XIX веке, далее Рассел и остальные продолжили работу.

Парадоксы (логики и теории множеств) — (греч. — неожиданный) — формально-логические противоречия, которые возникают в содержательной множеств теории и формальной логике при сохранении логической правильности рассуждения. Парадоксы возникают тогда, когда два взаимоисключающих (противоречащих) суждения оказываются в равной мере доказуемыми. Парадоксы могут появиться как в пределах научной теории, так и в обычных рассуждениях (например, приводимая Расселом перифраза его парадокса о множестве всех нормальных множеств: «Деревенский парикмахер бреет всех тех и только тех жителей своей деревни, которые не бреются сами. Должен ли он брить самого себя?»). Поскольку формально-логическое противоречие разрушает рассуждение как средство обнаружения и доказательства истины (в теории, в которой появляется парадокс, доказуемо любое, как истинное, так и ложное, предложение), возникает задача выявления источников подобных противоречий и нахождения способов их устранения. Проблема философского осмысления конкретных решений парадоксов — одна из важных методологических проблем формальной логики и логических оснований математики.

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

Тестирование – очень важный этап разработки мобильных приложений.

Стоимость ошибки в релизе мобильного приложения высока. Приложения попадают в Google Play в течении нескольких часов, в Appstore несколько недель. Неизвестно сколько времени будут обновляться пользователи. Ошибки вызывают бурную негативную реакцию, пользователи оставляют низкие оценки и истерические отзывы. Новые пользователи, видя это, не устанавливают приложение.

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

Поэтому в отделе тестирования у нас работает 8 человек (0,5 тестировщика на программиста), за его развитием и процессами следит выделенный тест-лид.

Под катом я расскажу как мы тестируем мобильные приложения.

Собственно речь пойдет о двоичной куче и ее построении с помощью Sift-Down(или Heapify). Многим наверное известно, что построение кучи таким образом осуществляется за . Здесь я приведу доказательство этого факта.

В этом году волей случая мне удалось побывать на выставке IFA 2013 — второй крупнейшей тематической IT-выставке Германии и одной из четырех крупнейших (CES, CeBIT, Computex, IFA) в мире. Впечатлений очень много, еще больше фотографий и мыслей. А начать обзор новинок IFA 2013 я решил с action-камер, которым мои коллеги уделяют немало внимания в своих постах.