.png "BitSorting Алгоритм со сложностью О(n)")
В свободное от работы время решил поразмыслить, а нельзя ли создать алгоритм соритировки который имел бы сложность O(n) не занимал бы много дополнительной памяти и мог бы быть легко распараллелен. И добился некоторого результата.
Читать полностью »
Думаю, всем читателям хабра хорошо известны алгоритмы энтропийного сжатия с использованием префиксных кодов (алгоритмы Шеннона-Фано, Хаффмана и др.). Особенностью этих алгоритмов является тот факт, что длина кода определённого символа зависит от частоты этого символа в закодированном сообщении. Соответственно при декодировании сообщения необходимо иметь таблицу частот. Данная статья посвящена рассмотрению малоизученной, но важной задачи – передаче частот исходного алфавита.Читать полностью »
Использование случайных битов — один из способов усиления возможностей компьютеров. Вероятностные алгоритмы позволяют решать некоторые задачи теоретической информатики, для которых не работают детерминированные алгоритмы. Самый интересный вопрос — это насколько использование случайностей сокращает время работы алгоритма? Частично на этот вопрос уже можно ответить: при некоторых предположениях истинную случайность можно подменить фальшивой и детерминированно смоделировать любой вероятностный алгоритм с незначительной потерей во времени работы. Проверка этих предположений будет, по всей видимости, одной из центральных тем теоретической информатики XXI века.
Лекцию читает старший научный сотрудник Вычислительного центра им. А.А. Дородницына РАН, доцент кафедры математических основ управления МФТИ, кандидат физико-математических наук Михаил Вялый.
Представим, что у нас есть два калькулятора. Один обычный, а у второго есть дополнительная кнопка, которая при нажатии выдает дополнительный бит. Попробуем ответить на вопрос, полезна ли будет такая функция?
Такая постановка, конечно, слишком общая. Постараемся уточнить ее с точки зрения теоретической информатики. Для этого сначала введем понятие алгоритма. Алгоритм — настолько точно определенная инструкция, что она может быть исполнена механически. Основное свойство детерминированных алгоритмов заключается в том, что каждое следующее состояние однозначно определяется текущим состоянием. Вероятностные алгоритмы отличаются тем, что в любой момент они могут определить значение случайного бита (подбросить монету), который с равной вероятностью будет равен 0 или 1. В процессе исполнения вероятностного алгоритма это может происходить неоднократно, и разные подбрасывания будут независимы.
Читать полностью »
И сила и слабость современных компьютеров в том, насколько они точны. Сегодня в нашей серии лекций от Яндекса рассказ о том, как использование случайностей может помочь сделать вычисления более эффективными.
Вероятностные алгоритмы позволяют решать некоторые задачи теоретической информатики, для которых не работают детерминированные алгоритмы. Самый интересный вопрос — это насколько использование случайностей сокращает время работы алгоритма? Частично на этот вопрос уже можно ответить: при некоторых предположениях истинную случайность можно подменить фальшивой и детерминированно смоделировать любой вероятностный алгоритм с незначительной потерей во времени работы. Проверка этих предположений будет, по всей видимости, одной из центральных тем теоретической информатики XXI века.
Лекцию читает старший научный сотрудник Вычислительного центра им. А.А. Дородницына РАН, доцент кафедры математических основ управления МФТИ, кандидат физико-математических наук Михаил Вялый.
Начнём с самого простого. Представим, что у нас есть два калькулятора. Один обычный, а у второго есть дополнительная кнопка, которая при нажатии выдает дополнительный бит. Попробуем ответить на вопрос, полезна ли будет такая функция?
Читать полностью »
На прекрасной Coursera скоро снова начинается курс по Алгоритмам от Тима из Стэнфорда. И я не могу про него не написать. А в свете вот этого поста про дистанционное образование так тем более.
Начну с того, что это самый интересный курс, который мне вообще когда-либо приходилось брать. А я провела во всяких не самых худших университетах немало лет. Курс называется Algorithms: Design and Analysis. Рассказывается в курсе про разные алгоритмы для графов, обсуждаются подходящие структуры данных для каждого алгоритма, присутствует теория и краткие доказательства этих алгоритмов. Во второй части рассказывается в том числе про P=NP проблему и алгоритмы с неполиномиальным временем.
Почему этот курс мне так понравился. Потому что лектор невероятно классный! Он настолько вовлечен, он так все это рассказывает. И потом каждую неделю надо запрограммировать новый алгоритм (на языке по собственному выбору) и найти с помощью своей имплементации ответ на вопрос. Ответ на вопрос засабмитить на сайте, и еще раз, пока не получится правильный ответ. Каждую неделю, как я сказала, новый алгоритм. И соответственно дедлайны. Мотивировало меня это просто сумасшедше: я бежала домой с работы и я не расставалась с алгоритмами по выходным, я ездила в отпуск, сидела на вершине самой высокой точки страны и программировала merge sort.
Я ждала полгода, чтобы снова объявили о его начале, чтобы посоветовать его другим людям, потому что для меня это было как найденный клад.
Здравствуйте.
Знаете, иногда я вижу, что группе людей нужно выбрать некий случайный объект. Например, дежурного, если нет графика, или он запутался (по поводу «правильных» графиков дежурств я бы тоже рассказал). Или же, что меня начало в последнее время раздражать, победителя в каком-либо конкурсе репостов.
Проблема следующая. Организаторы конкурса заявляют, что вот вам последовательность действий, совершите её для участия в конкурсе (например, сделайте репост этой записи), а затем мы такого-то числа выберем случайного победителя из репостнувших. Люди совершают все эти действия, приходит долгожданный день и мы получаем…
Победителя. В лучшем случае мы так же получим видео, как организатор при помощи random.org выбирает номер, а затем находит победителя в какой-нибудь таблице.
Однако здесь кроется одна неувязка. Организаторы обещают честный рандом, но ничего, кроме их честного слова мы не имеем. Они могут сотни раз снимать видео, пока не выпадет нужное число, подменить сайт на локалхосте и так далее. Нет никаких гарантий, что мы получили действительно случайный выбор.
Я же считаю, что системы должны быть спроектированы таким образом, чтобы совершить нечто неправильное в них не было возможно, поэтому…
Если помните, Рей Курцвейл обещал приход сингулярности уже в 30 годах этого века. Похоже, что первые предвестники уже появляются: два бывших наших соотечественника, Алексей Лисица и Борис Конев, работающие в Ливерпульском университете, запустили на расчет задачу несоответствия Эрдеша. Задача считается неразрешенной, и программа, запущенная исследователями с задачей справилась. Но! Проблема в том, что доказательства решения сами по себе занимают 13 Гб (еще раз, текстовый лог-файл, по сути и являющийся доказательством, занимает 13 Гб) и с трудом поддается верификации. Отсюда напрашивается простой вопрос – можем ли мы доверять решению компьютера, если не в состоянии проверить его выкладки?
Доброго времени суток! Сегодня решил поделиться с Вами сокровенным — одним из своих любимых велосипедов.
Начну издалека — довольно долго я работал на одном радиозаводе в Челябинске, и был у нас (вообще и сейчас есть, просто я уже не там) один мега-проект: оптико-электронный модуль для охраны физических объектов. Это такая здоровая штука на поворотной установке, с тремя камерами на все случаи жизни (цветная — дневная, ЧБ светочувствительная — для сумерек, и тепловизор — для ночного наблюдения). Берётся такой модуль, ставится на вышку высотой метров 50 — и можно днём и ночью держать под наблюдением территорию в радиусе 4-5 километров. Подробности писать не стану, не о том пост. Кому интересно — сами найдут.
Разумеется, интересных задачек по обработке изображений было много. Об одной из таких я и хочу рассказать. А именно — как использовать массивно-парралельные вычисления для компенсации дрожания камеры в реальном времени, или почему SURF подходит не всегда. Добро пожаловать под кат.
Читать полностью »
Казалось бы… Всё субъективно. Но сама приставка «всё», если вдуматься — замечательно разрушает это распространенное утверждение. У дураков при всей их субъективности — процессы очень даже идут, но «самолеты не летают» (реальных результатов — нет).
Встречая некий выраженный эффект, прекрасный или наоборот неприятный — хочется (эволюция просит), пусть и не сразу, но поделить всех людей на две категории. Именно две, так чтобы в одну попали все те, кто его создают, а в другую прочие.
Есть такой неприятный «эффект критика». Очень распространенный на постсоветском пространстве: Тут все про всё знают всё. Только делать сами не умеют. Но критике это не мешает. Наоборот — способствует. Однако, такое деление: на постсовок и прочих — не проясняет картину. Не несет в себе явных корреляций.
Нередки случаи, когда требуется определить набор свойств вновь созданного объекта. Например, это может касаться сайта с описаниями товаров, фильмов (и, соответственно, для каждого объекта необходим набор тегов или свойств). Вообще, это касается любого хранилища описаний любых объектов, которые предполагают наличие свойств и возможности сравнивать объекты между собой по принципу «похож или непохож».
Итак, дано: на сайте есть готовый набор объектов, свойства для которых определены и проверены. И добавляется новый объект, о котором мы ничего не знаем, но посетители сайта могут судить. Задача: сделать так, чтобы администратору не надо было добавлять вручную требуемые свойства, а все делалось само, руками посетителей сайта.
Читать полностью »
