|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[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) называется прямоугольная таблица чисел. |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||