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

в 10:14, , рубрики: BitFunnel, microsoft, Алгоритмы, амортизационный анализ, битовое поле, вопросы Ферми, головоломки, дизайн механизмов, задача про лампочки, Занимательные задачки, Карьера в IT-индустрии, круглые люки, оптимизация, рефакторинг, собеседования, управление персоналом, управление проектами

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

Когда я спрашиваю людей в модных больших технологических компаниях, почему на собеседовании так обязательно спрашивать об алгоритмах, самый распространённый ответ — что-то вроде: «У нас такой масштаб, мы не можем позволить, чтобы кто-то случайно написал функцию O(n^2) и повалил всю систему»1. Что особенно забавно, в последнее время я немало применял на практике эти алгоритмы и решал реальные проблемы, но не могу пройти собеседования, где о них спрашивают! Думаете, я проваливаю половину собеседований или что-то в этом роде? Нет, больше половины. Я участвовал примерно в 40 «настоящих» собеседованиях и прошёл, может, одно или два. Или ни одного2.

Когда я написал черновик этой статьи, друзья посчитали его занудным, потому что я провалил слишком много собеседований. Они говорят, нужно свести все неудачи в таблицу, потому что никто не станет читать десять страниц текста с длинным перечнем неудач. Хороший совет. Уже работаю над таблицей.
Читать полностью »

в 13:12, , рубрики: Алгоритмы, Анализ и проектирование систем, Занимательные задачки, логические игры, Научно-популярное, общая теория систем, системный анализ, системный подход, системология, системы, Стратегия, шахматы

image

Предисловие

Существует такой тип людей, для которых исследования и создание сложных и функциональных систем — высшая степень удовольствия. К такому типу можно отнести и меня. Любой целостный объект, обладающий единством всей своей структуры, материального, социального и абстрактного миров обладает системностью: человек, семья (да и любой социальный институт), биосфера, химические вещества и пр. Системность присутствует даже в неявных вещах.

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

в 20:11, , рубрики: assisted gps, big data, data engineering, gis, gps, location based services, POI, point of interest, Алгоритмы, бизнес-кейс, большой брат следит за тобой, Геоинформационные сервисы, Глобальные системы позиционирования, информационная безопасность, кейс по проекту, ликбез, приватность это миф, эвристические алгоритмы

Данная статья является частью серии «Кейс Locomizer», см. также
• Как мы за два года ускорили расчёт тепловой карты в 20000 раз (послезавтра)
• Открываем One Ring — инструментарий для гибкой конфигурации сложных процессов обработки данных на Spark в облаке (скоро)

Здравствуйте.

КДПВ: Тепловая карта, построенная алгоритмами Locomizer для KFC

Недавно издание The New York Times опубликовало претендующую на сенсационность статью о том, как отследить пользователей по коммерчески доступным анонимизированным датасетам с координатами их перемещений, и здесь, на Хабре её вольный перевод с дополнениями от неизвестного корпоративного копирайтера собрал большое количество комментариев разной степени обеспокоенности.

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

Но есть и доля истины по ту сторону чёрного зеркала, возможно, куда большая. Или интересная.
Читать полностью »

в 17:18, , рубрики: android development, kotlin, layers, Алгоритмы, маппер, маппинг, Разработка под android

Маппинг данных – один из способов для разделения кода приложения на слои. Маппинг широко используется в Android приложениях. Популярный пример архитектуры мобильного приложения Android-CleanArchitecture использует маппинг как в оригинальной версии (пример маппера из CleanArchitecture), так и в новой Kotlin версии (пример маппера).

Маппинг позволяет развязать слои приложения (например, отвязаться от API), упростить и сделать код более наглядным.

Пример полезного маппинга изображен на схеме:

Практичные способы маппинга данных в Kotlin - 1

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

в 14:58, , рубрики: автоматизация, Алгоритмы, Блог компании Инфосистемы Джет, машинное обучение

Автоматическое машинное обучение: когда data scientist’ы будут не нужны - 1

Уже третий год мы проводим форум по искусственному интеллекту RAIF (Russian Artificial Intelligence Forum), на котором спикеры из мира бизнеса и науки рассказывают о своей работе. Самыми интересными докладами мы решили поделиться. В этом посте Андрей Фильченков, руководитель лаборатории машинного обучения ИТМО, рассказывает всю правду об AutoML.

В рамках прошедшего в Сколково форума RAIF 2019, организованного «Инфосистемы Джет», я выступил с докладом, в котором рассказал об AutoML и перспективах его использования. Поскольку я ученый, мне не так уж часто приходится выступать на подобных мероприятиях: обычно я участвую в научных конференциях.

Одной из основных областей, которой мы занимаемся, является AutoML. Кроме того, я являюсь техническим директором двух небольших стартапов. Один из них – Statanly technologies – создает сервисы AutoML и занимается анализом данных. Фактически я являюсь тем человеком, который придумывает алгоритмы, внедряет их и пользуется ими. Наверное, я единственный человек, который может рассказать про AutoML со всех трех возможных позиций.
Читать полностью »

в 11:48, , рубрики: Алгоритмы, Блог компании OTUS. Онлайн-образование, дерево отрезков

Накануне очередного запуска курса «Алгоритмы для разработчиков» мы провели открытый урок. На нём поговорили об известной идее дерева отрезков, обсудили, как его строить, обновлять и быстро O(log n) вычислять сумму чисел любого отрезка данного массива. Алгоритм очень простой и экономный: нужно O(n) памяти. Для закрепления материала решили олимпиадную задачу.

Дерево отрезков: просто и быстро - 1

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

в 11:09, , рубрики: agda, computer science, coq, haskell, serokell, Алгоритмы, будущее программирования, зависимые типы, Программирование, Промышленное программирование, функциональное программирование

Зависимые типы в Haskell: почему это будущее разработки программного обеспечения - 1

В Serokell мы занимаемся не только коммерческими проектами, но стараемся изменить мир к лучшему. Например, работаем над улучшением главного инструмента всех хаскелистов – Glasgow Haskell Compiler (GHC). Мы сосредоточились на расширении системы типов под впечатлением от работы Ричарда Айзенберга "Зависимые типы в Haskell: теория и практика".

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

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

в 11:00, , рубрики: classification, data mining, loss function, machine learning, margin, ods, ods.ai, open data science, python, support vectors, SVM, Алгоритмы, Блог компании Open Data Science, машинное обучение, опорные вектора

Привет всем, кто выбрал путь ML-самурая!

Введение:

В данной статье рассмотрим метод опорных векторов (англ. SVM, Support Vector Machine) для задачи классификации. Будет представлена основная идея алгоритма, вывод настройки его весов и разобрана простая реализация своими руками. На примере датасета $Iris$ будет продемонстрирована работа написанного алгоритма с линейно разделимыми/неразделимыми данными в пространстве $R^2$ и визуализация обучения/прогноза. Дополнительно будут озвучены плюсы и минусы алгоритма, его модификации.

image
Рисунок 1. Фото цветка ириса из открытых источников

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

в 12:14, , рубрики: compact, implicit, LOUDS, maps.me, sparse array, succinct, Алгоритмы, Блог компании Mail.Ru Group, деревья поиска, компактные структуры данных, массивы данных, математика, оптимизация, Программирование

image

Как быть, если дерево поиска разрослось на всю оперативку и вот-вот подопрет корнями соседние стойки в серверной? Что делать с инвертированным индексом, жадным до ресурсов? Завязывать ли с разработкой под Android, если пользователю прилетает «Память телефона заполнена», а приложение едва на половине загрузки важного контейнера?

В целом, можно ли сжать структуру данных, чтобы она занимала заметно меньше места, но не теряла присущих ей достоинств? Чтобы доступ к хэш-таблице оставался быстрым, а сбалансированное дерево сохраняло свои свойства. Да, можно! Для этого и появилось направление информатики «Succinct data structures», исследующее компактное представление структур данных. Оно развивается с конца 80-х годов и прямо сейчас переживает расцвет в лучах славы big data и highload.

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

в 8:37, , рубрики: c++, merge sort, mergesort, newgenerationsort, O(n), quick sort, quicksort, Алгоритмы, алгоритмы сортировки, быстрая сортировка, ненормальное программирование, Программирование, сортировка вставками, сортировка выбором, сортировка нового поколения, сортировка слиянием

imageМногие программисты думают, что Quick Sort — самый быстрый алгоритм из всех существующих. Отчасти это так. Но работает она действительно хорошо только если правильно выбран опорный элемент (тогда сложность составляет O (n log n)). В противном же случае асимптотика будет примерно такой же как и в пузырика (то-есть O (n2)).
При этом, если массив уже отсортирован, то алгоритм всё-равно будет работать не быстрее, чем за O (n log n)

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

«Дело было вечером, делать было нечего», — Сергей Михалков.

Требования:

  1. Лучший случай O (n)
  2. Средний случай O (n log n)
  3. Худший случай O (n log n)
  4. В среднем быстрее быстрой сортировки

Для понимания темы, нужно знать:

А теперь давайте обо всём по порядку

Чтобы наш алгоритм всегда работал быстро, нужно чтобы в среднем случае асимптотика была хотя бы O (n log n), а в лучшем — O (n). Все мы прекрасно знаем, что в лучшем случае сортировка вставками работает за один проход. Но в худшем ей придётся гонять по массиву столько раз, сколько в нём элементов.

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

1...1020...525354...6070...324
Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js