Алгоритмы *

Всё началось в далёком 2004 году, когда я учился в СПб ГУ ИТМО на кафедре Прикладной и компьютерной оптики (ПиКО). Однажды на лекции по "Основам оптики" преподаватель рассказал о голографии. Эта тема меня сразу увлекла, и, несмотря на то, что многое тогда было непонятно, проявленный интерес не угас до сих пор. Помню, как лектор объяснял свойства голограмм, а так же привел схему связывающую параметры записи с типом получаемых голограмм: Габора, Лейта и Упатниекса, Денисюка и другие (рис. 1). Это был тот не редкий момент, когда: «Очень интересно и ничего не понятно»

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

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

В этой части используем двойную рекурсию для "раскраски" регионов на карте.

Привет! Меня зовут Павел Астахов, я работаю в департаменте системного анализа SM Lab. Сегодня расскажу про проектировочную документацию и её стандартизацию в нашей компании.

Причины внедрения стандартизации

Причина 1. Сотрудники

Департамент системного анализа появился в 2020 году: на тот момент нас было 50 человек в 20 командах; к 2024 году мы сильно разрослись и нас стало уже 260 системных аналитиков, которые трудились в 85 командах. Рост и увеличение масштаба департамента выявили проблемы, которые ранее не были видны и постепенно стали выходить на первый план.

Как известно, горизонтальный инфракрасный счётчик считает, в сущности, не людей, а вызванные их прохождением прерывания горизонтального инфракрасного луча.
Рекомендуемая абсолютно всеми производителями высота установки счётчика (точнее было бы говорить о высоте установки его сенсорной системы) составляет 120-150 см. При такой высоте инфракрасный луч приходится на голову и плечи взрослого человека. В этом случае одно прерывание луча должно означать, что прошёл один человек.

Давайте рассмотрим работу горизонтального инфракрасного счётчика в крайне неблагоприятных условиях. Установим его на уровне ног.

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

Компании, такие как Google, Amazon или Microsoft, в процессе собеседований проверяют именно эти знания, поскольку они являются универсальными и применимыми ко всем областям разработки.

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

Существует 2 вида структуры агента: гетерогенное и гомогенное. Гомогенные агенты сконструированы идентично, то есть особо не отличаются друг от друга. А гетерогенный вид означает, что агенты отличаются друг от друга.

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

Существует 2 основных подхода управления роботами: централизованная и децентрализированная. Централизованная система означает, что есть один какой‑то агент, который руководит всем. А децентрализованная противоположна централизованной, то есть каждый агент действует независимо.

Мультиагентная система (МАС) — это система, состоящая из нескольких интеллектуальных агентов. Например, муравейник, он состоит из множества агентов, муравьев.

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

Цель работы — Создание математической модели и алгоритма для роботизированной системы. Задачи:

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

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

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

Роботакси сталкиваются с серьезными проблемами в городских условиях. Предлагаемое (не мое и не новое) решение – изолированные полосы. Но для движения по ним необходима модификация автопилота роботакси.

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

Заголовок отсылает к знаменитой работе Attention Is All You Need, которая фактически перевернула мир ИИ, сделав его другим, не таким, как прежде. В этой научной публикации описаны принципы реализации архитектуры трансформеров, но в ее названии упоминается именно механизм внимания. Долгое время я пытался ответить себе на один простой вопрос: где все-таки заканчивается ML и начинается AI для задачи коммивояжера и вообще? Мне кажется, ответ пролегает где-то рядом с проростанием механизма внимания, который в 2014 году был предложен Dzmitry Bahdanau (извиняюсь, не знаю, как правильно писать по-русски его фамилию). Безусловно, были работы Хопфилда, получившего в 2024 Нобелевскую премию по физике, в том числе, за свою архитектуру нейронной сети, которая способна решать задачу коммивояжера. Были и другие работы, но, в случае разбора еще одного алгоритма из прошлого века, боюсь, нарваться на обратную связь в стиле: “дядь, не мороси, давай уже там про свой ИИ пиши, а не вот эти свои нафталиновые алгоритмы описывай”, поэтому про нейронную сеть Хопфилда готов написать, но только если будет ощутимая обратная связь.

Механизм внимания был предложен как способ улучшить seq-to-seq модели, применяемых для перевода текста с одного языка на другой. Кто бы мог подумать, но токены слов можно заменить координатами городов и попробовать решить задачу TSP той же моделью. В конце концов человек тоже использует одно и тоже серое вещество для решения разных задач. Первые попытки реализации этой идеи подразумевали наличие оптимального эталонного маршрута в виде, например, посчитанного решения Concorde. Но позже появилась идея использования техники обучения с подкреплением или Reinforcement learning. Таким образом, появилась нейронная сеть Pointer Networks, о которой собственно я и хотел сегодня поговорить.

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

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

В этой части снова сталкиваемся с вложенным в цикл рекурсивным поиском "в ширину".

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

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

В этой части рассмотрим некоторые "грабли", на которые можно наступить, реализуя рекурсивные алгоритмы на SQL... Которые иногда можно сделать вовсе нерекурсивными, ускоряя запрос в десятки раз!

Хэширование — простой и надёжный способ проверить целостность данных. Но как быть, если нужно удостовериться, что часть данных принадлежит определённому набору? Например, проверить отдельную транзакцию в блоке Bitcoin или чанк файла в BitTorrent? Для этого используется уникальная структура данных — Merkle-tree. В этой статье вы узнаете, как с её помощью решать задачи проверки данных без доступа к их полному объёму.

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

Предыстория и казус газетных судоку

Как и прежде, ближе к Новому году в почтовых ящиках жителей нашего городского округа чаще стали появляется номера газеты «Восточный округ» (ВО). И традиционно в конце каждого номера приводится головоломка судоку. И наверное, тоже уже традиционно, эти судоку ̶ неправильные, то есть имеют много решений (ответов), и только одно из них назначено в виде заполненной цифрами таблицы как «Ответы на судоку». На этот раз судоку, попавшееся на глаза (в номере ВО №40 (563)), побило все прежние рекорды по числу решений (их оказалось 83 132), из которых уважаемому читателю предложено как-то угадать единственное, приведённое в газете как «Ответы на судоку». На такой казус газетных судоку я прежде обращал внимание редакции газеты ВО. И на этот раз я не удержался, и  не внял просьбе близких: «перестать заниматься ерундой» не тратить время на публикацию в сети. Год назад, анализируя последние номера газеты ВО 2023 года, я предлагал (см. habr.com/ru/articles/787496) «подправлять» подобные неправильные судоку так, чтобы они имели единственное решение. Но предлагаемая тогда «правка» налагала на судоку дополнительные ограничения, меняя их классическую структуру. Например, для судоку №149 из sudoku.bestcrosswords.ru/generator, имеющего 26918 отличных друг от друга решений, предлагалось дополнительно потребовать, чтобы на побочной диагонали матрицы располагался полный набор цифр от 1 до 9. Это дополнительное требование меняло классическую структуру судоку и усложняло восприятие привычной головоломки.
 А как дополнить исходную таблицу судоку минимальным числом новых  цифр-подсказок, чтобы получилось судоку с классической структурой и единственным решением, например, с тем, что приведено в газете как  «Ответы на судоку»? В этом и состоит задача, решение которой позволит преодолеть казус  газетных судоку.

Алгоритм Дейкстры долгое время считался самым эффективным способом обхода графа. Теперь исследователи доказали, что он «универсально оптимален». 

Если вы долгое время ездите по одному и тому же маршруту, вы, вероятно, считаете его лучшим. Но «лучший» — это относительное понятие. Возможно, однажды произойдёт авария или дорога будет перекрыта, и ваш самый быстрый маршрут станет самым медленным. 

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

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

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

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

Скретч-лотереяTic Tac Toe («крестики‑нолики»), выпущенная компанией Ontario Lottery в 2003 году обладала интересными правилами: в правой части билета находится игровое поле с числами, в левой — «ваши счастливые числа», скрытые защитным слоем. Игроку предстоит стереть защитный слой и посмотреть, на каких позициях на игровом поле расположены его счастливые числа. Если три счастливых числа образуют линию, то игрок получает соответствующий выигрыш (для каждой линии — свой).

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

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

Приветствую, Хабравчане!

Решил сделать цикл статей по написанию на С++, различных небольших программ. Под новые и старые ОС. Мне кажется мы стали забывать как раньше программировали:) Для себя определил несколько важных критериев.