Головоломка на тему раскраски графа
Попробуйте раскрасить симметричный граф в минимальное количество цветов так, чтобы соседние вершины были разных цветов.
Подробнее здесь.
Гипотеза о вычислительной сложности алгоритмов.
Пусть есть задача (проблема) размера 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 раз!
Большинство университетских профессоров в мире - ленивые. Как выдумали в 1970-е годы преподавать дизайн конечных автоматов примером FSM для светофора (Traffic Light Controller FSM), так и тянут эту бодягу и по 21-му веку. При том, что современные дизайнеры чипов не светофоры конструируют, а ускорители тренировки нейросетей.
Короче мы на Школе Синтеза Цифровых Схем решили преломить эту дурную традицию (которая встречается от Южной Америки до Средней Азии и Филиппин, с провинциальными вузами в Штатах включительно) и ввести в преподавание современный хардкор. То есть сделать домашку с конструированием FSM для управления блоками FPU выдранными из современного реального открытого RISC-V процессора.
По сложности начинается не сложнее светофора, зато куда ближе к реальности и можно сделать миллион вариантов домашек и экзаменов, чтобы студенты друг у друга не списывали один и тот же светофор.
Пример домашки: сконструировать FSM (а потом и конвейер) для вычисления такого-то ряда Маклорена (для синуса, экспоненты итд), имея в наличии N блоков умножения, M сложения и R деления с плавающей точкой - с разными латентностями.
При обсуждении такой домашки возник вопрос нужно ли для операций с плавающей точкой устанавливать флаг error для нечисел и бесконечностей. Конечно нужно, потому что это удобный повод рассказать про концепцию NaN и Infinity. Полез в википедию и в шоке обнаружил, что статья IEEE_754 на русском отсутствует, хотя есть на украинском. Это непорядок, нужно срочно поправить!
Ближайшие события
Тестировал всякое для ATARI XL/XE и написал небольшую демку в 106 Байт.
Чтобы понимать куда именно смотреть - тут экран 48х24, то есть 1152 байта, но в ОЗУ весь экран представлен всего 48 байтами, еще 78 байт (кто захочет посчитать 48+78=126, тут просто кодом реализованы однотипные строки) для программирования видеочипа, которому объяснено, что каждая строка на экране смотрит на одну и ту же часть ОЗУ, так мы заполняем весь экран. Для получения нестандартного узора используется 8 байт и перепрограммирование таблицы символов. Рисунок изначально подбирается так чтобы формировался равномерный узор. Для плавности движения используется VSYNC, анимация реализована битовым сдвигом.
.include "atari.asm"
*= $3000
lda #48
?copy
sta screen-1, y
dey
bpl ?copy
; ldy #$00
iny
?copydl
lda #$42
sta dlist2, y
iny
lda #<screen
sta dlist2, y
iny
lda #>screen
sta dlist2, y
iny
cpy #72
bne ?copydl
lda #>font_data
sta CHBAS
lda #$23
sta SDMCTL
lda #<dlist
sta SDLSTL
lda #>dlist
sta SDLSTL+1
?main
ldx #1
?start
lda RTCLOK+2
?wait
cmp RTCLOK+2
beq ?wait
dex
bpl ?start
?ring
lda font_data, x
asl
adc #00
sta font_data, x
inx
cpx #08
bne ?ring
beq ?main
dlist
.byte $70, $70, $70
dlist2
*= dlist2+72
.byte $41, <dlist, >dlist
screen
*= $7400
font_data
.byte ~11000011
.byte ~10011001
.byte ~00100100
.byte ~01000010
.byte ~01000010
.byte ~00100100
.byte ~10011001
.byte ~11000011upd: -1 байт от @vadimr
upd: -1
Продолжаем разбираться с алгоритмами DFS и BFS.
В прошлый раз мы знакомились с тем, как работают алгоритмы поиска по N-деревьям. А в новом ролике Артур Михайлов, head of iOS в Технократии, показывает, как применять эти алгоритмы на практике.
Полезно как для тех, кто готовится к собеседованиям, так и тем, кто применяет алгоритмы в работе.
Интересный механизм генерации экрана для ATARI XL/XE. Из-за особенности работы видеочипа мы можем для каждой строки сканирования указать видеорежим и то, с какого участка памяти брать данные для строки.
На картинке можно увидеть зоны хода луча, когда он выключен, это Horizontal Retrace и Vertical Retrace, соответственно интервал между строками и между следующими кадрами. В эти интервалы можно выполнять код, который будет делать что-то интересное для нас. Тут будем переключать таблицы символов. Зачем это нужно? Есть текстовый режим графики 40х24 с пятью цветами, который можно использовать для игр, но мы сильно ограничены в рисовании контента динамически, так как это по сути спрайты ориентированные по знакоместам. Символы в XL/XE представлены таблицей в 128 штук (1024 байт) и мы можем рисовать изображение внутри кодовой таблицы, а потом выводить символы в виде текста. Кажется, что 128 символов не хватит чтобы заполнить экран в 40х24=960 байт, вот тут мы и получаем профит.
Новый экран будет (условно) выглядеть так:
ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890!@#$И так 24 раза. После каждых 8 строк сканирования (1 знакоместо) мы сдвигаем кодовую таблицу на 40*8 байт, где уже готово изображение для второй порции строк и т.д. То есть рисуем в памяти где участок для кодовой таблицы, а видеочип рисует их как символы. Мы получаем динамическую генерацию экрана и 5 цветов.
Когда я такое придумал, то думал, что это изобретение века, но потом нашёл информацию о таком способе: Источник 1, источник 2.
Разбираемся, как работают алгоритмы 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) не пробегая массив. Улучшение - теперь время пропорционально квадрату.
Можно решить и за "линейное" время - т.е. пропорциональное размеру массива без всякой степени. Когда я сообразил, то сказал "да это же старая задачка на новый лад". Попробуйте - вдруг пригодится на собесе :)