Алгоритмы *

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

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

Интересно, что, как и «обычных» магических квадратов, возможно бесчисленное множество вариантов МКП. В общем случае для трёх чисел 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 регулятора

Обновление и ускорение моего GA для FlappyBird!

Теперь все птицы запускаются одновременно, поэтому обучение ускорилось с ~3-5 часов до 5-10 минут при запуске на CPU, то есть в 50 раз!

https://github.com/LanskoyKirill/GenNumPy.git

Большинство университетских профессоров в мире - ленивые. Как выдумали в 1970-е годы преподавать дизайн конечных автоматов примером FSM для светофора (Traffic Light Controller FSM), так и тянут эту бодягу и по 21-му веку. При том, что современные дизайнеры чипов не светофоры конструируют, а ускорители тренировки нейросетей.

Короче мы на Школе Синтеза Цифровых Схем решили преломить эту дурную традицию (которая встречается от Южной Америки до Средней Азии и Филиппин, с провинциальными вузами в Штатах включительно) и ввести в преподавание современный хардкор. То есть сделать домашку с конструированием FSM для управления блоками FPU выдранными из современного реального открытого RISC-V процессора.

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

Пример домашки: сконструировать FSM (а потом и конвейер) для вычисления такого-то ряда Маклорена (для синуса, экспоненты итд), имея в наличии N блоков умножения, M сложения и R деления с плавающей точкой - с разными латентностями.

При обсуждении такой домашки возник вопрос нужно ли для операций с плавающей точкой устанавливать флаг error для нечисел и бесконечностей. Конечно нужно, потому что это удобный повод рассказать про концепцию NaN и Infinity. Полез в википедию и в шоке обнаружил, что статья IEEE_754 на русском отсутствует, хотя есть на украинском. Это непорядок, нужно срочно поправить!

Продолжаем разбираться с алгоритмами DFS и BFS.

В прошлый раз мы знакомились с тем, как работают алгоритмы поиска по N-деревьям. А в новом ролике Артур Михайлов, head of iOS в Технократии, показывает, как применять эти алгоритмы на практике.

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

Разбираемся, как работают алгоритмы BFS и DFS. Конечно, в «Алгоритмической качалке»

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

Так что знания максимально полезные. Переходите по ссылке и не забывайте поставить лайк и написать комментарий — это очень помогает нам продвигать контент.

Напишем код для управления пушкой, сбивающей корабли пришельцев!

Планирую несколько постов о разных технических решениях на моём (теперь опенсорсном!) сайте CodeAbbey. Но начать хочется с чего‑нибудь весёлого — поэтому начнем не по порядку, а с краткого рассказа о сравнительно новом типе задач.

Упражнения на сайте устроены так, что решать можно на любом языке — отправляем код решения и результат вычислений — но проверяется только результат (а код просто чтобы не потерялся). Но хотелось добавить и какой‑нибудь «интерактив» — и один из типов интерактивных задач — это игры, для которых пользователь пишет код выполняемый «с двух сторон»:

• в браузере, чтобы игру и решение пользователя тут же визуализировать

• на сервере, чтобы проверить насколько хорошо код пользователя работает

Первой идеей приходит сделать такие задачи на JavaScript — но т.к. сайт учебный, популярен здесь Python (больше 40% используют его). Пробовал реализации Питона на JS (Skulpt, позже Brython) — но у них есть недостатки... Короче, остановился на Lua — с одной стороны она похожа на Питон, но даже попроще, так что любой освоит в нужном для задачи объёме за 10–15 минут (есть инструкция). С другой — я её смог скомпилировать в JS (с помощью EMCC — вот на github).

Пример кода который пытается сбивать пришельцев «не глядя» — занимает 10–12 строк — он есть в тексте задачи. Есть и предыдущая задача попроще — определять попадание в пришельца. Было бы интересно услышать отзыв того, кто попробует решать не имея опыта в Lua!

Задачка от Т-Банка, тоже с собеседования - по сравнению с предыдущей что я показывал, от Яндекса, эта кажется ещё менее актуальной для рекрутинга в энтерпрайз - но я просто порадовался что смог её решить в live-coding режиме. Судите сами - хотели бы вы подобное встретить на собесе или нет :)))

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

• разовый билет стоит 5 копеек

• безлимитный проездной на 2 дня - 18 копеек

• проездной на 3 дня с лимитом 6 поездок - 22 копейки

Входные данные - массив - сколько поездок пришлось на каждый день в месяце, например:

2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 3 4

(здесь ответ 51)

Как это решается? Если вы знаете про "динамическое программирование" (ДП) то наверное уже поняли что задача об этом - поэтому я и удивился встретив такую задачу на собесе - скорее всего нам это не понадобится в энтерпрайзе (хотя в олимпиадных задачках популярно). Если не знаете про ДП, представьте рекурсию - вы пробуете в цикле каждый из трёх типов билетов, ездите сколько он позволяет - и дальше снова вызываете эту функцию для оставшихся поездок. Просто с рекурсией вы не дождётесь окончания работы, но с "мемоизацией" получите то же ДП "навывоворот". Я возился минут 30, но повтороив задачу у себя на сайте увидел что друзья решают аж в 3-4 строчки (ну, на питоне с @cache).

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

В массиве целых чисел нужно найти фрагмент с заданной суммой.

Например, дан массив a = [4, 3, -8, 4, -1, 12, -5, 2] и целевая сумма 5 - тогда ответом будет фрагмент начиная с 3 и заканчивая -5, то есть в синтаксисе Питона sum(a[1:7]) = 5

В чем тут сложность? Сложность во "временной сложности" - требуется чтобы на массиве из миллиона чисел вычисление не занимало минуты. Поэтому наивный вариант не годится:

target = 5
for i in range(len(a)):
    for j in range(i+1, len(a)+1):
        if sum(a[i:j]) == target:
            print(i, j)

Здесь два вложенных цикла - каждый в среднем совершает число итераций сравнимое с длиной массива. Но функция sum(...) внутри тоже бежит по массиву - итого время выполнения пропорционально длине массива в кубе O(N*N*N)

Одно из усовершенствований заключается в том чтобы построить второй массив, в котором хранить сумму от начала массива до i-го элемента. Это позволит считать sum(i, j) не пробегая массив. Улучшение - теперь время пропорционально квадрату.

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

ZPAQ - консольный append-only архиватор, способный эффективно снапшотить целые директории с тысячами файлов и/или BLOBы в десятки ГБ (хоть с целыми ФС внутри) в один единственный файл. В процессе архивирования используется дедупликация на уровне фрагментов данных, сохраняющая только уникальные последовательности, а сжатие осуществляется адаптивным алгоритмом, который подстраивается под характер самих данных. Поддержка шифрования тоже имеется.

Внутри архива могут содержаться тысячи снапшотов, любой из них может быть извлечен, новые - всегда дописываются только в конец, а удалять из такого архива ничего нельзя. Можно сказать, что zpaq это такой своеобразный single-file git репозиторий для бинарных данных, стремящийся к максимальной компрессии.

Пример (не мой):

~7GB of Thunderbird mbox become ~6MB (!) in ~4 minutes.

Подход append-only архивирования zpaq, в сочетании с rsync --append дает возможность вывести инкрементальное резервное копирование на новый уровень (даже для такого простого в использовании инструмента) и приблизиться к теоретическому пределу эффективности сжатия на реальных задачах, по сравнению с классическими архивами.

Разработка не новая, оригинальный проект zpaq более не развивается, но присутствует в некоторых дистрибутивах. А также существует вполне живой форк, совместимость формата архива с оригинальным zpaq сохранена: https://github.com/fcorbelli/zpaqfranz

Tg: lomalkin_log