У меня возникла необходимость вычислять в Java-приложении значения формул, вводимых пользователями (да еще и так, чтобы приложение понимало комплексные числа). Внимание сразу привлекла библиотека Jep, но ввиду определенных ограничений использовать ее не представилось возможным. Поэтому я решил написать свой парсер, используя Алгоритм Дейкстры для преобразования входной записи из инфиксной нотации в постфиксную, также известный, как Алгоритм сортировочной станции. Он довольно прост, но в то же время элегантен, и я получил удовольствие, реализовывая его. Заинтересовавшихся — прошу под кат.
Рубрика «Алгоритмы» - 312
Реализация алгоритма сортировочной станции на Java
2012-03-15 в 23:51, admin, рубрики: java, math, postfix, Алгоритмы, Программирование, метки: java, math, postfix, парсингНаписание компилятора LALR(1)-парсеров. Часть 1
2012-03-15 в 15:27, admin, рубрики: c++, lalr, Алгоритмы, Компиляторы, парсеры, синтаксический анализ, метки: lalr, компиляторы, парсеры, синтаксический анализВведение, или зачем нужны синтаксические анализаторы
Добрый день.
Не так давно появилась у меня задача синтаксического анализа одной грамматики. Существующие решения мне увы не подходили, поэтому встала проблема написания собственного генератора парсеров. Несмотря на то, что тема довольно популярная и существует не так уж и мало статей и книг по данному сабжу, я всё-таки решил еще раз описать данный процесс, причём начать с самых базовых понятий.
Эта часть посвящена базису, общей теории computer science. Возможно, что это даже преподаётся в школах/вузах России. Самая мякота пойдет со второй части.
Итак, зачем же кому-то может понадобиться писать парсер и что вообще это такое? Парсер — это код, который наделяет входящий набор символов семантическим смыслом. То есть, происходит анализ этих символов, и на основе этого анализа программа понимает как интерпретировать эти буквы и цифры. Простой пример — «1+2», после или во время процесса парсинга знак "+" это не просто символ плюса, но обозначение бинарноого оператора сложения, а в "+3" это унарный оператор знака числа. Большинству людей это очевидно, машине — нет.
Парсеры используются всюду — в Word'e для анализа приложений, словоформ, формул, etc; практически на любом сайте при валидации входных данных: email'а, телефонного номера, номера кредитки; конфигурационные файлы; сериализованные данные (например, в xml); во многих играх — скриптовые ролики, скрипты ИИ, консоль. В общем, это неотъемлемая часть computer science.
Факторный анализ вектора критериев в задачах распознавания образов
2012-03-15 в 9:47, admin, рубрики: data mining, Алгоритмы, обработка изображений, распознавание образов, метки: распознавание образовВведение
При разработке систем распознавания образов часто возникают проблемы при оценке параметров, которые используются в качестве входного вектора. В данной статье я опишу подход, который можно применять при анализе векторов обучающей выборки, с целью обнаружения зависимостей между параметрами, а также сокращения размерности, что позволит в свою очередь сократить затрачиваемые вычислительные ресурсы при анализе данных и повысить репрезентативность обучающей выборки.
Целью данной работы является определение факторов входного вектора критериев обучающей выборки, предназначенных для решения данной задачи.
Читать полностью »
К вопросу о безопасности, или зачем вообще хранить пароли
2012-03-15 в 9:17, admin, рубрики: авторизация, Алгоритмы, безопасность, Веб-разработка, криптография, пароли, хеширование, метки: авторизация, безопасность, пароли, хеширование Переодически встречаю статьи про способы хранения паролей, например сегодня. И хочу предложить свой способ.
В статье используется MD5, можно взять любое другое хеширование.
Общие рассуждения
Когда передо мной встала задача авторизации пользователей, я пришел к выводу что хранение паролей, в любом виде, недопустимо. Ни в открытом виде, ни в виде хеша, кроме того недопустима передача пароля в открытом или хешированном виде по сети, при авторизации пользователя на сайте. Причины просты:
- передачу пароля можно перехватить (троян, обезьяна в середине)
- базу с паролями могут украсть, и расшифровать
Игра Super Mario признана NP-полной задачей
2012-03-14 в 20:56, admin, рубрики: game development, PSPACE, Super Mario, Алгоритмы, Игровые приставки, класс NP, теория сложности, метки: PSPACE, Super Mario, класс NP, теория сложности 
Математический анализ сложности пяти классических игр для Nintendo показал, что среди них есть NP-полные задачи, то есть которые решаются за полиномиальное время на так называемых недетерминированных машинах Тьюринга. Проще говоря, это математически очень сложные задачи, сравнимые с задачей коммивояжёра или проблемой раскраски графа.
Учёные проанализировали следующие игры: Mario, Donkey Kong, Legend of Zelda, Metroid и Pokemon. Как выяснилось, ко всем играм серий Mario и Donkey Kong применимо определение о NP-полноте. Кроме того, отдельные игры других серий принадлежат к классу NP, а некоторые игры из серии Zelda — к классу PSPACE.
Читать полностью »
Игра Super Mario определена как NP-полная задача
2012-03-14 в 20:56, admin, рубрики: game development, PSPACE, Super Mario, Алгоритмы, Игровые приставки, класс NP, теория сложности, метки: PSPACE, Super Mario, класс NP, теория сложности 
Математический анализ сложности пяти классических игр для Nintendo показал, что среди них есть NP-полные задачи, то есть которые решаются за полиномиальное время на так называемых недетерминированных машинах Тьюринга. Проще говоря, это математически очень сложные задачи, сравнимые с задачей коммивояжёра или проблемой раскраски графа.
Учёные проанализировали следующие игры: Mario, Donkey Kong, Legend of Zelda, Metroid и Pokemon. Как выяснилось, ко всем играм серий Mario и Donkey Kong применимо определение о NP-полноте. Отдельные игры других серий принадлежат к классу NP, а некоторые игры — к классу PSPACE.
Читать полностью »
Доказано, что игра Super Mario является NP-полной задачей
2012-03-14 в 20:56, admin, рубрики: game development, PSPACE, Super Mario, Алгоритмы, Игровые приставки, класс NP, теория сложности, метки: PSPACE, Super Mario, класс NP, теория сложности 
Анализ вычислительной сложности пяти классических игр для Nintendo показал, что среди них есть NP-полные задачи, то есть которые решаются за полиномиальное время на так называемых недетерминированных машинах Тьюринга. Проще говоря, это математически очень сложные задачи, сравнимые с задачей коммивояжёра или проблемой раскраски графа.
Учёные проанализировали следующие игры: Mario, Donkey Kong, Legend of Zelda, Metroid и Pokemon. Как выяснилось, ко всем играм серий Mario и Donkey Kong применимо определение о NP-полноте. Отдельные игры других серий принадлежат к классу NP, а некоторые игры — к классу PSPACE.
Читать полностью »
… или как я получил «Аленку» за консольное приложение
Существует довольно распространённое мнение, что выполнение различных тестовых заданий помогает очень быстро поднять свой профессиональный уровень. Я и сам люблю иногда откопать какое-нить мудреное тестовое и порешать его, чтобы быть постоянно в тонусе, как говорится. Как-то я выполнял конкурсное задание на стажировку в одну компанию, задачка показалась мне забавной и интересной, вот её краткий текст:
Представьте, что ваш коллега-нытик пришел рассказать о своей непростой задаче — ему нужно не просто упорядочить по возрастанию набор целых чисел, а выдать все элементы упорядоченного набора с L-го по R-й включительно!
Вы заявили, что это элементарная задача и, чтобы написать решение на языке C#, вам нужно десять минут. Ну, или час. Или два. Или шоколадка «Алёнка»
Предполагается, что в наборе допускаются дубликаты, и количество элементов будет не больше, чем 10^6.
К оценке решения есть несколько комментариев:
Ваш код будут оценивать и тестировать три программиста:
- Билл будет запускать ваше решение на тестах размером не больше 10Кб.
- В тестах Стивена количество запросов будет не больше 10^5, при этом количество запросов на добавление будет не больше 100.
- В тестах Марка количество запросов будет не больше 10^5.
Решение может быть очень интересным, поэтому я посчитал нужным его описать.
Читать полностью »
Учебный процесс в IT / Обновление по онлайн-курсам Stanford University
2012-03-06 в 19:38, admin, рубрики: nlp, Алгоритмы, дистанционное образование, статистический анализ, метки: nlp, Алгоритмы, дистанционное образование, статистический анализПонимаю, что все заинтересованные уже получили оповещение по почте, но для тех кто не в танке — объявление: онлайн курсы от Stanford University наконец-то начинаются.
Probabilistic Graphical Models — начинается 19 марта, лекции пока не доступны.
По данным курсам доступны первые лекции и задания
Natural Language Processing — начало с 12 марта, первое задание Spamlord должно быть уже выполнено к 19 марта, так что регистрируемся.
Design and Analysis of Algorithms I — курс по дизайну и анализу алгоритмов.
Обработка изображений / [Из песочницы] Реализация RGB-алгоритма изменения контраста изображения
2012-03-05 в 9:49, admin, рубрики: opencv, openmp, Алгоритмы, обработка изображений, оптимизация, метки: opencv, openmp, Алгоритмы, обработка изображений, оптимизация ![Обработка изображений / [Из песочницы] Реализация RGB алгоритма изменения контраста изображения](https://www.pvsm.ru/images/8500084d02aab5ffea8d0e925eef91fe.png "Обработка изображений / [Из песочницы] Реализация RGB алгоритма изменения контраста изображения")
Во время работы над программой, предназначенной для обработки видео-потока, возникла необходимость реализовать алгоритм изменения контраста изображения.
Так как программа была предназначена для обработки видео, то от реализации требовалась высокая производительность, в том числе способность обрабатывать видео разрешения Full HD. Код был написан на С++ с использованием библиотеки OpenMP.
Существует несколько алгоритмов изменения контраста, часть из которых рассмотрена в этой статье [1].
Рассмотрим RGB-алгоритм изменения контраста.
Вначале мыЧитать полностью »