Все потоки
Поиск
Написать публикацию
Обновить
205.15

Алгоритмы *

Все об алгоритмах

Сначала показывать
Порог рейтинга
Уровень сложности

Построение при помощи циркуля и линейки, только… без циркуля

Время на прочтение2 мин
Количество просмотров13K
Все мы знакомы из школьной программы с построениями при помощи циркуля и линейки. А что будет, если вдруг циркуль затеряется? Можно ли при помощи одной линейки строить ещё что-то нетривиальное? Предлагаю вашему вниманию задачу, решение которой принесло мне немало приятных часов. Задача со звёздочкой, поэтому не расстраивайтесь, если сходу решение не найдёте. Хотя один мой знакомый справился за пять минут, думаю, что это скорее исключение из правил.

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



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

Читать дальше →

Что такое алгоритм! Часть 3+1 «Математика»

Время на прочтение11 мин
Количество просмотров8.5K

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


Title

Читать дальше →

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

Время на прочтение3 мин
Количество просмотров20K

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

Пошагово и с картинками

3. Частотные характеристики звеньев и систем автоматического регулирования. 3.6 Инерционно-дифференцирующее звено

Время на прочтение5 мин
Количество просмотров8.6K

Лекции по курсу «Управление Техническими Системами» читает Козлов Олег Степанович на кафедре «Ядерные реакторы и энергетические установки» факультета «Энергомашиностроения» МГТУ им. Н.Э. Баумана. За что ему огромная благодарность!

Данные лекции готовятся к публикации в виде книги, а поскольку здесь есть специалисты по ТАУ, студенты и просто интересующиеся предметом, то любая критика приветствуется. В доугих сериях:

1. Введение в теорию автоматического управления.
2. Математическое описание систем автоматического управления 2.1 — 2.32.3 — 2.82.9 — 2.13.
3. ЧАСТОТНЫЕ ХАРАКТЕРИСТИКИ ЗВЕНЬЕВ И СИСТЕМ АВТОМАТИЧЕСКОГО УПРАВЛЕНИЯ (РЕГУЛИРОВАНИЯ).
3.1. Амплитудно-фазовая частотная характеристика: годограф, АФЧХ, ЛАХ, ФЧХ.
3.2. Типовые звенья систем автоматического управления (регулирования). Классификация типовых звеньев. Простейшие типовые звенья.
3.3. Апериодическое звено 1–го порядка (инерционное звено). На примере входной камеры ядерного реактора.
3.4. Апериодическое звено 2-го порядка.
3.5. Колебательное звено.
3.7. Форсирующие звено.

Тема сегодняшней статьи: 3.6. Инерционно-дифференцирующее звено

Будет как всегда интересно познавательно и жестко.

Читать далее

Как работает рендеринг в 3D-играх: сглаживание

Время на прочтение13 мин
Количество просмотров27K

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

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

Читать далее

Вебинар от Яндекс.Практикума «Открытое алгоритмическое собеседование»: 12 мая в 19.30

Время на прочтение1 мин
Количество просмотров3.8K
В интернете можно найти множество статей, в которых написано, что нужно делать, чтобы успешно пройти собеседование. Но это всё теория, 12 мая Яндекс.Практикум проведёт самое настоящее, непостановочное алгоритмическое собеседование так, как его проводят в крупных компаниях.

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

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


Читать дальше →

Прямоугольные тайловые миры

Уровень сложностиСредний
Время на прочтение17 мин
Количество просмотров28K

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

Огромное множество игр на самом деле содержат тайлы - так просто проще представлять игровой мир. Такая упорядоченность помогает геймдизайнерам строить игровые механики, упрощает жизнь художников и делает код программистов понятнее. Самих видов тайлов тоже огромное количество - сегодня поговорим о прямоугольных и изометрических.

Читать далее

Преобразуем миры Minecraft в трёхмерные фотореалистичные сцены с помощью нейросетей

Время на прочтение6 мин
Количество просмотров14K


Мы представляем GANcraft — работающий без участия человека фреймворк нейронного рендеринга для генерации фотореалистичных изображений больших миров из 3D-блоков, например, таких, которые созданы в Minecraft. Наша система получает на входе мир из семантических блоков, в котором каждому блоку назначена метка, например, «земля», «дерево», «трава», «песок» или «вода».

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

Кроме позиции камеры, GANcraft позволяет пользователю задавать семантику и стиль сцены.

Расстояние Махаланобиса

Время на прочтение24 мин
Количество просмотров24K

Основной смысл использования метрики Махаланобиса
1. Термины и определения
2. Расстояние Махаланобиса между двумя точками и между точкой и классом
2.1. Теоретические сведения
2.2. Алгоритм вычисления расстояния между двумя точками и между точкой и классом
2.3. Пример вычисления расстояния между двумя точками и между точкой и классом
3. Расстояние Махаланобиса между двумя классами
3.1. Теоретические сведения
3.2. Алгоритм вычисления расстояния между двумя классами
3.3. Пример вычисления расстояния между двумя классами
4. Расстояние Махаланобиса и метод k-ближайших соседей
5. Взвешенное расстояние Махаланобиса
6. Заключение

Если есть замечания или ошибки, пишите на почту quwarm@gmail.com или в комментариях.

Читать далее

ДНК (Деление на команды) – визуализация взаимосвязей людей и команд

Время на прочтение4 мин
Количество просмотров4K
image
На рисунке – граф, визуализирующий межкомандное взаимодействие в Дивизионе развития и сопровождения производственного процесса (SberWorks) Сбера

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

  1. Jira – тикет-системе для управления задачами
  2. Confluence – вики-системе для управления требованиями
  3. Bitbucket – системе управления кодом

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

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

В итоге, получили следующую визуализацию коммуникаций:

  • Точка – это человек или команда.
  • Линия между точками – свидетельствует о наличии связи, которая является агрегатом взаимодействий, найденных в источниках данных, которые мы определили у людей. У линии связи есть свой вес, начало и конец.
Читать дальше →

Доступность ИТ-сервисов как ключевой бизнес показатель, и причем тут арбуз

Время на прочтение10 мин
Количество просмотров18K

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

Но есть у этого благородного начинания серьезное препятствие (философскую проблему “Можно ли все свести к числу” оставим для другой, профильной площадки и антиутопий типа “Черного зеркала”). В бизнесе метрик очень и очень много, а в ИТ их страсть сколько. В результате объем данных растет, количество наблюдаемых параметров также увеличивается. Мы начинаем делить метрики на ключевые и второстепенные, на метрики для бизнеса и метрики для “технарей”. Мы теряем фокус и вместо прозрачности получаем несвязный набор тысяч показателей. Погружаясь в свои метрики, сотрудники теряют из вида ключевую цель организации: решать “боли” своих клиентов, делать их жизнь лучше и получать за это вознаграждение. В результате мы получаем то, что принято называть “эффектом арбуза”, когда кожура “зеленых” метрик скрывает “красную и накаленную” сердцевину нашего бизнеса: удовлетворенность клиентов. 

Читать далее

Вебинар от Яндекс.Практикума «Конечные автоматы в реальной жизни»: теория, кодинг и Q&A за один вечер

Время на прочтение1 мин
Количество просмотров3.3K
Теория конечных автоматов лежит в основе многих алгоритмов, к которым часто прибегают разработчики. Решение многих проблем уже давно придумано и зачастую с использованием конечных автоматов.

8 мая в 15.00 (Мск) Яндекс.Практикум проводит открытый вебинар «Конечные автоматы в реальной жизни», на котором наставник курса «Мидл фронтенд-разработчик» Захар Овчаров расскажет про применение автоматов, а выпускник курса Антон Субботин попытается понять, зачем они нужны и как их применять.

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


Читать дальше →

Создаем кэшируемую пагинацию, которая не боится неожиданного добавления данных в БД

Время на прочтение10 мин
Количество просмотров27K

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

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

Показать статью полностью

Ближайшие события

Что такое алгоритм???? Часть 101 «Эволюция поведения»

Время на прочтение16 мин
Количество просмотров3.8K

Опять изучаем алгоритм. И уже который раз в заголовке слово "Эволюция". Эволюция программного проекта, эволюция памяти и теперь эволюция поведения. Это простое совпадение?


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


Почему для понимания алгоритма необходим разговор о поведении???


Где в формализации алгоритма есть место эмоциям????


И все эти вопросы в ограниченной объемом статье. Задача не проста, и тем интереснее начать...


Title

Читать дальше →

Даешь свободную литературу! Или как я с политикой вуза боролся

Время на прочтение5 мин
Количество просмотров9.4K

Доброго времени суток, хабровчане!  Это мой первый пост на форуме, так что прошу строго не судить.

 Как и полагается любому техническому вузу – в нашем есть куча интернет ресурсов, которыми вуз чрезмерно гордится. Однако есть оборотная сторона медали – качество этих сервисов. А именно, если говорить про электронную библиотеку, о коей и пойдет речь в данной статье, то в ней напрочь отсутствует возможность скачивания pdf-версии нужной тебе методички, точнее она есть, но за это придется заплатить немало денЯк. Деньги далеко не маленькие (если говорить именно про цену за вузовские методички). Если же такой формат не устраивает, то можешь пользоваться онлайн библиотекой.

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

И теперь представьте картину: человек пытается подготовиться к контрольной по квантовой механике по методичкам преподавателя, объемом 700 страниц, где необходимый материал находится на 500, и может перелистывать по 5 страничек в минуту, и каждые 20 минут, его попытки приходится возобновлять.… В общем, жесть…. И вот после очередной неудачной попытки прочитать нужную главу,  я решил, что пришло время положить конец данному произволу.

Читать далее

Введение в v-agent ориентированное программирование

Время на прочтение5 мин
Количество просмотров14K

v-agent ориентированное программирование (VAOP) - это методология программирования, основанная на представлении алгоритма в виде v-agent script, который позволяет программному агенту, получившему название v-agent, выполнять операции закодированные в модулях v-agent box.

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

Парадокс заключается в том, что мы должны меняться, чтобы все было по-прежнему, поэтому главная задача v-agent ориентированного программирования это обеспечить Бессмертие программного продукта при минимальных вложениях средств в его постоянную модернизацию.

Читать далее

Категория контекста

Время на прочтение12 мин
Количество просмотров2.3K

Математической моделью знаковых последовательностей с повторами (текстов) является мультимножество. Мультимножество было определено Д. Кнутом в 1969 году и позже подробно изучено А.Б. Петровским [1]. Универсальное свойство мультимножества – существование одинаковых элементов. Предельным случаем мультимножества при единичных кратностях элементов является множество. Множество с единичными кратностями, соответствующее мультимножеству, называется его порождающим множеством или доменом. Множество с нулевой кратностью – это пустое множество.

Читать далее

Одномерный генератор случайных действительных чисел

Время на прочтение7 мин
Количество просмотров3.6K

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

Класс генераторов "True Random" использует физические явления и внешние связи, так например для генерации десятичного случайного числа вы можете найти рекомендацию использования "атмосферного датчика". Естественно как любителю программирования такое положение дел мне показалось несправедливым, и довольно долгое время "задача созревала". Вариант решения, как и следовало ожидать из постановки задачи, появился случайно, как дополнение к задаче компрессии для упаковки твердых сфер. Задача не нашла аналитического решения как и нет пока доказательств его отсутствия, соответственно источник по внешним признакам вполне подходящий. Однако без дополнительного источника случайности, более чем бесконечной сложности в обратном вычислении состояния генератора я не получил.

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

Читать далее

Тихая революция и новый дикий запад в ComputerVision

Время на прочтение7 мин
Количество просмотров35K

Казалось бы, революция с Computer Vision уже была. В 2012 году выстрелили алгоритмы основанные на сверточных нейронных сетях. Года с 2014 они дошли до продакшна, а года с 2016 заполонили все. Но, в конце 2020 года прошел новый виток. На этот раз не за 4 года, а за один. поговорим о Трансформерах в ComputerVision. В статье будет обзор новинок, которые появились в последний год.

Читать далее

Разработка критически важных алгоритмов, часть 3: Интеграция

Время на прочтение10 мин
Количество просмотров2.3K
  1. Проектирование
  2. Реализация
  3. Интеграция

Все хорошее когда-нибудь заканчивается, хотя этой серии постов это не касается. Хоть они скоро и закончатся, далеко не факт, что они хороши.

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

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

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

Но в результате получается что-то, что работает, и это круто. Но, возможно, что еще более важно, вы прокачаетесь и станете немного лучше, сделав это в первый и самый худший раз. (Я бы сказал, что это похоже на написание академической статьи).
Читать дальше →

Вклад авторов