Недавно на Хабре промелькнула интересная задачка про двух мудрецов. Здесь я хочу предложить свой вариант решения и рассказать, как к этому решению можно прийти. Напомню условие:

У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: «Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа».
Султан сказал Али произведение, а Вали – сумму. Мудрецы задумались. Первым нарушил молчание Али.
— Я не знаю этих чисел, — сказал он, опуская голову.
— Я это знал, — подал голос Вали.
— Тогда я знаю эти числа, — обрадовался Али.
— Тогда и я знаю! — воскликнул Вали.
И мудрецы сообщили пораженному султану задуманные им числа.
Назовите эти числа.

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

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

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



Все этапы Яндекс.Алгоритма в этом году пройдут в онлайне, так что поучаствовать в нём смогут и те, кто не готов куда-то ехать. Алгоритм состоит из нескольких отборочных раундов, в каждом из которых нужно решить пять задач за 100 минут. В финал, который состоится 6 августа, выйдут 25 лучших по результатам отбора. Тренировочный раунд, до которого стоит зарегистрироваться, пройдет 3 мая.

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

Сегодня мы предлагаем вашему вниманию очередную публикацию в рамках постоянной рубрики «Лекции Техносферы». В этот раз вы можете изучить материалы по курсу «Методы использования СУБД в интернет-приложениях». Цель курса — изучение топологии, многообразия и основных принципов функционирования систем хранения данных, а также алгоритмов, заложенных в основу как централизованных, так и распределённых систем, демонстрация фундаментальных компромиссов присущих тем или иным решениям. Преподаватели курса: Константин Осипов kostja, Евгений Блих bigbes, Роман Цисык.

Сегодня мы публикуем пятую лекцию из курса «Анализ изображений и видео», прочитанного Натальей Васильевой в петербургском Computer Science Center, который создан по совместной инициативе Школы анализа данных Яндекса, JetBrains и CS-клуба. Всего в программе девять лекций, из которых уже были опубликованы:

1. Введение в курс «Анализ изображений и видео».
2. Основы пространственной и частотной обработки изображений.
3. Морфологическая обработка изображений.
4. Построение признаков и сравнение изображений: глобальные признаки.

Под катом вы найдете план этой лекции, слайды и подробную расшифровку.

Здравствуйте. Думаю, что большинство веб-программистов знает, как работает php-интерпретатор.

Для тех, кто не знает:
Вначале, написанный нами код разбирается лексическим анализатором. Далее, полученные лексемы, передаются в синтаксический анализатор. Если синтаксический анализатор дал добро, то лексемы передаются транслятору, а он, в свою очередь, генерирует так называемые opcodes (operation codes). И только после этого, в дело вступает виртуальная машина PHP (та самая Zend Engine) которая и выполняет наш алгоритм из получившихся opcodes. Opcodes так же называют эдаким php-шным ассемблером.
Данная статья расскажет вам о том, какие opcodes и в каких случаях генерируются. Конечно, рассказать про все opcodes в рамках одной статьи не получится, но в данной статье будет рассмотрен конкретный пример и на его основе мы попытаемся разобраться что к чему у этих opcodes. На мой взгляд, самое главное, что вы узнаете прочитав статью, это то, как на самом деле происходит выполнение ваших исходных текстов и, возможно, это поможет вам в лучшем понимании языка php.

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

При внедрении систем мониторинга и управления IT-инфраструктурой часто приходится сталкиваться с «нестандартными» устройствами. Нередко про такое устройство наверняка известно только то, что оно поддерживает SNMP. Подключение его к проекту придется начать с ответа на вопрос о том, какую информацию о себе оно предоставляет. Обычно для этого проводится полный опрос устройства, и полученные данные анализируются на предмет выявления полезной информации… Но тут, как говорится, есть нюансы. В этой заметке я расскажу об одном таком — о разработанном нами алгоритме быстрого определения «поддерживаемых» устройством MIB-модулей.

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

Вернемся к нашей задаче, нам нужно интеллектуально генерировать карты для IPhone/IPad игры типа «Марио», для начала мы рассмотрим генерацию карты в пределах поля 128х128 кубов.

Понятие факториала известно всем. Это функция, вычисляющая произведение последовательных натуральных чисел от 1 до N включительно: N! = 1 * 2 * 3 *… * N. Факториал — быстрорастущая функция, уже для небольших значений N значение N! имеет много значащих цифр.

Попробуем реализовать эту функцию на языке программирования. Очевидно, нам понадобиться язык, поддерживающий длинную арифметику. Я воспользуюсь C#, но с таким же успехом можно взять Java или Python.

Наивный алгоритм

Итак, простейшая реализация (назовем ее наивной) получается прямо из определения факториала:

static BigInteger FactNaive(int n)
{
    BigInteger r = 1;
    for (int i = 2; i <= n; ++i)
        r *= i;
    return r;            
}

На моей машине эта реализация работает примерно 1,6 секунд для N=50 000.

Далее рассмотрим алгоритмы, которые работают намного быстрее наивной реализации.

Мы продолжаем публиковать лекции Натальи Васильевой, старшего научного сотрудника HP Labs и руководителя HP Labs Russia. Наталья Сергеевна читала курс, посвящённый анализу изображений, в петербургском Computer Science Center, который создан по совместной инициативе Школы анализа данных Яндекса, JetBrains и CS-клуба.



Всего в программе девять лекций. Уже были опубликованы:

• Введение в курс «Анализ изображений и видео».
• Основы пространственной и частотной обработки изображений.
• Морфологическая обработка изображений.

Под катом вы найдете план этой лекции, слайды и подробную расшифровку.

Перевод поста Стивена Вольфрама (Stephen Wolfram) "Frontiers of Computational Thinking: A SXSW Report".
Выражаю огромную благодарность Кириллу Гузенко за помощь в переводе.

---

На прошлой неделе я выступал на SXSW Interactive 2015 в Остине, штат Техас. Вот несколько отредактированная стенограмма моего выступления:

Содержание

Наиболее продуктивный год
Язык Wolfram Language
Язык для реального мира
Философия Wolfram Language
Программы размером в один твит
Вычислительное мышление для детей
Ввод запросов на естественном языке
Масштабная идея: Символьное программирование
Язык для развёртывания
Автоматизация программирования
Масштабные программы
Интернет вещей
Машинное обучение
Исследования Вычисляемой Вселенной
Вычислять, подобно тому, как это делает мозг
Язык как символьное представление
Пост-лингвистические понятия
Древняя история
Чем будет заниматься искусственный интеллект?
Бессмертие и за его пределами
Коробка триллиона душ
Обратно в 2015 год

Продолжаем публиковать материалы наших образовательных проектов. В этот раз предлагаем ознакомиться с лекциями Техносферы по курсу «Алгоритмы интеллектуальной обработки больших объемов данных». Цель курса — изучение студентами как классических, так и современных подходов к решению задач Data Mining, основанных на алгоритмах машинного обучения. Преподаватели курса: Николай Анохин (@anokhinn), Владимир Гулин (@vgulin) и Павел Нестеров (@mephistopheies).



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

Структура публикации

• Оговорка про крен
• Подготовка GPS-трека
• Как из массива векторов получить углы Крылова-Эйлера
• Имитация показаний гироскопа
• Вектор ускорения свободного падения и направление «на север»
• Имитация показаний акселерометра, компаса и барометра

Для отладки алгоритма, работающего с датчиками инерциальной навигации, может потребоваться имитировать показания этих самых датчиков. Например, вы имеете отладочную последовательность точек пути, имитирующую определённую ситуацию. Вы можете иметь некий GPS-трек, имеющий особенности, или напротив их не имеющий. В моём случае результат полевых испытаний есть, а плата ещё не готова (в производстве) — нужно чем-то заняться.

Непростые простые числа

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

Наверное, каждый из нас сталкивался с ситуацией, когда нужно выполнить большой объем вычислений или передать/получить большой объем информации за ограниченный промежуток времени. А сколько из нас остановилось на последовательном алгоритме и закрыли глаза на продолжительность выполнения? Ну и что, что 20 часов ведется расчет/отправка/получение (подчеркнуть нужное) каких-то данных? Ну, я «выжал» из системы все, что можно, быстрее не получится… При этом серверное железо загружено на минимум.

На самом деле, почти всегда доступна альтернатива в виде распараллеливания выполняемой задачи. Конечно, параллельные алгоритмы несколько сложнее — балансировка нагрузки, синхронизации между потоками, а так же, в случае разделяемых ресурсов, борьба с ожиданием на блокировках и избегание deadlock’ов. Но, как правило, оно того стоит.

Об этом мы сегодня и поговорим… в контексте 1С Предприятия.

Что это такое?

Полностью гомоморфное шифрование (Fully Homomorphic Encryption) очень долго было самым ярким открытием в молодой и бурно развивающейся области Computer Science — криптографии. Вкратце, такой тип шифрования позволяет делать произвольные вычисления на зашифрованных данных без их расшифровки. Например, гугл может осуществлять поиск по запросу не зная, что это за запрос, можно фильтровать спам, не читая писем, подсчитывать голоса, не вскрывая конверты с голосами, делать DNA тесты, не читая DNA и многое, многое другое.

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

Здорово, правда? И это не из области фантастики — это то, что уже можно «теоретически» воплотить в жизнь.

Как вы думаете, что машины с искусственным интеллектом сегодня уже умеют делать, а что нет?


На фото робот, умеющий складывать полотенца.

В дистанционном курсе CS188.1x Artificial Intelligence от Калифорнийского университета в Беркли профессор Dan Klein приводит список некоторых задач в области искусственного интеллекта. Часть из них уже решены (полностью или частично), а другая часть — еще нет. Курс посвящен алгоритмам ИИ, на которых базируются многие современные интеллектуальные системы. Хочется вкратце поделиться тем, с чего он начинается и подробней рассказать про первое практическое задание.

Кручинин Дмитрий, Долотов Евгений, Кустикова Валентина, Дружков Павел, Корняков Кирилл

Введение

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

Глубокое обучение (deep learning) рассматривает методы моделирования высокоуровневых абстракций в данных с помощью множества последовательных нелинейных трансформаций, которые, как правило, представляются в виде искусственных нейронных сетей. На сегодняшний день нейросети успешно используются для решения таких задач, как прогнозирование, распознавание образов, сжатие данных и ряда других.

Совершенно случайно узнал об интересной задаче, которая очень даже может взбодрить.

Задача:

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

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

Так появилось «Электрокардиографическое дерево Пифагора».