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

Это версия классической задачи о разборчивой невесте. У неё есть красивая оптимальная стратегия — правило . Возможно, вы о нём слышали. Но знаете ли вы, почему оно работает? И как вообще до него додуматься?

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

Недавно я узнал о Теореме о Шансах — более общем подходе, который, неожиданно, работает гораздо проще, чем классическое доказательство. По-русски о ней еще никто не писал

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

Эта задача стоит того, чтобы пройти её до конца. Будет понятно, красиво и интересно

Привет, Хабр! Представьте, что ваш мозг — это IDE, в которой 95% крутых плагинов попросту спят. Мы часто слышим об «Антихрупкости» или «FOMO», но сейчас этого стало настолько много, что я решил аггрегировать всё в одну статью, с примерами, чтобы всем было понятно.

В этой статье я собрал 50 самых насущных концепций из психологии, нейронауки и философии — от «синдрома утёнка» до «нейроэстетики».

Нас ждёт мозговыносящая смесь 64/32-битного ассемблера и старого-доброго C++. Мы сделаем собственную реализацию... Волокон (fibers) без вызова Win API и звонков в службу спасения.

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

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

Есть множество материалов написанных о работе полупроводников и работе транзисторов.

Зачем еще одна?

Дело в том, что я заметил такую тенденцию в вузовских учебниках – довольно подробное описание работы p-n перехода и очень поверхностное описание работы биполярного транзистора. Зачастую «механика» работы такого транзистора описывается довольно схематично (в совершенно неработоспособном виде) и далее следует быстрый переход на описание внешних параметров. Причем у этих же авторов описание «механики» работы полевого транзистора дается куда обширнее. Видимо, авторы учебников сами не очень «догоняют», как там все работает. И это не удивительно. Человечество вначале эры полупроводников пыталось повторить схему работы вакуумной лампы на полупроводниках, т.к. работа лампы достаточно логична. И собственно полевые транзисторы, в какой-то степени повторяют принцип работы вакуумных ламп. Но вот биполярный транзистор, хотя и был изобретен первым, но это было скорее случайное изобретение, а не осознанный путь к цели.

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

Если Вы задавали себе вопросы наподобие таких:

почему через коллекторный p-n переход, включенный в обратном направлении, течет ток, да еще и самый, что не на есть главный рабочий ток?

почему неосновные носители тока базы в биполярном транзисторе, вдруг стали вполне себе главными представителями тока?

Почему ток в базы через открытый эмиттерный p-n переход меньше тока через закрый коллекторный p-n переход?

Ну и совсем «подковыристый» вопрос. Почему при включении биполярного транзистора по схеме с общим эмиттером, когда транзистор полностью открыт (находится в режиме насыщения), напряжение на коллекторе становиться меньше напряжения базы? Ведь если смотреть на транзистор с точки зрения пирога n-p-n переходов (как рисуют в учебниках), то сумма падения напряжения на двух p-n переходах (открытом эмиттерном и закрытом коллекторном) должно быть больше напряжения на одном открытом эмиттерном переходе. А оно у нас меньше.

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

Однажды по работе мне прилетела задача по сборке и запуску Linux на одноплатном ПК. Тогда я, будучи разработчиком ПО для микроконтроллеров, встал в небольшой ступор — задачка явно не решалась установкой IDE и нажатием в ней кнопки «Собрать проект». Гугл помог узнать о том, что существует некий Buildroot. В материалах по теме всё выглядело довольно просто: скачай, настрой, дерни пару команд, загрузи результат на одноплатник — и можно запускать! Получается, процесс не многим сложнее установки дистрибутива Linux или Windows на обычный ПК? Конечно же, нет. Ведь если у тебя в руках кастомный одноплатник неизвестного китайского бренда, а не BeagleBone или Raspberry Pi, то зарыться в Buildroot придётся с головой...

Задача
Три айтишника — Маша, Вася и Петя — пошли в поход. После ужина они решают, кто будет мыть посуду. Петя дежурит один, а Маша с Васей — вдвоём. Значит, нужно выбрать Петю с вероятностью ⅓, а Машу с Васей — с вероятностью ⅔. Под рукой — только честная монетка. Как с её помощью устроить такой жребий?

Когда мы обсуждали эту задачу со студентами, они предложили такой способ. Бросим монету дважды: если выпали два орла — дежурит Петя; если один орёл и одна решка — Маша с Васей; если две решки — перебрасываем

Чтобы выбрать дежурного так, в среднем уходит 8⁄3 броска (чуть позже мы это докажем). Можно ли сделать это быстрее? Существует ли алгоритм, для которого ожидаемое число бросков меньше?

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

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

В финале мы обобщим эту идею: научимся моделировать любую вероятность p от 0 до 1 — и любое дискретное распределение. Заодно познакомимся с важным понятием, называемым энтропией

А в самом конце, как всегда — красивая задача

Привет! На связи Антон Полухин из Техплатформы Городских сервисов Яндекса, и сейчас я расскажу о софийской встрече Международного комитета по стандартизации языка программирования C++, в которой принимал активное участие. Это была последняя встреча, на которой новые фичи языка, с предодобренным на прошлых встречах дизайном, ещё могли попасть в C++26.

И результат превзошёл все ожидания:

• compile-time-рефлексия
• рефлексия параметров функций
• аннотации
• `std::optional<T&‍>`
• параллельные алгоритмы

На прошлой неделе в Софии, столице Болгарии, закончилась работа над стандартом C++26, который помимо контрактов, std::execution и всего прочего теперь включает и рефлексию.

В этой статье будет продемонстрирован один из примеров её использования: преобразование строк в формате JSON в объекты C++ на этапе компиляции.

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

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

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

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

Новый стандарт C++, C++23, впервые с C++11 расширил всем привычную линейку контейнеров: помимо знакомых array, vector, (unordered_)set, (unordered_)map и прочим в нее теперь входят непонятные flat_set, flat_map, flat_multiset и flat_multimap. Ответим на вопросы, что это за контейнеры, когда они могут быть полезны, сравним дизайн стандартизированных «плоских» контейнеров с дизайном плоских контейнеров из Boost и ETL и, конечно, произведём замеры и сравним производительность flat_ и не flat_ контейнеров.

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

Получение имени типа, не важно это структура или перечисление, в C++ — проблема. То, что тривиально известно компилятору на этапе парсинга исходников, не получится перевести в человеко-читаемый вид в рантайме. Можно использовать std::type_info::name, который не является переносимым решением, потому что зависит от реализации манглинга в компиляторе. Некоторые компиляторы (например, MSVC, IBM, Oracle) создают "удобное" имя типа, а вот gcc и clang, возвращают искаженное имя, котороe можно преобразовать в удобочитаемую форму с помощью дополнительных функций, например abi::__cxa_demangle. Чтобы вся эта магия работала нужно подключить RTTI, который тоже не всегда доступен, а иногда и вообще-то вреден, потому что сжирает драгоценную производительность, но можно сделать по другому.

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

Этими словами заканчивалось письмо Эвариста Галуа, написанное для своего друга Огюста Шевалье за два дня до его смерти от полученных на дуэли ран на 21 году жизни. Ни Якоби, ни Гаусс в его теоремах не разобрались, зато спустя 15 лет разобрался Жозеф Лиувилль и опубликовал работы Галуа, ставшие впоследствии фундаментом современной алгебры, известные сейчас как теория Галуа. В статье расскажу про одну из частей этой теории - поля Галуа, получившая настолько повсеместное применение в криптографии и избыточном кодировании, что Intel и AMD выпустили набор процессорных расширений для эффективной реализации операций над этими полями.

Заметка! Если вам довелось использовать/реализовывать поля Галуа, то большая часть статьи для вас скорее всего будет не интересна, но возможно в последних разделах будет что-то для вас новое.

Ручное управление ресурсами в низкоуровневом си-подобном коде на C++ — довольно хлопотное занятие. Создание достойных RAII-врапперов для каждого используемого сишного API не всегда практично, а использование подходов с goto cleanup или множеством вложенных if (success) вредит читаемости кода.

Макрос defer как никогда кстати! Отложенная лямбда будет выполнена при выходе из области видимости, независимо от того, будет ли выполнен return, брошено исключение, или даже выполнен goto наружу. Данный макрос по-настоящему zero-cost и не зависит от рантайма C или стандартной библиотеки, поэтому его можно использовать даже в разработке под ядро ОС.

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

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

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

В этой статье разберём мутный, но крайне важный инструмент ‒ std::launder. Мы поглядим, зачем его протащили в C++17 и что компилятор делает, когда видит launder.

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

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

Статья рассчитана на читателей, которые не являются гуру C++ или знатоками тонкостей языка, но в целом знакомы с языком и его идеями, хотя знание ассемблера x86 не требуется, я буду прикладывать ссылки на примеры кода quickbench, чтобы объяснить, почему даю те или иные советы.

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