Теория вычислительных процессов и структур. Селиверстов М.Н. - 7 стр.

       47. Глубинное остовное дерево. Типы дуг по отношению к глубинному остовному
дереву. Каркас, натуральный цикл. Прямая и обратная нумерации, их свойства. Выделе-
ние зон.
       48. Свойство интервальной сводимости и его применение. Одновходовость, за-
прещенный подграф, обобщенная сводимость. Аранжировки. Аранжируемость, связь с
отношением обязательного предшествования и сводимостью.
       49. Свойство единственности каркаса. Доминирование сводимом графе и его кар-
касе. Разборность. Представления вершин и дуг при разборе. Разборность и сводимость.
Тест на сводимость.
       50. Классические задачи анализа потоков данных: reaching definitions, constant
propagation, live variables. Неформальные решения.
       51. Решеточная модель задачи анализа потоков данных. Потоковые функции и их
неподвижные точки. Уравнения по всем путям, связь между их решениями и неподвиж-
ными точками.
       52. Задача распределения регистров и ее особенности для различных машинных
архитектур. Загрузка, выгрузка и пересылка. Связь других оптимизирующих преобразо-
ваний с задачей распределения регистров.
       53. Сведение задачи экономии памяти к задаче раскраске графов. Информацион-
ные маршруты, области действия и граф несовместимости.
       54. Хроматическое число графа, его оценки. Классы графов с известными хромати-
ческими числами.

Семантическая теория программ

       55. Логическая спецификация программ.
       56. Анализ корректности последовательных программ.
       57. Аксиоматическая семантика последовательных программ.
       58. Автоматизация верификации программ.
       59. Доказательство корректности программ в проблемных областях.
       60. Языки спецификаций. Языки, специализированные по средствам (табличные,
эквациональные, функциональные, диаграммные и сетевые). Языки, специализированные
по области применения (управление, структуры данных, языки и трансляторы, базы дан-
ных и знаний, пакеты прикладных программы). Универсальные и расширяемые языки.
       62. Денотационная, операционная и аксиоматическая семантики. Теория непод-
вижных точек. Семантика состояний. Абстрактные типы данных и сигнатурные графы.
       63. Формальные методы спецификации программ. VDM (венский метод построе-
ния программ). Логико-алгебраические спецификации. Машины абстрактных состояний.


Модели вычислительных процессов

        64. Модели вычислительных процессов: Модель графов распределения ресурсов.
Сети Петри. Вычислительные схемы.
        65. Взаимодействие процессов, асинхронные процессы: Синхронизация параллель-
ных процессов. Проблема критических участков. Анализ подходов к решению проблемы.
Алгорифм Деккера. Программная реализация взаимоисключений: блокирование (spin
lock). Семафоры и мониторы: определение, назначение, реализация.
        66. Протоколы и интерфейсы: открытость разработки стандартов; уровневые про-
токолы; драйверы; средства оконного интерфейса.

Сети Петри



                                         7