Как стать автором
Обновить
236.08

Алгоритмы *

Все об алгоритмах

Сначала показывать
Порог рейтинга
Уровень сложности

Алгоритмы на кристалле (анонс книги)

Время на прочтение7 мин
Количество просмотров13K
Я начал работать над книгой.
Уже опубликованы:
Глава 1(начало): Вычислительная модель.
Глава 1(продолжение): Быстродействие элементарных схем.

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

О чем и для кого эта книга


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

Основной акцент повествования сделан на математическую и алгоритмическую стороны решаемых задач. Это скорее не «еще одно» руководство по проектированию электронных схем, а учебник по очень специфическому способу реализации алгоритмов. Я надеюсь, что его содержание заинтересует и увлечет широкий круг любителей математики и программирования, даже если они раньше никогда и не сталкивались с разработкой микросхем. В то же время я старался подобрать материал так, чтобы и типичный hardware-разработчик мог легко в нем разобраться и с пользой применить в своем ремесле.
Читать дальше →
Всего голосов 61: ↑59 и ↓2+57
Комментарии51

Сказка про Guid.NewGuid()

Время на прочтение11 мин
Количество просмотров24K

C#. Guid.NewGuid(). Linux. Windows. Randomness or Uniqueness. RNG and PRNG. Performance. Benchmarking.

Цель нашей сегодняшней сказки — развлечься как следует. Детективная история в поисках потерянного перфоманса с красивым финалом и эффектным результатом непосредственно связана с набором слов из предыдущего абзаца.

Читать далее
Всего голосов 71: ↑69 и ↓2+67
Комментарии34

8 ошибок, из-за которых ты проиграешь в соревновательном Data Science

Время на прочтение8 мин
Количество просмотров16K

Привет, чемпион!

Если ты читаешь этот пост, значит, тебе стало интересно, не допускаешь ли этих ошибок ты?! Почти уверен, что ты допускал эти ошибки хотя бы раз в жизни. Мы не застрахованы от совершения ошибок, такова наша человеческая натура — ошибаться для нас естественно. Однако, я постараюсь уберечь тебя от тех ошибок, которые совершал сам или замечал у других.

Так вышло, что за время участия в чемпионатах по соревновательному анализу данных я достаточно часто бывал в призовых местах. Однако, бывали случаи, когда я лишался призовых по глупости или неосторожности. Рассказываю по порядку.
Читать дальше →
Всего голосов 59: ↑57 и ↓2+55
Комментарии10

STM32. Про синус

Время на прочтение7 мин
Количество просмотров16K

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

Тригонометрические функции, характеризующиеся высоким потреблением процессорного времени, могут негативно влиять на выбор бюджетных микроконтроллеров ( без модуля FPU ) для задач, где важна скорость счёта, например, контроль пространственного положения.

Читать далее
Всего голосов 61: ↑60 и ↓1+59
Комментарии100

Истории

Алгоритм Томасуло как фактор импортозамещения российских процессоров

Время на прочтение7 мин
Количество просмотров42K

Проектированием простого процессора сейчас никого не удивишь. Любой способный студент может за пару недель написать на верилоге однотактный RISC-V или ARM процессор и синтезировать его для ПЛИС. Процессор будет работать на учебной плате и выполнять простые программы на Си и ассемблере.

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

На границе между вводным и продвинутым курсом микроархитектуры CPU принято ставить внеочередное выполнение инструкций, именно оно отделяет мальчика от мужа. Эта фича впервые появилась еще в 1960-е годы в суперкомпьютерах CDC 6600 и IBM 360/91, но проникла в персоналки с PentiumPro только в 1996 году и в Apple iPhone в 2012 году.

Именно внеочередное выполнение инструкций - главная козырная карта самого горячего процессорного проекта российской микроэлектроники - двухгигагерцового RISC-V процессора для ноутбуков от компании Ядро / Syntacore. Этот проект был объявлен в прошлом году. Что с ним станет в результате известных событий?

Читать далее
Всего голосов 110: ↑89 и ↓21+68
Комментарии127

Программирование необычных шахмат

Время на прочтение18 мин
Количество просмотров19K

Написание своего шахматного движка - обширная тема, про которую пишут целые книги.

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

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

Я запрограммировал 15 шахматных вариаций - для каждой опишу неожиданные ходы и результаты партий компьютера друг с другом.

Читать далее
Всего голосов 67: ↑67 и ↓0+67
Комментарии17

Случайные лабиринты и сапёр от третьего лица, инопланетные жуки и алгоритм Брезенхема

Время на прочтение4 мин
Количество просмотров7.3K

Всем привет! Уже больше 30 лет я занимаюсь разработкой видеоигр и регулярно экспериментирую с различными игровыми механиками. В результате я пришел к идее создать игру по типу сапёра, но от третьего лица и на roguelike подобном уровне.

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

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

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

Читать далее
Всего голосов 61: ↑60 и ↓1+59
Комментарии17

Вычисление стихотворного размера

Время на прочтение8 мин
Количество просмотров23K

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

Читать далее
Всего голосов 87: ↑87 и ↓0+87
Комментарии30

Как получил оффер от Microsoft

Время на прочтение6 мин
Количество просмотров53K

О чем эта статья

Это продолжение моих похождений по ФААНГ. Предыдущая статья была о моем опыте собеседования в Амазоне.

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

К слову, все собеседования тоже сейчас проходят онлайн, и никаких онсайт интервью нет.

Читать далее
Всего голосов 88: ↑80 и ↓8+72
Комментарии139

Мой опыт собеседования в Amazon

Время на прочтение6 мин
Количество просмотров62K

О чём эта статья

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

Это история о моем опыте собеседования в Амазоне, почему мне в целом не понравилось по сравнению с другими FAANG. Так же тут будут ответы на “а что конкретно спрашивали на интервью, какие были задачки, что на систем дизайне было”, потому что мне не дали подписать NDA, все с пруфами, скринами и прочее.

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

Начало, предложение от Amazon

В один прекрасный день 6 сентября, мне пришел такой сообщение в Линкедин.

Читать далее
Всего голосов 93: ↑90 и ↓3+87
Комментарии177

Разумная слизь? Тварь, способная решать сложные задачи, что не под силу даже существам, обладающим развитым мозгом

Время на прочтение7 мин
Количество просмотров67K

Автор Лысый Камрад (@LKamrad)

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

Знакомьтесь, Physarum polycephalum  – не животное, не растение и даже не гриб...

Примечание: данную публикацию можно использовать для начала ознакомления учащихся с принципами динамического программирования.

Читать далее
Всего голосов 190: ↑177 и ↓13+164
Комментарии85

Формула Бине без плавающей точки

Время на прочтение4 мин
Количество просмотров12K

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

Читать далее
Всего голосов 77: ↑76 и ↓1+75
Комментарии29

Ещё 20+ игр, которые прокачивают логику, алгоритмы и радуют умный мозг [по следам комментариев на Habr]

Время на прочтение9 мин
Количество просмотров118K
image

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

Еще я веду канал в Telegram: GameDEVils, делюсь там клевыми материалами (про геймдизайн, разработку и историю игр).
Читать дальше →
Всего голосов 83: ↑82 и ↓1+81
Комментарии59

Ближайшие события

15 игр, которые прокачивают логику, алгоритмы, ассемблер и силу земли

Время на прочтение8 мин
Количество просмотров102K


Есть «Super Mario», признанная классика видео игр. Есть «Doom», который запускают на чайниках и тестах на беременность. Есть супер-популярные по статистике twitch.tv игры («League of Legends», «GTA V», «Fortnite», «Apex Legends») которые стримят пятая часть всех стриммеров.

А есть игры, на которые очень мало обзоров, но они супер крутые — игры про алгоритмы. Игры, в которых можно кодить на ретро-компьютере; игры, которые надо взламывать; игры, где можно программировать контроллеры или поведение персонажей; игры, где можно создавать свою игру внутри игры.

Под катом подборка классных игр про алгоритмы за последние 10 лет. Если что-то упустила — буду рада дополнениям.

Еще я создала канал в Telegram: GameDEVils, буду делиться там клевыми материалами (про геймдизайн, разработку и историю игр).
Читать дальше →
Всего голосов 98: ↑93 и ↓5+88
Комментарии98

PROOF OF STAKE – это скам

Время на прочтение16 мин
Количество просмотров104K

Proof of Stake (PoS) – это мошенничество. Когда я говорю это, я имею в виду, что PoS 1) заявлен как система консенсуса, и 2) фактически неспособен на самом деле обеспечить консенсус.

Читать далее
Всего голосов 118: ↑99 и ↓19+80
Комментарии485

Муравей Лэнгтона — загадочный клеточный автомат

Время на прочтение4 мин
Количество просмотров17K

В мире существует около 14 000 видов муравьёв, каждый из которых имеет собственное название. Но, даже если вы зададитесь такой целью, вы не найдёте ни в одном биологическом справочнике муравья Лэнгтона. Дело в том, что этот муравей — математическая абстракция, модель для описания поведения динамической системы.

Невесёлая жизнь у муравья Лэнгтона, но, как мы увидим, он не готов мириться с такой возмутительной ситуацией и всеми силами старается сбежать.

Читать далее
Всего голосов 60: ↑59 и ↓1+58
Комментарии23

Пример применения кода Рида-Cоломона

Время на прочтение9 мин
Количество просмотров20K

Пример применения кода Рида-Cоломона

О чём это всё?

Всем привет! Наконец дошли руки описать то как я проверял на практике знания, полученные в ходе написания трёх статей об избыточном кодировании по методу Рида-Соломона (раздватри)

Читать далее
Всего голосов 102: ↑102 и ↓0+102
Комментарии46

LJV: Чему нас может научить визуализация структур данных в Java

Время на прочтение26 мин
Количество просмотров28K

Эта статья является пересказом моего доклада на Java-конференции SnowOne 2021 года. LJV — проект, созданный в 2004 году как инструмент для преподавания языка Java студентам. Он позволяет визуализировать внутреннее устройство структур данных. В этом докладе я запускаю LJV на разных структурах (от String до ConcurrentSkipListMap) в разных версиях Java и разбираю, что там внутри, как оно менялось от версии к версии, и как это всё работает.


image

Читать дальше →
Всего голосов 85: ↑85 и ↓0+85
Комментарии11

О русской науке замолвите слово или за что я люблю Тинькофф, часть 1

Время на прочтение34 мин
Количество просмотров51K


Так сложилось, что я уже много лет руковожу научной группой, а с недавних пор лабораторией в МГУ. При этом львиная доля финансирования нашей лаборатории идет от компаний. Изначально она была создана в рамках контракта с Intel (совместная лаборатория), а позднее мы очень активно работали ещё и с RealNetworks (20+ проектов), Samsung (совместная лаборатория), Cisco, Huawei (до 5 контрактов параллельно) и другими. И так получилось, что большая часть наших контрактов (примерно 95% по количеству и 99% по деньгам) приходилась на иностранные компании, при этом взаимодействие с российскими компаниями в среднем заметно контрастировало.

Моим наилучшим примером отношения русских компаний к университетам является любимый пример Олега Тинькова из его книги:

«Третий пример, мой любимый. Весной 2011 года я выступал на мехмате МГУ и с присущим мне эпатажем заявил: «Что такое фундаментальная наука. Ходить грязным, вонючим и в итоге стать нобелевским лауреатом? Так вот, это все булшит! Зарабатывайте деньги. Не думайте про фундаментальную науку, потому что это отстой».
Олег Тиньков, «Революция. Как построить крупнейший онлайн банк в мире»
 

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

Меня периодически спрашивают друзья из компаний: «Как там наука? Поднялась с колен? Я слышал — ситуация получше стала». Кому интересно, как Тиньков развалил мехмат что происходит в науке в разрезе работы с компаниями (этюды в багровых тонах, вечерние зарисовки из окопа автора) — добро пожаловать под кат!
Читать дальше →
Всего голосов 177: ↑166 и ↓11+155
Комментарии348

Три архитектуры эльфам, семь гномам, девять людям… где же искать ту, что объединит их все?

Время на прочтение60 мин
Количество просмотров29K

Проводится сеанс разоблачения магии (CISC, RISC, OoO, VLIW, EPIC, ...).
Без традиционной рубрики “а что, если” тоже не обошлось.

Добро пожаловать под кат, правда, лёгкого чтения ожидать не стоит.

Читать далее
Всего голосов 141: ↑141 и ↓0+141
Комментарии55

Вклад авторов