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

в 14:30, , рубрики: Alga, google summer of code, haskell, hse, hse spb, Алгоритмы, Блог компании Питерская Вышка, вшэ, графы, питерская вышка, Учебный процесс в IT, функциональное программирование

Прошлым летом я участвовал в Google Summer of Code — программе для студентов от компании Google. Ежегодно организаторы отбирают несколько Open Source-проектов, в том числе от таких известных организаций, как Boost.org и The Linux Foundation. Для работы над этими проектами Google приглашает студентов со всего мира. 

Как участник Google Summer of Code 2019 я делал проект в рамках библиотеки Alga с организацией Haskell.org, занимающейся развитием языка Хаскелль — одного из самых известных функциональных языков программирования. Alga — библиотека, представляющая типобезопасное представление для графов в Хаскелле. Она используется, например, в semantic — библиотеке компании Github, строящей по коду семантические деревья, графы вызовов и зависимостей и умеющей их сравнивать. Мой проект состоял в добавлении туда типобезопасного представления для двудольных графов и алгоритмов для этого представления. 

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

GSoC 2019: Проверка графов на двудольность и трансформеры монад - 1
Читать полностью »

в 9:56, , рубрики: array, dba, explain, explain.tensor.ru, postgresql, sql, sql tips and tricks, unnest, Администрирование баз данных, Алгоритмы, базы данных, ненормальное программирование, рекурсия

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

Наиболее «жизненный» пример — вывести 20 самых старых задач, числящихся на списке сотрудников (например, в рамках одного подразделения). Для различных управленческих «дашбордов» с краткими выжимками по участкам работы похожая тема требуется достаточно часто.

SQL HowTo: пишем while-цикл прямо в запросе, или «Элементарная трехходовка» - 1

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

в 8:44, , рубрики: navmesh, Алгоритмы, двоичное разбиение пространства, дерево квадрантов, закон Амдала, Карьера в IT-индустрии, манипулирование, навигационная сетка, офисная политика, поиск A*, психология, техножаргон, технолепет

У программистов есть разные поговорки о трудных проблемах. Наверное, мой любимый вариант: «В информатике две трудные проблемы: недействительность кэша, присвоение имён и ошибки на единицу».

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

А это очень трудно.

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

в 12:53, , рубрики: cleverbot, dialogpt, Google, meena, mitsuku, open AI, xiaoice, Алгоритмы, искусственный интеллект, машинное обучение, нейросети, чатботы

Google представляет Meena, чат-бота на нейросетях - 1

В Google попытались создать чат-бота, максимально похожего на человека. Результатом разработок стала Meena — модель, работающая на основе нейросетей. По оценке Google, чат-бот способен достигнуть большей «человечности» в беседе по сравнению с другими моделями.Читать полностью »

в 11:00, , рубрики: arxiv.org, data science, machine learning, ods, open data science, science, Алгоритмы, Блог компании Open Data Science, математика, машинное обучение, обработка изображений

Рубрика «Читаем статьи за вас». Октябрь — Декабрь 2019 - 1

Привет! Продолжаем публиковать рецензии на научные статьи от членов сообщества Open Data Science из канала #article_essense. Хотите получать их раньше всех — вступайте в сообщество!

Статьи на сегодня:

  1. Poly-encoders: Transformer Architectures and Pre-training Strategies for Fast and Accurate Multi-sentence Scoring (Facebook, 2019)
  2. Implicit Discriminator in Variational Autoencoder (Indian Institute of Technology Ropar, 2019)
  3. Self-training with Noisy Student improves ImageNet classification (Google Research, Carnegie Mellon University, 2019)
  4. Momentum Contrast for Unsupervised Visual Representation Learning (Facebook, 2019)
  5. Benchmarking Neural Network Robustness to Common Corruptions and Perturbations (University of California, Oregon State University, 2019)
  6. DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter (Hugging Face, 2019)
  7. Plug and Play Language Models: A Simple Approach To Controlled Text Generation (Uber AI, Caltech, HKUST, 2019)
  8. Deep Salience Representation for F0 Estimation in Polyphonic Music ( New York University, USA, 2017)
  9. Analyzing and Improving the Image Quality of StyleGAN (NVIDIA, 2019)

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

в 8:57, , рубрики: Алгоритмы, машина Тьюринга, машины состояний, ненормальное программирование, плитки вана, Программирование, тьюринг-полнота

Плитки (домино) Вана были изобретены Хао Ваном в 1961 году для математических задач, но нашли широкое применение в играх при создании тайловой графики. Благодаря им результаты не выглядят повторяющимися, как в 2D-текстурах, так и в 3D-моделях с тайлингом.

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

Это удивительное и непонятное заявление, поэтому в данном посте я немного исследую этот вопрос.

Вкратце о плитках Вана

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

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

Графические примеры, более подробную информацию и ссылки на Shadertoy можно найти здесь: Wang Tiling.

Вот созданный мной пример. Моя графика — это «арт программиста», но надеюсь, идея понятна. Рисунок составлен из 16 тайлов, и для каждой грани есть два различных типа граней.

Плитки Вана для симуляции машин Тьюринга - 1

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

в 22:46, , рубрики: fpga, Алгоритмы, математика, реализация умножения

Лёшенька, Лёшенька, сделай одолжение!
Выучи, Алёшенька, таблицу умножения !
Агния Барто

Домашка по арифметике - 1

Сначала задачка для первоклассника. Дано некоторое положительное число. Нужно умножить на него другое число, заранее неизвестное. Вопрос, как посоветуют это сделать благородные доны ??? Бывалый разраб наверняка скажет, мол мужик, ставь умножитель и не парь мне мОзги. И возможно будет в корне неправ! Ибо кроме монстров от Alterra и Xilinx существует ещё и такое замечательное семейство как iCE-40 от Lattice. Ультрамикропотребляющее. Очень дешевое. Да вот беда, больно мелкие они, и увы, умножителей там нет. Я столкнулся с этим года 4 назад, когда портировал некий ADPCM-кодек с ассемблера adsp-2185 на такой кристалл.
Читать полностью »

в 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 опубликовало претендующую на сенсационность статью о том, как отследить пользователей по коммерчески доступным анонимизированным датасетам с координатами их перемещений, и здесь, на Хабре её вольный перевод с дополнениями от неизвестного корпоративного копирайтера собрал большое количество комментариев разной степени обеспокоенности.

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

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

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