Параллельные алгоритмы вычисления компонент связности и минимальных остовных деревьев: различия между версиями

Минимальное остовное дерево графа представляет собой остовное дерево с минимальной возможной суммой весов ребер. Параллельная равнодоступная машина (PRAM) – это абстрактная модель для разработки параллельных алгоритмов и понимания возможностей параллелизма. В этой модели процессоры (каждый из которых является равнодоступной машиной) работают синхронно, обмениваясь друг с другом сообщениями при помощи совместно используемой памяти. Параллельные равнодоступные машины можно [[Вычислительная_модель_PRAM|различать]] по тому обстоятельству, разрешается ли более чем одному процессору одновременно производить операции чтения и записи с одной и той же ячейкой совместно используемой памяти. Самой сильной является модель с одновременным чтением и одновременной записью CRCW (concurrent-read, concurrent-write), самой слабой – с эксклюзивным чтением и эксклюзивной записью, EREW (exclusive-read, exclusive-write). Введение в алгоритмы PRAM см. в работах Карпа и Рамачандрана [8] и Джаджи [5].