Все потоки
Поиск
Написать публикацию
Обновить
153.97

Алгоритмы *

Все об алгоритмах

Сначала показывать
Порог рейтинга
Уровень сложности

Лекции Технопарка. 1 семестр. Алгоритмы и структуры данных

Время на прочтение2 мин
Количество просмотров169K
Очередной пост в рамках нашего цикла лекций Технопарка. В этот раз мы предлагаем вашему вниманию курс, посвящённый алгоритмам и структурам данных. Автор курса — Степан Мацкевич, сотрудник компании ABBYY.

Лекция 1. Основы


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


Читать дальше →

Доказательство некорректности алгоритма сортировки Android, Java и Python

Время на прочтение13 мин
Количество просмотров76K
Тим Петерс разработал гибридный алгоритм сортировки Timsort в 2002 году. Алгоритм представляет собой искусную комбинацию идей сортировки слиянием и сортировки вставками и заточен на эффективную работу с реальными данными. Впервые Timsort был разработан для Python, но затем Джошуа Блох (создатель коллекций Java, именно он, кстати, отметил, что большинство алгоритмов двоичного поиска содержит ошибку) портировал его на Java (методы java.util.Collections.sort и java.util.Arrays.sort). Сегодня Timsort является стандартным алгоритмом сортировки в Android SDK, Oracle JDK и OpenJDK. Учитывая популярность этих платформ, можно сделать вывод, что счёт компьютеров, облачных сервисов и мобильных устройств, использующих Timsort для сортировки, идёт на миллиарды.

Но вернёмся в 2015-й год. После того как мы успешно верифицировали Java-реализации сортировки подсчётом и поразрядной сортировки (J. Autom. Reasoning 53(2), 129-139) нашим инструментом формальной верификации под названием KeY, мы искали новый объект для изучения. Timsort казался подходящей кандидатурой, потому что он довольно сложный и широко используется. К сожалению, мы не смогли доказать его корректность. Причина этого при детальном рассмотрении оказалась проста: в реализации Timsort есть баг. Наши теоретические исследования указали нам, где искать ошибку (любопытно, что ошибка была уже в питоновской реализации). В данной статье рассказывается, как мы этого добились.

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

McPaintio — программа, преобразующая изображение в набор мышиных команд, рисующих это изображение

Время на прочтение13 мин
Количество просмотров90K
Привет, Хабрахабр!
В этот раз речь пойдёт о сугубо развлекательном эксперименте. Статья претендует исключительно на пятничное чтиво и ничего феноменального в ней нет. В ней повествуется об истории создания и разработке приложения McPaintio, которое может рисовать изображения в любом* контексте любой** программы рисования. Статья будет интересна людям, увлекающимся программированием ботов и графической анимацией. Ave, добро пожаловать!
Читать дальше →

Использование цветовых пространств в ATTiny13a для WS2811

Время на прочтение6 мин
Количество просмотров18K
image

И вновь приветствую, Хабр!


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

Фрактальное пламя — алгоритм построения

Время на прочтение4 мин
Количество просмотров29K


Фрактальное пламя (или фрактальные искры, англ. fractal flame) – алгоритм, предложенный Скоттом Дрейвсом (Scott Draves) и использующий для построения изображений системы итерируемых функций (СИФ). Благодаря разным значениям seed для генератора псевдослучайных чисел можно получить множество разнообразных «картин». Хотя фрактальность в них просматривается далеко не всегда, результаты получаются очень интересными.

Под катом – краткое описание основных моментов реализации алгоритма.
Читать дальше →

Генерация текстур планет с помощью алгоритма Fault Formation

Время на прочтение2 мин
Количество просмотров18K

Возможно, кто-то помнит замечательную олдскульную космическую игру Star Control 2. В свое время меня поразила огромная звездная карта с неизведанными планетами, которые предстояло исследовать на фоне разворачивающейся глобальной катастрофы. С тех пор как авторами были опубликованы исходные коды, игра была портирована под новым именем The Ur-Quan Masters на большинство современных платформ.

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

Сжатие изображений с потерями

Время на прочтение10 мин
Количество просмотров28K
Идея, лежащая в основе всех алгоритмов сжатия с потерями, довольно проста: на первом этапе удалить несущественную информацию, а на втором этапе к оставшимся данным применить наиболее подходящий алгоритм сжатия без потерь. Основные сложности заключаются в выделении этой несущественной информации. Подходы здесь существенно различаются в зависимости от типа сжимаемых данных. Для звука чаще всего удаляют частоты, которые человек просто не способен воспринять, уменьшают частоту дискретизации, а также некоторые алгоритмы удаляют тихие звуки, следующие сразу за громкими, для видеоданных кодируют только движущиеся объекты, а незначительные изменения на неподвижных объектах просто отбрасывают. Методы выделения несущественной информации на изображениях будут подробно рассмотрены далее.
Читать дальше →

Сжатие изображений без потерь

Время на прочтение7 мин
Количество просмотров38K
Как я уже обещал постом ранее, представляю вашему вниманию вторую часть большого рассказа о сжатии изображений. На этот раз речь пойдёт о методах сжатия изображений без потерь.
Читать дальше →

Методы сжатия данных

Время на прочтение16 мин
Количество просмотров104K
Мы с моим научным руководителем готовим небольшую монографию по обработке изображений. Решил представить на суд хабрасообщества главу, посвящённую алгоритмам сжатия изображений. Так как в рамках одного поста целую главу уместить тяжело, решил разбить её на три поста:
1. Методы сжатия данных;
2. Сжатие изображений без потерь;
3. Сжатие изображений с потерями.
Ниже вы можете ознакомиться с первым постом серии.
Читать дальше →

Ekspozzer — создание панорамы из видео, усреднение видеопотока

Время на прочтение11 мин
Количество просмотров31K
Привет, Хабрахабр!


Сразу скажу: ничего феноменального в статье нет. Эта статья посвящена разработанной «на коленке» программе по созданию панорам из видео и временному усреднению видеопотока (кадров). Программа также может быть использована как виртуальная slit-камера. Статья будет интересна всем тем, кто увлекается обработкой видео и изображений, а так же гик-артом. Весьма простая программа — весьма интересный результат. В конце статьи ссылка на скачивание. Осторожно, трафик!
Читать дальше →

Необычные модели Playboy, или про обнаружение выбросов в данных c помощью Scikit-learn

Время на прочтение7 мин
Количество просмотров130K
Мотивированный статьей пользователя BubaVV про предсказание веса модели Playboy по ее формам и росту, автор решил углубиться if you know what I mean в эту будоражащую кровь тему исследования и в тех же данных найти выбросы, то есть особо сисястые модели, выделяющиеся на фоне других своими формами, ростом или весом. А на фоне этой разминки чувства юмора заодно немного рассказать начинающим исследователям данных про обнаружение выбросов (outlier detection) и аномалий (anomaly detection) в данных с помощью реализации одноклассовой машины опорных векторов (One-class Support Vector Machine) в библиотеке Scikit-learn, написанной на языке Python.
Читать дальше →

О переборе на примере генерации кроссвордов

Время на прочтение5 мин
Количество просмотров11K
С статье "Алгоритм формирования кроссвордов" были предложены несколько эвристик, которые были реализованы в программе автоматической генерации кроссвордов. Несмотря на то, что предложенные эвристики хорошо проработаны, даже они не позволили за разумное время сгенерировать кроссворд для самой сложной из приведенных сеток:

image
Этот и все последующие рисунки взяты из исходной статьи

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

Введение в курс «Анализ изображений и видео». Лекции от Яндекса

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



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

Ближайшие события

Translit для JavaScript и ГОСТ-7.79-2000

Время на прочтение5 мин
Количество просмотров22K

Переводы как женщины: если красивы — неверны, если верны то некрасивы.
Мориц Готлиб
Ссылки
Информация: Wiki,
PDF ГОСТа
Репозиторий: GitHub,
NpmJs
Исходный код
/* jshint -W100 */
/**
* @name      translit.js
* @author    XGuest <xguest@list.ru>
* @link      https://github.com/xguest/iso_9_js
* @version   1.0.4
* @copyright GPL applies.
*            No warranties XGuest[28.03.2016/07:59:18] translit [ver.1.0.4]
* #guid      {E7088033-479F-47EF-A573-BBF3520F493C}
*
* @description Прямая и обратная транслитерация
*              Соответствует ISO 9:1995 и ГОСТ 7.79-2000 системы А и Б
*
* @param {String}  str транслитерируемая строка
* @param {Number}  typ ± направление (тип) транслитерации
*                      + прямая с латиницы в кириллицу
*                      - обратная
*                      system A = 1-диакритика;
*                      system B = 2-Беларусь;3-Болгария;4-Македония;5-Россия;6-Украина;
* @example
* function example() {
*  var a, b = [
*     [],
*     ["Диакритика", "Съешь ещё этих мягких французских булок, да выпей же чаю!"],
*     ["Беларускую", "З'ясі яшчэ гэтых мяккіх французскіх булак, ды выпі ж чаю!"],
*     ["Български",  "Яжте повече от тези меки кифлички, но също така се пие чай!"],
*     ["Македонски", "Јадат повеќе од овие меки францускиот ролни, па пијат чај!"],
*     ["Русский",    "Съешь ещё этих мягких французских булок, да выпей же чаю!"],
*     ["Українська", "З'їж ще цих м'яких французьких булок, та випий же чаю!"]
*  ], c, d;
*  for(a = 1; a < b.length - 1; a++) {
*   c = b[a][0];                                       // Language
*   d = b[a][1];                                       // Source
*   e = translit(d, a);                                // Forward
*   console.log(
*    "%s - %s\nSource  : %s\nTranslit: %s\nReverse : %s\n",
*    c,                                                // Language
*    translit(c, a),                                   // Transliterated language
*    d,                                                // Source
*    e,                                                // Forward
*    translit(e, -1 * a)                               // Reverse
*   );
*  }
* };
**/
function translit(str, typ) {
  var func = (function(typ) {
  /** Function Expression
  * Вспомогательная функция.
  *
  * FINISHED TESTED!
  * В ней и хотелось навести порядок.
  *
  * Проверяет направление транслитерации.
  * Возвращает массив из 2 функций:
  *  построения таблиц транслитерации.
  *  и пост-обработки строки (правила из ГОСТ).
  *
  * @param  {Number} typ
  * @return {Array}  Массив функций пред и пост обработки.
  **/
    function prep (a) {
      var write = !a ? function(chr, row) {trantab[row] = chr;regarr.push(row);} :
      function(row, chr) {trantab[row] = chr;regarr.push(row);};
      return function(col, row) {        // создаем таблицу и RegExp
        var chr = col[abs] || col[0];    // Символ
        if (chr) write(chr, row);        // Если символ есть
        }
    }
    var abs = Math.abs(typ);             // Абсолютное значение транслитерации
    if (typ === abs) {                   // Прямая транслитерация в латиницу
      str = str.replace(/(i(?=.[^аеиоуъ\s]+))/ig, '$1`'); // "i`" ГОСТ ст. рус. и болг.
      return [prep(),                    // Возвращаем массив функций
        function(str) {                  // str - транслируемая строка.
          return str.replace(/i``/ig, 'i`').    // "i`" в ГОСТ ст. рус. и болг.
           replace(/((c)z)(?=[ieyj])/ig, '$1'); // "cz" в символ "c"
        }];
    } else {                             // Обратная транслитерация в кириллицу
      str = str.replace(/(c)(?=[ieyj])/ig, '$1z'); // Правило сочетания "cz"
      return [prep(1),function(str) {return str;}];// nop - пустая функция.
    }
  }(typ));
  var iso9 = {                           // Объект описания стандарта
    // Имя - кириллица
    //   0 - общие для всех
    //   1 - диакритика         4 - MK|MKD - Македония
    //   2 - BY|BLR - Беларусь  5 - RU|RUS - Россия
    //   3 - BG|BGR - Болгария  6 - UA|UKR - Украина
   /*-Имя---------0-,-------1-,---2-,---3-,---4-,----5-,---6-*/
    '\u0449': [   '', '\u015D',   '','sth',   '', 'shh','shh'], // 'щ'
    '\u044F': [   '', '\u00E2', 'ya', 'ya',   '',  'ya', 'ya'], // 'я'
    '\u0454': [   '', '\u00EA',   '',   '',   '',    '', 'ye'], // 'є'
    '\u0463': [   '', '\u011B',   '', 'ye',   '',  'ye',   ''], //  ять
    '\u0456': [   '', '\u00EC',  'i', 'i`',   '',  'i`',  'i'], // 'і' йота
    '\u0457': [   '', '\u00EF',   '',   '',   '',    '', 'yi'], // 'ї'
    '\u0451': [   '', '\u00EB', 'yo',   '',   '',  'yo',   ''], // 'ё'
    '\u044E': [   '', '\u00FB', 'yu', 'yu',   '',  'yu', 'yu'], // 'ю'
    '\u0436': [ 'zh','\u017E'],                                 // 'ж'
    '\u0447': [ 'ch','\u010D'],                                 // 'ч'
    '\u0448': [ 'sh', '\u0161',   '',   '',   '',    '',   ''], // 'ш'
    '\u0473': [   '','f\u0300',   '', 'fh',   '',  'fh',   ''], //  фита
    '\u045F': [   '','d\u0302',   '',   '', 'dh',    '',   ''], // 'џ'
    '\u0491': [   '','g\u0300',   '',   '',   '',    '', 'g`'], // 'ґ'
    '\u0453': [   '', '\u01F5',   '',   '', 'g`',    '',   ''], // 'ѓ'
    '\u0455': [   '', '\u1E91',   '',   '', 'z`',    '',   ''], // 'ѕ'
    '\u045C': [   '', '\u1E31',   '',   '', 'k`',    '',   ''], // 'ќ'
    '\u0459': [   '','l\u0302',   '',   '', 'l`',    '',   ''], // 'љ'
    '\u045A': [   '','n\u0302',   '',   '', 'n`',    '',   ''], // 'њ'
    '\u044D': [   '', '\u00E8', 'e`',   '',   '',  'e`',   ''], // 'э'
    '\u044A': [   '', '\u02BA',   '', 'a`',   '',  '``',   ''], // 'ъ'
    '\u044B': [   '',      'y', 'y`',   '',   '',  'y`',   ''], // 'ы'
    '\u045E': [   '', '\u01D4', 'u`',   '',   '',    '',   ''], // 'ў'
    '\u046B': [   '', '\u01CE',   '', 'o`',   '',    '',   ''], //  юс
    '\u0475': [   '', '\u1EF3',   '', 'yh',   '',  'yh',   ''], //  ижица
    '\u0446': [ 'cz',     'c'],                                 // 'ц'
    '\u0430': [ 'a'],                                           // 'а'
    '\u0431': [ 'b'],                                           // 'б'
    '\u0432': [ 'v'],                                           // 'в'
    '\u0433': [ 'g'],                                           // 'г'
    '\u0434': [ 'd'],                                           // 'д'
    '\u0435': [ 'e'],                                           // 'е'
    '\u0437': [ 'z'],                                           // 'з'
    '\u0438': [   '',      'i',   '',  'i',  'i',   'i', 'y`'], // 'и'
    '\u0439': [   '',      'j',  'j',  'j',   '',   'j',  'j'], // 'й'
    '\u043A': [ 'k'],                                           // 'к'
    '\u043B': [ 'l'],                                           // 'л'
    '\u043C': [ 'm'],                                           // 'м'
    '\u043D': [ 'n'],                                           // 'н'
    '\u043E': [ 'o'],                                           // 'о'
    '\u043F': [ 'p'],                                           // 'п'
    '\u0440': [ 'r'],                                           // 'р'
    '\u0441': [ 's'],                                           // 'с'
    '\u0442': [ 't'],                                           // 'т'
    '\u0443': [ 'u'],                                           // 'у'
    '\u0444': [ 'f'],                                           // 'ф'
    '\u0445': [  'x',     'h'],                                 // 'х'
    '\u044C': [   '', '\u02B9',  '`',  '`',   '',   '`',  '`'], // 'ь'
    '\u0458': [   '','j\u030C',   '',   '',  'j',    '',   ''], // 'ј'
    '\u2019': [ '\'','\u02BC'],                                 // '’'
    '\u2116': [  '#']                                           // '№'
   /*-Имя---------0-,-------1-,---2-,---3-,---4-,----5-,---6-*/
  }, regarr = [], trantab = {};
  /* jshint -W030 */                     // Создание таблицы и массива RegExp
  for (var row in iso9) {if (Object.hasOwnProperty.call(iso9, row)) {func[0](iso9[row], row);}}
  /* jshint +W030 */
  return func[1](                        // функция пост-обработки строки (правила и т.д.)
      str.replace(                       // Транслитерация
      new RegExp(regarr.join('|'), 'gi'),// Создаем RegExp из массива
      function(R) {                      // CallBack Функция RegExp
        if (R.toLowerCase() === R) {     // Обработка строки с учетом регистра
          return trantab[R];
        } else {
          return trantab[R.toLowerCase()].toUpperCase();
        }
      }));
}
module.exports = translit;
Читать дальше →

Бильярдный бот: история создания

Время на прочтение21 мин
Количество просмотров27K
Привет, хабрахабр! Эта статья посвящена подробному описанию процесса создания бильярдного бота, который без участия человека играет в игру pool billiard и принимает решения, зарабатывая очки. Статья будет полезна и интересна людям, увлекающимся созданием ботов и программированием.


Читать дальше →

Новый журнал «Математическое моделирование и численные методы»

Время на прочтение1 мин
Количество просмотров15K
В рамках проходившего вчера заседания ПТК №700 «МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ И ВЫСОКОПРОИЗВОДИТЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ТЕХНОЛОГИИ» был представлен новый журнал «Математическое моделирование и численные методы».
Журнал выпускается под покровительством кафедры ФН-11 МГТУ им.Баумана.
Главный редактор д.ф.-м.н., Профессор Димитриенко Юрий Иванович.
Приглашаю всех интересующихся темой математического моделирования и информационного моделирования читать и писать статьи.

Антивирус, Android и х86. Особенности взаимодействия

Время на прочтение4 мин
Количество просмотров13K


Тема оптимизации Android-приложений под платформу х86 не сходит со страниц нашего блога. Сегодня мы посмотрим на проблему под несколько специфическим углом. Портируются ли под Intel… вирусы? В чем заключаются нюансы функционирования антивирусов на разных платформах? С какими проблемами встречаются разработчики антивирусного ПО на пути оптимизации? С этими вопросами обратились к команде лаборатории Касперского, разрабатывающей антивирус для Android.
Читать дальше →

Прикладная практика оптимизации и немного истории

Время на прочтение6 мин
Количество просмотров12K
«Тысячу долларов за один удар кувалдой?!» — вскричал удивлённый, но счастливый (и спасённый решением проблемы) инженер паровой машины. «Нет, удар стоит 1$, остальное — за знание куда, когда и как сильно ударить» — ответил старый мастер.
Типа эпиграфа

В патентовании есть такая категория изобретений, когда патентуется не то, что человек/коллектив придумал (оно уже достаточно давно известно, например, клей), и не новый способ достижения актуальной цели (например, герметизация раны от инфекции). А патентуется, например, применение широко известного вещества в совершенно новом (для данного вещества), но тоже хорошо и давно известном для достижения цели применении. «А давайте попробуем заклеить рану клеем БФ-6? О! А он, оказывается, имеет бактерицидные свойства..., и рана под ним дышит..., и быстрее заживает! Надо застолбить и применять!»

В прикладной математике есть инструменты, грамотное применение которых позволяет решать оч-ч-чень большой круг самых различных задач. Об этом я и хочу вам рассказать. Может кого натолкну на поиски своего нетривиального применения успешно освоенных алгоритмов или приёмов/программ. Здесь будет мало отсылок на строгие математические инструменты или соотношения, больше качественный разбор преимуществ и приложений численного метода (методов), сыгравшего в моей жизни большую роль и ставшего основой решения важных профессиональных задач.
Читать дальше →

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

Время на прочтение2 мин
Количество просмотров14K
В России обсуждают вопросы о создании мега Национального биометрического Центра с объемом базы данных 100 – 150 млн. записей. А в Госдумму уже внесен проект закона об обязательной биометрической регистрации. Так как работать все это, теоретически, обязано на патриотическом оборудовании, то есть из соображений защиты информации желательно и мозги и оборудование географически должно располагаться внутри страны, я думаю, вам будет интересно ознакомится с тем, что же хорошего, теоретически, у нас может с этим получиться.

Совсем недавно завершилось двухлетнее тестирование pVTE-12 (Fingerprint Vendor Technology Evaluation 2012) при национальном институте стандартов США (НИСТ).



Цель тестирования – оценка реальных возможностей систем идентификации по отпечаткам пальцев на сегодняшний день. Это самое крупное тестирование (крупные базы и типы данных), которое длилось в течение двух лет.
Читать дальше →

Поиск в ширину (BFS) на С#

Время на прочтение4 мин
Количество просмотров49K
Сразу скажу, что статья больше подойдёт людям, желающим познакомиться с поиском в ширину, и новичкам, осваивающим программирование. К тому же, когда мне понадобился этот метод, я нигде не нашёл наглядного рабочего примера на C#.

Устно об алгоритме:

Разберём алгоритм на произвольном графе (для простоты примера рёбра не имеют вес).

Последовательность алгоритма заключается в следующим:

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


Читать дальше →

Вклад авторов