Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[218]

Видеопамять можно рассматривать как матрицу битов М размера рхр (считаем, что точки бывают чёрными и белыми). При этом на дисплее видна её часть - верхняя левая подматрица размера га X га. Определим операцию переноса блока битов (Block Transfer of bits, BitBLT). Процедура BlTBLT(ri, c\, r2, c2, гаг, гас, *) выполняет присваивания

M[r2 + i, c2 + j] <- M[r2 + i, c2 + j] * M[ri + г, ci + j]

для всех г = 0,1,... , гаг - 1, j = 0,1,... , гас - 1. Здесь * обозначает любую из 16 бинарных логических операций.

Пусть требуется транспонировать видимую часть изображения: <- M[j,i]. Будем предполагать, что время копирования битов меньше, чем время переноса блока битов, так что мы оцениванием именно число операций BitBLT.

Докажите, что можно транспонировать изображение, вызвав процедуру BitBLT всего лишь O(lgra) раз. Предполагается, что р существенно больше, чем га, так что имеется большое рабочее пространство, где можно сохранять промежуточные результаты. Какая часть этого пространства используется? (Указание: используйте подход «разделяй и властвуй», запуская процедуру BitBLT с операцией И).

30.7. Комментарии

Параллельные алгоритмы для комбинаторных задач описывают Акл [9], Карп и Рамачандра [118] и Лейтон [135]. Различные модели параллельных вычислений описали Хванг и Бриггс [109], а также де Гроот [110].

Начало теории параллельных вычислений относится к концу 1940-х годов XX века, когда Дж. фон Нейман [38] ввёл понятие клеточного автомата, который по сути является двумерным массивом процессоров с конечным числом состояний, расположенных в узлах клетчатой бумаги, сетке. Модель PRAM ввели Форчун и Вайли [73] (похожие модели предлагались многими авторами и раньше).

Метод переходов по указателям был предложен Вайли [204]. Параллельная обработка префиксов была рассмотрена в работе Оф-мана [152] (в контексте сложения с предвычислением переносов). Метод эйлерова цикла предложили Тарьян и Вишкин [191].

Соотношения между числом процессоров и временем для задачи нахождения максимума га элементов изучал Валиантом [193]; он же доказал, что для этой задачи не существует эффективного по затратам алгоритма со временем работы 0(1). Кук, Дворк и Рай-шук [50] доказали, что вычисление максимума на CREW-машине требует времени £7(lgra). Метод моделирования CRCW-машины с


помощью EREW-машины предложил Вишкин [195].

Теорему 30.2 доказал Брент [34]. Эффективный эффективный алгоритм для нахождения номеров в списке предложили Андерсон и Миллер [11]. Они предложили также эффективный детерминированный алгоритм для этой задачи [10]. Детерминированный алгоритм нарушения симметрии взят из работы Гольдберга и Плоткина [84]; он основан на похожем алгоритме с тем же временем работы, который придумали Коул и Вишкин [47].


31

Матрицы и действия с ними

Матрицы часто встречаются в научных расчётах, поэтому важно уметь эффективно с ними работать. Эта глава содержит краткое введение в теорию матриц и операций над ними. Особое внимание уделяется умножению матриц и решению систем линейных уравнений.

В разделе 31.1 мы введём основные понятия и обозначения. В разделе 31.2 излагается алгоритм Штрассена, позволяющий умножить две матрицы размера га X га за время 0(ralg7) = 0(га281). (Появление алгоритма умножения матриц, работающего быстрее, чем стандартный, было в своё время большой неожиданностью.) В разделе 31.3 мы введём понятия квазикольца, кольца и поля, а затем сформулируем допущения, необходимые для правильной работы алгоритма Штрассена. Этот раздел содержит также асимптотически быстрый алгоритм перемножения булевых матриц, основанный на алгоритме Штрассена. В разделе 31.4 рассказывается, как решать системы линейных уравнений с помощью так называемого LUP-разложения. В разделе 31.5 мы обсудим связь между задачей умножения матриц и задачей обращения матрицы. Наконец, в разделе 31.6 мы рассмотрим симметрические положительно определённые матрицы и покажем, как с их помощью можно решать переопределённые системы линейных уравнений методом наименьших квадратов.

31.1. Матрицы и их свойства

В этом разделе мы напомним основные понятия теории матриц, используемые в дальнейшем. Матрицы и векторы.

Матрицей (matrix) называется прямоугольная таблица чисел.



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]