Вы, наверное, слышали о Дэвиде Хаффмане и его популярном алгоритме сжатия. Если нет, то предлагаю вам самостоятельно поискать в интернете — в этой статье я не буду донимать вас уроками истории или математики. Я попробую показать вам на практике, как применить этот алгоритм к текстовой строке. Наше приложение просто сгенерирует значения кода для символов из введенной строки и наборот — воссоздаст оригинальную строку из представленного кода.
Читать полностью »
Рубрика «Алгоритмы» - 300
Простой пример кодирования текстовой строки по Хаффману
2012-06-22 в 12:38, admin, рубрики: алгоритм хаффмана, Алгоритмы, кодирование, сжатие, сжатие без потерь, ХаффманМинимакс на примере игры в зайца и волков
2012-06-21 в 22:56, admin, рубрики: алгоритм, Алгоритмы, альфа-бета-отсечения, здравый смысл, искусственный интеллект, минимакс, Программирование, теория игр, метки: алгоритм, альфа-бета-отсечения, здравый смысл, искусственный интеллект, минимакс, теория игр 
Данная статья предназначена для разъяснения сути фундаментальных методов построения и оптимизации «искусственного интеллекта» для компьютерных игр (в основном антагонистических). На примере игры в зайца и волков будет рассмотрен алгоритм «Минимакс» и алгоритм его оптимизации «Альфа-бета отсечение». Помимо текстового описания, статья содержит иллюстрации, таблицы, исходники, и готовую кроссплатформенную игру с открытым кодом, в которой вы сможете посоревноваться с интеллектуальным агентом.Читать полностью »
Реализация метода главных компонент на c#
2012-06-21 в 7:26, admin, рубрики: .net, data mining, principal component analysis, Алгоритмы, метки: .net, c++, data mining, principal component analysisВсем привет. На этой неделе в курсе по машинному обучению профессор Andrew Ng рассказал слушателям про метод главных компонент, с помощью которого можно уменьшить размерность пространства признаков ваших данных. Но к сожалению он не рассказал про метод вычисления собственных векторов и собственных чисел матрицы, просто сказал, что это сложно и посоветовал использовать матлаб/октавовскую функцию [U S V] = svd(a).
Для моего проекта мне понадобилась реализация этого метода на c#, чем я сегодня и занимался. Сам метод главных компонент очень элегантный и красивый, а если не понимать математику которая лежит за всем этим, то это можно это все назвать шаманством. Проблема вычисления собственных векторов матрицы в том, что не существует быстрого способа вычисления их точных значений, так что приходится выкручиваться. Я хочу рассказать об одном из таких способов выкрутиться, а так же приведу код на c# выполняющий эту процедуру. Прошу под кат.
Читать полностью »
Я не могу написать бинарный поиск
2012-06-21 в 5:42, admin, рубрики: Алгоритмы, бинарный поиск, двоичный поиск, Программирование, Совершенный код, метки: Алгоритмы, бинарный поиск, двоичный поискНедавно (буквально два года назад) тут пробегала статья Только 10% программистов способны написать двоичный поиск. Двоичный поиск — это классический алгоритм поиска. Мало того, это еще чрезвычайно простой алгоритм, который можно очень легко описать: берем отсортированный массив, смотрим в середину, если не нашли там число, в зависимости от того, что в середине — ищем это число этим же методом либо в левой части, либо в правой, откидывая средний элемент. Для функций также, просто берем не массив, а функцию. Все очень и очень просто, алгоритм описан почти везде, все баги словлены и описаны.
Так вот, я не могу реализовать двоичный поиск. Для меня он ни капельки не тривиален. Наверное, я ненастоящий программист. А ведь так и есть, я всего-лишь студент, но ведь это не оправдание? Если точнее, я не могу реализовать хороший корректный красивый двоичный поиск. Все время у меня вылезает проблема либо с корректностью, либо с красивостью, либо и с тем, и с другим. Так что, да, заголовок немного желтоват.
Прежде чем читать этот топик, напишите свою версию бинарного поиска — для отсортированного массива. Причем, в зависимости от параметра, поиск должен выдавать или первый элемент, или любой из дублирующих. Еще для сравнения, напишите бинарный поиск для функций
Парадокс двух конвертов и стратегия Ковера (реализация на .NET)
2012-06-20 в 23:02, admin, рубрики: .net, Алгоритмы, теория вероятности, метки: теория вероятности .jpg "Парадокс двух конвертов и стратегия Ковера (реализация на .NET)")
Парадокс двух конвертов относится к так называемой теории принятия решений. Представим, что у нас имеются два одинаковых конверта, причем в одном денег (в рублях) в два раза больше, чем в другом. Играющему предлагается выбрать конверт и посмотреть на сумму внутри. После этого он может либо поменять конверт, либо оставить себе данную сумму денег. Существует ли способ при котором из серии множества пар конвертов можно получить максимально возможную сумму? (с учетом того, что сами конверты в каждой паре будут перемешаны в случайном порядке).
Перевод из любой системы счисления в любую чисел большой длины
2012-06-20 в 10:41, admin, рубрики: c++, Алгоритмы, конвертер, Песочница, системы счисления, метки: c++, Алгоритмы, конвертер, системы счисления 
Недавно решал задачи по криптографии, и возникла необходимость переводить очень большие числа из одной системы счисления в другую. С двоичной, восьмеричной, десятичной и шестнадцатеричной системой справляется и стандартный калькулятор ОС. Но он не рассчитан на числа большой длины. А мне как раз необходимо работать с числами длиной >1000 знаков.
Для этих целей решил написать небольшой консольный конвертер, позволяющий работать с числами любой длины и любой системы счисления от 2 до 36.
Требования:
• Конвертер должен работать с числами любой длины.
• Конвертер должен работать в любой системе счисления от 2 до 36.
• Конвертер должен уметь работать с файлами.
Читать полностью »
Формирование высокоуровневых признаков с помощью широкомасштабного эксперимента по обучению без учителя
2012-06-19 в 6:42, admin, рубрики: Алгоритмы, искусственный интеллект, нейронные сети, обработка изображений, обучение без учителя, распознавание лиц, метки: нейронные сети, обучение без учителя, распознавание лиц В статье Распознавание лиц человеческим мозгом: 19 фактов, о которых должны знать исследователи компьютерного зрения упоминался экспериментальный факт: в мозге примата имеются нейроны, селективно реагирующие на изображение морды лица (человека, обезьяны и т.п.), причем средняя задержка составляет около 120 мс. Из чего в комментарии я сделал дилетантский вывод о том, что зрительный образ обрабатывается прямым распространением сигнала, и количество слоёв нейронной сети — около 12.
Предлагаю новое экспериментальное подтверждение этого факта, опубликованное concretely нашим любимым Andrew Ng.
Читать полностью »
ПИД-регулятор своими руками
2012-06-18 в 2:26, admin, рубрики: Алгоритмы, вычисления, математика, пид-регулятор, подводные камни, Программинг микроконтроллеров, программирование микроконтроллеров, физика, метки: вычисления, математика, пид-регулятор, подводные камни, программирование микроконтроллеров, физикаI. Постновка задачи
Нужно держать температуру на заданном неком уровне и менять задание. Есть микроконтроллер, к которому прицеплены измеритель температуры, и симистор для управления мощностью. Не будем греть голову на ТАУ, ни разностными схемами, просто возьмём и сделаем «в лоб» ПИД-регулятор.
Читать полностью »
Биовычисления по сворачиванию. Снова простым языком о полученной модели сворачивания
2012-06-15 в 23:33, admin, рубрики: Алгоритмы, биоинформатика, кибернетика, сворачивание рнк, теория игр, Фолдинг белков, метки: кибернетика, сворачивание рнк, теория игр, Фолдинг белковЯ тут написал уже более 7 статей на тему одного своего подхода (набора алгоритмов и проблем) к задаче сворачивания РНК. Читающих становилось с каждой статьей все меньше, а кое кто признавался, что мозг выносило уже после второй статьи. Сравнительный успех первых двух статей, по сравнению с остальными — кажется заключается в простоте изложения и не углубления в детали. Хотя последние статьи давали возможность самим взять демо моей программы и прочувствовать проблематику — это видимо интересует меньше.
Поэтому я постараюсь тут изложить простым языком еще одну проблему, которая мешает решить эту задачу. И мне представляется, что это проблема связанна не только с выбранным мной подходом к решению, а она скорее общая для задачи.
В своем ПО RNAInSpace — я реализовал возможность «покрутить» спираль РНК вручную, чтобы стала понятна геометрия и ограничения такого вращения. Но так как по предыдущим статьям — это ПО не сильно заинтересовало, то тут очередную демо версию этого ПО я представлять не буду. А поговорим о том, что получается у меня.
Как сделать программу нетерпеливой?
2012-06-15 в 12:36, admin, рубрики: linux, UNIX, Айдеко, Алгоритмы, Блог компании Айдеко, обучение, Программирование, сетевое программирование, метки: c++, linux, unix, Айдеко, обучение, Программирование, сетевое программирование 
Программы, которые были написаны в прошлых лекциях курса «Сетевое программирование в UNIX», обладали бесконечным запасом терпения, то есть беспрекословно ждали, пока не поступят данные для обработки. В новой лекции вы узнаете, как ограничить терпение программы определенными временными рамками.Читать полностью »