Главная » Просмотр файлов » Тема 07(2016)Анализ на основе областей

Тема 07(2016)Анализ на основе областей (1161802)

Файл №1161802 Тема 07(2016)Анализ на основе областей (Лекции)Тема 07(2016)Анализ на основе областей (1161802)2019-09-19СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

7. Анализ потока данныхна основе областей17.1 Области графа потока управления7.1.1. Определение областиОпределение. Областью графа потока называется его подграфR = NR, ЕR такой, что1. существует узел h  NR, доминирующий над всеми узлами в R;этот узел называется заголовком области R;2. если из некоторого узла r2 графа потока управления можнодостичь узла r1  R, минуя заголовок h, то и r2  R;3. множество ЕR включает все ребра графа потока управлениямежду любыми узлами r1, r2  R, за исключением некоторыхребер, входящих в заголовок h;4. единственным входом в область является ее заголовок.27.1 Области графа потока управления7.1.1.

Определение областиПример 1.37.1 Области графа потока управления7.1.1. Определение областиПримеры.7. Рассмотрим граф на рисунке справа1) узлы В1 и В2 вместе с ребром В1  В2образуют область с заголовком В12) узлы В1, В2 и В3 и ребра В1  В2,В2  В3, В1  В3образуют область с заголовком В147.1 Области графа потока управления7.1.1. Определение областиПримеры.1.

Рассмотрим граф на верхнем рисунке3) подграф R = {В2, В3}, {В2  В3} область необразует, так как управление может попастьв него и через В2, и через В3:В2 не является доминатором В3,В3 не является доминатором В2и, следовательно, условие 1 определения 7.1.1(существует узел h  NR, доминирующийнад всеми узлами в R;)не выполняется (нижний рисунок)57.1 Области графа потока управления7.1.1.

Определение областиПример 2.Суперблок (рассматривался, когда изучался метод глобальнойнумерации значений) – пример области. В частности граф нарисунке – область с заголовком В1.Узел В1 доминирует над остальными узламиB1B2B3B4B567.1 Области графа потока управления7.1.1. Определение областиПример 3.Граф на рисунке – область с заголовком В3(естественный цикл).77.1 Структурный анализ графа потока управления7.1.2.

Классификация областей Определения:(1) Каждый базовый блок B может рассматриваться как областьR = {B}, . Такая область называется область-лист.(2) Пусть L – самый внутренний цикл гнезда циклов.Тело цикла L (все узлы и ребра, за исключением обратных реберк заголовку цикла) можно заменить узлом, представляющимобласть R. Такая область называется область-тело.(3) Если к области-телу R, соответствующей телу цикла Lприсоединить обратное ребро к заголовку цикла L, получитсяновая область Q. Такая область называется область-цикл.87.1 Структурный анализ графа потока управления7.1.2. Виды областей. ПримерR1R2R3R4R5R6R7Фрагмент процедурыБазовые блоки – области-листья97.1 Структурный анализ графа потока управления7.1.2.

Виды областей. ПримерR2R3R4R5R6Тело внутреннего цикла107.1 Структурный анализ графа потока управления7.1.2. Виды областей. ПримерR2R8R3R4R5можно заменить наобласть-тело R8R6Тело внутреннего цикла117.1 Структурный анализ графа потока управления7.1.2. Виды областей. ПримерR2R8R3R4R5R6можно заменить наобласть-тело R8добавив обратнуюдугу,R8получим областьцикл R9Тело внутреннего циклаR9127.1 Структурный анализ графа потока управления7.1.2. Виды областей.

ПримерГраф потокауправления примет видТело внешнего циклаR10R1R1R9R9R7Добавив обратнуюдугу, получимобласть-цикл R11R7R11R10Заменяетсяобластью-телом R10137.1 Структурный анализ графа потока управления7.1.2. Виды областей. ПримерДерево управленияR11R10R1R9R7R8R2R3R4R5R6147.1 Структурный анализ графа потока управления7.1.3.

Выделение областей Рассмотрим ГПУ, показанный на рисунке.B1B2B3B4B5ijaiaj..- m, 1nu1+ i, 1u2u3. .d1d2d3d4d5d6157.1 Структурный анализ графа потока управления7.1.3. Выделение областей1) Заменив базовые блокиEntry, B1, ..., B5, Exitобластями-листьямиRen, R1, …, R5, Rex ,получим граф167.1 Структурный анализ графа потока управления7.1.3. Выделение областей2) Области-листья R2, R3 и R4 и ребра R1R2, R2R3,R2 R4, R3 R4, R3 R5, R4 R5составляют область-тело R6 .R6 = {R2, R3, R4}, {R1R2, R2R3, R2R4, R3R4,R3R5, R4R5}R2R6R6R3R4177.1 Структурный анализ графа потока управления7.1.3.

Выделение областей3) Область-тело R6, и обратное ребро R4  R2составляют область-цикл R7 = {R6}, {R4 R2}.R7R7187.1 Структурный анализ графа потока управления7.1.4. Алгоритм построения иерархии областей Алгоритм.1.Найти все естественные циклы.2.Найденные естественные циклы упорядочить изнутригнезд наружу, т.е. начиная с наиболее внутренних циклов.3.Выбрать очередной естественный цикл (сначала – самыйпервый, потом – следующий по порядку).Если циклов больше нет, алгоритм заканчивается.4.Тело выбранного цикла L (все узлы и ребра, за исключениемобратных ребер к заголовку) заместить узлом R,представляющим область-тело.После замещения обратное ребро в заголовок L становитсяпетлей.5.Построить область-цикл Q, представляющую цикл L(в отличие от области R область Q не содержит петли).Перейти к шагу 3.197.1 Структурный анализ графа потока управления7.1.5. Построение иерархии областей Пример.

Применим алгоритм к следующему ГПУИсходный ГПУ207.1 Структурный анализ графа потока управления7.1.5. Построение иерархии областей Пример. Применим алгоритм к следующему ГПУИсходный ГПУБазовые блокизаменены областямилистьями217.1 Структурный анализ графа потока управления7.1.5. Построение иерархии областей Пример. Применим алгоритм к следующему ГПУИсходный ГПУБазовые блокизаменены областямилистьямиПосле шага 2227.1 Структурный анализ графа потока управления7.1.5. Построение иерархии областей Пример.После шага 4После шага 5Область R8 – весь ГПУ237.1 Структурный анализ графа потока управления7.1.5. Построение иерархии областей Пример.Исходный ГПУПоследовательность преобразований247.1 Структурный анализ графа потока управления7.1.5.

Построение иерархии областей Пример.Вся иерархияДерево управления257.1 Структурный анализ графа потока управления7.1.5. Построение иерархии областей Пример.Исходный ГПУДерево управления267.1 Структурный анализ графа потока управления7.1.6. Алгоритм построения восходящего порядка областей Вход: приводимый ГПУ G. Выход: список областей графа G, который может использоваться взадачах анализа потоков данных на основе областей. Метод: выполняем следующие действия.1)Составляем список областей-листьев, состоящих из отдельныхблоков в произвольном порядке.2)Выбираем очередной естественный цикл L, такой, что всеобласти, соответствующие естественным циклам, содержащимсяв L, уже внесены в список.

Сначала добавляем в список область-тело для L, а затем – область-цикл L.3)Если весь граф G является естественным циклом, добавляем вконец списка область, состоящую из всего графа потока целиком.277.1 Структурный анализ графа потока управления7.1.7. Скорость сходимости итерационных алгоритмовПостроение областей и дерева управления позволяет ускоритьобход графа потока управления во время выполнения различныхалгоритмов анализа потока данных.В алгоритмах анализа потока данных, в которых в качестве сбораиспользуется объединение, удается, заменив каждый цикл узломтипа область-цикл, оставить только ациклические пути дляраспространения атрибутов.Это позволяет сократить время выполнения соответствующегоанализа потока данных.287.2.

Анализ потока данных на основе областей7.2.1. Схема анализа потока данных на основе областейНа каждом уровне иерархии областей: Для каждой области R и для каждой подобласти R'  R вычисляется передаточная функцияf R , InR , суммирующая влияниевсех возможных путей в R, ведущих от входа в R ко входу в R'.Мы рассматриваем анализ в прямом направлении (сверху вниз).Анализ в обратном направлении рассматривается аналогично сочевидными изменениями.297.2. Анализ потока данных на основе областей7.2.1.

Схема анализа потока данных на основе областейНа каждом уровне иерархии областей: Для каждой области R и для каждой подобласти R'  R вычисля-fется передаточная функция R , In R  , суммирующая влияниевсех возможных путей в R, ведущих от входа в R ко входу в R‘. Например, для области R6и её подобластей R2, R3 и R4будут вычислены передаточные функцииf R6 , InR2 f R6 , InR3 f R6 , InR4 307.2.

Анализ потока данных на основе областей7.2.1. Схема анализа потока данных на основе областейНа каждом уровне иерархии областей: Область R  R называется выходной подобластью области R,если у R есть выходное ребро к некоторой области,не принадлежащей области R. Для каждой выходной области R  R вычисляется передаточнаяфункцияf R ,Out R, суммирующая влияние всех возможныхпутей в R, ведущих от выхода из R к выходу из R.317.2.

Характеристики

Тип файла
PDF-файл
Размер
1,73 Mb
Материал
Тип материала
Высшее учебное заведение

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6451
Авторов
на СтудИзбе
305
Средний доход
с одного платного файла
Обучение Подробнее