• Поиск декартова произведения с помощью LINQ

    • Перевод
    Постановка вопроса: как найти декартово произведение произвольного количества последовательностей с помощью LINQ?

    Для начала, давайте убедимся, что мы знаем, о чем идет речь. Я буду обозначать последовательности как упорядоченные множества: {a, b, c, d...} Декартово произведение двух последовательностей S1 и S2 есть последовательность всех возможных упорядоченных пар таких, что их первый элемент из S1, а второй — из S2. Так, к примеру, если у вас есть две последовательности {a, b} и {x, y, z}, то их декартово произведение выглядит как {{a, x}, {a, y}, {a, z}, {b, x}, {b, y}, {b, z}}.

    Для упрощения, предположим, что S1 и S2 состоят из элементов одного типа. Разумеется, мы можем определить декартово произведение последовательности строк с последовательностью чисел как последовательность кортежей (string, int), но впоследствии это окажется тяжело обобщать, потому что система типов C#, в частности, не лучшим образом работает с кортежами произвольной длины.
    Читать дальше →
  • Автоматизация очистки снимков документов с помощью Sikuli

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

      Проблема


      Основная задача, которую будем решать в рамках данного топика — подготовка сканов и фотографий письменных источников (книг, лекций и т.п.) для их печати, компактного хранения, упаковки в djvu и т.п.
      Photoshop и FineReader рассматривать не будем. Хотя они и предоставляют ряд полезных инструментов, но стоят денег, вообще говоря.
      При наличии сканера обычно всё просто: получаются изображения достаточно хорошего качества, чтобы можно было обойтись минимальной обработкой.
      С фотографиями интереснее: добавляются проблемы с освещением и геометрические искажения. Увы, исправление геометрических искажений автоматизировать, как минимум, сложно. А вот с освещением и фоном вполне можно побороться. Чем и займёмся.
      Читать дальше →
    • Make3D из одной фотографии, часть 2



        Продолжение статьи про проект Stanford University (ныне Cornell University) "Make3D", который поставил перед собой пока еще не ставшую типичной задачу восстановления трехмерной модели сцены всего из одного фотоснимка.

        Публикация состоит из: Часть 1, Часть 2
        Публикуется для утоления любопытства, с целью разоблачения магии дать понять как это устроено.

        Продолжаем разговор...
      • Make3D из одной фотографии, часть 1



          Проект из Stanford University (ныне Cornell University) "Make3D", примечателен тем, что поставил перед собой пока еще не ставшую типичной задачу восстановления трехмерной модели сцены всего из одного фотоснимка. До сих пор, чтобы добиться подобного результата, разработчики восстанавливали трехмерную информацию, комбинируя несколько (два и более) снимков одного и того же объекта. В данном же случае было продемонстрировано, что значительный объем информации содержится в монокулярных признаках (monocular cues) самого изображения, которые до этого зачастую игнорировались. В практической реализации уже удалось добиться удовлетворительных результатов более чем на 60% произвольных фотоснимков, предоставленных и оцененных сторонними пользователями системы при проведении ее испытаний.

          Публикация состоит из: Часть 1, Часть 2
          Публикуется для утоления любопытства, с целью разоблачения магии дать понять как это устроено.

          Тебе страшно? Мне нет...
        • Задача о рюкзаке: а что же внутри?

            Достопочтенный SergeyACTIVITI в своём посте поведал нам про такую полезную вещь, как задача о рюкзаке, решение которой с успехом реализовано в решателях COIN-OR или GLPK. А что же внутри?

            Итак, пусть у нас есть рюкзак объёма W, и список из n вещей, у каждой из которых есть объём v[i] и стоимость c[i], и каждую из которых можно брать сколько угодно раз. При этом все объёмы и все стоимости будут положительными и целыми. Как же работает алгоритм?

            Читать дальше →
          • Эрик Липперт — Генерация всех произвольных деревьев

            • Перевод
            BinaryTrees1В прошлый раз мы говорили о том, что число бинарных деревьев с n вершинами равно C(n), где C(n) – это n-ое число Каталана. Я заинтересовался чего больше: произвольных деревьев из n вершин или бинарных деревьев из n вершин. Ответ может вас удивить, он не лежит на поверхности.
            BinaryTrees2

            Распространённый ответ на этот вопрос я получу сразу: «Разумеется, произвольных деревьев больше, т.к. бинарное дерево – это частный случай произвольного дерева». Можете ли вы сказать, почему это неверно? Бинарных деревьев больше, чем произвольных деревьев! Существует два бинарных дерева из двух вершин: одно с левым потомком ребёнком корня, а другое – с правым потомком корня. Но есть только одно произвольное дерево с двумя вершинами, в нём нет разницы между «левым» и «правым» потомком.
            Читать дальше →
          • Ой, у вас баннер убежал!

            Ну. И что?
            Реклама
          • Эрик Липперт — Генерация всех бинарных деревьев

            • Перевод
            Раньше я описывал небольшой алгоритм, который делал небольшие операции на бинарными деревьями. Я хотел протестировать его. Я попробовал несколько небольших тестов и они прошли, но я не был доволен. Я был почти уверен, но возможно какая-то непонятная топология бинарного дерева могла привести к ошибке. Я сообразил, что существует конечное количество бинарных деревьев данного размера. Я решил попробовать их все.
            Читать дальше →
            • +25
            • 6,8k
            • 8
          • Алгоритмы поиска старшего бита

              Здесь я хочу рассказать и обсудить несколько алгоритмов для нахождения старшего единичного бита числа.

              На всякий случай, поясню: старшим битом называется единичный бит числа, отвечающий за самую большую степень двойки. Иными словами, это самая большая степень двойки, не превосходящая числа. Чтобы избежать многих случаев, будем здесь считать, что мы имеем дело с натуральным числом в пределах от 1 до 2^31 — 1 включительно. Кроме того, чтобы не слишком углубляться в теорию вероятности, будем считать, что число, в котором требуется определить старший бит, с одинаковой вероятностью будет любым из возможных чисел.

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

              int bit1(int x) {
                 int t = 1 << 30;
                 while (x < t) t >>= 1;
                 return t;
              }
              


              Читать дальше →
            • Квадрарный поиск

                Тернарный (или троичный) поиск — это алгоритм поиска минимума (или максимума) выпуклой функции на отрезке. Можно искать минимум (максимум) функции от вещественного аргумента, можно минимум (максимум) на массиве. Будем, для определённости, искать минимум функции f(x).

                Он многим знаком, а для тех, кто не знает, расскажу вкратце.

                Тернарный поиск заключается в следующем. Пусть есть рекурсивная функция search(L, R), которая по двум концам отрезка L, R определяет минимум на орезке [L, R]. Если R — L < eps, то мы уже вычислили точку, где достигается минимум, с точностью eps. Иначе, разделим отрезок [L,R] на три равных по длине отрезка [L, A], [A, B] и [B, R]. Сравним значение в точках А и В. Вспомнив, что функция f выпуклая, можно сделать вывод, что если f(A) > f(B), то минимум лежит на отрезке [A,R]. Иначе — на отрезке [L, B]. В соответсвии с этим, можно рекурсивно запуститься от одного из отрезков [L, B] или [A, R]. Каждый раз длина области поиска уменьшается в полтора раза, значит, минимум на отрезке длины X с точностью eps будет найден за время O(log(X/eps)).

                А здесь я хочу рассказать о квадрарном (или четверичном) поиске.

                Читать дальше →
                • +23
                • 5,8k
                • 6
              • Как же все-таки правильно написать двоичный поиск?

                  В обсуждениях статьи Только 10% программистов способны написать двоичный поиск так никто и не написал, как же правильно подойти к решению этой задачи.
                  Если мы не хотим использовать циклический метод «гадание, затем тестирование, затем исправление ошибок», то без инварианта цикла здесь не обойтись.
                  Инвариант цикла – это соотношение, которое истинно перед циклом, истинно в процессе выполнения цикла и истинно при выходе из цикла. Все это описано у Дейкстры в книге «Дисциплина программирования», и детально разжевано у Гриса в книге «Наука программирования». Тем не менее, по моим наблюдениям, на практике этот метод практически НИКТО не использует, считая, что все это к реальности не имеет никакого отношения. Это большая ошибка.
                  Читать дальше →
                Самое читаемое