Общеизвестно, что Решето Эратосфена (РЭ) один из древнейших алгоритмов, появившийся задолго до изобретения компьютеров. Поэтому можно подумать, что за века этот алгоритм изучен вдоль и поперек и добавить к нему ничего невозможно. Если посмотреть Википедию – там море ссылок на авторитетные источники, в которых запросто утонуть. Поэтому удивился, когда на днях случайно обнаружил, что вариант, который в Википедии преподносится как оптимальный, можно заметно оптимизировать.
Читать полностью »
Рубрика «Алгоритмы» - 74
Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
2019-05-05 в 15:06, admin, рубрики: Delphi, Алгоритмы, Занимательные задачки, математика, оптимизация, Программирование, простые числа, решето ЭратосфенаЧётные числа Фибоначчи
2019-05-05 в 12:54, admin, рубрики: php, Алгоритмы, комментарии на хабре, математика, собеседование, числа фибоначчиНавеяно комментарием под постом Фибоначчи на собеседовании. Пользователь pavellyzhin упомянул следующую задачу на собеседовании (комментарий):
Больше года назад откликнулся на вакансию «php-программист», прислали ТЗ и там было задание с Фибоначчи: выбрать все четные числа Фибоначчи в диапазоне от 1 до 10000. Решил с помощью цикла(for). Еще там нужно было SQL-запрос составить на выборку ближайших дней рождений пользователей, что-то сверстать, точно не помню и какую-то функцию написать. Все сделал, отправил. Прислали ответ: «по итогам тестового задания Вы не приняты». Что конкретно им не понравилось так и не написали. Вот сейчас сижу и думаю, наверное все-таки из-за Фибоначчи пролетел… :)
В данном посте я собираюсь показать как можно было решить эту задачу эффектно, а может даже и эффективно, но это не точно. Заодно продемонстрирую парочку из тысяч доказанных про числа Фибоначчи фактов.
Читать полностью »
Искусственный интеллект, великий и ужасный. Часть третья
2019-05-05 в 9:14, admin, рубрики: Алгоритмы, базы данных, искусственный интеллект, нейронные сети, ПрограммированиеНейронные сети
В последнее время про НС говорят очень много. Я бы даже сказал, неприлично много. Я никогда не считал НС даже намёком на ИИ и, судя по многочисленным комментариям, это мнение разделяет немало людей. Некоторые высказывания: Читать полностью »
Трассировка лучей на GPU в Unity — Часть 3
2019-05-02 в 11:20, admin, рубрики: gpu programming, ray tracing, unity, Алгоритмы, Работа с 3D-графикой, разработка игр, рендеринг, трассировка лучей, шейдеры
Сегодня мы совершим большой скачок. Мы отойдём от исключительно сферических конструкций и бесконечной плоскости, которые трассировали ранее, и добавим треугольники — всю суть современной компьютерной графики, элемент, из которого состоят все виртуальные миры. Если вы хотите продолжить с того, чем мы закончили в прошлый раз, то воспользуйтесь кодом из части 2. Готовый код того, что мы будем делать сегодня, выложен здесь. Давайте приступим!
Треугольники
Треугольник — это всего лишь список трёх соединённых вершин, каждая из которых хранит свою позицию, а иногда и нормаль. Порядок обхода вершин с вашей точки обзора определяет, на что мы смотрим — на переднюю или заднюю грань треугольника. Традиционно «передом» считается порядок обхода против часовой стрелки.
Во-первых, нам нужно иметь возможность определять, пересекает ли луч треугольник, и если да, то в какой точке. Очень популярный (но совершенно точно не единственный) алгоритм для определения пересечений луча с треугольником был предложен в 1997 году джентльменами Томасом Акенин-Меллером и Беном Трембором. Подробно о нём можно прочитать в их статье «Fast, Minimum Storage Ray-Triangle Intersection» здесь.
Читать полностью »
О разложении многоканального отклика системы по «псевдособственным» формам колебаний
2019-05-02 в 7:40, admin, рубрики: data mining, Алгоритмы, вибрация, математика, многоканальный, собственные формы, стохастические процессыОбклеенный десятками датчиков «объект исследований» при натурных динамических испытаниях (например, при исследовании виброактивности транспортного средства) легко обеспечивает нас большим объемом полученных данных, но вот что с ними делать, зачастую не очень-то ясно. То же самое — при симуляционом моделировании динамических процессов систем с большим количеством степеней свободы.
Это может быть не совсем понятно тем, кто не сталкивается с проблемой регулярно, но — отсматривать соответствующую анимацию процесса, стохастического во времени и пространстве, как правило, почти бессмысленно. Где сломается или почему так трясет — обычно «не видно». Что придумывали кроме анимации, ниже расскажу, а порекомендую вот что.
Путем элементарнешей процедуры можно получить и сами пространственные «формы» колебаний, причем именно реально проявляющиеся в данных условиях нагружения, и интенсивности их проявления (дисперсии; при желании — и сами процессы).
| Исходный многоканальный процесс
|
Разложение  
|
Рис.1 Разложение многоканального отклика по псевдоформам. «Струна в вязкой среде»(см.рис.2)
Читать полностью »
Почему data scientist — это не data engineer?
2019-04-30 в 12:03, admin, рубрики: big data, data engineer, data scientist, Алгоритмы, анализ данных, Блог компании Mail.Ru Group, машинное обучение, теория анализа данных, Управление продуктом
«Ученый может открыть новую звезду, но не может создать её. Для этого ему пришлось бы обратиться к инженеру». Гордон Линдсей Глегг, «Дизайн дизайна» (1969)
Несколько месяцев назад я писал о различиях между специалистами по теории и методам анализа данных (data scientist) и специалистами по обработке данных (data engineer). Я говорил об их навыках и общих отправных точках. Произошло кое-что интересное: data scientist'ы начали наступать, утверждая, что они на самом деле так же компетентны в области инженерии данных, как и специалисты по обработке данных. Это было интересно, потому что специалисты по обработке данных не высказывали возражений и не говорили, что они являются специалистами по теории анализа данных.
Поэтому последние несколько месяцев я занимался сбором информации и наблюдением за поведением специалистов по теории анализа данных в их естественной рабочей среде. В этом посте я подробнее расскажу о том, почему data scientist не является data engineer'ом.
Читать полностью »
Быстрый кэш на C-C++, потокобезопасность
2019-04-29 в 13:48, admin, рубрики: c++, cache, github, LRU, MRU, Алгоритмы, высокая производительность, ПрограммированиеСравнительное тестирование многопоточных кэшей реализованных на C/C++ и описание как устроен LRU/MRU кэш серии O(n)Cache**RU
Создание игры Tower Defense в Unity, часть 1
2019-04-29 в 12:59, admin, рубрики: C#, pathfinding, tiles, tower defense, unity, Алгоритмы, поиск в ширину, поиск пути, разработка игр, тайловые карты, тайлыПоле
- Создание тайлового поля.
- Поиск путей с помощью поиска в ширину.
- Реализация поддержки пустых и конечных тайлов, а также тайлов стен.
- Редактирование контента в режиме игры.
- Опциональное отображение сетки поля и путей.
Это первая часть серии туториалов, посвящённых созданию простой игры в жанре tower defense. В этой части мы рассмотрим создание игрового поля, поиск пути и размещение конечных тайлов и стен.
Туториал создавался в Unity 2018.3.0f2.
Поле, готовое к использованию в тайловой игре жанра tower defense.
Игра жанра Tower Defense
Tower defense — это жанр, в которой целью игрока является уничтожение толп врагов, пока они не добрались до своей конечной точки. Игрок выполняет свою цель, строя башни, которые атакуют врагов. У этого жанра очень много вариаций. Мы будем создавать игру с тайловым полем. Враги будут двигаться по полю в сторону своей конечной точки, а игрок будет создавать им препятствия.
Читать полностью »
Искусственный интеллект, великий и ужасный. Часть вторая
2019-04-28 в 8:54, admin, рубрики: азимов, Алгоритмы, искусственный интеллект, мозг, Программирование, самообучение, сознание, тест тьюринга, ЭмоцииКак и предыдущая, эта заметка представляет собой обзор статей и комментариев к ним здесь, на Хабре, сгруппированный по нескольким темам.
Законы робототехники Азимова
Пожалуй, самая смешная, но, как ни странно, до сих пор широко обсуждаемая тема. Собственно, говорить тут просто не о чем: разве кому-то не ясно, что если ИИ хоть немного станет вылезать из пелёнок (и даже раньше — уже сейчас!), на него тут же наложат лапу военные и всякая там «госбезопасность»? И они будут учить ИИ именно эффективно убивать, не заморачиваясь всякой ерундой на тему «псевдоэтики». Разве не ясно, что эти «законы» в принципе не работают и работать не могут, о чём прекрасно знал и сам Азимов? Разве не ясно, что главная угроза со стороны ИИ как раз связана с контролем со стороны человека? И что, мы так и будем верить в сказки, вопрошая: «Дадим ли мы военным роботам лицензию на убийство»? А разве нас кто-то спрашивает? Или: «Крупнейшие ИТ-компании не дадут ИИ вырваться из-под контроля человека». А разве их кто-то спрашивает? Или: «Известные во всём мире разработчики ИИ договорились не создавать умное оружие». Тупое будут создавать? Или: «Эксперт ООН призвал мировое сообщество притормозить создание боевых роботов с искусственным интеллектом». А разве крупные страны, способные создать таких роботов, хоть раз считались с мнением ООН? Так что давайте прекратим обсуждать очевидные глупости — это даже не детский сад, это младшая ясельная группа.
Тест Тьюринга
Фибоначчи на собеседовании
2019-04-26 в 7:57, admin, рубрики: javascript, Алгоритмы, собеседование, числа фибоначчиВычисление ряда Фибоначчи — это классическая алгоритмическая задача, потому её нередко дают на собеседованиях, когда хотят проверить, что кандидат в принципе хоть как-то умеет в алгоритмы. Предположим, вы тот самый кандидат. Вам дали задание: на языке JavaScript написать функцию fib(n), возвращающую энное число Фибоначчи. Считаем, что нулевое число Фибоначчи — это нуль. Проверка корректности аргумента не требуется. Какие у вас есть варианты?
