Вы вероятно слышали о Дэвиде Хаффмане и его популярном алгоритме сжатия. Если нет, то поищите информацию в интернете — в этой статье я не буду вас грузить историей или математикой. Сегодня я хочу просто попытаться показать вам практический пример применения алгоритма к символьной строке.
Афанасьев Вениамин @ULTRAWEN
Пользователь
Максимально просто про перебор комбинаций в реальных бизнес-задачах
4 min
Если начать искать материал про перебор комбинаций, возникает масса примеров как перебрать все сочетания всех букв или всех цифр. Но как создать все сочетания элементов матрицы, в которой заранее неизвестна размерность, не углубляясь в Иосифа Романовского и его «Дискретный Анализ», такого материала я не нашел, поэтому и решил написать его здесь. Вдруг кому-то понадобится.
Патентование алгоритмов компьютерных программ
10 min
Продукты в сфере информационных технологий (далее – ИТ) в общем случае содержат несколько компонентов, правовая охрана которых реализуется разными способами.
Архитектура, алгоритмическое решение, аппаратная часть ИТ-продукта и графическая часть интерфейса пользователя охраняются как объекты патентного права.
Особенности патентования архитектурных и аппаратных решений достойны отдельного обсуждения и поэтому здесь не рассматриваются.
Код компьютерных программ, реализующих алгоритм и интерфейс пользователя, регистрируется как объект авторского права (т.е. как литературное произведение), соответственно, в его отношении охраняется только текстовая форма, а не алгоритм. Графическая часть интерфейса пользователя может патентоваться в качестве промышленного образца. При этом регистрация кода компьютерных программ и патентование графической части интерфейса пользователя может рассматриваться, скорее, как вспомогательный инструмент обеспечения правовой охраны в ИТ-индустрии.
Наиболее надежным и поэтому основным механизмом защиты интересов разработчика программного обеспечения является патентование алгоритмов компьютерных программ в качестве изобретений.
Архитектура, алгоритмическое решение, аппаратная часть ИТ-продукта и графическая часть интерфейса пользователя охраняются как объекты патентного права.
Особенности патентования архитектурных и аппаратных решений достойны отдельного обсуждения и поэтому здесь не рассматриваются.
Код компьютерных программ, реализующих алгоритм и интерфейс пользователя, регистрируется как объект авторского права (т.е. как литературное произведение), соответственно, в его отношении охраняется только текстовая форма, а не алгоритм. Графическая часть интерфейса пользователя может патентоваться в качестве промышленного образца. При этом регистрация кода компьютерных программ и патентование графической части интерфейса пользователя может рассматриваться, скорее, как вспомогательный инструмент обеспечения правовой охраны в ИТ-индустрии.
Наиболее надежным и поэтому основным механизмом защиты интересов разработчика программного обеспечения является патентование алгоритмов компьютерных программ в качестве изобретений.
О талантах, деньгах и алгоритмах сжатия данных
16 min
Алгоритмы сжатия — это очень коварная тема, привлекающая многих новичков. Это правда! Часто человеку кажется, что его осенила божественная идея, как сильно сжать данные. Любые, кстати! Без потерь! Рекурсивно! А поскольку данные — это хранение информации и передача, то если хотя бы на единицы процентов результат улучшить — это миллиарды долларов (смотрим экономию всех провайдеров на передаче и хранении, всех дата-центров компаний, всех домашних пользователей, перемножаем… аж дух захватывает)! И люди пишут письма:
«Обращаюсь к вам, как «создателю и демиургу проекта ;) compression». Мной придуман алгоритм, основанный на простом рассуждении – если файл условно несжимаемый, есть вероятность что, часть файла имеет избыточность и файл можно сжать частично. …»
«Обращаюсь к Вам, как к одному из главных специалистов в области сжатия информации. Предлагаю Вам ознакомиться с изобретением в области сжатия информации. [...] По мнению автора, основным достоинством данного «Способа кодирования информации» является способность одинаково хорошо сжимать без потери качества информацию любого типа (видео, аудио, текст, архив и т.д.). Помимо этого «Способ» позволяет проводить процесс кодирования (сжатия) повторно....»
Бывает даже так:
«Мне, для начала, нужно 30–60 минут общения с Вами по Скайпу.
Вопрос: каково Ваше вознаграждение и куда его отправить?»
И если вы думаете, что обращения типа последнего — мои любимые, то реакция ровно обратная («Боже, дай мне терпения!»). Ибо по опыту в последнем случае люди наиболее настойчивые… Кстати, это могут быть не только авторы, но и инвесторы, о которых ниже тоже будет.
Кому интересно, в чем же таки коварство алгоритмов, есть ли у нас таланты, и где же, наконец, деньги — добро пожаловать под кат! (Талантливые авторы алгоритмов могут сразу переходить в раздел «Про деньги»).
Как мы воспринимаем цвет. Занимательные факты. Просто об очень сложном
11 min
Фото сетчатки в разрезе с электронного микроскопа.
Дорогие читатели, в этой статье о цвете я не буду приводить аналогии с цифровым фотоаппаратом и фотошопом для «лучшего» понимания физиологии зрения, как не делал этого и в прошлой статье «О разрешении нашего зрения». Такой приём, при кажущемся удобстве, только усложнит картину мира и запутает вас. Буду вести рассказ последовательно и в меру сложно.
Каково разрешение человеческого глаза (или сколько мегапикселей мы видим в каждый отдельный момент времени)
5 min
Очень часто фотографы, а иногда и люди из других специальностей, проявляют интерес к собственному зрению.
Вопрос, казалось бы, простой на первый взгляд… можно погуглить, и всё станет ясно. Но практически все статейки в сети дают либо «космические» числа — вроде 400-600 мегапикселей (Мп), либо это и вовсе какие-то убогие рассуждения.
Поэтому постараюсь кратко, но последовательно, чтобы никто ничего не упустил, раскрыть эту тему.
Сетчатка состоит из трёх типов рецепторов: палочки, колбочки, фоторецепторы(ipRGC).
Вопрос, казалось бы, простой на первый взгляд… можно погуглить, и всё станет ясно. Но практически все статейки в сети дают либо «космические» числа — вроде 400-600 мегапикселей (Мп), либо это и вовсе какие-то убогие рассуждения.
Поэтому постараюсь кратко, но последовательно, чтобы никто ничего не упустил, раскрыть эту тему.
Начнём с общей структуры зрительной системы
- Сетчатка
- Зрительный нерв.
- Таламус(ЛКТ).
- Зрительная кора.
Сетчатка состоит из трёх типов рецепторов: палочки, колбочки, фоторецепторы(ipRGC).
Полностью электрический ускоритель космических кораблей
14 min
Дамы и Господа, в этой статье я представлю вашему вниманию революционный безтопливный ускоритель, не имеющий аналогов в мире, который ничего не выбрасывает (требуется только электричество). Мой ускоритель в тысячи раз эффективней обычных ракетных двигателей, он просто перевернёт всю мировую космонавтику и позволит колонизировать всю Солнечную систему за 50-100 Лет. 3 недели до Марса, 7 месяцев до Юпитера и 11 месяцев до Сатурна — такого даже в научной фантастике нет — но сегодня это станет реальностью.
Как и все безтопливные ускорители — мой ускоритель может работать только в вакууме, но главное преимущество моего ускорителя перед другими безтопливными двигателями заключается в том — что другие ускорители не работают, а мой работает!!! — мой ускоритель никаким законам физики не противоречит. Мой ускоритель противоречит лишь животным инстинктам — человек так устроен, что в процессе жизнедеятельности, человеку постоянно необходимо гадить — и поэтому Людям кажется, что если не нагадить в космосе — то ракета не полетит — но это в корне не верно! Хватит обезьяних технологий!!! Реактивный … струя, импульс, формула Циолковского — сегодня вы забудете про эту гадость как про плохой сон.
Для начала давайте отправимся на Луну со второй космической скоростью.
Итак, чтобы отправиться с орбиты Земли на Луну, нам понадобится:
Когда и как Вселенная стала проницаемой для света?
11 min
Translation
Физика и большие данные идут рука об руку. Благодаря свету, который простирается во Вселенной на миллионы километров и гораздо дальше, мы ищем и находим экзопланеты, узнаём о Вселенной всё новые факты, движемся к пониманию происходящего. Но когда и как Вселенная вообще начала пропускать свет настолько далеко? Давайте разбираться под катом, в статье Итана Сигеля, которую мы перевели к старту флагманского курса по Data Science.
Демосцена
26 min
"… особую пикантность придаёт тот факт, что всё это по сути бессмысленно..."
/ sq/skrju /
Чаще всего, попытки объяснить людям, что такое «демосцена», начинаются со слов «компьютерное искусство...». Однако, даже по вопросу о том, что такое искусство, во все времена не было единого мнения. Явление, о котором пойдёт речь, называют искусством скорее в том смысле, в каком говорят об искусстве токаря или плотника, а не скульптора или художника. Что, конечно, не означает, что одно хуже другого.
Слово «демосцена» («demoscene») мало того, что не переводится на русский язык, но даже и на английском имеет не вполне очевидный смысл. Если со словом «demo» всё интуитивно понятно — оно происходит от слова «demonstration» («демонстрация»), то со словом «scene» всё куда сложнее. Своим появлением оно обязано вовсе не театру, как могло бы показаться, а возникшей в конце 1970-х практике нелегального распространения и взлома программного обеспечения, главным образом — компьютерных игр.
Триумвират угля, железа и пара
15 min
Translation
<< До этого: Паровой насос
Паровой двигатель вряд ли бы развился во что-то стоящее, если бы не два его помощника – уголь и железо. Все вместе они сформировали триумвират, взошедший на трон промышленной империи. Возможно, тут больше подойдёт экологическая метафора – возник симбиоз трёх видов, каждый из которых взращивал другого, формируя ядро новой механической экосистемы, жизнь в которой активно тряслась и клацала. Или, возможно, это были три вида тканей единого организма – кости и сухожилия из железа; лёгкие и сердце из угля; а духом, или жизненной силой, был пар. Но что-то я отдаляюсь от темы.
И всё равно невозможно отрицать тесные узы, связывающие три этих материала. Паровые двигатели впервые набрали популярность как средство откачки воды из угольных шахт, и использовали при этом тот же самый продукт, что добывали в шахтах. Позднее двигатели задували свежий воздух в шахты и поднимали на поверхность руду – во всех шахтах, включая и железные. Затем уголь, добытый из шахт, начали использовать в качестве топлива для плавления железа, а специальные паровые двигатели при этом раздували кузнечные мехи. Часть полученного железа пошла на создание новых паровых двигателей. И так по кругу. Анаксагор, предшественник Сократа, утверждал, что трансформация материалов – например, превращение еды в плоть и кровь – возможна потому, что в каждой субстанции содержатся части всех остальных субстанций. На такие мысли наводит и история взаимного преобразования угля, пара и железа на заре промышленной эры.
Спросите Итана: как быстро можно достичь скорости света?
5 min
Translation
Для достижения скорости, близкой к скорости света, многоступенчатой ракете нужно было бы отбрасывать часть своей массы по мере увеличения скорости, как делает изображённая здесь ракета Super Haas
Допустим, вы хотите отправиться в межзвёздное путешествие и добраться до точки назначения как можно быстрее. Возможно, у вас не получится сделать это до завтра, но если бы у вас были все необходимые инструменты и технологии, а также немного помощи от относительности Эйнштейна – смогли бы вы добраться туда через год? А что насчёт приближения к скорости света? Именно об этом задаёт наш читатель свой вопрос на этой неделе:
Я недавно читала книгу, автор которой пытался объяснить парадокс близнецов, представляя космический корабль, 20 лет летящий с ускорением в 1 g, а затем возвращающийся назад. Возможно ли в течение такого времени поддерживать такое ускорение? Если, допустим, начать путешествие в первый день нового года и лететь с ускорением 9,8 метра в секунду в секунду, то, если верить расчётам, до конца года можно достичь скорости света. Как после этого дальше ускоряться?
Для путешествия к звёздам совершенно необходимо поддерживать такое ускорение.
Интерполяция — мать анимации — Твинеры в Unity
9 min
Одним из неотъемлемых элементов игровых приложений, обеспечивающих красочный пользовательский опыт, является анимация. Основным компонентом Unity для анимации является "Mecanim", имеющий более привычное название "Аниматор". Это очень мощный инструмент, позволяющий управлять сложнейшими системами объектов, совместимый со скелетными анимациями, экспортируемыми из 3D-пакетов, с инструментами для работы с IK, смешивания анимаций или частичного их проигрывания. И как только ты уверишься в том, что пробовал в аниматоре все, будь уверен - на следующий день ты найдешь новую функцию, с которой не сталкивался ранее. И это будет та самая функция, которой тебе так не хватало. Но не всегда...
Ассоциативная самозамкнутая сеть. Что нужно для создания сильного ИИ
6 min
Свойственное поведение — искажение результатов работы системы, обусловленное её строением. Как уменьшить влияние данной проблемы и организовать логическую связь между неограниченным множеством разнородных объектов для дальнейшего использования их не только в качестве знаний, но и описаний действий, что много важнее.
Теперь персональные данные должны удалять отовсюду по первому требованию, но есть побочка
12 min
Речь идет о поправках к закону о персональных данных, что вступили в силу в марте. Теперь любые персональные данные обязаны убрать откуда угодно по первому требованию их владельца. Причем владельцу не надо ничего никому доказывать и объяснять.
Ситуация одновременно и правильная, и проблемная. Причем проблемы появятся (по факту уже появились) у всех владельцев сайтов, интернет-площадок и СМИ, кто так или иначе взаимодействует с пользователями.
Что касается нововведений, я попытался разложить все по полочкам. А еще собрал в отдельный список то, что придется поменять и добавить владельцам сайтов.
Теории вероятностей: готовимся к собеседованию и разрешаем «парадоксы»
17 min
Каждый год я участвую примерно в сотне собеседований в образовательных проектах JetBrains: собеседую абитуриентов в Computer Science Center и корпоративную магистратуру ИТМО (кстати, набор на программу идёт прямо сейчас). Все собеседования устроены по одному шаблону: мы просим на месте порешать задачи и задаём базовые вопросы по дисциплинам, которые студенты изучали в университетах. Большинство вопросов, которые мы задаём, довольно простые — нужно дать определение некоторого понятия, сформулировать свойство или теорему. К сожалению, у значительной доли студентов все эти определения выветриваются сразу после экзаменов в университетах. Казалось бы, что тут удивительного? В современном мире любое определение можно за пару секунд нагуглить, если это нужно. Но невозможность восстановить базовое определение свидетельствует о непонимании сути предмета.
Если непонимание алгебры или математического анализа может мало влиять на вашу жизнь, то непонимание теории вероятностей делает из вас лёгкую мишень для обмана и манипулирования. Суждения о вероятностях различных событий настолько глубоко вошли в нашу повседневную жизнь, что умение правильно рассуждать и отличать правду от невежества или манипуляции является необходимым. В этом небольшом обзоре мы поговорим о базовых понятиях теории вероятностей, научимся правильно формулировать утверждения про простые случайные процессы и разберём несколько парадоксов. Часть материала позаимствована из брошюры А. Шеня «Вероятность: примеры и задачи», которую я очень рекомендую для самостоятельного изучения.
Unity, ECS и все-все-все
7 min
Сколько уже было мануалов "Как сделать игру на Unity за 3 часа", "Делаем Counter-Strike за вечер" и т.п.? Низкий порог входа — это, несомненно, главный плюс и минус Unity. Действительно, можно накидать “ассетов”, дописать несколько простых “скриптов”, обмотать синей изолентой и это даже будет как-то работать. Но когда проект обрастает игровыми механиками, сложной логикой поведения, то проблемы при подобном подходе нарастают как снежный ком. Для внедрения новых механик требуется переписывание кода во многих местах, постоянная проверка и переделывание префабов из-за побившихся ссылок на компоненты логики, не говоря уже об оптимизации и тестировании всего этого. Разумеется, архитектуру можно продумать изначально, но на практике это всегда недостижимая цель — дизайн-документ довольно часто меняется, какие-то части выкидываются, добавляются абсолютно новые и никак не связанные со старой логикой поведения. Компоненты в Unity — это шаг в правильном направлении в виде декомпозиции кода на изолированные блоки, но особенности реализации не позволяют достичь необходимой гибкости, а самое главное, производительности. Разработчики придумывают свои фреймворки и велосипеды, но чаще всего останавливаются на ECS (Entity Component System). ECS – одно из решений, продолжающее идею компонентной модели Unity, но придающее ей ещё больше гибкости и сильно упрощающее рефакторинг и дальнейшее расширение приложения новым функционалом без кардинальных изменений в текущем коде.
Отойти от IT: куда расти, когда код ради кода больше не интересен
20 min
Интернет завален статьями «как войти в IT и начать писать код», но куда реже говорят о том, как перестать его писать. Что делать, если больше не хочется весь день смотреть в IDE, но и в тимлиды не тянет? Конечно, можно освоить свиноводство, но есть ли сферы, где пригодится уже полученный опыт? Куда можно свернуть «в сторону» от разработки, и какие скиллы для этого понадобятся?
Это похоже на прокачку веток развития персонажа в RPG-игре. Ставишь на ловкость или качаешь силу — получаешь разный результат. Мы выбрали четыре направления, в которых можно качать своего персонажа, и задали вопросы людям, которые уже прошли этими путями:
Большой город для мобильных устройств на Unity. Опыт разработки и оптимизации
7 min
Привет Хабр! В этой публикации хочу поделиться опытом разработки массивной мобильной игры, с большим городом и трафиком. Примеры и приемы описанные в публикации не претендуют называться эталонными и идеальными. Я не являюсь дипломированным специалистом и не призываю повторять свой опыт. Целью работы над игрой было — получение интересного опыта, получение оптимизированной игры с открытым миром. При разработке я старался максимально упрощать код. К сожалению, я не использовал ECS, а грешил с singleton.
Игра
Игра на тематику мафии. В игре я попытался воссоздать Америку 30-40. По сути игра является экономической стратегий от первого лица. Игрок захватывает бизнес и старается удержать его на плаву.
Реализовано: автомобильный трафик (светофоры, избегание столкновений), human трафик, бар, казино, клуб, квартира игрока, покупка костюма, смена костюма, покупка/покраска/заправка автомобиля, копы, охрана/гангстеры, экономика, продажа/покупка ресурсов.
Архитектура
Я жалею, что не использовал ECS, а пытался в велосипед. В итоге получилось все громоздко и слишком зависимо. У приложения одна точка входа — игровой объект application(go), на котором висит одноименный класс Application. Он отвечает за предварительную загрузку БД, заполнение пулов и первичные настройки. Кроме того, на плечи application(go) ложатся и несколько других singleton классов-компонентов-менеджеров.
Гексагональные тайловые миры
Hard
32 min
Tutorial
Тайловость в играх – очень распространенное явление, особенно в играх инди сегмента. Чаще всего используют квадратные тайлы – в них проще всего задать необходимые данные, будь то карта уровня или инвентарь. Однако на квадратных и прямоугольных формах возможности подобной системы не ограничиваются.
В топовых играх конца девяностых - начала нулевых часто можно увидеть шестиугольную сетку заместо квадратной – в то время это смотрелось очень интересно, в особенности в сочетании с изометрией. Именно о работе с такими сетками и пойдет речь.
Wild Horizon или как осуществляется на практике мечта игродела
4 min
Длинный монолог о том, как я рисовал Дикий Запад для Google Play. История глазами дизайнера.