Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683

линейный класс
. 
Для любой его программы проводится самый тщательный анализ 
информационной структуры. Второй уровень открытый. В него входят все 
программы, которые каким
-
либо способом сводятся к программам базового 
уровня.
Алгоритм может быть записан с помощью следующих средств языка:
- 
в программе может использоваться любое число простых 
переменных и переменных с индексами;
- 
единственным типом исполнительного оператора может быть 
оператор присваивания, правая часть которого есть арифметическое 
выражение; допускается любое число таких операторов;
- 
все повторяющиеся операции описываются только с помощью 
циклов БО; структура вложенности циклов может быть произвольной; шаги 

---

171 
изменения параметров циклов всегда равны +1; если у цикла нижняя граница 
больше верхней, то цикл не выполняется;
- 
допускается использование любого числа условных и 
безусловных операторов перехода, передающих управление "вниз" по тексту; 
не допускается использование побочных выходов из циклов;
- 
все индексные выражения переменных, границы изменения 
параметров циклов и условия передачи управления задаются, в общем 
случае, неоднородными формами, линейными как по параметрам циклов, так 
и по внешним переменным программы; все коэффициенты линейных форм 
являются целыми числами;
- 
внешние переменные программы всегда целочисленные, и 
вектора их значений принадлежат некоторым целочисленным
многогранникам; конкретные значения внешних переменных известны 
только перед началом работы программы и неизвестны в момент ее 
исследования.
Программы, удовлетворяющие описанным условиям, будем называть 
линейными или 
принадлежащими линейному классу
. 
Подход к изучению программ называется 
статическим
, если анализ 
информационной структуры программ из линейного класса, опирающийся 
только на анализ текста программ, без привлечения каких
-
либо 
дополнительных сведений как о самих программах, так и об описанных ими 
алгоритмах. Его основное достоинство заключается в том, что вся 
информация о структуре программы получается до ее реализации и, 
следовательно, может быть использована наиболее эффективно. Главная 
трудность проведения статического анализа связана с тем, что тексты 
программ почти всегда зависят от внешних переменных, значения которых 
не известны. Поэтому все исследования приходится проводить для 
параметризованных объектов.
1. 
Рассмотрите любой известный вам язык программирования. Как 
на этом языке описывается линейный класс программ?

---

172 
2. 
Приведите различные примеры программ, которые формально не 
являются линейными, но становятся таковыми после каких
-
то эквивалентных 
преобразований.
3. 
'Пусть программа содержит вызовы процедур. Предложите 
различные способы замены этих вызовов программными фрагментами, при 
которых исходная программа становится линейной и сохраняет все прежние 
информационные зависимости.
4. 
Приведите различные примеры программ, которые формально не 
являются линейными и которые вы не можете привести к линейным с 
помощью эквивалентных преобразований.
5. 
Как выглядят графы алгоритмов для примеров п. 4?
6. 
Насколько различны графы алгоритмов для примеров п. 4?
7. 
Как часто примеры п. 4 встречались в вашей практике?