Контрольная работа по курсу «Программирование»

1.Написать развернутый ответ на теоретический вопрос. Выполнить анализ существующей информации сделать аргументированный вывод. Оформить список использованных источников согласно ГОСТ 7.0. 100-2018.

1. Стандартные схемы программ. Базис класса стандартных схем программ. Графовая форма стандартной схемы. Линейная форма стандартной схемы. Интерпретация стандартных схем программ.
2. Свойства и виды стандартных схем программ. Эквивалентность, тотальность, пустота, свобода. Свободные интерпретации. Согласованные свободные интерпретации.
3. Трансляция схем программ. О сравнении класс сов схем. Схемы с процедурами.
4. Моделирование стандартных схем программ. Одноленточные, многоленточные, двухголовочные автоматы. Построение схемы, моделирующей автомат.
5. Обогащенные и структурированные схемы. Классы обогащенных схем. Трансляция обогащенных схем. Структурированные схемы.
6. Рекурсивные схемы. Рекурсивное программирование. Определение рекурсивной схемы.
7. Теоретические модели вычислительных процессов. Взаимодействующие последовательные процессы.
8. Теоретические модели вычислительных процессов. Параллельные процессы.
9. Теоретические модели вычислительных процессов. Взаимодействие – обмен сообщениями.
10. Теоретические модели вычислительных процессов. Разделяемые ресурсы.
11. Теоретические модели вычислительных процессов. Программирование параллельных вычислений.
12. Теоретические модели вычислительных процессов. Модели параллельных вычислений
13. Сети Петри. Основные понятия и определения. Маркировка, правила выполнения.
14. Моделирование систем на основе сетей Петри.
15. Анализ сетей Петри.
16. Верификация программ. Методы доказательства правильности программ. Использование утверждений в программах.
17. Семантическая теория программ. Операционная и декларативные семантики.
18. Семантическая теория программ. Аксиоматическая семантика. Преобразователь предикатов.
19. Семантическая теория программ. Операционная и декларативные семантики.
20. Принципы и способы технической реализации моделей процессов и структур.
21. Параллельное и асинхронное программирование. Процессы и потоки. Синхронизация потоков. Проблемы синронизации.
22. Современные вычислительные системы. Интеллектуальные системы.
23. Языки формальных спецификаций. Спецификации задачи взаимодействия процессов.

Составьте программу на любом языке программирования с использованием только стандартных библиотек и модулей. Исходные данные должны вводиться из текстового файла, результаты должны сохраняться в текстовый файл. Для ввода, вывода и представления графов или сетей можно использовать любые способы.

1. Для заданного орграфа определите, является ли он Гамильтоновым и, если да, найдите Гамильтонов цикл.
2. Для заданного орграфа определите, является ли он сильно связным.
3. Для заданного орграфа определите, является ли он бесконтурным.
4. Для заданного вектора определите, является ли он графическим по критерию Гавела-Хакими.
5. Для заданного вектора определите, является ли он графическим по критерию Эрдёша-Галлаи.
6. Для заданного числа вершин n постройте все вектора степеней n-вершинных графов.
7. Для заданного числа вершин n постройте все вектора степеней n-вершинных деревьев.
8. Постройте хотя бы одну реализацию заданного вектора степеней.
9. Постройте связную реализацию заданного вектора степеней.
10. Постройте все неизоморфные реализации заданного вектора степеней.
11. Проверить изоморфизм двух заданных графов.
12. Для заданного графа построить максимальный матричный код.
13. Для заданного графа построить минимальный матричный код.
14. Для двух заданных графов проверить вложение одного из них в другой.
15. Для заданной сети построить остовное дерево по алгоритму Прима.
16. Для заданной сети построить остовное дерево по алгоритму Краскала.
17. Для заданной сети найти кратчайшие пути от заданной вершины до всех остальных по алгоритму Дейкстры.
18. Для заданной сети найти кратчайшие пути от заданной вершины до всех остальных по алгоритму Беллмана-Форда.
19. Для заданной сети найти кратчайшие пути между всеми парами вершин по алгоритму Флойда-Уоршалла.
20. Для заданного дерева рассчитайте код Прюфера.
21. Для заданного дерева рассчитайте эксцентриситеты его вершин.
22. Для заданного дерева найдите его центр.
23. Для заданного дерева найдите его центроид.