Pull to refresh
-7
@StarCuriosityread⁠-⁠only

User

Send message

Математик оптимизировал решето Эратосфена, чтобы искать простые числа с меньшим расходом памяти

Reading time4 min
Views31K

38-летний перуанский математик Харальд Хельфготт три года назад доказал тернарную гипотезу Гольдбаха, а сейчас сумел оптимизировать компьютерный алгоритм для расчёта решета Эратосфена. Фото: Matías Loewy

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

Суть понятна из названия. Решето Эратосфена означает поиск простых чисел методом исключения. Берём список чисел, исключаем из него все составные числа — и получаем список простых чисел, словно просеяв список через решето.
Читать дальше →
Total votes 57: ↑46 and ↓11+35
Comments50

Разбор задач финального раунда RCC 2016

Reading time12 min
Views7.6K


18-го сентября был проведен последний, финальный этап чемпионата по спортивному программированию Russian Code Cup 2016 года. Первое место в упорной борьбе занял Геннадий Короткевич, второе и третье места — Владислав Епифанов и Николай Калинин соответственно.

Турнирную таблицу финала можно найти здесь, призовой фонд в этом году впервые распределен на первые 25 мест рейтинга. Это не единственное нововведение — впервые в RCC имели возможность поучаствовать англоговорящие программисты, коих набралось более тысячи из 4.5 тысяч участников. Помимо традиционных для соревнования стран СНГ, в финальном раунде боролись представители Германии, Финляндии, Японии, Швейцарии, Китая и Южной Кореи. Кроме того, в этот раз был проведен зеркальный раунд на Codeforces — сразу после финала основного состязания, у всех желающих была возможность решить задачи финала в специально организованном соревновании для первого дивизиона, поучаствовало чуть больше 200 программистов.

Традиционно предлагаем вам разбор задач финала (тесты можно скачать здесь):

A. Церемония закрытия
B. Кактусофобия
C. Домашнее задание
D. Слалом
E. Шифр
F. Покрытие массива
Читать дальше →
Total votes 29: ↑28 and ↓1+27
Comments6

Асинхронная (и не очень) загрузка данных в Unreal Engine 4

Reading time8 min
Views25K


Содержание:



Всем привет!

Сегодня я расскажу о том, как обращаться с ассетами на Unreal Engine 4 так, чтобы не было мучительно больно за бесцельно занятую память и стоны игроков за время загрузки вашей игры.
Читать дальше →
Total votes 33: ↑32 and ↓1+31
Comments9

Чистая энергия за копейки

Reading time10 min
Views64K
Когда появятся термоядерные электростанции? Ученые чаще всего говорят, что-то вроде “через 20 лет мы решим все принципиальные вопросы”. Инженеры из атомной индустрии говорят про вторую половину 21 века. Политики рассуждают про море чистой энергии за копейки, не утруждая себя датами. Экономисты говорят — никогда.


Создатели первого в мире токамака Т-1 Арцимович, Явлинский тоже обещали электростанции через 20 лет.

Люди склонны давать прогнозы, экстраполируя имеющийся опыт. В случае попыток создания коммерческой термоядерной электростанции опыт отрицательный — 60 лет усилий привели к половинчатому успеху — что-то есть, но это явно не то что можно использовать каждый день для получения электроэнергии. Интуиция говорит, что если за 60 лет мы не преодолели эту стену, то и в будущем чего-то хорошего ждать не стоит.
И зря.
Total votes 123: ↑122 and ↓1+121
Comments369

Распознавание образов в R с использованием сверточных нейронных сетей из пакета MXNet

Reading time8 min
Views15K
Это подробная инструкция по распознаванию образов в R с использованием глубокой сверточной нейронной сети, предоставляемой пакетом MXNet. В этой статье приведен воспроизводимый пример, как получить 97,5% точность в задаче распознавания лиц на R.

image

Читать дальше →
Total votes 33: ↑33 and ↓0+33
Comments2

Входим в форму: от гиперболической геометрии до кубических комплексов и обратно

Reading time28 min
Views22K

Доказательство отмечает конец эпохи в изучении трёхмерных форм.


Тридцать лет назад математик Уильям Тёрстон [William Thurston] рассказал о своём видении: систематизации всех возможных конечных трёхмерных форм.

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


Уильям Тёрстон в Беркли в 1991 году.

«У многих людей после многих лет обучения складывается впечатление, что математика – это строгий и формальный предмет, занимающийся сложными и непонятными правилами,- писал он в 2009-м. – Хорошая математика являет собой полную противоположность этому. Математика – это искусство человеческого понимания… Математика поёт, когда мы чувствуем её всем мозгом».

В основании видения Тёрстона находился брачный союз между двумя, на первый взгляд, несопоставимыми подходами к изучению трёхмерных фигур: геометрией, знакомым царством углов, длин, областей и объёмов, и топологией, изучающей свойства формы, не зависящие от точных геометрических измерений – свойства, не меняющиеся, если форму растянуть или перекрутить, как "хэндгам".
Читать дальше →
Total votes 45: ↑43 and ↓2+41
Comments15

SMAS: «Отсортированная мульти-массивная структура» (Sorted Multi Array Struct) — альтернатива бинарному дереву поиска

Reading time6 min
Views5.4K

Вступление


Здравствуйте, хабравчане. Это моя первая публикация, в которой хочу поделиться структурой данных SMAS. В конце статьи будет предоставлен С++ — класс предложенной структуры данных. Реализация рекурсивная, но моя цель — донести идею. Реализацию не рекурсивной версии — дело второе. Важно «услышать» мнения.

Что не так с деревом?


Да, всё так и можно завершать статью, всем спасибо. было бы плюнуть на значительный оверхеад памяти на вспомогательные данные в виде ссылок на левые-правые поддеревья и флаг для балансировки (разный в зависимости от используемой техники — красно-чёрные, АВЛ и т.п. деревья). Ещё один, не то чтобы минус — это постоянная модификация дерева при вставке для балансировки (тут особенно важна сложность и запутанность методов для новичков). На этом минусы заканчиваются и сложно себе представить что-то лучше и более универсальное (хеш-таблицы, ИМХО, ещё круче, но ОХ УЖ ЭТИ КОЛЛИЗИИ).
Читать дальше →
Total votes 19: ↑12 and ↓7+5
Comments91

C++ без new и delete

Reading time15 min
Views88K
Привет, хабравчане!

Меня зовут Михаил Матросов, я технический менеджер в компании Align Technology. Сегодня я поработаю капитаном и немного расскажу об основах современного С++.

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

Мне бы хотелось поговорить об этих основах и начну я со своей любимой темы. Будем говорить об операторах new и delete. А точнее, об их отсутствии. Я расскажу, как писать надёжный и современный код на С++ без использования операторов new и delete.

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

Статья будет интересна в первую очередь начинающим разработчикам и регулярам, но я уверен, что и опытные программисты узнают для себя что-то новое.


Изображение взято с сайта behappy.me
Читать дальше →
Total votes 59: ↑59 and ↓0+59
Comments134

Представление движений в 3D моделировании: интерполяция, аппроксимация и алгебры Ли

Reading time14 min
Views29K
В этой статье мне бы хотелось рассказать об одном интересном математическом приеме, который будучи весьма интересным и полезным мало известен широкому кругу людей, занимающихся компьютерной графикой.

Сколько существует разных способов представить обыкновенный поворот в трехмерном пространстве? Большинство людей, когда-либо занимавшихся 3D-графикой или 3D-моделированием, сходу назовут три основных широко распространенных варианта:

  • Матрица поворота 3x3;
  • Задание поворота через углы Эйлера;
  • Кватернионы.

Люди с богатым опытом добавят сюда почему-то не пользующийся популярностью четвертый пункт:
  • Ось поворота и угол.

Мне бы хотелось рассказать о пятом способе представления вращений, который симпатичен тем, что удобен для параметризации, позволяет эффективно строить полиномиальные аппроксимации этих параметризаций, проводить сферическую интерполяцию, и главное, универсален — с минимальными изменениями он работает для любых видов движений. Если вам когда-либо был нужен метод, который позволял бы легко сделать «аналог slerp, но не для чистых вращений, а для произвольных движений, да еще и с масштабированием», то читайте эту статью.
Читать дальше →
Total votes 54: ↑53 and ↓1+52
Comments14

Марковские случайные поля

Reading time4 min
Views45K
Статья посвящена описанию метода CRF (Conditional Random Fields), являющимся разновидностью метода Марковских случайных полей (Markov random field). Данный метод нашел широкое применение в различных областях ИИ, в частности, его успешно используют в задачах распознавания речи и образов, обработки текстовой информации, а также и в других предметных областях: биоинформатики, компьютерной графики и пр.
Читать дальше →
Total votes 30: ↑27 and ↓3+24
Comments13

Первые успехи сложного игрового бота

Reading time5 min
Views36K
(Приглашение к совместному проекту с открытым исходным кодом)

Зачем люди пишут игровых ботов? – Можно назвать много возможных причин, одной из них, безусловно, является чисто академический интерес решения сложной задачи AI. В литературе по философии CS и по философии математики программирование неоднократно сравнивалось с альпинизмом. Трудно сказать, кто первый сделал такое сравнение. На наш взгляд, оно очень подходит и к нашему случаю, поэтому, рискуя показаться не оригинальными, все же сделаем утверждение: написание нетривиального бота для программиста – такой же вызов, как покорение вершины для альпиниста. Чем недоступнее вершина – тем сильнее желание ее покорить. Поэтому, прежде всего, нужно выбрать действительно достойную вершину в интересном горном массиве. Одним из таких массивов со множеством сложных, никем пока не покоренных вершин, является игра "Космические Рейнджеры 2 HD: Революция" (КР2) — продолжение серии игр "Космические Рейнджеры" (КР).
Читать дальше →
Total votes 33: ↑31 and ↓2+29
Comments57

Интерполяция: рисуем плавные графики с помощью кривых Безье

Reading time4 min
Views41K
Доброго времени суток, харбачитатель.

В этой статье мне хотелось бы рассказать об одном придуманном когда-то алгоритме (или скорее всего — переизобретённом велосипеде) построения плавного графика по заданным точкам, используя кривые Безье. Статья была написана под влиянием вот этой статьи и очень полезного комментария товарища lany, за что им отдельное спасибо.

Постановка задачи
Есть массив Y-ков точек, расположенных равномерно по оси X. Нужно получить плавный график, который проходит через все заданные точки. Пример на рисунке ниже:



Всех, кому интересно, прошу под кат.
Читать дальше →
Total votes 24: ↑21 and ↓3+18
Comments53

Метод Монте-Карло для поиска в дереве

Reading time4 min
Views36K


Метод Монте-Карло это алгоритм принятия решений, часто используемый в играх в качестве основы искусственного интеллекта. Сильное влияние он оказал на программы для игры в Го, хотя находит свое применение и в других играх, как настольных, так и обычных компьютерных (например Total War: Rome II). Так же, стоит отметить, что метод Монте-Карло используется в нашумевшей программе AlphaGo, победившей го-профессионала 9-го дана Ли Седоля в серии из 5 игр.

В данной статье хотелось бы рассказать про версию алгоритма Монте-Карло под названием Upper Confidence bound applied to Trees (UCT). Именно после публикации этого алгоритма в 2006-м году, программы для игры в Го сильно усилили свои позиции и достигли значительных успехов в игре против человека.
Читать дальше →
Total votes 19: ↑19 and ↓0+19
Comments8

Космические туннели и железо на голову или зачем нам космодром «Восточный»

Reading time5 min
Views62K

На днях меня попросили проконсультировать инфографику РИА Новости, посвященную первому пуску с космодрома «Восточный». И там будет одно серьезное упрощение из-за ограничений формата материала. На самом деле, космодром «Восточный» нужен нам не из-за того, что большинство гражданских запусков происходит с космодрома «Байконур». Но, чтобы объяснить, зачем он нам нужен, придется рассказать, почему орбиту космического аппарата можно сравнить с туннелем, а также объяснить, что за «железо» падает с неба, и на кого оно падает.
Читать дальше →
Total votes 94: ↑92 and ↓2+90
Comments302

Быстрое умножение многочленов при помощи преобразования Фурье — это просто

Reading time9 min
Views79K
Добрый вечер.
Этот пост посвящён быстрому преобразованию Фурье. Будут рассмотрены прямое и обратное преобразования (в комплексных числах). В следующей части я планирую рассмотреть их применения в некоторых задачах олимпиадного программирования (в частности, одна задача про «похожесть» строк), а также рассказать про реализацию преобразования в целых числах.
БПФ — это алгоритм, вычисляющий значения многочлена степени n=2k в некоторых n точках за время O(n⋅logn) («наивный» метод выполняет ту же задачу за время O(n2)). За то же время можно выполнить и обратное преобразование. Так как складывать, вычитать и умножать массивы чисел гораздо легче, чем многочлены (особенно умножать), БПФ часто применяется для ускорения вычислений с многочленами и длинными числами.
Читать дальше →
Total votes 112: ↑105 and ↓7+98
Comments38

Создание пакета Debian с нуля

Reading time10 min
Views39K
Создание пакета Debian с нуля является своего рода волшебным процессом. Вы могли бы начать гуглить с запросом “Создание пакета Debian с нуля” и получить множество результатов, ни один из которых не стал бы тем, который Вам необходим. Несомненно, Вы найдете большой обзор команд, которые используются в Debian и, если Вы роете достаточно глубоко, Вы сможете все же найти пару команд, которые помогут создать базовый пакет Debian, но не смогут объяснить, что происходит. Более подробную информацию о том, что все же «происходит» Вы можете получить, в данном посте мы попробуем это частично затронуть.

Читать дальше →
Total votes 51: ↑34 and ↓17+17
Comments27

Задача про обезьян и бесконечность

Reading time9 min
Views34K

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



Потрясающий факт, но еще интереснее попытаться понять, сколько же времени ей понадобится для набора конкретного текста. Чтобы не водить лишний параметр — скорость набора обезьяной — будем искать ответ на вопрос: сколько нажатий на клавиши ей потребуется в среднем. А вам очевидно, что строку «abc» набирать гораздо легче чем «aaa»? Решению этой задачи и посвящен этот пост. Попутно объясняется префикс функция и ее свойства.

Читать дальше →
Total votes 27: ↑23 and ↓4+19
Comments88

Стандартная библиотека Visual Studio 2015 и телеметрия

Reading time7 min
Views38K

Преамбула


Программы на C и C++, как правило, проводят бо́льшую часть своей жизни внутри функции main() и функций, прямо или косвенно вызываемых из main(). Тем не менее, на самом деле выполнение программы начинается вовсе не с main(), а с некоторого кода из стандартной библиотеки, поставляемой вместе с компилятором. Таковой код, по идее, должен подготавливать окружение для других функций стандартной библиотеки, которые, возможно, позовёт main(), а также параметры самой main() (под Windows; Unix-системы имеют тенденцию передавать argc/argv/envp в подготовленном виде прямо при запуске процесса, но речь не о них). Симметрично, завершающий return в функции main() — вовсе не последняя инструкция программы, после него следует ещё немного кода из стандартной библиотеки.
В Visual Studio «настоящая» точка входа в программу называется mainCRTStartup. В комплекте с VS идут исходники стандартной библиотеки, в VS2015 определение mainCRTStartup находится в %PROGRAMFILES(X86)%\VC\crt\src\vcruntime\exe_main.cpp, но, впрочем, всю работу выполняет exe_common.inl рядом. Давайте туда посмотрим.
...
        // If this module has any thread-local destructors, register the
        // callback function with the Unified CRT to run on exit.
        _tls_callback_type const * const tls_dtor_callback = __scrt_get_dyn_tls_dtor_callback();
        if (*tls_dtor_callback != nullptr && __scrt_is_nonwritable_in_current_image(tls_dtor_callback))
        {
            _register_thread_local_exe_atexit_callback(*tls_dtor_callback);
        }

        __telemetry_main_invoke_trigger(nullptr);

        //
        // Initialization is complete; invoke main...
        //

        int const main_result = invoke_main();

        //
        // main has returned; exit somehow...
        //

        __telemetry_main_return_trigger(nullptr);

        if (!__scrt_is_managed_app())
            exit(main_result);

        if (!has_cctor)
            _cexit();

        // Finally, we terminate the CRT:
        __scrt_uninitialize_crt(true, false);
        return main_result;
...

Ой, а что это за вызовы __telemetry, обрамляющие вызов main?
Total votes 35: ↑32 and ↓3+29
Comments26

Четвертое поколение

Reading time10 min
Views55K
Атомная энергетика заслуженно считается одной из самых консервативных отраслей, достигшей вершины пути на своей S-кривой. Последние 25 лет внешний наблюдатель не заметил бы изменения в ключевых технология — все те же сборки из тепловыделяющих элементов, греющие или кипятящие воду, с преобразованием тепловой энергии в электрическую. Тем удивительнее тот факт, что свое будущее атомная энергетика видит в 6 революционных концепциях, каждая из которым по своему сдвигает парадигму атомной энергетики в ту или иную сторону.

image
Корпус исследовательского реактора на расплаве солей MSRE, 70е

Важен и тот факт, что все эти концепции возникли не сегодня, а на заре рождения атомной индустрии и проиграли в конкурентной борьбе за звание отраслевого стандарта реакторам с водой под давлением (PWR в западной терминологии или BBЭР в отечественной). Однако, как и в случае с электромобилями, постепенное накопление суммы технологий может вернуть на пьедестал забытых героев зари атомного века.

Четвертое поколение
Total votes 60: ↑60 and ↓0+60
Comments174

Математика на пальцах: ардуино головного мозга или линейно-квадратичный регулятор для управления электродвигателем

Reading time8 min
Views46K

Постановка задачи: как со школьными знаниями дойти до выводов университетского уровня


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

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

Продолжая рабочий эксгибиционизм, знакомлю вас с Bubble Bobble, который живёт у нас с коллегой в кабинете. Он рецензирует статьи для конференции SIGGRAPH.


Читать дальше →
Total votes 21: ↑21 and ↓0+21
Comments78

Information

Rating
Does not participate
Registered
Activity