Реализация алгоритма Флойда-Уоршелла на C/C++

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

Реализация поиска в ширину на графе;
Реализация поиска в глубину на графе;
Реализация топологической сортировки и поиска компонент сильной связности;

Реализация обычного алгоритма Флойда-Уоршелла нужна мне для того, чтобы запрограммировать параллельное вычисление этой задачи с помощью библиотеки MPI. Отчет о результатах распараллеливания я напишу уже совсем скоро(я очень на это надеюсь). А сейчас поговорим о стандартном алгоритме Флойда-Уоршелла.

Суть алгоритма Флойда-Уоршелла

Как я упомянул, алгоритм предназначен для нахождения кратчайших путей между всеми вершинами в графе. По сути он представляет собой простой перебор всех путей и выбор из них наименьшего. Перебор осуществляется по так называемой «матрице смежности» размера NxN, где N — количество вершин графа.

читать далее «Реализация алгоритма Флойда-Уоршелла на C/C++»

Реализация преобразования string to int на C/C++

Доброго времени суток! Такие функции, как stoi, atoi, atol, soul, stof, to_string и некоторые другие появились в стандарте C++11 и уже стали привычными. Особенно для пользователей Visual Studio версии 13 года и старше. Но бывают исключительные случаи, когда под рукой нет такого крутого инструмента, а только блокнот и старенький gcc. Либо инструмент есть, но он упорно отказывается работать с C++11.

Именно с такой проблемой я недавно столкнулся. Мне позарез нужно было конвертировать строку в целое число, а мой Eclipse даже через 2 часа шаманствования с бубном так и не стал дружить с функцией stoi. Было принято волевое решение написать свою реализацию преобразования string to int. Я остановился на реализации преобразования целых десятичных положительных и отрицательных чисел, этого вполне хватило.

Функция преобразования string  to int на C/C++

читать далее «Реализация преобразования string to int на C/C++»

Реализация алгоритма Рабина-Карпа на C++

Приветствую вас, друзья мои! Сейчас я расскажу о своей первой курсовой работе, которая была написана и сдана на далеком втором курсе. Суть заключается в реализации и тестировании алгоритма Рабина-Карпа поиска подстроки в строке, в качестве языка программирования мне был рекомендован C++. В принципе больше во вступлении добавить нечего, перейдем сразу к делу.

Суть алгоритма Рабина-Карпа

Алгоритм представляет из себя улучшенную версию последовательного поиска, улучшение заключается в использовании хэш-функции. Это объясняется тем, что сравнить два числа(два хэша) гораздо быстрее и дешевле, чем сравнивать подстроки посимвольно. Сравнивать подстроки придется только один раз, когда хэши совпали, сделать это придется для увеличения надежности и защиты от случая коллизии хэша.

читать далее «Реализация алгоритма Рабина-Карпа на C++»

Реализация и криптоанализ шифра простой замены

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

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

Прежде чем продолжить чтение, обратите внимание на реализации других шифров

Шифр простой замены

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

Пример шифрования

читать далее «Реализация и криптоанализ шифра простой замены»

Реализация и криптоанализ шифра гаммирования

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

Прежде чем продолжить чтение, обратите внимание на реализации других шифров

Шифр гаммирования

Вся суть шифра описывается красивым схематичным изображением, которое я позаимствовал у википедии.gammacode1

читать далее «Реализация и криптоанализ шифра гаммирования»