Метка «алгоритм»

Об одном алгоритме сжатия случайных сигналов (с потерями)

Аннотация

Известно, что существуют различные способы формирования псевдослучайных чисел для моделирования случайных величин на ЭВМ. Если допустить, что высокочастотный (ВЧ) сигнал представляет из себя реализацию некоторой случайной величины, то возникает большой соблазн подобрать для этой реализации свою модель случайной величины, имеющую известные параметры реализации алгоритма её формирования. Тогда мы можем представить ВЧ сигнал в виде этого алгоритма, а хранить лишь его параметры, т.е. происходит сжатие.
Читать полностью »

image
Привет! Недавно у меня возникла идея создать собственный алгоритм хеширования, на вход которого можно бы было подать информацию любой длины и получить хеш определенного размера. Особенность всех алгоритмов хеширование — в их необратимости. Но существует и другой, не менее важный момент — однозначность.
Читать полностью »

Пролог

Друзья, всем привет! Недавно начал изучать помехоустойчивые коды и моделировать процесс их работы, и понял что по-человечески написанных топиков по этой теме совсем немного, а точнее мало. Мудрёные книги есть, но на то они и мудрёные, что на их изучение нужно время, а порой нужно получить какие-то базовые знания и представления по теме, за совсем сжатый промежуток времени. Как пример, могу привести статью по кодам Хэмминга, она мне здорово помогла, когда я только начинал возиться с кодами. Так же доступно подобные коды описаны здесь.

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

Построение множества Жюлиа Привет. Кипят страсти, конец года, сессии, дедлайны, новый год, а так же цензура проникает во все слои интернетов, что не может не печалить. Хабр уже не торт. Просто хотелось написать, что я не согласен с таким подходом, но тогда бы меня просто забанили. Так что придется написать интересный контент. Хотя если забанят из-за предисловия к посту о множестве Жюлиа, ну что, тогда остатки торта стухли и шансов нет.

Итак, вернемся к теме поста. Я давно хотел немного больше узнать о комплексных числах, а не только то, что корень из минус единицы равен i. Особенно вызывали интерес фигуры имеющие фрактальную структуру, хотелось понять, что это значит, и как сделать такую визуализацию. Где то на полке стояла книжка по ТФКП, а так же закончился курс по комплексному анализу на курсере, и появилось немного свободного от работы времени. Приступим.

Читать полностью »

Проверка на простоту

Чтобы определить, является ли данное число N простым, безусловно, достаточно написать простой цикл поиска делителей числа N:

bool prime(long long n){ 
	for(long long i=2;i<=sqrt(n);i++)
		if(n%i==0)
			return false;
	return true;
}

Данная функция проверки числа на простоту достаточно эффективна — асимптотика ее работы O (sqrt(N)). Однако, иногда в спортивном программировании нужно уметь проверять число на простоту быстрее.

В некоторых случаях, когда требуется выполнять такую проверку для чисел из некоторого диапазона, то целесообразно воспользоваться алгоритмом Решето Эратосфена.

В данной статье я рассмотрю другой способ выполнять единичные проверки на простоту — тест Ферма.
Читать полностью »

Доброго времени суток, в этом посте хотел разобрать пару примеров для помехоустойчивое кодирование.

Для чего это нужно?

Предположим у нас есть канал связи C, содержащий источник помех, а также S — множество отправляемых данных и S' — множество принятых данных. Рассмотрим следующий пример:
Множество S = {1,0,0,1} мы отправляем данные по каналу связи C и получаем S' = {1,0,0,0}. Что случилось? Почему данные отличаются? А все потому, что на канале связи была помеха. И из-за этого произошла ошибка типа «замещение разряда», т.е. 1 -> 0, 0 -> 1. Как видно из-за таких ошибок данные могут меняться, а это не допустимо.
Читать полностью »

Автоматическая проверка орфографии, модель Noisy Channel Доброго времени суток. На днях у меня возникла задача по реализации алгоритма пост-обработки результатов оптического распознавания текста. Для решения этой проблемы не плохо подошла одна из моделей для проверки орфографии в тексте, хотя конечно слегка модифицированная под контекст задачи. Этот пост будет посвящен модели Noisy Channel, которая позволяет осуществлять автоматическую проверку орфографии, мы изучим математическую модель, напишем на c# немного кода, обучим модель на базе Питера Норвига, и под конец протестируем то что у нас получится.

Читать полностью »

На досуге мне пришла интересная идея, которую я развил в алгоритм нахождения наименьшего общего предка(LCA) двух вершин в дереве. До появления этой идеи других алгоритмов для поиска LCA я не знал. Проверив корректность работы я поспешил изучить другие алгоритмы для решения этой задачи, но аналогичных моему я не нашел. Теперь поспешу поделиться им с сообществом.

Введение

Деревом называется неориентированный связный граф из N вершин и N-1 ребер. Из любой вершины до любой другой существует ровно один простой путь.
Корнем дерева будет называться такая вершина, от которой задано направление движения по дереву при его обходе.
Наименьшим общим предком двух вершин u и v будет называться такая вершина p, которая лежит на пути из корня и до вершины v, и до вершины u, а также максимально удаленная от него.
Читать полностью »

sudoku250title
Доброго времени суток!

Думаю, головоломка Судоку не нуждается в представлении. Многие из нас проводят за её решением достаточно много времени. Например, когда нужно убить время в дороге или просто поворочать мозги, чтобы не сохли. На хабре есть довольно много постов о решении головоломки. Но когда человек решает с десяток, а может и сотню головоломок, то найдётся пытливый ум, который задаст себе вопрос «А как же получается таблица Судоку, имеющая единственное решение? И как можно описать алгоритм для сетки 9x9?».

Приведённый алгоритм является вполне логичным. Но моей задачей было описание и реализация. Обо всём этом написано под катом.

Читать полностью »

В написанной на днях статье Вернулся невод с тиной морскою я дал ссылку на частотный словарь Википедии. Колличество скачиваний на порядки превзошло все мои ожидания. Я почувствавал огромное духовное родство с читателями Хабра. Одна часть скачавших (как и я!) любит всячески возиться со словами и словарями, а вторая часть (как и я!), увидев на просторах сети интересный артефакт, тут же хватает его и тащит к себе в гнездо, а что с ним делать — потом разберёмся!

К первой части у меня просьба. Если Вы нашли интересное применение словарю или у вас есть идея такого применения и это всё не коммерческая тайна, поделитесь, пожалуйста, в комментариях.

А для второй части, для тех, кто скачал словарь, а теперь мучительно думает, что делать со свалившимся счастьем, я хочу написать несколько статей. Собственно с этой и начну.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js