Алгоритмы *

Привет всем читателям Хабра! Нас зовут Сергей и Павел, мы студенты Томского государственного университета систем управления и радиоэлектроники (ТУСУР). В прошлом году мы победили в треке “Искусственный интеллект” IV Межвузовского конкурса выпускных проектов «‎IT Академии Samsung»‎. Там мы представили проект, использующий нейронные сети для анализа информации на ценниках.

Мы распознавали ценники сети магазинов “Лента” при помощи нейронных сетей для сегментации и OCR и теперь хотим рассказать о том, как проходила работа над проектом и что мы узнали за это время.

Памяти Насти. Памяти дочери.

Что знаем об алгоритмах поиска? Есть граф. Чаще ориентированный. И некое целевое состояние. Фиксированное. А если нет?

Как, например, найти ребенка, который потерялся в лесу? Ведь не только вы его будете искать, но и он вас.

Передвигаться случайно? Да. Но еще лучше выбирать те направления, где меньше всего были. Есть дополнительные признаки, например следы? Отлично. В первую очередь ориентируемся на них. Потерялись следы? Вновь возвращаемся к поиску с учетом только памяти.

Недавно от знакомых прилетела задачка написать программу для самотестирования. Порылся в инете, думал в лёгкую найду наработки, но ничего кроме платных и бесплатных конструкторов тестов не нашёл (может плохо искал, кто знает…). Мне показалось, что устанавливать какие-то инородные проги, а потом ещё туда все вопросы ручками забивать - совсем некрасиво. Так родилось приложение для самотестирования, написанное на Python с помощью GUI библиотеки Tkinter.

Thread Pool достаточно популярный паттерн в программировании, с которым рано или поздно сталкивается каждый первый программист. Если вы новичок и не хотите бездумно пользоваться пулом потоков, то эта статья поможет вам разобраться с его устройством и написать наивные реализации с использованием С++ 14 и С++ 17. Так же статья будет полезна всем, кто изучил теорию по многопоточности, но не знает как можно применить свои знания.

Меня зовут Абай Баймуканов, я – разработчик-алгоритмист международной IT-компании Relog. Уже несколько лет увлекаюсь олимпиадными программированием, поэтому в этой статье хотел бы поделиться своим видением по этому поводу.

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

Здесь есть свой нюанс: программа может работать настолько долго, сколько не существует даже вселенная, а может сработать за долю секунды. Причем в обоих случаях результат будет один и тот же. Любой олимпиадник стремится к тому, чтобы его программа была как можно эффективнее. Для этого существуют алгоритмы и структуры данных - методы, позволяющие сделать определенные программы более эффективными с точки зрения необходимого времени или памяти компьютера.

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

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

Программирование в Солидити отличается от других языков, так как каждое инструкция и байт памяти тратят газ - деньги пользователей. В сети уже есть много ресурсов с основными техниками оптимизации кода (например, стараться использовать calldata вместо memory), но я хочу показать несколько совсем безумных и неочевидных.

Понять о чем я говорю без базового опыта в solidity будет очень сложно, но может быть эти оптимизации проявят в вас интерес в ethereum программировании.

Проектированием простого процессора сейчас никого не удивишь. Любой способный студент может за пару недель написать на верилоге однотактный RISC-V или ARM процессор и синтезировать его для ПЛИС. Процессор будет работать на учебной плате и выполнять простые программы на Си и ассемблере.

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

На границе между вводным и продвинутым курсом микроархитектуры CPU принято ставить внеочередное выполнение инструкций, именно оно отделяет мальчика от мужа. Эта фича впервые появилась еще в 1960-е годы в суперкомпьютерах CDC 6600 и IBM 360/91, но проникла в персоналки с PentiumPro только в 1996 году и в Apple iPhone в 2012 году.

Именно внеочередное выполнение инструкций - главная козырная карта самого горячего процессорного проекта российской микроэлектроники - двухгигагерцового RISC-V процессора для ноутбуков от компании Ядро / Syntacore. Этот проект был объявлен в прошлом году. Что с ним станет в результате известных событий?

Для всех кто хочет познакомиться с книгой Космофизические факторы в случайных процессах Симона Эльевича Шноля оставляю ссылку

Артем Мурадов — Senior Software Development Engineer в Amazon и автор курса «Алгоритмы: roadmap для работы и собеседований». Уже больше 14 лет он использует алгоритмы для решения рабочих задач и прохождения собеседований. С помощью алгоритмов он повышал производительность приложений, побеждал в спорах с коллегами и ускорял исследование ДНК. Даже попасть в Amazon ему помогло знание алгоритмов.

Мы пообщались с Артемом, чтобы узнать о его опыте. Он подробно рассказал, как изучал алгоритмы и как они помогали ему в работе.  

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

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

Написание своего шахматного движка - обширная тема, про которую пишут целые книги.

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

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

Я запрограммировал 15 шахматных вариаций - для каждой опишу неожиданные ходы и результаты партий компьютера друг с другом.

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

Друзья по играм: Бен, Билли, Том Миллер и другие, с интересом ждали правил игры, в которую Сойер превратит задание на этот раз. 

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

-- Пропади я пропадом, если не уберу подальше от улицы все кусты, что будут похуже этого!

Том в задумчивости осмотрел ряд таких же кустов.

-- Вот второй куст, он повиднее этого! Но почём мне знать насколько он хорош? Пусть пока постоит на месте. Тётушка точно будет недовольна, если мы будем дёргать горшки почём зря.

-- Третий тоже повыше моего, оставим и его до срока.

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

-- Попался, оборванец! Что ж поделать, многоуважаемый недоросль, ваше место займёт более возвышенный кандидат!

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

Он схватил второй куст и перенёс его на пустующее место в ряду, возле своего образца.

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

Есть данные за 2 дня мая 2005 года 2 дня мая 2006 года. Цель найти в сумме 1440 сравнений[60*24] звездный год.

На сайте habr.com/ru уже были похожие публикации осенью 2021 года:

Как посчитать синус быстрее всех

Как посчитать синус быстро

Не на Habr Как сделать быструю функцию для вычисления синуса? топик начат в 2003 году последний отклик в 2020 году.

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

Разбираю разные подходы к созданию ботов и смотрю на их эффективность

Заработает ли бот достаточно денег?
Будет ли стабильный заработок?
Достигнет ли он когда-нибудь годового дохода в $100,000?

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

Поиск самого длинного палиндрома в строке за O(n).

Сегодня, в субботу 26 февраля, на Сколковской Школе Синтеза Цифровых Схем Михаил Коробков проводит занятие по технологиям функциональной верификации: constrain solvers, cover bins и concurrent assertions. Примеры, которые мы подготовили для школы, вращаются вокруг протокола AXI для систем на кристалле, вопросы про который спрашивают например на интервью в хардверное отделение компании Meta и другие.

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

Суть деятельности Verification Engineer заключается в создание фреймворков, которые тестируют хардверные дизайны на прочность, посылая к ним псевдослучайные транзакции и учитывая покрытие интересных сценариев (functional coverage). Базовые элементы этих технологий должен знать и хороший RTL Design Engineer.

Приглашаем присоединяться к трансляции занятия на канале школы в YouTube, в субботу 26 февраля с 12.00 до 15.00:

Всем привет! Уже больше 30 лет я занимаюсь разработкой видеоигр и регулярно экспериментирую с различными игровыми механиками. В результате я пришел к идее создать игру по типу сапёра, но от третьего лица и на roguelike подобном уровне.

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

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

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