Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!

Generative art (генеративное или процедуральное искусство) может отпугнуть, если вы никогда с ним раньше не сталкивались. Если коротко, то это концепция искусства, которое буквально создает само себя и не требует хардкорных знаний программирования для первого раза. Поэтому я решил немного разбавить нашу ленту, погнали.

Я всегда хотел написать подробное руководство для начинающих о том, как создать roguelike, содержащее как общие, так и более специфические советы. Проведённый в этом году очередной праздник Roguelike Celebration показался мне отличной возможностью наконец-то заставить себя это сделать, поэтому я подготовил получасовой доклад по этой теме.

У меня есть довольно большой опыт — в течение последних семи лет я работал только в этом жанре (Cogmind, Cogmind 7DRL, POLYBOT-7, REXPaint, X@COM), и в течение последних пяти эта работа была моей основной. К тому же, все эти годы я помогал превращению r/RoguelikeDev в крупнейшее сетевое сообщество разработчиков roguelike.

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

Ошибка в коммите… Как её исправить? Беспорядок в истории коммитов… Как привести всё в пристойный вид? Автор статьи, перевод которой мы публикуем сегодня, говорит, что она написана специально для тех, кто задавался такими вопросами. По его словам, изучив методики работы с Git, представленные здесь, можно значительно продвинуться по пути освоения Git.

Предполагается, что читатель этой статьи уже знаком с основами Git. Если это не так — сначала рекомендуется освоить базу, например, воспользовавшись этим материалом.

Мы собрали дайджест из материалов, посвященных принципам работы блокчейн-технологии и разработке децентрализованных приложений. В него вошли наши собственные статьи и ресурсы по теме, на которые рекомендовали обратить внимание резиденты Hacker News, Quora и Reddit.

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

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

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

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

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

Данная статья в большей мере рассчитана на новичков в системном программировании и тех, кто просто хочет узнать немного больше о том, как работают процессы в Linux.

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

В этой статье мы напишем с нуля калькулятор обратной польской записи (RPN) на чистом ассемблере x86. Когда закончим, то сможем использовать его так:

$ ./calc "32+6*" # "(3+2)*6" в инфиксной нотации
30

Весь код для статьи здесь. Он обильно закомментирован и может служить учебным материалом для тех, кто уже знает ассемблер.

Начнём с написания базовой программы Hello world! для проверки настроек среды. Затем перейдём к системным вызовам, стеку вызовов, стековым кадрам и соглашению о вызовах x86. Потом для практики напишем некоторые базовые функции на ассемблере x86 — и начнём писать калькулятор RPN.

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

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

Введение

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

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

Что же такое «игровой ИИ»?

Игровой ИИ в основном занимается выбором действий сущности в зависимости от текущих условий. В традиционной литературе по ИИ называет это управлением "интеллектуальными агентами". Агентом обычно является персонаж игры, но это может быть и машина, робот или даже нечто более абстрактное — целая группа сущностей, страна или цивилизация. В любом случае это объект, следящий за своим окружением, принимающий на основании него решения и действующий в соответствии с этими решениями. Иногда это называют циклом «восприятие-мышление-действие» (Sense/Think/Act):

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

Никлаус Вирт, швейцарский ученый-информатик, в 1976 году написал книгу под названием «Алгоритмы + Структуры данных = Программы».

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

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

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

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

Переведено в Alconost

Привет, Хабр! Это начало небольшого цикла из двух статей с пошаговым проектированием цифрового устройства с уклоном на практику. Минимум «воды» и максимум практики!

Всем привет. В статье хочу описать свой эксперимент по созданию «искусственной жизни» на компьютере.

Как это выглядит?

картинка кликабельна

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

Ну а дальше за работу принимается эволюция и естественный отбор.

А мне остаётся только наблюдать за развитием мира.

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

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

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

Внутреннее устройство кода — это самое интересное в проекте.

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

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

Продолжаю знакомить читателей Хабра с главами из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.



Это, одна из первых глав, в которой на примере велосипедиста рассматриваются нужные нам инструменты для измерения несправедливости: кривая Лоренца и индекс Джини, а также упоминаются пресловутый Парето и грозный инспектор.

Предисловие от переводчика

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

И вот в один прекрасный момент я увидел данную статью, до перевода которой у меня наконец дошли руки. Всего 7 простых и коротких правил, и — о чудо — смотреть на историю коммитов стало не только полезно, но и приятно. Ничего революционного, все довольно очевидно, но сформулировано и резюмировано просто отлично.

Всем привет, меня зовут Оля. Две недели назад на CodinGame завершился очередной контест — соревнование по программированию ботов для игры. Я попала в топ-300 мирового лидерборда, поэтому хочу рассказать, почему контесты это круто, и поделиться своими секретами. А ещё секретами поделится Иван spaceorc, который попал в топ-100 того же соревнования.

Вы узнаете, как успешно выступать на соревнованиях по программированию игрового искусственного интеллекта.

Что такое CodinGame

codingame.com — обучающая платформа для разработчиков всех возрастов и уровней подготовки. Можно писать на 26 языках: от C# и Python до Bash и Haskell. Самое крутое, что задачки там не скучные и непонятные, а настоящие игры с неплохим GUI:

Привет всем читателям Habrahabr, в этой статье я хочу поделиться с Вами моим опытом в изучении нейронных сетей и, как следствие, их реализации, с помощью языка программирования Java, на платформе Android. Мое знакомство с нейронными сетями произошло, когда вышло приложение Prisma. Оно обрабатывает любую фотографию, с помощью нейронных сетей, и воспроизводит ее с нуля, используя выбранный стиль. Заинтересовавшись этим, я бросился искать статьи и «туториалы», в первую очередь, на Хабре. И к моему великому удивлению, я не нашел ни одну статью, которая четко и поэтапно расписывала алгоритм работы нейронных сетей. Информация была разрознена и в ней отсутствовали ключевые моменты. Также, большинство авторов бросается показывать код на том или ином языке программирования, не прибегая к детальным объяснениям.

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

Давайте я за 5-10 минут чтения и понимания коротенькой статьи добавлю вам в резюме строчки «машинное обучение» и «нейронные сети»? Тем, кто далек от программирования, я развею все мифы о сложности ИИ и покажу, что большая часть всех проектов на машинном обучении строится на предельно простых принципах. Поехали — у нас всего пять минут.

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