Питання до екзамену
Теорія програмування Питання до екзамену
Вступ.
1. Програми та їх графічні моделі. Графічна модель програми: U-Y схема програми.
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. Фізична внтерпретація оператора присвоєнні
27. Фізична внтерпретація операnорів управління
28. Алгоритм статичного аналізу фізичних розмірностей у програмах.
29. Постановка задачі аналіза границь значень змінних у програмах
30. Математичний алгоритм задачі аналіза границь значень змінних
31. Метод базисів Гребнера
32. Метод Штурма та правило трбох епсилон
33. Алгоритм перевірки приналежності значення фізичної величини даному інтервалу.
Задача генерації інваріантів програм
34. Постановки задач аналізу програм.
35. Загальний підхід до процесу доведення програми. Інваріанти програми.
36. Інваріанти у програмі обчислення НОД двох чисел.
37. Поняття інваріанта контрольної точки програми.
38. Задача автоматичної генерації інваріантів програм.
39. Аналіз предметних областей та мови інваріантів.
40. Інваріантні рівності. Ідеали інваріантів та їх властивості
41. Алгоритм побудови інваріантів обмеженого степеня.
42. Алгоритми побудови поліноміальних інваріантів лінійних циклів.