Алгоритмы *

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

В чем сложность?

Главная трудность – "пропасть" между миром четких картинок (на которых обычно учатся модели) и миром размытых кадров. Алгоритмы плохо переносят знания из одного "мира" в другой.

Как с этим бороться?

В нашей новой (и первой) статье мы подробно разобрали ключевые подходы к решению такой проблемы в контексте распознавания лиц:

1. "Дорисовка" деталей: специальные нейросети пытаются увеличить и улучшить размытое изображение перед анализом. Работает, но есть риск "придумать" несуществующие детали.

2. Адаптация модели: как "подружить" алгоритм с плохим качеством?

• Трюки с данными: искусственно ухудшаем хорошие изображения при обучении (сжатие, шум), чтобы модель привыкла к помехам.

• Дообучение: учим модель на реальных размытых данных. Важно делать это аккуратно, чтобы она не забыла, как работать с четкими изображениями. Помогают методы вроде LoRA (дообучение только маленькой части сети).

• "Учитель" для "ученика": мощная модель, видящая четкие картинки, учит компактную модель работать с размытыми, передавая свои "знания".

3. PETALface: новый подход, который динамически комбинирует разные "настройки" (LoRA-адаптеры) в модели в зависимости от качества конкретного входящего кадра. Перспективно, но требует дальнейшего изучения.

Хотите разобраться глубже?

В статье мы подробно разбираем плюсы и минусы каждого подхода, рассматриваем специализированные датасеты (TinyFace, BRIAR) и анализируем нюансы свежего метода PETALface.

Сталкивались ли вы с проблемой низкого разрешения в своих проектах? Какие методы оказались эффективными? Делитесь опытом в комментариях!

Представлен бесплатный ресурс GoalKicker с книгами по IT-тематике от проджект-менеджмента и UX-райтинга до тем по алгоритмам, структурам данным и низкоуровневым языкам, включая ОС и архитектуру компьютеров,.Bash, UNIX, Linux, гайды по работе с командной строкой и прочими тулзами типа Vim, книги по самым востребованным на рынке языкам программирования, всё о работе с базами данных от основ до построения связанных таблиц и интеграции их в системы.

Эффективные хеш-таблицы на Go

В Go нет недостатка хеш-таблиц. Вы всегда можете использовать встроенную map[Key]Val, с ошеломительной скоростью обладающую непревзойденным удобством! А изобилие типов Key, разрешенных к использованию, способно довести до изумления!

Вот только ни указатель, ни слайс не подходят... Невозможно подсунуть свои операции (равенства и хеширования). Но хоть со скоростью все хорошо! (извините, не удержался)

Итого, мне пришлось написать HashMap[K, V any], закрывающую проблемы.

------------------8<------------------

В это трудно поверить, но:

• Без резервирования памяти (конфигурация R0), map[uint64]uint64 работает в 1.93 раза медленнее UintMap! И производит в 5.64 раза больше мусора!!

• А с полным резервированием (R1), в 1.72 раза медленнее! И аж в 16.5 раз больше мусора!!!

Вдумайтесь! На коленке написанная хеш-таблица для целых чисел UintMap почти в два раза обгоняет ЖУТКО оптимизированную нативную map[uint64]uint64!! И существенно менее мусорит!!!

Но раз трудно поверить, то давайте проверим:

func MyUintMap() {
    const N = umN

//R0|    um := lib.NewUintMap(0)
    um := lib.NewUintMap(N) //R1|

    for i := uint64(0); i < N; i++ {
        um.Findsert(i, i+N)
    }
    lib.Assert(um.Size() == N)

    cnt := 0
    for i := uint64(0); i < N; i++ {
        if *um.Val(um.Find(i)) == i+N {
            cnt++
        }

        if um.Find(i+N) == -1 {
            cnt++
        }
    }
    lib.Assert(cnt == N*2)

    for i := uint64(0); i < N; i++ {
        um.Delete(i)
    }
    lib.Assert(um.Size() == 0)
}

func GoUintMap() {
    const N = umN

//R0|    m := make(map[uint64]uint64)
    m := make(map[uint64]uint64, N) //R1|

    for i := uint64(0); i < N; i++ {
        m[i] = i + N
    }
    lib.Assert(len(m) == N)

    cnt := 0
    for i := uint64(0); i < N; i++ {
        if m[i] == i+N {
            cnt++
        }

        if _, ok := m[i+N]; !ok {
            cnt++
        }
    }
    lib.Assert(cnt == N*2)

    for i := uint64(0); i < N; i++ {
        delete(m, i)
    }
    lib.Assert(len(m) == 0)
}

Здесь всего-то лишь вставка, два поиска и удаление. Запустите go test -bench=UintMap -benchmem и увидите сами. Вот только можно ли ругать Google за неэффективный map[uint64]uint64?

------------------8<------------------

Итоги?

1. Смело берите HashMap[K, V any] для слайсов и указателей!

2. Немного оптимизированная BytesMap -- лучший выбор для []byte.

3. Интересно оптимизированная UintMap -- это выбор для целых чисел. Разберитесь, что там "не так", и используйте за основу.

И как всегда, исходный код, подробности и пару неудачных шуток вы можете найти в моей статье https://ders.by/go/hashmap/hashmap.html

🔒 Ваш сервис готов к "Кузнечику"?

У нас в РФ есть ГОСТ 34.12-2018, в котором описана реализация этого алгоритма и еще одного "Магма" - это импортозамещение международного AES.

Как думаете, как скоро дадут приказ переходить на данные алгоритмы?

Задача о Тирексе, который строил сеть наугад

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

Условие

Тирекс построил собственный дата-центр и теперь хочет объединить 15 серверов в одну сеть. Он не задумывается о надежности топологии, поэтому хочет использовать минимально возможное количество кабелей — 14. 

Задача

Тирекс случайным образом проложил 14 проводов. С какой вероятностью все серверы будут соединены в одну сеть? 

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

Предлагайте свое решение в комментариях. А правильный ответ можно подсмотреть в Академии Selectel.

Представлена игра 2048 на Bash в терминале с 64 битами состояния.

«Поделитесь своим игровым состоянием с друзьями, просто отправив им число! Если переменная $STATE env не установлена, она генерирует новое случайное начальное число. В противном случае состояние доски и все будущие созданные ячейки будут детерминированными»,‑ пояснил автор проекта.

15 лет назад я думал что образование в области компьютерной архитектуры поломано только в России, а на Западе с этим все хорошо. Что значит "поломано"? Студент может поговорить про суперскалярные процессоры и многоядерные кластеры, но не может ничего спроектировать.

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

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

И я выдвинул теорию, что им профессор дает готовый код процессоров посимулировать и посинтезировать, а сами они на верилоге ничего не пишут. То есть у меня в голове образовалась модель такого студента, своего рода теоретический Бозон Хиггса, который умозрительно представили задолго до обнаружения.

И вот сегодня я такой Бозон Хиггса засек на LinkedIn. Выпускник этого самого вуза X написал пост, как он изучал учебник Хеннесси-Паттерсона. Он показал фото листка бумаги, испещренного заметками и диаграммами. Он просто сидел, читал по частям учебник и делал такие заметки.

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

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

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

Для Бозона Хиггса эта идея была в новинку. А между тем такой же подход нужно делать и с курсами по компиляторам, и ядрам OS.

Хотя зачем я все это говорю. Сейчас грянет LLM и наша цивилизация исчезнет.

Генерация последовательностей случайных чисел с помощью DRAM — возможно ли это? Проверим с помощью RISC-V

На основе DRAM мы создали модель одноканального источника шума, который возвращает один случайный бит за один условный такт. Память разбита на два региона, которые не пересекаются. Первый отвечает за инициализацию одноканального сигнатурного анализатора (ОСА), который инициализирует второй подобный анализатор. Затем мы сможем взять другой регион памяти и заново инициализировать первый ОСА, что абсолютно случайным образом изменит выход второго ОСА. Такая схема позволит не перезагружать память после каждой генерации числовой последовательности — ведь в реальных проектах это, как правило, невозможно. 

Далее мы направляем данные из DRAM PUF в два подмодуля — постобработки, а также тестирования, анализа и оценки качества данных. Первый частично запускается на «железе», второй — на собранных данных на машине хоста.

Для постобработки мы протестировали шесть комбинаций. Последняя нам кажется наиболее перспективной:

• сырые данные,

• чистый корректор фон Неймана,

• одноканальный сигнатурный анализатор,

• чистый корректор фон Неймана + одноканальный сигнатурный анализатор,

• одноканальный сигнатурный анализатор + чистый корректор фон Неймана,

• многоканальный сигнатурный анализатор (МСА).

Зимняя школа RISC-V дала начало множеству интересных проектов. В отдельной статье мы рассказали об одном из них, где команда из БГУИР проверила гипотезу о наличии PUF в динамической памяти и создала модель одноканального источника шума. А затем реализовала постобработку и тестирование, измерила производительность генератора и оптимизировала код.

Магические квадраты с произведением

 О магических квадратах известно, наверное, всё. А возможны ли магические квадраты, в которых равны не суммы значений в строках, столбцах и на диагоналях, а их произведения? Оказывается – возможны. В дальнейшем буду называть такие квадраты «магическими квадратами с произведением» (сокращённо – МКП).

Интересно, что, как и «обычных» магических квадратов, возможно бесчисленное множество вариантов МКП. В общем случае для трёх чисел a, b и n МКП размером 3 × 3 имеют вид:

При этом a ≠ b, a ≠ 1, b ≠ 1, a ≠ b², b ≠ a²,

Интересно, что любой МКП размером 3 × 3 может быть основой для формирования бóльших МКП. Одно из возможных решений заключается в том, чтобы поместить такой  квадрат в центр квадрата 5 × 5 и потом подобрать такие остальные числа, чтобы они соответствовали свойствам МКП. Это означает, что МКП являются также так называемыми «рамочными магическими квадратами» – магическими квадратами, которые сохраняют свое магическое свойство, если в них отбросить окаймляющие «полосы» в две клетки.

После комментариев  @miksoft я удалю сей свой пост

Головоломка на тему раскраски графа

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

Подробнее здесь.

Гипотеза о вычислительной сложности алгоритмов.

Пусть есть задача (проблема) размера N. Пусть также существует (известен) алгоритм (метод, способ) решить эту задачу за время O(N*N), и существует способ проверки корректности решения за время O(N).
Тогда существует алгоритм решения этой задачи за время O(N*logN).

Пример 1. Сортировка массивов. Существует алгоритм сортировки за время O(N*N). Корректность работы алгоритма сортировки можно проверить за время O(N). Следовательно, существует алгоритм сортировки за время O(N*logN).

Пример 2. Перемножение длинных (больших) целых чисел (миллионы цифр). Их можно перемножить за время O(N*N). Результат можно проверить за время O(N) с некоторой заранее заданной достоверностью, например, 0,999999... . Следовательно, существует алгоритм перемножения чисел за время O(N*logN).

Есть ли контрпримеры? Ищу их.

Из комментариев к статье о гитарном тюнере выяснилось, что многие НЕ верят, что можно вычислять ОЧЕНЬ ТОЧНО частоту синусоидального сигнала по очень небольшому количеству отсчетов не равному степени двойки для FFT и намного точнее чем FFT на том же количестве отсчетов и том же временном интервале накопления данных. Например, ошибка определения частоты может быть 0.05 Гц при небольшом количестве отсчетов на интервале 0.1 сек (FFT дало бы ошибку в 10 Гц = 1/0.1 сек) . Однако, кажется, это возможно. Вот ссылка на мой код на Python (>>исходник) (в телеграм) Коллеги, прошу проверить код, возможно я где-то ошибся.

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

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

Часть «мысленное противопоставление» (WOO: желание, результат, препятствие) помогает зарядить людей энергией на пути к цели и выявить препятствия, стоящие на этом пути.

Другая часть — «намерения по реализации» (P: план) соединяет каждое препятствие («если») с конкретным действием («тогда») и упрощает контроль над чувствами. Вот пример того, как можно использовать метод WOOP:

• Желание: «Я хочу быть более терпеливым со своими детьми, когда они меня раздражают»;

• Результат: «У меня будут лучшие отношения с ними, и я стану лучшим родителем»;

• Препятствие: «Когда они называют друг друга глупыми, я иногда выхожу из себя. Я вырос в атмосфере, где оскорбления были нормой, и я очень остро на это реагирую»;

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

За последние 20 лет несколько исследований подтвердили действенность методики WOOP и её долгосрочное, устойчивое влияние на жизнь людей. Использование методика приводит к тому, что студенты лучше успевают в учёбе, лучше справляются с негативными чувствами, лучше питаются и практикуют физические нагрузки. А люди с депрессией лучше заботятся о себе.

Схема использования WOOP для решения эмоциональной проблемы, с которой многие люди постоянно сталкиваются:

W = Желание (написать важное для вас желание — сложное, но выполнимое);

О = Результат (Что вы почувствуете, когда добьетесь этого?);

О = Препятствие (Что является препятствием?);

П = План (Какие действия вы предпримете, столкнувшись с этим препятствием?);

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

«Если это кажется невозможным, просто вспомните, что мы делаем много вещей, которые поначалу даются нелегко, но при достаточном планировании и практике они могут стать почти автоматическими», — подытожил Кросс.

Увеличиваем точность БПФ. Изобретаем алгоритм для Гитарного Тюнера и оценки точности пения нот вокалистами. Это анонс статьи в разработке. Подписывайтесь на мой профиль на Хабре, чтобы не пропустить статью. Или присоединяйтесь к моей "телеге". Кратко: точности и быстродействия классического БПФ не хватает для точной и быстрой оценки частоты сигнала. Ищем и изучаем другие алгоритмы. Да, я знаю много китайских маленьких приборчиков и прищепок на гитару с весьма точной настройкой, но интересно разобраться как это достигается. Напишите в комментариях какие более точные алгоритмы определения частоты сигнала вы знаете? (я уже нашел несколько, сейчас тестирую, смотрите изображение ниже) На графиках амплитудный спектр суммы 7 синусоид с близкими частотами, интервал наблюдения 0.1 секунды, частота дискретизации 22050 Гц, как видите классический БПФ ошибается и даже не все синусы видит, а альтернатива дает меньшую ошибку и все синусы увидела. Вертикальные красные линии это реально находящиеся в тестовом сигнале синусоиды. Их частоты написаны над верхней границей графиков.

Нашел интересное видео - визуализация всех основных алгоритмов сортировки на Python

Забавно, но софт написан не на matplotlib, a на PyGame! https://github.com/Ctoic/Algorithm-Visualizer-Using-pygame

Я тоже попробовал графики рисовать на PyGame (рисую звук в реальном времени, осцилограф): https://habr.com/ru/articles/879786/

Слева сидит Лёша

Он не смог решить задачу и был отчислен из вуза. Аппетита нет, шаверма остывает. А ведь нужно было просто написать программу, которая построит симметричную матрицу размерности NxN (1 < N <= 100).

Может, у вас получится помочь Алексею решить задачу? Тогда переходите в Академию Selectel.

Principles and Practice of Programming Languages 

Новый зверь среди академических учебников.

Выложен втихую, доступен свободно, нигде не анонсировался.

Для точности ваших математических библиотек принимайте «Ульп». «Ульп» — и тесты не страшны!

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

Для этого достаточно договориться о единице измерения. Расстояние между соседними числами обозначается как 1 ульп (ulp — unit in the last place). Относительно него и будем оценивать погрешность вычисления математической функции. Поделим расстояние от результата до эталона на то, что является одним ульпом — то есть на расстояние от эталона до соседнего числа той же точности. Стандарт libm требует, чтобы ошибка не превышала 0,5 ульпа с учетом округления. 

Мы договорились о единицах измерения. Но остался еще один вопрос: с чем же мы сравниваем результаты? Откуда брать эталон в квазибесконечной точности? Здесь помогут системы компьютерной алгебры — прикладные программы для символьных вычислений и числовых операций произвольной точности.

Из таких систем ученые особенно любят Maple или Scilab, инженеры — Mathcad или Matlab, а разработчики — Sollya, поскольку эта библиотека имеет удобный C-интерфейс и ее можно вызывать прямо из тестов libm.

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

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

Читать статью →

Ещё раз о количестве способов набрать сдачу в n рублей из заданного набора монет/купюр

 Вот известная задача: «Имеется неограниченное количество монет достоинством 1, 2, 5 и 10 рублей. Определить, сколькими способами можно ими выдать сдачу в n рублей».

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

Возможно, эта идея будет полезна в других задачах.

Итак.

При n = 7 все варианты следующие:

1 + 1 + 1 + 1 + 1 + 1 + 1

1 + 1 + 1 + 1 + 1 + 2

1 + 1 + 1 + 2 + 2

1 + 2 + 2 + 2

1 + 1 + 5

2 + 5

 Среди них можно выделить те, в которых минимальным слагаемым является 1. Их – 5. В оставшемся шестом варианте минимальным слагаемым является 2. Вариантов, в которых минимальным слагаемым является 5 и 10, в данном случае нет.

При n = 10 все варианты следующие (без знака +):

1111111111, 111111112, 11111122, 1111222, 112222, 111115, 11125, 1225, 22222, 55, 10,

то есть

количество вариантов с минимальным слагаемым 1 равно 8;

количество вариантов с минимальным слагаемым 2 равно 1;

количество вариантов с минимальным слагаемым 5 равно 1;

количество вариантов с минимальным слагаемым 10 равно 1.

 Подумав (😊), можем сказать, что при n = 11:

· количество вариантов с минимальным слагаемым 1 будет таким же, как общее число всех вариантов для n = 10 (так как разность 11 – 10 не превышает 1);

· количество вариантов с минимальным слагаемым 2 будет равно сумме количеств с минимальными слагаемыми 2, 5 и 10 для n = 9 (так как разность 11 – 9 не превышает 2);

· количество вариантов с минимальным слагаемым 5 будет равно сумме количеств с минимальными слагаемыми 5 и 10 для n = 6  (так как разность 11 – 6 не превышает 5);

· количество вариантов с минимальным слагаемым 10 будет равно такому же количеству для n = 1 (так как разность 11 – 1 не превышает 10).

 Приведённые рекуррентные зависимости применимы для всех значений n, но с некоторыми исключениями – при n = 1 количество вариантов с минимальным слагаемым 1, при n = 2 количество вариантов с минимальным слагаемым 2, при n = 5 количество вариантов с минимальным слагаемым 5 и при n = 10 количество вариантов с минимальным слагаемым 10 будет равно 1 (в перечисленных случаях соответствующие слагаемые появляются впервые).

Допустим, что максимальное значение n равно 99.

В программе, реализующей описанную идею для такого случая, можно использовать двумерный массив из 109 строк и пяти столбцов (10 начальных строк массива являются условными для рекуррентного расчёта значений при n = 1..99).

Вся программа на так называемом «школьном алгоритмическом языке» (система программирования КуМир):

алг
нач цел таб м[-9:99, 1:5], цел n, j
  | Нули, в том числе в фиктивных строках   

нц для n от -9 до 99
    нц для j от 1 до 5
      м[n, j] := 0
    кц
  кц

  | Расчёты
  нц для n от 1 до 99
    если n = 1
      то
        м[n, 1] := 1
      иначе | Рекуррентная зависимость
        м[n, 1] := м[n - 1, 5]
    все
    если n = 2
      то
        м[n, 2] := 1       иначе
        м[n, 2] := м[n - 2, 2] + м[n - 2, 3] + м[n - 2, 4]
    все
    если n = 5
      то
        м[n, 3] := 1
      иначе
        м[n, 3] := м[n - 5, 3] + м[n - 5, 4]
    все
    если n = 10
      то
        м[n, 4] := 1
      иначе
        м[n, 4] := м[n - 10, 4]
    все
    | Последний столбец
    м[n, 5] := м[n, 1] + м[n, 2] + м[n, 3] + м[n, 4]    
  кц
  | Вывод всех значений
  нц для n от 1 до 99
    вывод нс, n, " | ", м[n, 5]
  кц
кон

 Конечно, вместо массива из 109 строк можно использовать 10-строковый массив и после расчёта значений для очередной строки переписать массив, отбросив «хвостовую» строку.

 Спасибо.

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

• Время дискретизации не всегда может оказаться фиксированным

• проблемы с дискретным дифференцированием

• проблемы с дискретным интегрированием

Попробуем посмотреть, как обстоят дела с решением этих проблем при реализации в доступных open source проектах на гитхабе.

Топ 16 проектов на гитхабе с заявленной реализацией PID алгоритма

Топ выбирался по запросу PID в поиске гитхаба с опцией "best match"

Из 16 проектов 4 являются откровенным мусором, студенческой липой, иначе трудно объяснить такое количество звезд и форков.

GyverPID добавлена по причине относительно широкой известности в аудитории отечественных ардуинщиков.

Буду благодарен, если в комментах укажут другие достойные реализации PID регулятора