Рубрика «Алгоритмы» - 31

image

Введение

Меня зовут Александр Садовников, я выпускник корпоративной магистерской программы ИТМО и JetBrains «Разработка программного обеспечения» и по совместительству старший разработчик биоинформатического ПО в департаменте вычислительной биологии компании BIOCAD.

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

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

Читать полностью »

Go и кэши CPU - 1

Источник: unsplash.com

По словам Джеки Стюарта, трехкратного чемпиона мира по гонкам Формулы-1, понимание автомобиля помогло ему стать лучшим пилотом: «Гонщику не обязательно быть инженером, но нужен интерес к механике».

Мартин Томпсон (создатель LMAX Disruptor) применил эту концепцию к программированию. Если в двух словах, то понимание базового оборудования улучшит ваши навыки, когда речь заходит о разработке алгоритмов, структур данных и так далее.

Команда Mail.ru Cloud Solutions перевела статью, автор которой углубился в устройство процессора и рассмотрел, как понимание некоторых концепций CPU помогает принимать оптимальные решения.
Читать полностью »

В конце мая я изучал игры для PlayStation, которые Sony ежемесячно дарит пользователям подписки PS Plus — там была игра Farming Simulator 19. Не то чтобы я прям целюсь в фермеры, но всё же решил посмотреть трейлер игры. Довольно забавно: тебе дают поле, по которому ты гоняешь на комбайне или тракторе, сеешь семена или собираешь урожай — интересная залипуха для самоизоляции, с весьма недурной графикой. Но сразу почему-то не скачал, а сейчас «уже всё, всё»: игра перестала быть бесплатной, в июньском предложении теперь другие игры (кстати, тоже неплохие — Star Wars Battlefront II и Call of Duty: WWII).

Беспилотный комбайн Ростсельмаш для сбора бутылок? - 1

К чему я это всё? Не знаю, в каких отношениях состоят Sony и Google, но недавно YouTube подсунул мне любопытное видео — «На что способен комбайн-беспилотник TORUM». И я не смог совладать с любопытством — очень уж захотелось узнать, что там и как нынче в сельском хозяйстве. Был приятно удивлён, узнав, что на видео речь про новую разработку компании РОСТСЕЛЬМАШ! Посмотрел… и если вы думаете, что под катом будет реклама комбайна, то нет. Под катом я призываю коллективный разум поковырять очередное достижение.
Читать полностью »

Постановка задачи

Рассмотрим задачу аппроксимации комбинации прямых линий по набору зашумленных координат точек, находящихся на данной комбинации линий (см. Рис. 1 и Рис. 2). Обычная формула линейной аппроксимации здесь не подойдет, так как точки перемешаны и результат будет некая усредненная линия между ними (см. Рис. 3).

Линейная аппроксимация комбинации линий по набору зашумленных точек - 1

Рис. 1 Комбинация линий и зашумленный набор координат

Читать полностью »

Armored Warfare: Проект Армата. Хроматическая аберрация - 1

Armored Warfare: Проект Армата — бесплатный танковый онлайн-экшн, разрабатываемый Allods Team, игровой студией MY.GAMES. Несмотря на то, что игра сделана на CryEngine, достаточно популярном движке с неплохим realtime render’ом, для нашей игры приходится многое дорабатывать и создавать с нуля. В этой статье я хочу рассказать о том, как мы реализовывали хроматическую аберрацию для вида от первого лица, и что это такое.
Читать полностью »

Гениальный алгоритм создания лабиринтов в игре Entombed, который до сих пор не могут разгадать - 1

В 2017 двое ученых, канадец John Aycock и британка Tara Copplestone, опубликовали анализ классической игры Entombed для игровой приставки Atari 2600. Механика этой игры, выпущенной в 1982, крайне проста: археолог, управляемый игроком, должен пробраться по прокручивающимся снизу вверх катакомбам, уворачиваясь от зомби.

У Atari 2600 было всего 128 байт ОЗУ; тем не менее, кажущийся бесконечным лабиринт при каждом запуске был новым, т.е. генерировался в памяти. Как же программистам это удалось? Вот комментарий Стивена Сидли — программиста, 38 лет назад создавшего эту игру:

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

Читать полностью »

Недавно я написал своё первое интро 4K на Rust и представил его на Nova 2020, где оно заняло первое место в конкурсе New School Intro Competition. Написать интро 4K довольно сложно. Это требует знания многих различных областей. Здесь я сосредоточусь на методах, как максимально сократить код Rust.

Можете просмотреть демо-версию на Youtube, скачать исполняемый файл на Pouet или получить исходный код с Github.
Читать полностью »

Идём в глубь острова сокровищ с названием "Алгоритм".

Title

Читать полностью »

Всем привет!

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

Game of Life с битовой магией, многопоточностью и на GPU - 1

Читать полностью »

Go School

Как вы знаете, в середине мая Ozon объявил о запуске школы программирования на языке Go. Обещали следующее:

  • бесплатное обучение
  • возможность получить знания по реальной разработке на Go от Ozon
  • возможность получить работу в Ozon

Чтобы попасть в школу, нужно было:

  • иметь опыт промышленного программирования
  • пройти тестовые задания по программированию на платформе Яндекс.Контест
  • пройти skype-собеседования

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

Тогда же было озвучено число студентов, которое готовы принять в Школу — около 40 человек.

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

  • желательно проживать в Москве
  • быть гражданином РФ
  • возраст старше 18 лет

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

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

Ozon go school: Как не нужно проводить отбор - 1
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js