Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Алгоритм автоматического распараллеливания арифметических

ЛЕКЦИЯ 6.

ВИДЫ АДМИНИСТРАТИВНЫХ ПРАВОНАРУШЕНИЙ.

1. В зависимости от сферы совершения:

- совершенные в экономической сфере;

- совершенные в административно-политической сфере;

- совершенные в социально-культурной сфере;

2. В зависимости от родового объекта посягательства:

- права граждан (глава 5 КоАП РФ);

- здоровье, санитарно-эпидемиологическое благополучие населения, общественную нравственность (глава 6 КоАП РФ);

- собственность (глава 7 КоАП РФ);

- окружающая природная среда и природопользование (глава 8 КоАП РФ);

-промышленность, строительства, энергетика (глава 9 КоАП РФ);

- сельское ходатайство, ветеринария, мелиорация земель (глава 10 КоАП РФ);

- транспорт (глава 11 КоАП РФ);

- дорожное движение (глава 12 КоАП РФ)

- связь и информация (глава 13 КоАП РФ);

- предпринимательская деятельность (глава 14 КоАП РФ);

- финансы, налоги и сборы, рынок ценных бумаг (глава 15 КоАП РФ);

- таможенное дело (глава 16 КоАП РФ);

- институты государственной власти (глава 17 КоАП РФ);

- защита государственной границы РФ и режим пребывания иностранных граждан и лиц без гражданства на территории РФ (глава 18 КоАП РФ);

- порядок управления (глава 19 КоАП РФ);

- общественный порядок и общественную безопасность (глава 20 КоАП РФ);

- воинский учет (глава 21 КоАП РФ).

3. В зависимости от характера деяния:

- совершенные в форме действия;

- совершенные в форме бездействия;

4. В зависимости от субъекта правонарушения:

- совершаемые индивидуальным субъектом;

- совершаемые юридическими лицами;

- совершаемые как индивидуальным, так и юридическими лицами;

5. В зависимости от формы вины:

- совершенные умышленно;

- совершенные по неосторожности;

6. В зависимости от состояния физического лица, совершивше­го правонарушение:

- совершенное лицом в трезвом состоянии;

- совершенное лицом в состоянии опьянения;

- совершенное лицом с психическими отклонениями.

 

 

выражений (по А.В.Вальковскому)

 

Этот метод, использует отношение старшинства между операциями. Идея метода в том, что в выражении выделяются подвыражения, содержащие самые высокоприоритетные операции. Выделенные подвыражения одинаковой глубины «склеиваются» в более крупное подвыражение, таким образом «вырастает» выражение, все подвыражения которого имеют равномерную глубину.

Обычно в качестве знаков арифметических операций используют: +, -, *, /,!,μ. Две последние операции — возведение в степень и унарный минус. При неформальном изложении знак умножения * иногда опускается. Вводится стар-

шинство, или приоритет, операций:

 

Pr(μ) = 4; Pr(!) = 3; Pr(*) = Pr(/) =2; Pr(+) = Pr(-) = 1.

 

Опишем один вариант алгоритма более подробно, используя для наглядности только лишь выражения с операциями +, *.

Для хранения текущей информации нам потребуется следующая память:

ячейки х — для сканируемых операндов, у — для сканируемых операций, L —

для операции, стоящей слева от текущего операнда, R — для аналогичной опе-

рации справа, Out — для выходного выражения, Т i — ячейки для записи про-

межуточных результатов. Кроме того, воспользуемся вектор-стеком: St = (St1,

St2) — компонента St1 для операндов; St2 — для операций; Sc — процедура

сканирования следующего символа входной строки; символ —> обозначает за-

сылку. Считается, что входное выражение слева и справа ограничено пробелами, Рг (▬) = 0. Первоначально в R и Out содержится пробел.

Шаг 1. Sc —> х, Sc—> у, R —> L, у — > R. Сканируется очередной опе-

ранд и знак операции после него. Операция (пробел) слева от операнда х засы-

лается в ячейку L, справа от x — в ячейку R.

Шаг 2. Если ( St = O OR Рг (L) < Рг (R) OR Рг (St2)<Рг (L) ) AND Рг (R)≠

O, то на шаг 3, иначе на шаг 4.

Шаг 3. х —> St1, y —> St2, переход на шаг1. Запоминаем операнд и операцию и переходим к сканированию следующей пары (операнд, операция).

Шаг 4. Если Рг (L) = Рг (St2), то на шаг 5, иначе на шаг 6.

Шаг 5. Out Tk у —> Out. Если Pr (y) = 0, то конец разбора, иначе па шаг 1. Здесь промежуточная ячейка Тk = (St1 St2 x). Таким образом, когда найдены две операции одного старшинства, первая из них с соседними операндами группируется в промежуточный результат Tk, вслед за ним выписывается вторая операция, и все это приписывается к выходной строке. Далее Tk воспринимается алгоритмом как атомный операнд.

Шаг. 6. Out х у —> Out, если у = "_", то конец разбора, иначе на шаг. 1. В

случае если не находится двух операций одного старшинства и приоритеты

пошли на убывание, операнд и операция просто приписываются к выходной

строке.

Приведенный алгоритм описывает один из проходов, после которого неко

торые из подвыражений «свертываются» в промежуточные результаты Т k. По-

сле этого алгоритм повторяется до тех пор, пока все выражение не сведется к

единственному Tk.

Покажем выражение е = а + b + с * d* I* f + g после серии последо-

вательных проходов.

1. Входная строка: ▬ а + b +c*d*l*f+g ▬.

2. Результат 1-го прохода: ▬ T1 + T2 * Т3 + g ▬, где

T1 = (а + b), T2 = (с*d), Т3 = (1 *f).

3. Результат 2-го прохода: ▬ T4 + Т5 ▬, где

T4 = (T2 * T3), T5 = (T1 + g).

4. Результат 3-го прохода: ▬T6 ▬; T6 = (T4 + T5).

5. Выходная строка: ▬ (((с * d) * (l * f)) + ((а + b ) + g))

Представим таблицу, подробно описывающую весь процесс преобразования указанного выражения.

Проход Такт x y L R Out
    a + +     a +
  b + + + +    
  c * + * +   c *
  d * * * +*    
  l * * * +*   l *
  f * * * +*+    
  g * +*+g▬      
    + + +   +
  * + * +*   + *
  + * + ++ =* +
  g + + =+g    
    + + +   +
  +      

 

 

Дерево выходного выражения (ЯПФ, полученная на основе сравнения старшинства операций)

 

 

 

Доказано, что описанный алгоритм дает в результате выражение с мини-

мальным временем выполнения. Однако он имеет ряд существенных недостат-

ков, главный из которых—многопроходность: он требует столько проходов, ка-

ково время выполнения сгенерированного выражения. Чтобы избавиться от

многопроходности, нужно в процессе разбора «нести» попутно информацию об

уровне формируемых конструкций. Имеется однопроходная версия метода.

 

<== предыдущая лекция | следующая лекция ==>
 | ЛЕКЦИЯ 7. Алгоритм распараллеливания программы базового блока
Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 668; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.01 сек.