Алгоритмы *

Минимакс - популярный алгоритм для принятия решений в играх с нулевой суммой (один выиграл - другой проиграл). Казалось бы, раз он так популярен, то всё что можно было про него сказать уже сказано? Не совсем. Информация сильно раздроблена, иногда ошибочна, а найти какие-либо примеры в играх довольно сложно. Поэтому в этой статье я постараюсь прояснить процесс разработки ИИ на основе минимакса для игры "Поймай Овечку".

В этой статье я расскажу об алгоритме процедурной генерации лабиринтов методом поиска в глубину (Randomized depth-first search with recursive backtracking).

Привет, Хабр! Меня зовут Владислав, и один из моих проектов — интернет‑магазин карликовых кроликов. Сегодня по приглашению коллег из ChatApp, я расскажу, как автоматизировал свой бизнес. Нет, речи ни о каком роботизированном выращивании кроликов не пойдет — только о продажах. Для меня это был интересный опыт, который в итоге помог прийти к значительному росту показателей. В этой статье мы поговорим о программировании чат‑ботов, об особенностях ведения бизнеса на АВИТО, а также немного о ботовой этике и эстетике. Текст будет интересен тем, кто является владельцем или открывает свой интернет‑магазин, тем, кто сомневается, что чат‑бот может быть этичным и удобным решением как для покупателя, так и для продавца.

Давайте поговорим о лексическом анализе. Сначала я собирался назвать этот пост «Реализуем токенайзер», но ветер переменился, времена изменились… и, чтобы не утонуть в потоке комментариев вида «фыр, а где мой BPE-токенизатор LLama, который вы мне обещали», ограничимся пока лексическим анализом.

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

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

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

Довольно слов, приступим.

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

В прошлой части мы научились разбивать исходное математическое выражение формата (log2(18)/3.14)*sqrt(0.11^(-3)/0.02)на токены. На выходе мы получаем массив токенов, каждый их которых содержит информацию о типе (оператор, скобка, число, ...) и об ассоциативности, если он таковую имеет.

Теперь мы хотим привести выражение к виду обратной польской записи (RPN), чтобы затем удобно его посчитать. Это нам позволяет сделать изобретенный Эдсгером Дейкстрой алгоритм сортировочной станции.

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

Я решил всерьёз выяснить, чему равна эта вероятность в зависимости от длины случайной строки? Можно ли получить явную математическую формулу для ответа? Что, если взять другое слово? Что, если взять другой алфавит?

Обо всём по порядку.

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

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

Доброго времени суток, когда вы в последний раз играли в крестики-нолики? Вспомните поле которое вы рисовали на бумаге: 3x3? 5x5? А что вы скажете насчёт 19x19? "Долго будем играть!" - и это только часть проблемы. Передо мной встала такая задача в ходе хакатона от компании Тинькофф - написать бота для игры в крестики-нолики на доске 19x19 с поиском самого лучшего хода за небольшое время.

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

Вот с чего ИИ начал: "Гипотеза о пустоте внутренней части Луны противоречит данным, полученным от различных космических миссий "

А вот к чему пришел: "В настоящее время отсутствуют непреложные доказательства, подтверждающие или опровергающие полую структуру Луны."

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

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

Двумерное преобразование Фурье — один из важнейших алгоритмов компьютерной науки этого столетия. Он нашел широкое применение в нашей повседневной жизни — от фильтров Instagram до обработки MP3-файлов.

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

По своей сути алгоритм, реализуемый NumPy, является поочередным применением обычного одномерного БПФ (FFT) к двум измерениям, что очевидно не может быть оптимальным решением.

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

Привет, хабр! На дворе 2023 год. Теперь более чем когда‑либо всё в нашем мире основано на числах. Некоторые из них, как вы уже знаете, имеют собственные имена. Число π (пи), число e. Математика везде. Карма и рейтинги в хабре, количество ваших денег, сегодняшняя дата (22.11.2023). Даже есть вид эзотерики, веры — нумерология, вера в том, что числа связаны с судьбой. И ведь все это появилось не на пустом месте.

Мы, будто факиры заклинают своих змей, будем познавать математический мир. Красивый, бездонный и невероятно интересный. Добро пожаловать в серию статей «Факир математики», и тема первой нашей статьи — золотое сечение!

Среди всех замечательных и не очень чисел, цифр есть одно особенно интересное число...

Кто-то ещё сомневается, что в мире машинного обучения происходит революция? Уверен, мы являемся свидетелями преобразования привычного взаимодействия с данными, поиска информации, да и вообще работы как таковой. Ведь умные ассистенты (ChatGPT, GigaChat, Bard) готовы взять на себя даже самые сложные задачи.

Но не всегда возможно сформулировать проблему в виде текстового запроса, иногда требуется информация из других “модальностей” — картинка, звук, 3D и тд. Ниже я разберу какие именно есть способы соединения больших языковых моделей (LLM) с дополнительными форматами данных, а также опишу как устроена наша новая модель OmniFusion.

Привет, Хабр!

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

Формулы, используемые в теории сложности, часто связаны с вычислительной сложностью задач. Например, NP-полные задачи, которые являются одними из самых сложных для вычисления, описываются с помощью полиномиальных уравнений. Сложность задачи может быть выражена как O(n^k), где n — размер входных данных, а k — степень, определяющая сложность алгоритма.

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

В этой статье я расскажу о нашей последней работе — Multilingual Triple Match — системе для поиска ответов на фактологические вопросы, которая по своей точности обходит даже ChatGPT.

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

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

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

Сразу скажу, что моя статья относится лишь к условному ФААНГу. Многие аргументы из этой статьи теряют значимость в других случаях: если у вас маленькая фирма, мало кандидатов или у вас всего 10 пользователей.

Я утверждаю, что алгоритмические интервью - лучший вариант для ФААНГа из всех пока придуманных.

Прошу простить заранее за несколько кликбейтный заголовок )

Не так давно писал в соцсетях хейт‑пост по поводу «алгоритмических секций» при приёме на работу в Яндекс.

Да и многие другие софтверные компании это практикуют и считают навыки написания алгоритмов — чуть ли не самым важным навыком для программистов.

И ставят данной компетенции очень высокий приоритет при приёме на работу.

Попробую сегодня развить эту мысль и объяснить почему ставить навыки написания алгоритмов на первый план — не правильно, почему этот «алгоритмический» критерий не релевантен и не отражает реальной ценности / уровня / потенциальной пользы от данного программиста.