Алгоритмы *

В школе Skyeng мы редко обучаем английскому с нуля. Обычно к нам приходят люди, уже обладающие каким-то набором знаний, причем этот набор бывает самым разным. Для того, чтобы обучение было полезным, нам нужно как-то определить границу этих знаний. Если в случае грамматики это относительно просто (выясняется на первых занятиях с методистом), то уточнение границ словарного запаса – задача не самая тривиальная. Для ее решения мы разработали и запустили инструмент WordMash.

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

Но ведь интереснее в него запихнуть муху.



Перед EDISON Software Developement поставили задачу написать софт для микротомографа. О том, как они успешно справились с задачей, была статья chookcha на Хабре (Как за 5233 человеко-часа создать софт для микротомографа) с описанием алгоритмов, математических методов, реализации и отладки.

Ненасытные читатели засыпали нас вопросами, на которые мы, наконец-то, сформулировали ответы…

Про чемпионат

Международная олимпиада ACM ICPC – крупнейшее мероприятие среди командных студенческих соревнований по программированию в мире. Проводится олимпиада с 70-х годов (тогда это было скорее соревнование между университетами США), с конца 90-х в ней активно участвуют и другие страны. Университет ИТМО в 2015 году стал шестикратным победителем ACM ICPC.

Естественно, интерес к олимпиаде проявляют не только сами вузы-участники, но и тысячи людей по всему миру. И для того, чтобы ACM ICPC было не «камерным» мероприятием для участников и их тренеров, существует онлайн-трансляция финала олимпиады, за которой можно наблюдать «в прямом эфире» и по окончании мероприятия (трансляцию финала 2015 года можно посмотреть здесь). О том, как организована трансляция, какие интересные технические решения используются в процессе ее проведения, мы и расскажем сегодня «из первых уст» – от лица ее организаторов.

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

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

Что нам понадобится:
• Установленный Python 2.7 с библиотеками NumPy и PIL
• OpenCV 2-й версии

Здесь ссылка на материал по установке всех необходимых компонентов. Установка всего необходимого не составит труда.

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

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

По мере изучения вопроса я обнаружил, что идея сама по себе не то чтобы очень нова – в нью-йоркской подземке аналогичные соревнования проходят с 1966 года. Что же касается московского метро, то ЖЖ-пользователь estrella-de-sur полгода назад проехал его за 12 часов 36 минут (расчётное время – 11 часов 50 минут) по правилу «один шаг на каждую станцию». Но у нас была другая задача – мы хотели выйти на каждой станции и по возможности красиво её сфотографировать. Это означало, что нам в большинстве случаев придётся ждать на ней следующего поезда. Исходя из этого я и строил расчёт.

Предупреждение: если вы умеете решать задачу коммивояжёра на 200 узлах (с помощью генетических алгоритмов или без них) – вас, скорее всего, ждут в другом месте. Можете просто пролистать пост и посмотреть картинки.

Работу каждой программы можно ускорить минимум в десять раз

Рабочая установка разработчиков Smart Engines

Мы расскажем о нескольких приемах ускорения распознавания с помощью OCR Tesseract. Всё рассказанное было использовано в реализации проекта, смысл которого состоял в классификации большого числа образов страниц деловых документов (таких документов как паспорт, договор, контракт, доверенность, свидетельство о регистрации и т.п.) и сохранении результатов в электронном архиве. Часть алгоритмов классификации была основана на анализе собственно образов страниц, а часть – на анализе извлечённых из образа текстов. Для извлечения текстов было необходимо распознавание с помощью OCR.

Сегодня в дайджесте (первый выпуск) собраны: наиболее интересные публикации о разработках и открытиях, сделанных в Университете ИТМО; видеорепортажи о работе ученых и исследователей; статьи о том, как ведется подготовка студентов, занимающихся спортивным программированием; а также ближайшие мероприятия Университета, принять участие в которых может любой желающий.

Какие алгоритмы используют социальные сети, чтобы осуществлять поиск по графу друзей? Как телекомпании выбирают, какую рекламу показывать, чтобы максимизировать прибыль? Как собрать геном из миллионов фрагментов? Как вычислить кратчайший путь из Нью-Йорка в Маунтин Вью в тысячи раз быстрее, чем это делают классические алгоритмы?

На Coursera появилась еще одна полезная специализация, созданная при участии Яндекса, — «Алгоритмы и структуры данных». Среди преподавателей не только представители Яндекса, Вышки, петербургского Computer Science Center, но и лекторы Калифорнийского университета в Сан-Диего, поэтому на этот раз все курсы специализации англоязычные.



Всего их пять, в конце слушателей ждет финальный проект. Один из них связан с биоинформатикой, второй — с поиском кратчайших путей в настоящих дорожных сетях и графах. В формате специализации все материалы доступны бесплатно. Оплата понадобится только в том случае, если вы захотите отправлять домашние задания на проверку и получить сертификат. Тогда вам нужно будет запрограммировать и сдать около 100 задач в тестирующую систему. Сделать это можно на C, C++, C#, Haskell, Java, JavaScript, Python2, Python3, Ruby и Scala.

Сегодня начинается первый курс — Algorithmic Toolbox. Под катом — программа специализации, информация о преподавателях и их мнение о том, кому она будет полезна и почему.

Продолжаю тему печати PDF документов из под .NET.

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

Введение

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

Надеюсь, данный пост не станет причиной ночных кошмаров у особо чувствительных хабрачитателей. В этом посте я постараюсь рассказать о простом способе увеличения ГРИП. Это весьма актуальная проблема для тех, кто работает с микроскопом и занимается макрофотографией. Суть проблемы в том, что на больших увеличениях размытие удаленных от точки фокуса предметов становится большой проблемой. Это в традиционной портретной съемке размытие фона позволяет подчеркнуть объект. В научной микрофотографии это чаще всего негативный эффект. Радует, что есть методика focus-stacking, которая позволяет сшить в единую резкую картинку стопку фотографий с разной точкой фокусировки. Но хватит рассуждать об абстрактном. Внесите клеща в студию!

Часть 1
Часть 2
Предисловие
История знает примеры, когда открытия давались человечеству волей случая: так оно узнало об обжиге глины, порохе и резине, а вот кремниевый транзистор или полиэтилен вряд ли кому-нибудь удалось бы открыть случайно. Архитектор, проектируя мост, чтобы быть уверенным в надежности возводимой конструкции, обязан иметь хорошее представление о свойствах механических напряжений. Если Вы вдруг раздумываете над тем, как создать алгоритм, позволяющий машине самостоятельно ориентироваться в лесной чаще или без чьей-либо помощи изучать новые для нее предметы, возможно содержание следующей главы, посвященное понятиям "предмет" и "место", окажется для вас полезным. Читать ее без больших потерь можно независимо от предыдущих глав, введение к части 1 поможет разъяснить некоторые детали.

Escher: man with cuboid

Предметы и места

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

«Пусть тахорги в страхе воют,
Издавая визг и писк!
Ведь на них идет войною
Структуральнейший лингвист!»

• Очень жесткий правдоруб.
• Мог бы стать физиком-теоретиком (как Ричард Фейнман, который тоже родился 11 мая), но выбрал несуществующую на тот момент профессию — программист.
• Носит имя алгоритма поиска кратчайшего пути. Алгоритм был создан при решении железячной задачи «О нахождении оптимального пути передачи электрического тока всем существенным элементам цепи, минимизируя при этом расход меди».
• Непримиримый враг goto.
• Инициатор мема Considered harmful. «GOTO Statement Considered Harmful», "„GOTO Considered Harmful“ Considered Harmful", «„«GOTO Considered Harmful» Considered Harmful“ Considered Harmful?»
• Автор концепции семафора.
• Разработчик операционной системы THE (Technische Hogeschool Eindhoven).
• Стоял у истоков структурного программирования и распределенных вычислений.
• Не написал ни одной статьи на компьютере.

В обычной жизни Э.В.Дейкстра был чудаком: предпочитал простую ручку компьютеру, в его доме не было телевизора, он не пользовался мобильным телефоном, не смотрел кино. Когда его коллеги подготовили и издали к 60-летнему юбилею специальный сборник, Дейкстра ответил каждому из них личным благодарственным письмом, написанным от руки (61 адресат). Ученому его уровня и положения полагался секретарь, но Дейкстра отказался от этой привилегии и все предпочитал делать сам. Любил музыку и был хорошим пианистом.

Под катом несколько цитат Дейкстры, пара сокращенных эссе и список статей на русском языке.

В нашем блоге на Хабре мы не только рассматриваем различные технологии финансового рынка, но и описываем различные инструменты, использующиеся аналитиками в ходе его анализа. В частности, не так давно мы писали о том, как гипотезу случайного блуждания можно использовать для прогнозирования состояния финансового рынка. Количественный аналитик хедж-фонда NMRQL Стюарт Рид опубликовал на сайте Turing Finance результаты своего исследования, где применил эту гипотезу для тестирования случайности поведения рынков.

Идея заключалась в следующем: генераторы случайных чисел «прогоняются» через группу тестов NIST, чтобы понять, где возникает уязвимость, позволяющая использовать неэффективность рынка для извлечения прибыли. В ходе эксперимента автор пришел к выводу, что поведение рынка нельзя описать в терминах простого подбрасывания монетки, как считают отдельные авторитетные ученые. Некоторым тестам удалось зафиксировать определенный уровень «шума» в поведении рынка. Один из них – тест на линейную сложность – привлек внимание автора, поскольку напоминает об идее отношения случайности и степени сжатия.

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

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

Доброго времени суток.
А знаете ли вы, что не все хеш таблицы одинаково полезны? Сейчас я расскажу вам историю, как одна плохая хеш таблица скушала всю производительность, и не поморщилась. И как исправление этой хеш таблицы ускорило код почти в 10 раз.
Конечно, согласно теме — в статье речь пойдет о Delphi, но даже если вы не Delphi разработчик, то все равно советую заглянуть под кат, а после прочтения статьи в исходный код хеш таблиц, которые вы используете. А Delphi разработчикам я советую вообще отказаться от стандартного TDictionary.

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

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

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



Всех, кому интересно, прошу под кат.

Клод Шеннон любил на выходных вместе с женой Бетти и коллегой сгонять в Лас-Вегас, чтобы поиграть в блэкджек. Они не поленились и даже разработали первый wearable-компьютер, чтобы заниматься «подсчетом карт» (метод High-Low).



Сегодня, 30 апреля 2016 года исполняется 100 лет со дня его рождения. Кстати, Шеннон является дальним родственником Томаса Эдисона.

Под катом немного интересных достижений именинника.

А не замахнуться ли нам на Эдсгера нашего Дейкстру?

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

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