Інфопакет

Теорія програмування

ОК.32

Обов’язкова дисципліна для ОП

Перший

2022/2023

5 Семестр

4

ПРН1. Застосовувати знання основних форм і законів абстрактнологічного мислення, основ методології наукового пізнання, форм і методів вилучення, аналізу, обробки та синтезу інформації в предметній області комп'ютерних наук. ПРН5. Проектувати, розробляти та аналізувати алгоритми розв’язання обчислювальних та логічних задач, оцінювати ефективність та складність алгоритмів на основі застосування формальних моделей алгоритмів та обчислюваних функцій.

1. Знати: основні поняття, засоби і методи програмування, їх застосування в інформатиці; знати мови програмування та логіки 1-го порядку, їх можливості для опису предметних областей. 2. Вміти: описувати на формальних мовах 1-го порядку твердження стосовно тих чи інших предметних областей та властивостей програм; встановлювати істинність пропозиційних формул, формул 1-го порядку. 3. Володіти елементарними навичками: програмування в сучасних мовах, тестування програм, перевірки виконуваності формул.

Частина 1. Основні поняття теорії програмування та їх формалізація Тема 1. Вступ до предмету. Основні методологічні принципи побудови формальних моделей програм. Мова SIPL. Самостійна робота: Аналіз визначень мов програмування. Тема 2. Формалізація мови SIPL. Тема 3. Алгебри даних та програм. Тема 4. Часткова та повна коректність програм. Тема 5. Предметні області та методи їх опису. Розвиток основних понять програмування. Тема 6. Уточнення основних понять програмування. Тема 7. Програмні системи різних рівнів абстракції. Мови специфікацій та програмування. Частина 2. Синтаксис та семантика програм. Рекурсивні програми. Тема 8. Основні методи подання синтаксису мов програмування: БНФ та їх модифікації. Формальні мови та граматики. Ієрархія граматик Хомського. Операції над мовами. Автоматні формалізми сприйняття мов. Тема 9. Контекстно-вільні граматики і мови та їх властивості. Нормальні форми. Рівняння в алгебрах формальних мов. Тема 10. Розв’язні та нерозв’язні проблеми теорії формальних мов. Тема 11. Функціональна семантика програм, композиційна семантика, денотаційна семантика, аксіоматична семантика. Абстрактні типи даних. Тема 12. Рекурсія в мовах програмування. Повні впорядковані множини. Теореми про найменшу нерухому точку. Застосування теорії найменшої нерухомої точки. Тема 13. Методи семантичного аналізу програм. Тема 14. Сучасні методи розробки програм та їх формалізація.

Основні 1. М.С. Нікітченко. Теорія програмування. Частина 1. Навчальний посібник. – Ніжин. Видавництво НДУ імені М.В. Гоголя, 2010.– 119 с. Додаткові 1. Eric C.R. Hehner. a Practical Theory of Programming. - Springer-Verlag Publishers, New York, 2021. – 243 р. 2. M. Balaban. Principles of Programming Languages. - Ben-Gurion University of the Negev Faculty of Natural Science Department of Computer Science, 2017. – 418 р. 3. Semantics - Advances in Theories and Mathematical Models. - IN-TECH, 2012. – 284 р. 4. J. V. Tucker, K. Stephenson. Data, Syntax and Semantics: An Introduction to Modelling Programming Languages. - University of Wales Swansea, 2006. – 840 p. 5. И.А. Басараб, Н.С.Никитченко, В.Н. Редько. Композиционные базы данных. - К., Либідь, 1992.– 182 с. 6. Дж. Хопкрофт, Р. Мотвани, Д. Ульман. Введение в теорию автоматов, языков и вычислений.– М.: Вильямс, 2002.– 528 с. ..

Лекції, практичні заняття, консультації, самостійна робота

- семестрове оцінювання: 1. Контрольна робота 1: РН 1.1, РН 1.2 — 10 балів/6 балів. 2. Контрольна робота 2: РН 1.1, РН1.3 - 15 балів/9 балів. 3. Проєктне завдання: РН 1.1, РН 1.2, РН 2.1, РН1.3, РН 3.1 - 10 балів/6 балів. 4. Домашні завдання: РН 1.1, РН 1.2, РН 2.1, РН1.3, РН 4.1 - 15 балів/9 балів 5. Поточне оцінювання: РН 2.1., РН 3.1, РН 4.1 – 10 балів/6 балів. - підсумкове оцінювання (у формі іспиту): - максимальна кількість балів які можуть бути отримані студентом: 40 балів/ 24 бали; - результати навчання які будуть оцінюватись: PH1.1, PH1.2, PH1.3, PH2.1, РН3.1, РН4.1; - форма проведення і види завдань: письмова робота. Види завдань: 4 письмових питання. 1 питання (теоретичне): PH1.1, РН3.1, РН4.1; 2 питання (теоретичне): PH1.2, РН3.1, РН4.1; 3 питання (практичне): PH1.3, РН3.1, РН4.1; 4 питання (практичне): PH2.1, РН3.1, РН4.1; За розгорнуту відповідь на кожне завдання студент може отримати від 1 до 10 балів. ..

Українська