Раздел 12. Теория вычислительных процессов

60. Элементы теории асинхронных процессов: концепция процесса, основные определения, глобальные свойства - параллельность, синхронность, недетерминизм; физическое и событийное время, понятие алгебры над процессами; модели вычислительных процессов - автоматная модель, способы задания и построения.

61. Основы специальной теории сетей: синтаксис и семантика сетей Петри, модельная и предметная интерпретация, определение, способы задания сетей Петри, понятие выполнения сети, основные соглашения выполнения сети, пространство состояний, множество и граф достижимости, динамические свойства сетей, анализ сетей; сетевая объектная модель процессов, ее особенности и отличие от автоматной модели.

62. Элементы теории вычислимости: вычислимость и разрешимость, интуитивное и точное понятие алгоритма, вычислимые функции, машина Тьюринга, массовые алгоритмические проблемы.

63. Математическая модель программы - схема программы, как основной инструмент исследования свойств и преобразований программ..Стандартные схемы программ, понятие стандартной схемы, стандартные схемы в линейной и графовой формах, интерпретация схем, понятие программы, основные свойства стандартных схем. Разрешимые подклассы стандартных схем программ.

64. Взаимодействие процессов: взаимодействие процессов через разделяемые ресурсы и общие данные, принципы организации взаимодействия процессов, классические задачи взаимодействия асинхронных процессов, динамика взаимодействия процессов и проблема тупиков, спецификация дисциплин взаимодействия процессов в терминах сетей Петри.

Раздел 13. Теория языков программирования и методы трансляции

65. Формальные языки и грамматики: универсальное множество цепочек над конечным алфавитом, формальный язык как множество цепочек, операции над языками, определение формального языка и формальной грамматики, теория формальных грамматик как математический аппарат для изучения синтаксиса языков программирования, классификация формальных языков и грамматик по порождающей способности.

66. Лексический анализ: роль лексического анализатора, взаимосвязь лексического и синтаксического анализаторов, принципы построения и функции лексического анализатора, связь лексического анализа, автоматных грамматик и конечных автоматов, конечные автоматы и распознаватели, недетерминированные и детерминированные конечные автоматы, преобразования конечных автоматов, цель этих преобразований.

67. Синтаксический анализ: роль синтаксического анализатора, контекстно-свободные грамматики (КС-грамматики) как основной инструмент формального изучения синтаксиса языков программирования: определение КС-грамматики, дерево вывода в КС-грамматике, однозначность КС-грамматик и языков, связь между КС-языками и МП-автоматами, автоматы с магазинной памятью, описание, функционирование, способы задания МП-автомата, недетерминированные и детерминированные МП-автоматы.

68. Общие алгоритмы синтаксического анализа: методы восходящего синтаксического анализа, табличные методы синтаксического анализа, формальное определение алгоритма разбора типа "перенос-сверт­ка", грамматики простого и операторного предшествова­ния, понятие отношений «<∙ , ∙>, ∙ = » между символами грамматики, особенности построения таблиц разбора, сравнительный анализ класса грамматик предшествования с другими классами грамматик.

69. Общие алгоритмы синтаксического анализа: нисходящие методы синтаксического анализа, метод рекурсивного спуска, предиктивный синтаксический анализатор, определение LL(k)-грамматики, алгоритм раз­бора для LL(1)-грамматик, алгоритм построения управляющей таблицы для LL(1)-грамматики, сравнительный анализ нисходящих методов синтаксического анализа.

70. Общие алгоритмы синтаксического анализа: методы восходящего синтаксического анализа, табличные методы синтаксического анализа, формальное определение алгоритма разбора типа "перенос-сверт­ка", определение LR(k)-грамматики, алгоритм раз­бора для LR(k)-грамматик, алгоритм построения управляющей таблицы, преимущества класса LR(k)-грамматик перед другими методами синтаксического анализа.

71. Общие принципы генерации кода: формальные методы описания перевода, внутренние формы программы: польская инверсная запись, представление основных конструкций языков программирования в польской инверсной записи, тетрады, триады, представление основных конструкций языков программирования с использованием тетрад и триад, косвенные триады, синтаксические деревья, ассемблерный код, особенности всех форм представления, их сравнительный анализ.

72. Атрибутные транслирующие грамматики: синтаксически управляемые определения и схемы трансляции как способы записи семантических правил, связанных с продукциями грамматик, понятие атрибута, синтезируемые и наследуемые атрибуты, вычисление значений атрибутов, L-атрибутные и S-атрибутные транслирующие грамматики, реализация атрибутного перевода.