Контрольная работа

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

Вопросы по теме 1
1. В чём заключается разница между компилятором и интерпретатором?
2. Каковы преимущества компилятора перед интерпретатором.
3. Каковы преимущества интерпретатора перед компилятором?
4. Каковы преимущества системы обработки языка, в которой компилятор даёт выход на языке ассемблера, по сравнению с системой, в которой компилятор даёт выход на машинном языке?
5. В чём заключается основная задача компилятора?
6. На какие две части можно разделить процесс отображения исходного кода в целевую программу?
7. Какая информация хранится в таблице символов?
8. Перечислите фазы компилятора?
9. Что такое лексема?
10. Назовите компоненты токена.
11. Какие действия производятся в фазе синтаксического анализа?
12. Какие действия производятся в фазе семантического анализа?
13. Что представляет собой синтаксическое дерево?
14. Какова функция фазы машинно-независимой оптимизации?
15. Какие модели используются при разработке компиляторов?
16. Каким требованиям должны отвечать оптимизации, выполняемые компилятором?
17. Какова наиболее важная цель при написании компилятора?
18. В чём заключается вторая цель при написании компилятора?
19. Какие основные технологии используются для получения высокопроизводительных систем?
20. Какие факторы приводят к ограничению производительности систем?
21. Какие стратегии используются компилятором для принятия решений?
22. Что такое область видимости программы?
23. Какие два отображения используются для описания связи имён переменных с их местоположением?
24. Что такое идентификатор?
25. Что такое переменная?
26. Какие используются механизмы передачи параметров?

Вопросы к теме 2
27. Какие компоненты имеет контекстно-свободная грамматика?
28. Для чего используется модель «дерево разбора»?
29. Каково предназначение схемы обхода в глубину?
30. Что представляет собой анализ методом рекурсивного спуска?
31. Что представляет собой предиктивный анализ?
32. Что называется ключевыми словами?
33. Что означает термин область видимости параметра?
34. В чём заключается правило последнего вложения?
35. Что представляет собой трёхадресный код?
36. Что представляет собой статическая проверка согласованности?
37. В чём состоит задача лексического анализатора?
38. Как происходит взаимодействие лексического анализатора с синтаксическим?
39. Для чего необходимо в процессе компиляции разделение на лексический и синтаксический анализы?
40. Что означает термин «лексема»?
41. Что означает термин «алфавит языка»?
42. Какие основные операции могут осуществляться над строками?
43. Какие термины используются при работе со строками?
44. Для чего применяется буферизация?
45. Какие преимущества разработчикам могут обеспечить грамматики?
46. Какое место занимает синтаксический анализатор в модели компилятора?
47. В чём заключаются нисходящие и восходящие методы, применяемые в компиляторах?
48. Какие типы ошибок могут присутствовать в исходном коде?
49. Какие цели выполняет обработчик синтаксического анализатора?
50. Что представляют собой терминалы и нетерминалы?
51. Из каких частей состоят продукции грамматики?
52. Какой тип конструкции можно создавать при помощи порождений?
53. С помощью каких сущностей помечаются листья дерева разбора?
54. С чего начинается обход в глубину?
55. С чего начинается восходящий синтаксический анализ?
56. Что представляет собой синтаксически управляемое определение (СУО)?
57. Какие атрибуты могут использовать синтаксически управляемые определения?
58. Что представляют собой синтаксически управляемые схемы трансляции (СУТ)?
59. Как формируются графы зависимостей?
60. От чего могут зависеть наследуемые атрибуты в дереве разбора?
61. Что представляют собой узлы синтаксического дерева?
62. Какие преимущества предоставляет использование модели «ориентированного ацикличного графа» для выражений?
63. Назовите наиболее распространённые трёхадресные команды.
64. Для чего в программировании могут использоваться булевы выражения?

Вопросы к теме 3
65. Какие задачи выполняются с помощью среды времени выполнения?
66. Как организовано хранение многобайтных объектов?
67. Для чего используется стек?
68. В чём заключается стратегия «статического выделения памяти»?
69. В чём заключается стратегия «динамического выделения памяти»?
70. Что представляет собой куча?
71. Для чего производится сборка мусора?
72. Какие две основные функции выполняет диспетчер памяти?
73. Какими свойствами должен обладать хороший диспетчер памяти?
74. Как организована иерархия памяти?
75. Для чего используется статическая оперативная память?
76. В чём заключается временная локальность?
77. В чём заключается пространственная локальность?
78. Каким образом можно повысить пространственную и временную локальность обращения к данным?
79. Какие методы используются для снижения фрагментации данных?
80. Какие проблемы могут возникнуть при освобождении памяти вручную?
81. Какие соглашения используются для управления памятью и для чего?
82. Что такое «безопасность с точки зрения типов»?
83. Какие критерии производительности, должны учитываться при проектировании сборщика мусора?
84. Что может делать компилятор для того, чтобы обеспечить возможность сборщику мусора корректно определить корневое множество?
85. Какие операции, выполняемые мутатором, приводят к изменению множества достижимых объектов.
86. Какие способы используются для поиска недостижимых объектов?
87. Какую роль играет оптимизатор?
88. Какие три основные задачи выполняет генератор целевого кода?
89. Что является наиболее важным критерием оценки генератора кода?
90. Что является входным потоком генератора кода?
91. Назовите варианты промежуточных представлений.
92. Какое преимущество имеет генерация абсолютной программы на машинном языке?
93. Какими факторами определяется сложность отображения промежуточного представления на последовательность машинных команд?
94. Какими критериями обычно определяется качество сгенерированного кода?
95. Каким образом осуществляется локальная оптимизация программ?
96. Приведите примеры преобразования программ, характеризующие локальную оптимизацию.
97. Что представляет собой виртуальная машина?
98. Что представляет собой CISC-компьютер?
99. Что представляет собой RISC-компьютер?
100. Что представляет собой базовый блок?
101. Что такое граф потока?

Вопросы к теме 4
102. Что такое оптимизация кода?
103. Какие действия могут привести к оптимизации кода?
104. На чём основано большинство глобальных оптимизаций?
105. Что должно обязательно сохраниться после выполнения оптимизации?
106. Приведите примеры избыточных операций.
107. Приведите примеры преобразований, сохраняющих семантику.
108. Что такое "общее подвыражение"?
109. Какая основная идея лежит в преобразовании "распространение копий"?
110. Какая переменная называется "живой"? "мёртвой"?
111. В чём состоит преобразование "перемещение кода"?
112. В чём состоит преобразование "снижение стоимости"?
113. В какой последовательности лучше работать с вложенными циклами?
114. Что означает понятие "анализ потоков данных"?
115. В чём заключается технология "распространение констант"?
116. В каких формах проявляется избыточность кода?
117. От каких факторов зависит время выполнения программы на процессоре с параллелизмом на уровне команд?
118. Что означает термин "конвейерное выполнение"?
119. Какие ограничения накладываются на планирование кода?
120. В чём заключается "зависимость через данные"?
121. Как вычисляется наибольшее количество одновременно выполняемых операций?
122. В чём заключается принцип действия простых аппаратных планировщиков?
123. В чём заключается преимущество метода "перемещение кода между блоками"?
124. Какие циклы называются универсальными? Перекрёстными?
125. Что представляет собой программная конвейеризация универсальных циклов?
126. Какая технология используется для работы с перекрёстными циклами? В чем она заключается?
127. Чем характеризуются симметричные мультипроцессорные системы?
128. Каким образом соединены кэши второго уровня в симметричной мультипроцессорной архитектуре?
129. Каким образом соединены кэши второго уровня в машинах с распределённой памятью?
130. Какие метрики используются для оценки работоспособности параллельного приложения?
131. В чём заключается закон Амадаля?
132. В чём заключается закон параллелизм на уровне задач?
133. Какие типы локальности данных вам известны? Охарактеризуйте их.
134. В чём заключается принцип работы межпроцедурного анализа?
135. Что такое точка вызова?
136. Что представляет собой "граф вызовов"?
137. Что такое чувствительность к потоку?
138. Что такое контекстная чувствительность?
139. Что является важным приложением межпроцедурного анализа?
140. Что представляет собой диаграмма бинарного выбора?
=============================================

Лабораторная работа №1 «ОПРЕДЕЛЕНИЕ ВРЕМЕНИ РАБОТЫ ПРИКЛАДНЫХ ПРОГРАММ»

Цели работы
1. Изучение методики измерения времени работы подпрограммы.
2. Изучение приемов повышения точности измерения времени работы подпрограммы.
3. Изучение способов измерения времени работы подпрограммы.
4. Измерение времени работы подпрограммы в прикладной программе.

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

ВАРИАНТЫ ЗАДАНИЙ
Таблица вариантов
№ Алгоритм 1 Алгоритм 2
1 Пузырьком Шелла
2 Перемешиванием Выбором
3 Расчёской Быстрая
4 Гномья Терпеливая
5 Вставками Слиянием
6 Слиянием Вставками
7 Терпеливая Гномья
8 Быстрая Расчёской
9 Выбором Перемешиванием
10 Шелла Пузырьком

КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Назовите цели измерения времени.
2. В чем состоит методика измерения времени работы программы?
3. Назовите способы измерения времени работы программы. Перечислите их особенности.
4. Каким способом лучше измерять большие промежутки времени (порядка нескольких часов)?
5. Каким способом лучше измерять малые промежутки времени (порядка времени работы нескольких команд процессора)?

Лабораторная работа №2 «ИЗУЧЕНИЕ ОПТИМИЗИРУЮЩЕГО КОМПИЛЯТОРА»

course
Цели работы
1. Изучение основных функций оптимизирующего компилятора, и некоторых примеров оптимизирующих преобразований и уровней оптимизации.
2. Получение базовых навыков работы с компилятором GCC.
3. Исследование влияния оптимизационных настроек компилятора GCC на время исполнения программы.
В лабораторной работе описаны основные возможности компилятора GCC/CNU, являющегося классическим образцом оптимизирующего компилятора. При выполнении задания в ОС Windows рекомендуется QT (https://www.qt.io/) - бесплатный IDE для C++ с компилятором MinGW (программный порт GCC под Windows).

ЗАДАНИЕ К ЛАБОРАТОРНОЙ РАБОТЕ
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. Вывод по результатам лабораторной работы.

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

8. КОНТРОЛЬНЫЕ ВОПРОСЫ (для самостоятельного изучения, преподавателю на проверку не присылаются)
1. Каковы главные функции оптимизирующего компилятора?
2. Приведите примеры характеристик программы, по которым осуществляется оптимизация?
3. Какие бывают примеры оптимизирующих преобразований, что они оптимизируют, в чем их суть?
4. Всегда ли оптимизирующая компиляция позволяет уменьшить время работы программы?
5. Чем отличается общая оптимизация от оптимизации под архитектуру?
6. Какие имеются группы ключей в GCC?
7. Какие уровни оптимизации есть в GCC, и чем они характеризуются?

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

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

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

2. Составить отчет по лабораторной работе. Отчет должен содержать следующее.
1. Титульный лист.
2. Цель лабораторной работы.
3. Вариант задания.
4. Полный компилируемый листинг реализованной программы.
5. Вывод по результатам лабораторной работы.

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

4. КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Что характеризует понятие временной сложности алгоритма?
2. Что является основным методом оценки временной сложности алгоритма?
3. Какие существуют типы сложности по времени работы алгоритма?
4. Всегда ли возможно улучшение временной сложности?
5. Что означают понятия "алгоритм сложности O(n)", "алгоритм сложности O(1)"?