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

Привет habr.

На geektimes habr было уже несколько статей про abc-гипотезу (например в 2013 и в 2018 годах). Сама история про теорему, которую сначала много лет не могут доказать, а потом столько же лет не могут проверить, безусловно заслуживает как минимум, художественного фильма. Но в тени этой чудесной истории, сама теорема рассматривается черезчур поверхностно, хотя она не менее интересна. Уже хотя бы тем, что abc-гипотеза — одна из немногих нерешенных проблем современной науки, постановку задачи которой сможет понять даже пятиклассник. Если же эта гипотеза действительно верна, то из нее легко следует доказательство других важных теорем, например доказательство теоремы Ферма.

Не претендуя на лавры Мотидзуки, я тоже решил попробовать решил проверить с помощью компьютера, насколько выполняются обещанные в гипотезе равенства. Собственно, почему бы нет — современные процессоры ведь не только для того чтобы в игры играть — почему бы не использовать компьютер по своему основному (compute — вычислять) предназначению…

Кому интересно что получилось, прошу под кат.
Читать полностью »

Как мы научили нейросеть определять документы - 1

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

Для чего это понадобилось

Чтобы разгрузить сотрудников и обезопасить людей от мошенников. Мы применяем новую нейросеть в двух сферах: когда пользователь восстанавливает доступ к странице и для скрытия личных документов из общего поиска.

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

в 14:30, , рубрики: ajax, ASCII, C#, c++, clang, computer, computer science, cs50, cs50 на русском, CS50 на русском языке, css, david, David J. Malan, dom, gdb, harvard, html, http, IP, java, javascript, malan, mvc, onlineuniver, php, return, rsa, science, Scratch, sql, tcp, Алгоритмы, аргументы командной строки, асимптотическая нотация, библиотеки, Бинарная нотация, бинарный поиск, Булевые выражения, быстрая сортировка, видеокурс, Гарвард, глобальные переменные, деревья, Дополнительные видео, Компиляторы, компьютерные науки, линейный поиск, массивы, методы, область видимости, обучение, основы программирования, очереди, переменные, приведение типа, приоритетность, Программирование, программист, рекурсивные деревья, рекурсия, связные списки, символьные строки, сортировка вставками, сортировка выбором, сортировка пузырьком, сортировка слиянием, стили, структуры, технологии, указатели, условия, хеш-таблицы, циклы, шифр, языки программирования

В этой статье я хочу немного рассказать о самом лучшем в мире курсе по программированию.

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

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

image

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

Суть задачи

В процессе медицинской диагностики может возникнуть необходимость исследовать сосуды пациента. Такое исследование называется ангиографией. С появлением томографов в дополнение к классической ангиографии появились методы МРТ и КТ ангиографии, которые в отличие от традиционной ангиографии, дающей только плоскую картинку в одной проекции, позволяют получить полное трехмерное представление сосудов. Для проведения таких исследований пациенту в кровь вводится контраст — специальное вещество, делающее сосуды на снимках более яркими. В зависимости от предполагаемого диагноза, врач или оценивает общую картину, или пытается найти конкретные участки сосудов, в которых возникли проблемы. Если участок сосуда сужен и пропускает меньше крови, чем должен, то это место называется стенозом.

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

Одна из задач врача — найти стенозы и оценить, насколько они опасны. Задача же разработчика, как обычно, облегчить работу конечного пользователя. Для этого необходимо построить полную 3D модель стенок сосуда и провести их первичный анализ. Это является большой и интересной задачей, однако, в её основе лежит более простая и известная проблема — построение центральной линии сосуда.
Читать полностью »

Делаем проект по машинному обучению на Python. Часть 3 - 1

Перевод A Complete Machine Learning Walk-Through in Python: Part Three

Многим не нравится, что модели машинного обучения представляют собой чёрные ящики: мы кладём в них данные и безо всяких объяснений получаем ответы — часто очень точные ответы. В этой статье мы постараемся разобраться, как созданная нами модель делает прогнозы и что она может рассказать о решаемой нами задаче. И завершим мы обсуждением самой важной части проекта по машинному обучению: задокументируем сделанное и представим результаты.

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

Вчера стартовал новый Яндекс.Блиц — на этот раз конкурс будет интересен разработчикам интерфейсов. Обладателям мест с первого по пятое мы предложим устроиться к нам по упрощённой схеме: одна секция собеседования вместо четырёх. Тем самым Блиц остаётся наиболее быстрым способом попасть в Яндекс.

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

Алгоритмические задачи во фронтенде. Примеры и конкурс Яндекса - 1

Блиц — хороший повод поговорить об истории алгоритмических задач, возникающих в промышленном фронтенде, и о том, как они отличаются от конкурсных.
Читать полностью »

Этой лекции не было в расписании, но ее пришлось добавить, чтобы не возникало окна между занятиями. Лекция, в сущности, посвящена тому, как мы знаем то, что мы знаем, если, конечно, мы и в самом деле это знаем. Эта тема стара как мир – она обсуждается последние 4000 лет, если не дольше. В философии для ее обозначения создан специальный термин – эпистемология, или наука о знании.

Я бы хотел начать с первобытных племен далекого прошлого. Стоит отметить, что в каждом из них существовали миф о сотворении мира. По одному древнеяпонскому поверью, некто взболтал грязь, из брызг которой появились острова. Подобные мифы были и у других народов: например, израильтяне верили, что Бог шесть дней творил мир, после чего устал и закончил творение. Все эти мифы схожи – хотя сюжеты их довольно разнообразны, все они пытаются объяснить, почему существует этот мир. Я буду называть такой подход теологическим, поскольку он не предполагает объяснений, кроме как «это произошло по воле богов; они сделали то, что посчитали нужным, и так появился мир».

В районе VI века до н. э. философы античной Греции начали задавать более конкретные вопросы – из чего состоит этот мир, каковы его части, а также попытались подойти к ним скорее рационально, нежели теологически. Как известно, они выделяли стихии: землю, огонь, воду и воздух; у них было еще множество других понятий и убеждений, и медленно, но верно все это преобразовалось в наши современные представления о том, что мы знаем. Тем не менее, тема эта озадачивала людей во все времена, и даже древние греки задавались вопросом, как они знали то, что они знали.
Читать полностью »

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

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

Однако, можно придумать нечто более надежное — Kronos. В статье мы посмотрим на алгоритм учета причинно-следственной связи и его применение для построения Key-Value хранилища с распределенными транзакциями.

image

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

Делаем проект по машинному обучению на Python. Часть 2 - 1

Перевод A Complete Machine Learning Walk-Through in Python: Part Two

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

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

Весь код проекта лежит на GitHub, а здесь находится второй блокнот, относящийся к текущей статье. Можете использовать и модифицировать код по своему усмотрению!
Читать полностью »

image

Пару месяцев назад для меня наступил исторический момент. Мне перестало хватать стандартных средств операционной системы для измерения времени. Понадобилось измерять время с наносекундной точностью и с наносекундными накладными расходами.

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

Так как на компьютере можно измерять много разных типов времени, сразу уточню, что здесь речь пойдет о «времени по секундомеру». Или wall-clock time. Оно же real time, elapsed time и т.п. То есть простое «человеческое» время, которое мы засекаем в начале исполнения задачи и останавливаем в конце.

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