Доброго времени суток! Буквально пару дней назад я опубликовал реализацию линейного алгоритма Флойда-Уоршелла поиска кротчайших путей между всеми вершинами взвешенного графа. В той статье я обещал разобраться и реализовать параллельный алгоритм Флойда-Уоршелла, прошло несколько дней и родилась эта статья.
Придумывать пришлось практически с нуля, потому что информации я не нашел вообще никакой, только отрывки чьих-то курсовых работ и прочие мелочи. Программного кода не найти в принципе.
В качестве инструмента будет использована уже знакомая библиотека MPICH(установка библиотеки).
Схема параллельного алгоритма Флойда-Уоршелла
В оригинальном линейном алгоритме единственная операция это нахождение минимума, как справедливо замечено в крохах источников, что я находил, ее нет смысла распараллеливать. Вся сложность алгоритма(О^3) заключается в полном переборе «матрицы смежности». Напомню, что я так называю матрицу размера NxN, в которой на пересечении i-й строки и j-го столбца стоит вес ребра из i-ой вершины в j-ую.
читать далее «Реализация параллельного алгоритма Флойда-Уоршелла» →
Доброго времени суток, друзья! Сегодня моя копилка реализованных алгоритмов на графах пополнится алгоритмом поиска кратчайших путей между всеми вершинами в графе. Для начала перечислю алгоритмы, которые уже опубликованы на сайте.
— Реализация поиска в ширину на графе;
— Реализация поиска в глубину на графе;
— Реализация топологической сортировки и поиска компонент сильной связности;
Реализация обычного алгоритма Флойда-Уоршелла нужна мне для того, чтобы запрограммировать параллельное вычисление этой задачи с помощью библиотеки MPI. Отчет о результатах распараллеливания я напишу уже совсем скоро(я очень на это надеюсь). А сейчас поговорим о стандартном алгоритме Флойда-Уоршелла.
Суть алгоритма Флойда-Уоршелла
Как я упомянул, алгоритм предназначен для нахождения кратчайших путей между всеми вершинами в графе. По сути он представляет собой простой перебор всех путей и выбор из них наименьшего. Перебор осуществляется по так называемой «матрице смежности» размера NxN, где N — количество вершин графа.
читать далее «Реализация алгоритма Флойда-Уоршелла на 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++» →
Приветствую своих маленьких всех любителей криптографии. На этот раз жертвой криптоанализа станет шифр простой замены. До него взлому подверглись такие личности, как шифр Цезаря, шифр простой перестановки и шифр гаммирования. Все они были программно реализованы и успешно взломаны.
По уровню сложности криптоанализ шифра простой замены я ставлю на почетное второе место, сразу после перестановочного шифра, над которым бился не одну неделю. Реализация по-прежнему на скриптовом языке Python. Предлагаю не растягивать вступление и сразу перейти к делу.
Прежде чем продолжить чтение, обратите внимание на реализации других шифров
Шифр простой замены
Поиграю немного в википедию и вкратце обрисую суть шифрования. Каждый символ открытого текста должен быть заменен на соответствующий ему символ из специальной таблицы. Я буду рассматривать случай, когда символы алфавита заменяются на символы из этого же алфавита, но в произвольном порядке. Грубо говоря, ключом шифрования будет служить перемешанный алфавит.
Пример шифрования
читать далее «Реализация и криптоанализ шифра простой замены» →
