Алгоритмы *

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

В этой статье я хочу рассказать о том, как реализовывал алгоритмы, связанные с базисами Грёбнера, на языке Haskell. Надеюсь, кому-нибудь мои идеи и объяснения окажутся полезными. Я не собираюсь вдаваться в теорию, так что читателю стоит быть знакомым с понятиями полиномиального кольца, идеала кольца и базиса идеала. Советую прочитать вот эту книгу МЦНМО, в ней подробно расписана вся необходимая теория.

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

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

Если вас заинтересовало, прошу под кат.

Мотивация

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

Этот текст задуман как популярное введение в теорию формальных языков и грамматик. Эта теория считается (и, надо сказать, справедливо) довольно сложной и запутанной. На лекциях студенты обычно скучают и экзамены тем более не вызывают энтузиазма. Поэтому и в науке не так много исследователей в этой тематике. Достаточно сказать, что за все время, с зарождения теории формальных грамматик в середине 50-х годов прошлого века и до наших дней, по этому научному направлению было выпущено всего две докторских диссертации. Одна из них была написана в конце 60-х годов Алексеем Владимировичем Гладким, вторая уже на пороге нового тысячелетия — Мати Пентусом.

Далее в наиболее доступной форме описаны два основных понятия теории формальных языков: формальный язык и формальная грамматика. Если тест будет интересен аудитории, то автор дает торжественное обещание разродиться еще парой подобных опусов.

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

Под катом будут рассмотрены некоторые свойства речевых сигналов и особенностей их восприятия человеком, объективные и субъективные способы оценки качества этих сигналов.

P.S. В данной статье использована моя дипломная работа, защищённая в 2011 году в Московском Авиационном Институте на факультете Радиоэлектроники Летательных Аппаратов каф. 402. Ранее работа нигде не публиковалась.

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

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

Доброго времени суток, Хабрахабр!
Этот пост для тех, кто хочет научиться строить Фундаментальную Матрицу решений Системы Линейных Дифференциальных Уравнений, но боится.

Предыстория

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

Введение

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

Это топик-перевод статьи Eller's Algorithm. В ней рассказывается о способе программной генерации лабиринтов. Дальнейшее повествование идет от лица автора.

 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __  
|__   |__       __ __|__   |   __|  |  |  |  |
|__   |__   |__|   __ __|   __ __      |     |
|        |  |  |     |  |__      |__|  |  |  |
|__|__|  |  |   __|   __|__   |   __|__|  |__|
|   __|  |     |__ __ __|  |  |__|  |     |  |
|  |  |  |  |__|  |__   |  |   __|__ __|  |  |
|  |__    __    __ __    __|  |   __   |  |  |
|  |  |  |  |      __|  |   __|  |  |__|  |  |
|  |     |     |__   |  |  |  |  |  |__    __|
|  |  |__|__|__ __|  |     |  |  |      __|  |
|__ __|  |  |  |__   |__|   __|     |   __ __|
|   __|  |   __|__      |__   |__|  |__    __|
|  |  |     |  |     |__|  |   __    __|   __|
|   __|  |__ __|__|      __|  |  |     |  |  |
|   __ __   |      __|__|  |__   |  |  |__|  |
|__ __ __|__ __|__ __ __ __ __|__|__|__ __ __|

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

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

В 2012м я начал потихоньку делать pymorphy2 (github, bitbucket) — думаю, самое время представить эту библиотеку тут: pymorphy2 может работать в сотни раз быстрее, чем pymorphy (втч без использования C/C++ расширений) и при этом требовать меньше памяти; там лучше словари, лучше качество разбора, лучше поддержка буквы ё, проще установка и более «честный» API. Из негатива — не все возможности pymorphy сейчас реализованы в pymorphy2.

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

Если позволите, начну без вступления и предыстории.

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

На известной шуточной конференции SIGBOVIK2013, которая проходила 1-го апреля 2013-го года и представляет собой, как правило, фальшивые шуточные исследования д-р Том Мерфи подготовил работу, которая, на мой взгляд, довольно интересна.
Если вкратце — он научил программу играть в старые добрые денди-игры на NES-эмуляторе. Как это происходит?

Привет. В этом посте мы продолжим экспериментировать с ограниченной машиной Больцмана. В предыдущем посте о регуляризации в РБМ мы увидели как можно получить более локальные фичи, которые обладают большей обобщающей способностью. Но мы не оценили их робастность по сравнению с более простыми и быстрыми алгоритмами. Для этого эксперимента мы обратимся к линейному методу главных компонент (вы можете ознакомиться с этим методом и глянуть реализацию на c# в моем первом посте). Желающим ознакомиться с первоисточником по теории сжатия размерности с использованием РБМ рекомендую глянуть статьи Джеффри Хинтона тут и тут. Мы же продолжим тестирование на множестве печатных больших букв: обучим РБМ, построим главные компоненты, сгенерируем сжатые представления данных, а из них восстановим первоначальные изображения, и затем оценим разницу между оригинальными изображениями и восстановленными.

Лишь вследствие нашей слабости, вследствие нашего невежества случайность для нас существует

А. Пуанкаре

Чем больше люди постигали тайны Вселенной, тем ближе они приближались к той точке незнания, в которой их предки все приписывали богам. Теперь это называется – случайность. И хотя Эйнштейн не верил в случайность – он говорил «Бог не играет в кости», – он в числе первых из списка: Эйнштейн, Шредингер, Лаплас…

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

К услугам программ-проксификаторов прибегали многие, но как они работают знают не все. Я расскажу об алгоритме положенному в их основу и практической реализации.

Группа учёных, работающих в Австралийском Центре Устройств Сверхвысокой Пропускной Способности для Оптических Систем (CUDOS), разработала алгоритм кодирования данных, который может существенно увеличить эффективность существующих оптических сетей. По утверждению исследователей, их разработка позволит передавать весь мировой трафик по единственному волокну!

Привет. В этом посте мы проведем эксперимент, в котором протестируем два типа регуляризации в ограниченной машине Больцмана. Как оказалось, RBM очень чувствительна к параметрам модели, таким как момент и локальное поле нейрона (более подробно обо всех параметрах можно прочитать в практическом руководстве в RBM Джеффри Хинтона). Но мне для полной картины и для получения шаблонов наподобие таких вот, не хватало еще одного параметра — регуляризации. К ограниченным машинам Больцмана можно относиться и как к разновидности сети Маркова, и как к очередной нейроной сети, но если копнуть глубже, то будет видна аналогия и со зрением. Подобно первичной зрительной коре, получающей информацию от сетчатки через зрительный нерв (да простят меня биологи за такое упрощение), RBM ищет простые шаблоны во входном изображении. На этом аналогия не заканчивается, если очень малые и нулевые веса интерпретировать как отсутствие веса, то мы получим, что каждый скрытый нейрон RBM формирует некоторое рецептивное поле, а сформированная из обученных RBM глубокая сеть формирует из простых образов более комплексные признаки; чем-то подобным, в принципе, и занимается зрительная кора головного мозга, правда, вероятно, как то посложнее =)

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


В последние несколько лет интенсивно развивается новое направлении в теории восстановления изображений — слепая обратная свертка (Blind Deconvolution). Появилось достаточно много работ по этой теме, и начинается активное коммерческое использование результатов.
Многие из вас помнят конференцию Adobe MAX 2011, на которой они как раз показали работу одного из алгоритмов Blind Deconvolution: Исправление смазанных фотографий в новой версии Photoshop
В этой статье я хочу подробнее рассказать — как же работает эта удивительная технология, а также показать практическую реализацию SmartDeblur, который теперь тоже имеет в своем распоряжении этот алгоритм.
Внимание, под катом много картинок!

Я хочу описать историю одного заносчивого и самовлюбленного студента Академического Университета, коим я, конечно, не являюсь, но хорошо представляю его мысли и переживания. Будем называть этого студента, например, Шурик. На момент поступления Шурика в Академический Университет (АУ), согласно его программистскому резюме, он уже был экспертом в области алгоритмов. Он мастерски владел алгоритмом поиска в глубину, знал несколько методов сортировки массивов, и имел представление о двоичном поиске. Естественно, курс алгоритмов его не интересовал совершенно, да и вообще, мало чему можно научить программиста с пятилетним опытом. Программа теоретической информатики АУ его заинтересовала тем, что в темах по известным ему предметам было слишком много неизвестных ему слов. Но это же Питер, там они и бордюр то странным словом называют, вероятно, и для поиска в глубину красивых слов понавыдумывали. Он тщательно изучил слайды и видеозаписи курсов. Оказалось, что существует какая-то там информатика, которой Шурик не владеет в совершенстве. Шурик собрал книги, носки и пять лет опыта, и отправился в Питер на собеседование. Там он встретил людей, которые могут научить чему-то даже программиста с таким опытом. Это все рушило Шурикову картину мира, в которой знание информатики измерялось количеством написанных классов на C#.
Во время учëбы в магистратуре Шурик занимался исследованиями в области схемной сложности и области экспоненциальных алгоритмов. Это действительно очень интересно и, что не менее важно, полезно для поступления в аспирантуру.
На данный момент Шурик является счастливым аспирантом New York University, использует слово «поребрик», и с глубокой благодарностью вспоминает Академический Университет. А кафедра математических и информационных технологий АУ и сейчас ведет набор новых магистрантов, в частности, по направлению «теоретическая информатика».
Сейчас я передаю слово Шурику, который и расскажет об одном своëм исследовании.

Бывает ли у вас такие ситуации, когда слово, идиома или грамматическая конструкция иностранного языка никак не могут удержаться в голове, несмотря на то, что вы встречали её уже много раз и даже специально учили? А сколько процентов иностранных слов вы помните спустя месяц после их изучения? А спустя полгода? Сложно ли вам мотивировать себя на занятия иностранным языком?



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

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