Лабораторные работы по информатике

Гуманитарные науки

У нас студенты зарабатывают деньги

 Дипломы, работы на заказ, недорого

 Контрольные работы

Контрольные работы

 Репетиторы онлайн по английскому

Репетиторы онлайн по английскому

Приглашаем к сотрудничеству преподователей

Приглашаем к сотрудничеству преподователей

Готовые шпаргалки, шпоры

Готовые шпаргалки, шпоры

Отчет по практике

Отчет по практике

Приглашаем авторов для работы

Авторам заработок

Решение задач по математике

Закажите реферат

Закажите реферат

Практикум по физике Лабораторные работы по информатике Microsoft Visio Алгоритмические основы машинной графики AutoCAD
Практикум по механике и молекулярной физике
ОПРЕДЕЛЕНИЕ МОМЕНТА ИНЕРЦИИ
МАТЕМАТИЧЕСКИЙ МАЯТНИК
Физический маятник
ОПРЕДЕЛЕНИЕ МОДУЛЯ ЮНГА
ПОПЕРЕЧНЫЕ КОЛЕБАНИЯ СТРУНЫ
ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ВЯЗКОСТИ
ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ПОВЕРХНОСТНОГО НАТЯЖЕНИЯ
ОПРЕДЕЛЕНИЕ ВЛАЖНОСТИ ВОЗДУХА
ОПРЕДЕЛЕНИЕ АДИАБАТИЧЕСКОЙ ПОСТОЯННОЙ ВОЗДУХА
Вынужденные колебания линейного осциллятора
Лабораторные работы по информатике
Определение параметров n-мерных коммутационных структур
Преобразование последовательного алгоритма в параллельный
Представление алгоритмов в виде граф–схем.

Построение матрицы логической несовместимости операторов

Построение множеств взаимно независимых операторов
Определение ранних и поздних сроков окончания выполнения операторов
Запуск параллельных программ на кластере
Microsoft Visio
Спецификация требований к информационной системе
Основы работы в редакторе деловой графики Microsoft Visio 2010.
Лабораторная работа №3
Лабораторная работа №4
Функциональное моделирование
Диаграмма классов
Алгоритмические основы машинной графики

Анимация и морфинг

Отсечение прямоугольным окном
Построение проекции трехмерного объекта
Создание простых объектов
Основные навыки работы с объектами
Привязка объектов
Редактирование формы произвольных кривых
Приемы работы с контурами объектов
Создание цветных изображений
Обмен изображениями с другими программами
Ввод и редактирование текста
СИСТЕМА АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ AutoCAD
Основы работы с использованием системы AutoCAD
Команды рисования
Нанесение надписей
Команды редактирования
Проставление размеров на чертеже
Работа с блоками чертежа
 

Лабораторная работа №5. Построение множеств взаимно независимых операторов

Цель работы – ознакомление с понятием множеств взаимно независимых операторов (ВНО). Вычисление матрицы ВНО. Определение множества ВНО и упорядочение его в порядке убывания.

Теоретическая часть

Для определения возможности распараллеливания операторов необходимо произвести анализ независимости операторов по данным и по управлению. Для этих целей вводится матрица независимости операторов М.

Определение 5.1. Симметричная матрица , где V – операция дизъюнкции булевой алгебры, , если ST(i, j) = 0 и , если ST(i, j) ≠ 0 для i = 1, …, RST и j = 1, …, RST, а L(i, j) – матрица логической несовместимости, называется матрицей независимости операторов.

Матрица М отражает информационно-логические связи между операторами без учета их ориентации с учетом транзитивных связей и логическую несовместимость операторов. Например, для графа, изображённого на рисунке 5.1, матрица независимости показана на рисунке 5.2.


Рисунок 5.1. Граф G с информационно-логическими связями

Рисунок 5.2. Матрица независимости М


Следует отметить, что в соответствии с определением 5.1 для информационного графа матрица М совпадает с матрицей .

Определение 5.2. Операторы  и  – взаимно независимые (ВНО), если в матрице независимости .

Определение 5.3. Операторы  образуют полное множество ВНО, если для любого оператора  существует пара элементов матрицы независимости .

Определение 5.4. Множество, содержащее наибольшее число элементов для данного графа, называется максимально полным.

Пусть некоторый алгоритм представлен информационно-логической граф-схемой (см. рисунок 5.1). По нулевым элементам матрицы независимости М в строке каждого оператора можно указать множество тех операторов, каждый из которых при выполнении некоторых условий может быть выполнен одновременно с данным, т.е. он информационно или по управлению не зависит от данного и не является с ним логически несовместимым.

Работа алгоритма поиска полного множество ВНО основана на использовании стека. В стек поочерёдно заносятся строки матрицы М, а также строки, получаемые в результате сложения строк матрицы М по правилу дизъюнкции: , где n – размер матрицы М, а m – складываемые строки.

В стеке также хранится информация о том, на каком элементе закончился просмотр строки, и какое множество ВНО при этом сформировалось. Эта информация нужна для того, чтобы возобновить просмотр строки с того места, где была сделана остановка (очередной виток рекурсии) и с тем же набором операторов во множестве ВНО. Структура стека показана на рисунке 5.3.

Рисунок 5.3. Структура стека для хранения нуль-единичных строк

Алгоритм 5.1. Нахождение полных множеств ВНО.

Пусть W – массив полных множеств ВНО. Максимальное полное множество ВНО обозначим через A, а l – число элементов в нём. Очередное формируемое множество ВНО обозначим через D (см. рисунок 5.3), d – количество элементов в нём. Номер очередного найденного нулевого элемента в строке обозначим через k. Изначально полагаем, что стек пуст, W=, A=, l=0, D=, d=0, k=0.

Загружаем очередную i-ю строку в стек, i=1, …, n, где n – размер матрицы М. Полагаем . Если все строки обработаны, то выполнение алгоритма заканчивается. Найдены все полные множества ВНО (W) и определено максимальное (A).

В строке-вершине стека находим очередной нуль, занимающий позицию . Если нуль найден, то переходим к выполнению шага 6, иначе выполняется следующий шаг.

Если такого нуля нет или все нули найдены, выполняем проверку на полноту найденного множества D. Если в строке-вершине стека все нули соответствуют всем операторам из D, то найденное множество полное. Производим сохранение  и переходим к шагу 7. Если в строке-вершине есть хотя бы один нуль, не соответствующий операторам из D, то найденное множество не является полным. Переходим к следующему шагу.

Исключаем из стека строку-вершину (не будем забывать, что, исключая строку, мы уничтожаем и текущее значение k и D и возвращаемся к их предыдущим значениям) Если после этого стек исчерпан, выполняем шаг 2. В противном случае выполняем шаг 3.

В текущей вершине стека присваиваем . Складываем логически (поэлементная дизъюнкция) строку, исключая поля k и D (см. рисунок 5.3), из вершины стека со строкой с номером j – формируем новую вершину стека. В новой вершине стека формируем множество . Переходим к шагу 3.

Сравниваем значения d и l. Если , то A=D, l=d. Независимо от результата сравнения переходим к шагу 5.

Конец алгоритма.

Рассмотрим работу приведённого выше алгоритма (точнее его основную часть – работу по складыванию строк в стеке) на примере графа, изображённого на рисунке 5.1 и его матрицы независимости, представленной на рисунке 5.2.

Записываем в стек первую строку (i = 1) матрицы М (см. рисунок 5.4а).

Начинаем просматривать эту строку на наличие нулей, начиная со второй позиции (i + 1). Выясняем, что в первой строке нет нулей в старших позициях. Это означает, что первое найденное нами полное множество ВНО будет состоять из единственного оператора: {1}. Исключаем первую строку матрицы М из стека и заносим вторую строку (рисунок 5.4б).

Осуществляем просмотр этой строки, начиная с третьей позиции. Находим первый нулевой элемент, который стоит в позиции 3. Это нуль указывает, что операторы 2 и 3 взаимно независимы (могут выполняться параллельно). Складываем логически строки, соответствующие операторам 2 и 3. Получаем новую строку  в вершине стека и весь стек в виде, представленном на рисунке 5.4в.

Строка в вершине стека содержит нули только в тех позициях, которые соответствуют образующим её операторам 2 и 3. Это означает, что мы нашли второе полное множество ВНО {2, 3}.

Убираем из стека строку s1 и начинаем просматривать строку 2 со следующего места после остановки (когда стали формировать строку s1), т.е. с позиции 4. Находим следующий нуль, который оказывается в позиции 6. Формируем новую вершину стека, складывая логически строки 2 и 6 (рисунок 5.4г)

Новая строка содержит нули только в позициях 2 и 6. Значит, найдено ещё одно полное множество ВНО {2, 6}.

Исключаем строку s2 из стека и во второй строке находим следующий нуль, находящийся в позиции 7. Формируем новую вершину стека – строку  (рисунок 5.4д).

В этой строке нули так же соответствуют только операторам, «участвующим» в её формировании. Значит, найдено четвёртое полное множество ВНО {2, 7}.

Исключаем строку s3 из стека. Все нули строки 2 найдены, поэтому исключаем и её из стека. Помещаем в стек третью строку матрицы независимости М (рисунок 5.4е).

Находим первый нуль в строке 3 правее третьей позиции. Этот нуль стоит в позиции 4. Складываем логически строки 3 и 4. Формируем новую строку в вершине стека и весь стек в виде, представленном на рисунке 5.4ж.

Строка s4 содержит нули не только в позициях 3 и 4. Первый такой нуль, правее позиции 4, находится в позиции 5. Формируем новую вершину стека . Стек принимает вид, показанный на рисунке 5.4и.

Строка s5 содержит нули только в позициях 3, 4, 5. Это значит, что найдено очередное полное множество ВНО {3, 4, 5}.

Исключаем строку s5 из стека. Строка s4 также исчерпана, поэтому исключаем и её. Просматриваем дальше строку 3. Следующий нуль будет найден в позиции 5. Формируем новую вершину стека, складывая логически строки 3 и 5 (рисунок 5.4к).

Рисунок 5.4. Пример работы алгоритма нахождения полных множеств ВНО. Начало

Проверяем полученную строку на наличие нулей правее позиции 5. Таких нулей нет. Казалось бы, можно формировать очередное полное множество ВНО {3, 5}, но не будем торопиться. Проверим множество {3, 5} на полноту. Для этого достаточно проверить строку s6 на наличие «дополнительных» нулей (т.е. нулей, позиции которых не совпадают с номерами из найденного множества ВНО), левее позиции 5. В строке s6 есть такой «дополнительный» нуль – в позиции 4. Это означает, что множество ВНО {3, 5} не является полным и его необходимо отбросить.

Следует обратить внимание на то, что проверку на полноту необходимо проводить лишь после получения «полного» множества ВНО, т.е. когда все нули правее последнего оператора из множества ВНО найдены. Если такую проверку проводить не после получения множества ВНО, а во время, то, к сожалению, будут полностью потеряны все возможные полные множества ВНО, которые могли бы получиться в результате дальнейших действий с данной строкой.

Рисунок 5.4. Окончание

Исключаем строку s6 из стека. Дальнейший просмотр строки 3 не выявил новых нулей, поэтому исключаем и её из стека. Поскольку стек пуст, то помещаем туда следующую строку – 4 (рисунок 5.4л).

Начинаем просмотр строки 4 с позиции 5. Первый нуль как раз находится в позиции 5. Складываем логически строки 4 и 5 (рисунок 5.4м).

В получившейся строке s7 имеются нули правее позиции 5. Найденный нуль занимает позицию 6. Формируем новую строку . Тогда стек будет иметь вид, изображённый на рисунке 5.4н.

Строка в вершине стека содержит нули только в позициях, соответствующих операторам, «участвующим» в её формировании. Значит, найдено ещё одно (шестое по счёту) полное множество ВНО {4, 5, 6}.

Убираем из стека строку s8. Следующий найденный нуль в строке s7 находится в позиции 7. Складываем соответствующие строки (s7 и 7). Получаем новую строку в вершине стека и весь стек в виде, показанном на рисунке 5.4о.

Строка s9 содержит нули только в позициях 4, 5 и 7. Это значит, что найдено очередное полное множество ВНО {4, 5, 7}.

Выгружаем строку s9 из стека. Строка s7 так же исчерпана, поэтому исключаем и её. Следующий найденный нуль в строке 4 занимает позицию 6. Формируем новую вершину стека, складывая строки 4 и 6 (рисунок 5.4п).

Получившаяся строка не содержит нулей правее позиции 6. Однако экзамен на полноту тоже не выдерживает: в позиции 5 появился «дополнительный нуль». Это значит, что найденное множество ВНО {4, 6} не является полным (т.е. комбинация операторов 4 и 6 уже встречалась с какими-то другими операторами, образующими полное множество ВНО) и его необходимо отбросить.

Исключаем строку s10 из стека. Следующий найденный нуль в строке 4 находится в позиции 7. Формируем новую строку  и помещаем её в вершину стека (рисунок 5.4р).

Ищем нули во вновь образованной строке правее позиции 7. Такой нуль есть – он находится в позиции 8. Формируем строку  и помещаем её в вершину стека. Стек будет выглядеть так, как показано на рисунке 5.4с.

Строка s12 содержит нули только в позициях 4, 7 и 8. Это означает, что найдено восьмое полное множество ВНО {4, 7, 8}.

Убираем строку s12 из стека. Строка s11 так же исчерпана, поэтому исключаем её из стека. В стеке остаётся единственная 4-ая строка. Последний найденный нуль находится в позиции 8. Формируем новую вершину стека, складывая строки 4 и 8 (рисунок 5.4т).

В получившейся строке обнаруживаем «дополнительный» нуль левее 8-ой позиции, но не совпадающий с позицией 4. Это значит, что найденное множество ВНО {4, 8} не является полным и его необходимо исключить из рассмотрения.

Исключаем строку s13 из стека. Строка 4 пройдена до конца, следовательно, её так же нужно исключить из стека. Заносим в стек следующую – 5-ую строку матрицы независимости М (рисунок 5.4у).

Строка 5 содержит нуль в позиции 6. Формируем новую вершину стека . Стек будет выглядеть так, как представлено на рисунке 5.4ф.

В строке s14 нет нулевых элементов, правее позиции 6. Проверим найденное множество ВНО на полноту. Выясняем, что в позиции 4 строки s14 есть «дополнительный» нуль – найденное множество ВНО не полное, поэтому отбрасываем его.

Выгружаем строку s14 из стека. Следующий нуль в строке 5 занимает позицию 7. Складываем логически строки 5 и 7 и формируем новую вершину стека – строку s15 (рисунок 5.4х).

Анализируя строку s15, замечаем, что эта строка содержит «дополнительный» нуль левее позиции 7, который не совпадает с позицией 5. Делаем вывод, что множество ВНО {5, 7} не является полным и отбрасываем его.

Исключаем строку s15 из стека. Строка 5 оказывается пройдена до конца, поэтому исключаем её. Помещаем в стек строку 6 (рисунок 5.4ц).

В этой строке нет нулевых элементов правее позиции 6. Возникает ситуация, похожая на ту, что складывалась на шаге 1. Проверим, является ли множество ВНО {6} полным. В отличие от шага 1, данное множество не является полным т.к. в строке 6 существуют другие нули, помимо позиции 6. Отбрасываем это множество.

Убираем строку 6 из стека и загружаем туда строку 7 (рисунок 5.4ш).

Строка 7 содержит нуль в позиции 8, следовательно, формируем новую строку  и помещаем её в вершину стека (рисунок 5.4э).

Обнаруживаем «дополнительный» нуль в строке s16 в позиции 4. Это говорит о том, что множество ВНО {7, 8} не является полным и его необходимо отбросить.

Выгружаем из стека строку s16. Все комбинации операторов с участием оператора 7 исчерпаны. Исключаем строку 7 из стека. Загружаем последнюю 8-ю строку в стек (рисунок 5.4ю).

В восьмой строке (как и в шестой) имеются нули левее позиции 8. Это значит, что множество ВНО {8} не является полным и его необходимо отбросить.

Таким образом, найдено 8 полных множеств ВНО: {1}, {2,3}, {2,6}, {2,7}, {3,4,5}, {4,5,6}, {4,5,7}, {4,7,8}.

Вопросы для самопроверки

Дайте определение полных множеств ВНО.

С какой целью строится максимально полное множество?

Что называется взаимной независимостью операторов?

Как строится матрица независимости?

Задание на лабораторную работу

Необходимо дополнить разработанные ранее программы следующими функциями: расчет и отображение отраженной матрицы . Расчет и отображение матрицы независимости M. Нахождение максимально полного множества ВНО.

Продемонстрировать работающую программу преподавателю и получить отметку о её выполнении.

Сохранить копию программы для выполнения последующих лабораторных работ на дискете.

Оформить отчет о проделанной работе.

Содержание отчета

Цель работы.

Ответы на вопросы для самопроверки.

Схемы алгоритмов и их описание.

Распечатки экранных форм, полученных в результате работы программы.

Анализ полученных результатов.

Лабораторные работы