Контрольная и Лабораторная работа №1,2,3 по дисциплине: Оптимизирующие компиляторы. Вариант №01

Контрольная работа представляет собой опрос. Список вопросов выбирается по последней цифре пароля из 140 штук по 14 вопросов каждому студенту (например, если у вас пароль заканчивается на цифру 5, то вы выбираете темы под номерами 5, 15, 25, 35, …, 135).
Контрольная работа должна содержать обязательно исходные данные (номер и текст вопроса)

Вопросы по теме 1
1. В чём заключается разница между компилятором и интерпретатором?
11. Какие действия производятся в фазе синтаксического анализа?
21. Какие стратегии используются компилятором для принятия решений?
31. Что представляет собой предиктивный анализ?
41. Что означает термин «алфавит языка»?
51. Из каких частей состоят продукции грамматики?
61. Что представляют собой узлы синтаксического дерева?
71. Для чего производится сборка мусора?
81. Какие соглашения используются для управления памятью и для чего?
91. Назовите варианты промежуточных представлений.
101. Что такое граф потока?

Вопросы к теме 4
111. В чём состоит преобразование "перемещение кода"?
121. Как вычисляется наибольшее количество одновременно выполняемых операций?
131. В чём заключается закон Амадаля?



ЛАБОРАТОРНАЯ РАБОТА №1
«ОПРЕДЕЛЕНИЕ ВРЕМЕНИ РАБОТЫ ПРИКЛАДНЫХ ПРОГРАММ»
Цели работы
1. Изучение методики измерения времени работы подпрограммы.
2. Изучение приемов повышения точности измерения времени работы подпрограммы.
3. Изучение способов измерения времени работы подпрограммы.
4. Измерение времени работы подпрограммы в прикладной программе.

5. ЗАДАНИЕ К ЛАБОРАТОРНОЙ РАБОТЕ
1. Написать программу на языке C или C++, которая реализует выбранный алгоритм из задания.
2. Проверить правильность работы программы на нескольких тестовых наборах входных данных.
3. Выбрать размерность массива N такой, чтобы время работы программы более медленным алгоритмом было порядка 5 секунд.
4. Оценить (на 5-10 тестах) относительное быстродействие алгоритмов.
5. Составить отчет по лабораторной работе. Отчет должен содержать следующее:
1. Титульный лист.
2. Цель лабораторной работы.
3. Вариант задания.
4. Описание методики для определения времени работы программы.
5. Результат измерения времени работы программы.
6. Полный компилируемый листинг реализованной программы и команду для ее компиляции.
7. Вывод по результатам лабораторной работы.

6. ВАРИАНТЫ ЗАДАНИЙ
№ Алгоритм 1 Алгоритм 2
1 Пузырьком Шелла



ЛАБОРАТОРНАЯ РАБОТА №2.
«ИЗУЧЕНИЕ ОПТИМИЗИРУЮЩЕГО КОМПИЛЯТОРА»
Цели работы
1. Изучение основных функций оптимизирующего компилятора, и некоторых примеров оптимизирующих преобразований и уровней оптимизации.
2. Получение базовых навыков работы с компилятором GCC.
3. Исследование влияния оптимизационных настроек компилятора GCC на время исполнения программы.

6. ЗАДАНИЕ К ЛАБОРАТОРНОЙ РАБОТЕ
1. Написать программу на языке C или C++, которая реализует выбранный алгоритм из задания.
2. Проверить правильность работы программы на нескольких тестовых наборах входных данных.
3. Выбрать значение параметра N таким, чтобы время работы программы было порядка 30-60 секунд.
4. Программу скомпилировать компилятором GCC с уровнями оптимизации -O0, -O1, -O2, -O3, -Os, -Ofast, -Og под архитектуру процессора x86.
5. Для каждого из семи вариантов компиляции измерить время работы программы при нескольких значениях N.
6. Составить отчет по лабораторной работе. Отчет должен содержать следующее.
1. Титульный лист.
2. Цель лабораторной работы.
3. Вариант задания.
4. Графики зависимости времени выполнения программы с уровнями оптимизации -O0, -O1, -O2, -O3, -Os, -Ofast, -Og от параметра N.
5. Полный компилируемый листинг реализованной программы и команды для ее компиляции.
6. Вывод по результатам лабораторной работы.

7. ВАРИАНТЫ ЗАДАНИЙ
Варианты заданий взять из лабораторной работы №1.


Лабораторная работа № 3.
Оптимизация временной сложности алгоритма

Цели работы
1. Изучение основных понятий, связанных с оценкой временной сложности алгоритмов .
2. Изучение практических приемов оптимизации кода.

2. ЗАДАНИЕ К ЛАБОРАТОРНОЙ РАБОТЕ
1. В соответствии с вариантом задания, реализовать алгоритмы так, чтобы их временная сложность соответствовала требуемой в постановке задачи или были проведены иные оптимизации (см. табл. 2). Решения представить в виде работающих программ на C++.

Таблица 2. Варианты задания
№ Алгоритм Реализация на C++ Текущая временная сложность кода Требуемая временная сложность кода и/или улучшение алгоритма
1 Выбор элементов главной диагонали квадратной матрицы A[n,n] for (int i=0; i<n; i++)
for (int j=0;j<n; j++)
if (i==j)
cout << a[i][j] << " "; O(n2) O(n)
10 Поиск в массиве натуральных чисел a[n] пары элементов со значениями item1 и item2, расстояние между которыми минимально const int n=10;
int a[n] = {
3,5,10,8,4,12,5,3,0,7
};
int item1=3,item2=8,min=n;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
{
if (a[i]==item1 &&
a[j]==item2 &&
abs(i-j)<min) {
min = abs(i-j);
}
}
cout << min; O(n2) O(n)


3. ВАРИАНТЫ ЗАДАНИЙ
Варианты заданий взять из табл. 2.
Таблица 2. Варианты заданий
№ вар. Алгоритм 1 Алгоритм 2
1  1  10

Уважаемый студент, дистанционного обучения,
Оценена Ваша работа по предмету: Оптимизирующие компиляторы
Вид работы: Контрольная работа
Оценка: Зачет
Дата оценки: 09.02.2020
Рецензия:Уважаемый ,

Уважаемый студент, дистанционного обучения,
Оценена Ваша работа по предмету: Оптимизирующие компиляторы
Вид работы: Лабораторная работа 1-3
Оценка: Зачет
Дата оценки: 11.02.2020
Рецензия:Уважаемый ,

Зырянов Кирилл Игоревич

Помогу с вашим вариантом, другой работой или дисциплиной.
E-mail: sneroy20@gmail.com