Алгоритмы *

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

Исходный код к этой статье выложен на GitHub.

Огонь как явление очень интересен с точки зрения компьютерной графики. Раньше огонь было принято имитировать. Например, в фильме «Властелин колец» Питера Джексона для изображения огня использовались спрайты с огромным количеством дыма (на тот момент симуляция флюидов обходилась слишком дорого, даже при бюджете блокбастера). Когда требовалось моделировать огонь в режиме реального времени, например, в видеоиграх, использовались почти исключительно нефизические подходы.

▍ Зачем ограничивать частоту?

Хабр, привет! Это снова Антон Разжигаев, аспирант Сколтеха и научный сотрудник лаборатории Fusion Brain в Институте AIRI, где мы продолжаем углубляться в изучение языковых моделей. В прошлый раз мы выяснили, что эмбеддинги трансформеров-декодеров сильно анизотропны. На этот раз я бы хотел рассказать об их удивительной линейности, ведь нашу статью про обнаруженный эффект («Your Transformer is Secretly Linear») несколько дней назад приняли на международную конференцию ACL!

Привет, Хабр! Мы представляем команду GigaCode. В декабре 2023 года наш продукт стал доступен широкой аудитории. До этого GigaCode использовался только внутри компании, и нас часто спрашивали о том, как GigaCode выглядит на фоне других ИИ-ассистентов, как вы сравниваете себя с остальными? Отвечая на эти вопросы, мы начали с простой задачи, которая оказалась не такой уж и простой и вылилась в увлекательное исследование со всем тем, что мы так любим: множеством измерений, математической статистикой и, конечно же, новыми горизонтами. Интересно? Добро пожаловать под кат.

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

Весь код сохранен в репозитории GitVerse.

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

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

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

В последние годы в нашей повседневной речи плотно закрепилось словосочетание «нейронные сети». Этот термин означает набор методов и программных решений из машинного обучения, дискретной математики и информатики. Но про что совсем часто забывают — он происходит из нейробиологии. Несмотря на очевидное название, нейросети — это не набор операторов IF и ELSE, а модели, вдохновлённые нервной системой живых организмов. Их эффективность в пору, когда у нас есть такие генеративные модели как GigaChat и Kandinsky, наглядно видна каждому. 

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

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

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

Внимание! В статье много картинок.

Внутри Dolt, первой в мире базе данных SQL с полнофункциональными возможностями контроля версий, таится много интересной computer science. Недавно я писал о системе хранения Dolt, в ней есть очень тонкая особенность — применение вероятностного поиска на больших выборках 64-битных целых чисел.

В любом учебном плане по Computer Science есть курс алгоритмов. Моим был CS 102, и одним из пунктов, который объяснялся в нём досконально, было то, что поиск — это, по сути, задача O(log2(N)) при условии, если данные отсортированы. За свою карьеру я многократно встречался с этим в том или ином виде — если сортируешь информацию и сохраняешь её, то стоит ожидать, что для поиска потребуется время O(log2(N)). В общем случае мы соглашаемся на время поиска O(log2(N)), потому что оказывается, что можно перебрать большой объём данных с логарифмическим коэффициентом масштабирования. Эта система работает, потому что мы уже почти автоматически сортируем всё заранее.

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

Будет ли эта статья историей о необязательной оптимизации? Да, будет. В этом конкретном случае поиск будет занимать гораздо меньше времени, чем чтение с диска. Мы говорим о величинах менее чем 0,1% от суммарного времени. Будет ли эта статья историей о преждевременной оптимизации? Нет, не будет. Это бы подразумевало, что мы не осознаём, что время тратится не на то. Эта статья — история о заманчивости алгоритма константного времени.

В этой статье я расскажу про систему команд — улучшение простого чат-бота. Суть системы команд в том, чтобы создать возможность создания команд во время работы программы не изменяя ее кода. Эта идея является логическим продолжением идей о простом чат-боте, которые я описал в предыдущей статье «Как начать мыслить о ИИ». Поэтому, чтобы лучше понимать идею этой статьи, можете прочитать предыдущую тут.

Связный список — классическая структура данных, которая позволяет быстрые вставки/удаления, но при этом просаживает другие операции (случайный доступ к элементу). Мы пройдёмся от базовой реализации до других возможных вариаций этой структуры данных и, надеюсь, вместе узнаем что‑то новое. Краем глаза увидим возможные применения связных списков. И в конце, для любителей C++, бонус: использование связного списка для сбора диагностики выделений динамической памяти в вашем коде.

Полтора года назад я рассказывал про свой пет‑проект по визуальному программированию — falang.io. Основная его особенность состоит в том, что пользователь не управляет расположением икон на схеме, только их содержимым. Все остальные соединительные линии рисуются автоматически алгоритмом по строгим правилам. В т.ч. continue, break, return.

На данный момент, помимо обычных текстовых диаграмм, у меня появился Low‑code констркутор логики с упрощенной семантикой, который может экспортироваться в 5 современных языков программирования: C++, C#, Rust, Go, TypeScript.

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

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

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

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

«То настроения, то сил нету, то задачи не понимаю.. Начинаю раз в полгода и бросаю» — самый обычный набор приколов, которые мешают.

Я предложил ему обернуть всё это в привычку и дисциплину. Я собрал свою методологию прививания привычек основываясь на:

Ежедневно он тратил на Литкод 15–20 минут. Не более. Иногда участвовал в турнирах, которые и зафиксировали результат в топ 4%.

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

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

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

Предлагаю с этого и начать.

Ранее был предложен некоторый Алгоритм деления 2W‑битовых чисел с использованием операций над W‑битовыми числами. Для тестирования использовались целые числа языка С++, что не позволяло проверять, например, 128-битные целые числа. Однако, в язык Python встроена поддержка целых чисел неограниченной ширины (Big Integer), а также имеется API для вызова методов Python из программ на языке С/С++. Это позволяет протестировать разные алгоритмы с числами, в том числе деление, используя в качестве результата строковое представление чисел.

В данной статье расписаны шаги для использования Python C API в программе на языке С++, а также показан пример вызова оператора деления двух целых чисел с возвратом результата в виде строки С. Использовалась следующая программная конфигурация:

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