Цветовая вычислительная фотография. Часть 2: Стандарты CIE 1931

Всем привет! На связи снова Егор Ершов, руководитель группы «Цветовая вычислительная фотография» в AIRI и заведующий сектором репродукции и синтеза цвета ИППИ РАН. Это вторая статья из длинного цикла, которая, фактически, является конспектом лекций курса по алгоритмам вычислительной фотографии, которые я читаю для студентов МФТИ и ВШЭ.

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

https://habr.com/ru/companies/airi/articles/916116/

Алгоритмы и Структуры данных

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

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

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

Но начнем мы все-таки с пузырька, как с самого популярного алгоритма.

https://habr.com/ru/companies/otus/articles/911968/

Алгоритмы и Структуры данных

GPT-4 уже не за горами. Что мы о нём знаем

Возможно, вы помните, что о появлении GPT-3 объявили в мае 2020 года. Его запустили через год после GPT-2, который также появился спустя год после первой версии GPT. Если бы эта тенденция сохранялась, то GPT-4 уже был бы доступен. Увы, четвёртой версии мы пока не дождались. Но генеральный директор OpenAI Сэм Альтман недавно заявил, что GPT-4 на подходе. Некоторые эксперты полагают, что релиз состоится где-то в июле-августе 2022 года.

https://habr.com/ru/companies/cloud4y/articles/667278/

Алгоритмы и Структуры данных

.NET 6: PriorityQueue

В .NET 6 появилась новая коллекция — PriorityQueue<TElement,TPriority>. До этого очереди с приоритетами уже были в .NET, но только в виде внутренних классов — они использовались под капотом разных механизмов в WPF, Rx.NET и в других частях фреймворка.

Но в .NET 6 PriorityQueue стала новой коллекцией, которой теперь можно пользоваться из клиентского кода. Давайте посмотрим, что предлагает эта очередь, как она устроена внутри и насколько быстро работает. Под катом будет постепенное погружение: от примеров использования в коде к введению n-арные деревья.

https://habr.com/ru/companies/skbkontur/articles/666018/

Алгоритмы и Структуры данных

Генератор бредовых идей

DevHumor

Симулятор x86 подобного процессора на машине Тьюринга

Привет, Хабр! В свободное от работы время по вечерам мне нравится воплощать в жизнь свои сумасшедшие идеи. В один из таких вечеров родилась мысль реализовать компилятор кода в машину Тьюринга. Осознав всю тщетность бытия сложность реализации, было принято решение начать с чего-то более простого – симулятора простенького процессора со своим собственным ассемблером, в котором команды выполнялись бы с помощью различных состояний машины Тьюринга, а данные хранились бы на одной ленте. В конечном итоге удалось осуществить практически первоначальную задумку, а именно получить одну единственную машину Тьюринга, способную выполнять скомпилированную из NASM подобного ассемблера программу без какого-либо внешнего взаимодействия.

https://habr.com/ru/articles/665776/

Алгоритмы и Структуры данных

Apache OpenOffice. Динамические массивы

Динамические массивы повышают интеграционную адаптивность программ.

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

Без претензии на толкование динамических массивов, далее по тексту изложены:

операторы языка StarBasic из Apache OpenOffice для работы с динамическими массивами;

демонстрационные примеры с динамическими массивами на языке StarBasic.

https://habr.com/ru/articles/665674/

Алгоритмы и Структуры данных

Задача о Выборе Билетов

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

Я решил положить этому конец и распетлять задачу при помощи ЭВМ.

https://habr.com/ru/articles/852100/

Алгоритмы и Структуры данных

Детальный обзор полей Галуа

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

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

https://habr.com/ru/articles/916740/

Алгоритмы и Структуры данных

Геометрический смысл комплексного гармонического осциллятора и винты

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

И что отдельно интересно, это то, что в очередной раз оказалось невероятно удобно работать с нейросетью DeepSeek:

https://habr.com/ru/articles/916654/

Алгоритмы и Структуры данных

Резервуарное сэмплирование и собачки

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

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

https://habr.com/ru/companies/ruvds/articles/916250/

Алгоритмы и Структуры данных

Проверяем написанную LLM библиотеку OAuth на уязвимости

Сегодня я решил изучить новую библиотеку Cloudflare OAuth provider, которую, судя по заявлениям, почти полностью написали при помощи LLM Claude компании Anthropic:

Эта библиотека (в том числе и документация по схеме) была по большей мере написана при помощи Claude — ИИ-модели компании Anthropic. Результаты работы Claude были тщательно проверены инженерами Cloudflare, уделившими особое внимание безопасности и соответствию стандартам. В исходный результат было внесено множество улучшений, в основном тоже при помощи промптов Claude (и с проверкой результатов). Промпты модели Claude и созданный ею код можно посмотреть в истории коммитов.

https://habr.com/ru/articles/916928/

Алгоритмы и Структуры данных

Думает ли искусственный интеллект о коте Шрёдингера? История о том, как я внедрял в алгоритм идею параллельных вселенных

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

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

https://habr.com/ru/articles/916524/

Алгоритмы и Структуры данных

Как я впервые столкнулся со связанными списками и не сдался

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

Сначала все шло неплохо: я успешно решал легкие задачки, используя обычные циклы (for, while). Редко когда надо было прям зависать и задумываться над решениями. Чаще, если даже решение было неверным, можно было в процессе искать ошибки и исправлять их. Но тут я наткнулся на задачу с пометкой "Easy" и названием "Merge Two Sorted Lists".

Прочитав название, я не обратил внимания на слово List и подумал, что это очередное задание на сортировку/конкатенацию массивов и в принципе обрадовался: “Щас решу в одну строку”, - подумал я. Однако компилятор остудил мой пыл.

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

https://habr.com/ru/articles/917218/

Алгоритмы и Структуры данных

Как я впервые столкнулся со связанными списками и не сдался

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

Сначала все шло неплохо: я успешно решал легкие задачки, используя обычные циклы (for, while). Редко когда надо было прям зависать и задумываться над решениями. Чаще, если даже решение было неверным, можно было в процессе искать ошибки и исправлять их. Но тут я наткнулся на задачу с пометкой "Easy" и названием "Merge Two Sorted Lists".

Прочитав название, я не обратил внимания на слово List и подумал, что это очередное задание на сортировку/конкатенацию массивов и в принципе обрадовался: “Щас решу в одну строку”, - подумал я. Однако компилятор остудил мой пыл.

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

https://habr.com/ru/articles/917218/

Алгоритмы и Структуры данных

Earcut на битах

Earcut - базовый, почти учебный алгоритм триангуляции, но при некоторых раскладах он обгоняет более "продвинутые" решения.

Я убедился в этом, тестируя iTriangle, который построен на монотонной триангуляции. Для замеров я использовал Earcut от MapBox - и C++ версию, и Rust-порт.

Результаты оказались предсказуемыми: Earcut стабильно выигрывал на простой геометрии и малом числе точек. Причём настолько уверенно, что я задумался: почему бы не встроить Earcut прямо в iTriangle?

Так и родилась идея: сделать мини-версию, заточенную только под одиночные контуры до 64 точек. С таким ограничением можно выжать максимум: обойтись без аллокаций, работать напрямую с битовой маской и попытаться обойти решение от MapBox.

https://habr.com/ru/articles/917688/

Алгоритмы и Структуры данных

10 лучших алгоритмов 20 века

Algos — греческое слово, означающее боль. Algor — латинское слово, означающее холод. Но ни то, ни другое не является корнем слова «алгоритм», которое происходит от имени Аль-Хорезми – арабского ученого девятого века – чья книга «al-jabr wa’l muqabalah» (Китаб аль-джебр ва-ль-мукабала) переросла современные учебники по алгебре для средней школы. Аль-Хорезми подчеркивал важность методических процедур для решения задач. Будь он сегодня здесь, то, несомненно, был бы впечатлен вершинами математического метода, названного в его честь.

Часть из лучших алгоритмов компьютерной эры были освещены в январско-февральском выпуске 2000 года журнала Computing in Science & Engineering — совместном издании Американского института физики и Компьютерного общества IEEE. Приглашенные редакторы Jack Dongarra (Джек Донгарра) из Университета Теннесси и Francis Sullivan (Фрэнсис Салливан) из Института оборонного анализа составили список из 10 алгоритмов, который они назвали «Top Ten Algorithms of the Century».

https://habr.com/ru/companies/timeweb/articles/666122/

Алгоритмы и Структуры данных

W-функция Ламберта и ее приложения

Математический анализ знает множество прекрасных функций с необычными свойствами. Среди них интегральные синус si(x)и логарифм li(x), также нельзя не отметить гамма-функцию \Gamma(x) или очень известную дзета-функцию Римана \zeta(s). Но сегодня я предлагаю читателю посмотреть на функцию W-Ламберта W(x).

https://habr.com/ru/articles/665634/

Алгоритмы и Структуры данных

Как устроены LLM-агенты: архитектура, планирование и инструменты

Всем привет! С вами Кирилл Филипенко, сисадмин из Selectel, и сегодня мы погрузимся в тему LLM-агентов. Сейчас об этих самых «агентах» кричат буквально из каждого утюга, поэтому пришло время наконец-то разобраться, что это такое, как они работают и с чем их, собственно, едят. Прыгайте под кат, будет интересно!

https://habr.com/ru/companies/selectel/articles/916798/

Алгоритмы и Структуры данных

Эвристические алгоритмы формирования портфеля инвестиций

Предположим, что у нас есть 100 млн. долларов, которые нужно вложить в несколько возможных инвестиций. Каждое из этих вложений имеет различную стоимость и различный ожидаемый доход. Мы должны решить, как потратить деньги, чтобы получить максимальную прибыль.
Задачи такого типа называются задачами формирования портфеля. У нас есть несколько позиций (инвестиций), которые должны поместиться в портфель фиксированного размера (100 млн. долларов). Каждая позиция имеет свою прибыльность. Необходимо найти набор позиций, которые помещаются в портфель и дают максимальную прибыль.
Многие из вас скажут, что никакие эвристики тут не нужны, и что вполне можно обойтись полным перебором. Другие заявят, что и полный перебор не нужен, ведь существует метод ветвей и границ. Но как быть, если количество возможных инвестиций 65? Полное дерево решений содержит более 7*10^19 узлов. Предположим, что метод ветвей и границ перебирает десятую часть процента этих узлов, а компьютер проверяет миллион узлов в секунду. В этих условиях для решения задачи потребовалось бы более 2 млн. лет. Именно для таких сложных задач и используются эвристики. Если вам интересно, милости прошу под кат.

https://habr.com/ru/articles/108961/

Алгоритмы и Структуры данных

«Живые графы» — выращивание графов на клеточных автоматах с примерами на Silverlight

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

Да и простого любопытствующего обывателя, не отягощённого подробностями органической химии, подобные вопросы не обходят стороной.

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

https://habr.com/ru/articles/107387/

Алгоритмы и Структуры данных