A3_2010 (Варианты языков от Волковой), страница 2

Системный (интегрированный) программный продукт есть комплекс (взаимосогласованных) программных продуктов (пакет).

КРИТЕРИИ: За отсутствие комментариев к какому-либо виду программ: -4.

7. Перечислить основные виды оптимизации циклов. Привести пример оптимизационного преобразования цикла.

Ответ: (1) вынесение инвариантных вычислений из тела цикла, (2) замена операций с переменными цикла, (3) слияние, (4) расщепление и (5) развертывание циклов

Например, расщепление цикла:

f or (i = 0; i < n; i ++) if (x < y)

{ if (x < y) { S₁; } for (i = 0; i < n; i ++) { S₁; }

else { S₂; } } else for (i = 0; i < n; i ++) { S₂; }

КРИТЕРИИ: (a) За отсутствие какого-либо из видов оптимизации: -2.

(б) За отсутствие примера: -4.

8. Описать деление библиотек систем программирования по функциональному признаку, дать краткие характеристики содержания различных видов библиотек. Признаки каких из перечисленных Вами видов библиотек можно наблюдать в стандартной библиотеке языка С++?

Ответ: По функциональному наполнению современные библиотеки делятся на (1) библиотеки функций (процедур) и макроопределений, (2) библиотеки классов и (3) библиотеки компонентов. В свою очередь библиотеки классов могут представлять собой (2.1) совокупности независимых классов, (2.2) иерархии классов, (2.3) иерархии шаблонов классов. Библиотека С++ относится к библиотекам, построенным на основе иерархий шаблонов классов с добавлением отдельных функций и макроопределений.

1. Библиотеки функций (процедур) и макроопределений содержат простые (с точки зрения библиотек) составные части, некоторые из которых имеют только неформализованные, семантические связи

2. Библиотеки классов, в зависимости от степени своей организации, содержат более или менее формально связанные и структурированные описания и реализации классов объектов.

3. Библиотеки компонентов содержат тесно связанные описания и реализации сложных программных объектов, предназначенных для совместного использования.

КРИТЕРИИ: За пропуск какого-либо вида библиотек: -2 (за каждый пропуск из 3-х видов библиотек и 3-х подвидов библиотек классов).

За пропуск объяснения: -3 (за каждый из трёх).

9. Дать определение эквивалентных грамматик. Для контекстно-свободной грамматики G построить эквивалентную ей неукорачивающую грамматику, выписывая результаты применения каждого шага используемого алгоритма.

G: S  Ab | BaCaC A  Ca B  Cb C  Aa | Bb | a | ε

Ответ: Грамматики G₁ и G₂ называются эквивалентными, если их языки совпадают: L (G₁) = L (G₂).

Строим множество правил X, в которое входят все правила, из которых за некоторое число шагов выводится пустая цепочка:

1. X₀ = {C}

2. X₁ = {C}, N₁ = N₀

Строим множество правил P', в которое входят все правила, кроме правил вида R  ε:

P': S  Ab | BaCaC A  Ca B  Cb C  Aa | Bb | a

Дополняем множество правил P' правилами с всевозможными комбинациями вхождений и невхождений символа C, так как в исходной грамматике есть правило С ε:

P'': S  Ab | BaCaC | BaaC | BaCa | Baa

A  Ca | a B  Cb | b C  Aa | Bb | a

P_неукор = P''

КРИТЕРИИ: Нет определения или оно неверно: 0.

За каждую существенную ошибку при преобразовании: -3.

10. По приведенной обратной польской записи фрагмента программы, написанной на языке Си++, восстановите этот фрагмент двумя способами: сначала, пользуясь операторами условного и безусловного перехода на метку, а затем (если это возможно), пользуясь только операторами структурного программирования без переходов. Операция ПОЛИЗ '@' соответствует унарной операции изменения знака.

Ответ: t = (p ++) + (++ q) / (– t) * 4;

L: if (! (t < u)) goto E;

goto N;

M: ++ t; goto L;

N: r –= p + 7; goto M;

E: r = r % 2;

for (t = (p ++) + (++ q) / (– t) * 4; t < u; ++ t) r –= p + 7; r = r % 2;

КРИТЕРИИ: за неверный ответ на первый вопрос: -7.

за неверный ответ на второй вопрос, если первый вариант верен: -3, иначе: -10