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



Скачати 272.81 Kb.
Дата конвертації05.03.2017
Розмір272.81 Kb.


Київський національний університет імені Тараса Шевченка
Факультет кібернетики

Кафедра теорії та технології програмування
Укладач: Доктор фіз.-мат. наук, професор Нікітченко М.С.



ТЕОРІЯ ПРОГРАМУВАННЯ

РОБОЧА НАВЧАЛЬНА ПРОГРАМА ДИСЦИПЛІНИ

для студентів спеціальності 6.040302 “Інформатика”

Затверджено

на засіданні кафедри теорії

та технології програмування

Протокол № 10

від „25” травня 2012 р.
Завідувач кафедри

Нікітченко М.С.
Затверджено

на засіданні Вченої Ради

факультету кібернетики

Протокол № 9

від „28” травня 2012 р.

Декан факультету



Анісімов А.В

КИЇВ-2012


Робоча навчальна програма з дисципліни “Теорія програмування”

Укладач: доктор фіз.-мат. наук, професор Нікітченко Микола Степанович


Лектор: доктор фіз.-мат. наук, професор Нікітченко М.С.

Викладач: професор Нікітченко М.С.,

доктор фіз.-мат. наук, професор Буй Д.Б.,

кандидат фіз.-мат. наук, асистент Поляков С.А..

Погоджено

з науково-методичною комісією

“___” _______________ 2012 р.

Голова НМК факультету

Хусаїнов Д.Я

ВСТУП

Дисципліна “Теорія програмування” є базовою нормативною дисципліною спеціальності "Інформатика", що читається в 5 семестрі в обсязі 5 кредитів, загальна кількість годин – 180, в тому числі 85 годин аудиторних занять, з них 51 годин лекцій, 34 годин практичних занять і 95 годин самостійної роботи. Закінчується курс іспитом у 5 семестрі.



Метою і завданням навчальної дисципліни "Теорія програмування" є засвоєння основних концепцій, принципів та понять сучасного, зокрема композиційного, програмування. В загальносвітоглядному аспекті, поняття і методи теорії програмування необхідні для обгрунтування та формалізації способів розробки правильних та ефективних програм. В прикладному аспекті, апарат теорії програмування необхідний для адекватного моделювання мов специфікацій і програмування та використання побудованих моделей для створення сучасних програмних та інформаційних систем високої якості.

Предмет навчальної дисципліни "Теорія програмування" включає в себе вивчення основних (базових) понять теорії програмування, розгляд основних аспектів програм (семантика та синтаксис), їх формалізацію та дослідження.

Вимоги до знань та вмінь. Для засвоєння курсу необхідні знання основ елементарної математики, дискретної математики, алгебри, математичної логіки та теорії алгоритмів. Студент повинен знати основи теорії множин, основи загальної алгебри, теорії алгоритмів, пропозиційної логіки та логіки предикатів.

Місце в структурно-логічній схемі спеціальності. Нормативна навчальна дисципліна "Теорія програмування" є складовою циклу професійної підготовки фахівців освітньо-кваліфікаційного рівня "бакалавр". Курс теорії програмування потрібен для подальшого вивчення нормативних дисциплін "Системне програмування", "Бази даних та інформаційні системи", "Інтелектуальні системи", "Теорія обчислень", "Штучний інтелект", "Формальні методи розробки програмних систем", "Інформаційні технології", "Прикладна логіка", низки спецкурсів відповідного напряму.
Контроль знань здійснюється за модульно-рейтинговою системою.

Робота в семестрі розділена на 3 змістових модулі. Результати навчальної діяльності студентів оцінюються за 100-бальною шкалою.



Оцінювання за формами контролю.

Семестрова оцінка – 65 балів; із них модульні контрольні роботи – 54 балів, активна робота студентів – 11 балів. Підсумкова екзаменаційна робота – 35 балів. Максимальна підсумкова оцінка – 100 балів.



Порядок розрахунку загальної оцінки.

Модульні контрольні роботи – 54 = 12+20+22 балів.

За активну роботу студента на практичних заняттях та на самостійній роботі до семестрової оцінки може бути додано до 11 балів.

Студент має право на одне перескладання модульної контрольної роботи із можливістю отримання максимальної кількості балів 10 (модуль 1), 18 (модуль 2) та 20 (модуль 2).

Термін перескладання визначається викладачем.

Розрахунок балів по модулях:

Модуль 1: 15 балів (модульна контрольна робота – 12, за активну роботу – 3).

Модуль 2: 23 балів (модульна контрольна робота – 20, за активну роботу – 3).

Модуль 3: 27 балів (модульна контрольна робота – 22, за активну роботу – 5).

Студент допускається до складання іспиту, якщо кількість набраних за семестр балів не менше 30.



Підсумкова екзаменаційна робота – 35 балів.
Шкала оцінювання

100-бальна система

Національна шкала

90-100

Відмінно

5

85-89

Добре

4

75-84

65-74

Задовільно

3

60-64

35-59

не задовільно

2

1-34

не задовільно

2



ТЕМАТИЧНИЙ ПЛАН ЛЕКЦІЙ ТА ЛАБОРАТОРНИХ ЗАНЯТЬ


№ лекції

Назва лекції

Кількість годин

Лекції

Практ.занять

Сам. р-та




Змістовий модуль 1. Основні поняття теорії програмування.










1

Вcтуп. Теоретичні та прикладні аспекти програмування.

2

2

2

2

Проста мова програмування SIPL: синтаксис.

2




2

3

Проста мова програмування SIPL: семантика.

2

2

4

4

Властивості програм мови програмування SIPL.

2

2

4

5

Розвиток основних понять програмування. Основні аспекти програм.

2




2

6

Уточнення основних понять програмування .

2

2

4

7

Програмні системи різних рівнів абстракції. Мови специфікацій та програмування.

2

2

2




Модульна контрольна робота 1







2



















Змістовий модуль 2. Синтактика










8

Основні методи подання синтаксису мов програмування: БНФ та їх модифікації.

2




2

9

Формальні мови та граматики. Ієрархія граматик Хомського. Операції над мовами.

2

2

4

10

Автоматні формалізми сприйняття мов.

2

2

4

11

Контекстно-вільні граматики і мови та їх властивості.

2




2

12

Нормальні форми контекстно-вільних граматик.

2

2

2

13

Рівняння в алгебрах формальних мов.

2

2

2

14

Розв’язні та нерозв’язні проблеми теорії формальних мов

2




2




Модульна контрольна робота 2







4


































Змістовий модуль 3. Семантика










15

Композиційна семантика. Функціональна семантика.

2

2

4

16

Натуральна семантика.

2

2

4

17

Взаємозв’язок семантик.

2




4

18

Рекурсія в мовах програмування. Повні впорядковані множини.

2

2

4

19

Теореми про найменшу нерухому точку. Застосування теорії найменшої нерухомої точки.

2

2

4

20

Аналіз рекурсивних програм.

2




4

21

Денотаційна семантика.

2

2

4

22

Аксіоматична семантика.

2

2

4

23

Абстрактні типи даних.

2




2

24

Принципи іменування та номінативні дані.

2

2

4

25

Сучасні методи розробки програм та їх формалізація.

2

2

4

26

Методи семантичного аналізу програм.

1




2




Модульна контрольна робота 3







5


































ВСЬОГО

51

34

95



Загальний обсяг годин – 180, у тому числі


Лекцій – 51 год.

Практичних занять – 34 год.

Самостійна робота – 95 год.

ТЕМАТИЧНО-ЗМІСТОВНА ЧАСТИНА КУРСУ

Змістовий модуль 1. Основні поняття теорії програмування.


Лекція 1. Вcтуп. Теоретичні та прикладні аспекти програмування – 2 год.

Вступ. Предмет теорії програмування. Мета курсу. Зв'язок з іншими дисциплінами. Структура курсу. Прикладний та теоретичний аспект програмування, їх взаємозв’язок. Чинники, що обґрунтовують важливість теорії програмування: помилки в програмному забезпеченні та їх наслідки, складність програмних систем та необхідність автоматизації їх побудови. [1,2].



Практичне заняття 1. Основні математичні поняття – 2 год.

1. Опитування та обговорення лекційного матеріалу.

2. Аналіз визначень мов програмування. Математичні поняття, що утворюють базис формалізації програм: множини та функції [9–12].

Завдання для самостійної роботи (2 год.)

Властивості множин та функцій, операції над ними. [9–12]



Лекція 2. Проста мова програмування SIPL: синтаксис. – 2 год.

Неформальний опис простої мови програмування. Формальний опис синтаксису мови SIPL: БНФ та її властивості. Дерева синтаксичного виводу. Індуктивні визначення синтаксису. [1,6]



Завдання для самостійної роботи (2 год.)

Властивості бінарних відношень, операції над ними. [9–12]



Лекція 3. Проста мова програмування SIPL: семантика. – 2 год.

Методи подання семантики. Алгебри даних та функцій. Композиції програм. Семантичні терми. Обчислення значень семантичних термів. [1, 2,9]



Практичне заняття 2. Формалізація програм мови SIPL. – 2 год.

1. Опитування та обговорення лекційного матеріалу.

2. Побудова дерев виводу програм мови SIPL. Побудова семантичних термів та обчислення їх значень. [1].

Завдання для самостійної роботи (4 год.)

Властивості алгебр даних та функцій. [1,9]



Лекція 4. Властивості програм мови програмування SIPL. – 2 год.

Властивості композицій послідовного виконання та циклу. Еквітонність та монотонність програм. Часткова та повна коректність програм. [1, 9, 13].



Практичне заняття 3. Доведення властивостей програм. – 2 год.

1. Опитування та обговорення лекційного матеріалу.

2. Розвязання задач на побудову доведень властивостей програм [1,4].

Завдання для самостійної роботи (4 год.)

Доведення властивостей композицій програм. Доведення часткової та повної коректності програм [1, 4, 13].



Лекція 5. Розвиток основних понять програмування. Основні аспекти програм.

Методологічні принципи визначення понять, пентада основних понять програмування. Основні аспекти програм: семіотичні та сутнісні. – 2 год. [1].



Завдання для самостійної роботи (2 год.)

Формалізація даних на прикладі простих мов програмування. [1]



Лекція 6. Уточнення основних понять програмування. – 2 год..

Принципи формалізації програмних понять. Класи функцій. Аплікативність функцій. Формалізація композицій. [1].

Практичне заняття 4. Формалізація програмних понять на прикладі простих мов програмування – 2 год.

1. Опитування та обговорення лекційного матеріалу.

2. Формалізація даних, функцій та композицій на прикладі простих мов програмування [1,9].

Завдання для самостійної роботи (4 год.)

Формалізація понять на прикладі простих мов програмування. [1]



Лекція 7. Програмні системи різних рівнів абстракції. Мови специфікацій та програмування.– 2 год.

Поняття програмної системи. Класифікація програмних систем. Поняття мов специфікацій та програмування.



Практичне заняття 5. Аналіз мов специфікацій та програмування. – 2 год.

1. Опитування та обговорення лекційного матеріалу.

2. Розгляд властивостей мов специфікацій та програмування. Побудова формальних моделей композиційного типу для мов специфікацій та програмування. [1].

Завдання для самостійної роботи (2 год.)

Побудова формальних моделей композиційного типу для фрагментів мов специфікацій та програмування.[1]



Модульна контрольна робота №1 [1,2]. – 2 год.

Типове завдання модульної контрольної роботи №1

  1. Описати основні поняття програмування та їх відношення.

  2. Побудувати програму на мові SIPL для однієї із наступних задач (x,y, n – додатні цілі числа):

    • обчислення xy, використовуючи функції +, –,

  • обчислення n!,

  • обчислення x–y, використовуючи функцію віднімання одиниці (–1),

  • перевірки парності числа n,

  • обчислення x div y, використовуючи функції +, –,

  • обчислення xy, використовуючи функції ,+, –,

  • обчислення [lg n], використовуючи функції div, mod, +, –,

  • обчислення x mod y, використовуючи функції +, –,

  • обчислення 3x, використовуючи функції ,+, –,

  1. Перевірити синтаксичну правильність створеної програми, побудувавши їх дерева синтаксичного виводу. Побудувати семантичні терми цих програм, та застосувати їх до певних вхідних даних.

  2. Довести часткову та повну коректність створеної програми.


Контрольні запитання до змістового модуля 1.

  1. Які недоліки неформального опису мов програмування?

  2. Яким чином задається синтаксис мови SIPL?

  3. Що є деревом синтаксичного виводу програми?

  4. Коли програма є синтаксично правильною?

  5. Що таке неоднозначна БНФ?

  6. Для чого вводиться пріоритет операцій?

  7. Які пріоритети введено для операцій мови SIPL?

  8. Які синтаксичні категорії та метазмінні введені в мові SIPL?

  9. Які типи даних використовуються у мові SIPL?

  10. Які алгебри даних пов’язані з мовою SIPL?

  11. Як визначаються операції іменування та розіменування?

  12. Які класу функцій використовуються для формалізації семантики мови SIPL?

  13. Які типи номінативних функцій використовуються для формалізації семантики мови SIPL?

  14. Як визначається суперпозиція в n-арну функцію?

  15. Як визначається композиція присвоєння?

  16. Як визначається композиція послідовного виконання?

  17. Як визначається композиція розгалуження?

  18. Як визначається композиція циклу?

  19. Які програмні алгебри пов’язані з мовою SIPL?

  20. За якими критеріями в перелік композицій включають функції?

  21. Як визначається підалгебра алгебри A_Prog, породжена мовою SIPL?

  22. Як частковість функцій впливає на визначення композицій?

  23. Як визначається семантичний терм програми?

  24. Як будується семантичний терм програми?

  25. Які властивості виконуються для програмних алгебр?

  26. Як визначаються монотонні функції?

  27. Як визначаються еквітонні функції?

  28. Які визначають програми мови SIPL?

  29. Що таке часткова коректність програм?

  30. Що таке повна коректність програм?

  31. Розкрийте зміст формалізації поняття програми.

  32. Визначте різні класи функцій.

  33. Визначте програмні системи різного рівня абстракції.

  34. Дайте визначення класу номінативних даних.

Рекомендована література: [1,2,4,5,9,12].


Змістовий модуль 2. Синтактика


Лекція 8. Основні методи подання синтаксису мов програмування: БНФ та їх модифікації. – 2 год.

БНФ та їх модифікації. Синтаксичні діаграми. Автомати.[1,6]



Завдання для самостійної роботи (2 год.)

Побудова граматик та синтаксичних діаграм для фрагментів мов програмування. [1, 6].



Лекція 9. Формальні мови та граматики. Ієрархія граматик Хомського. Операції над мовами. – 2 год.

Розвиток понять формальної мови та породжучої граматики. Визначення основних понять формальних мов. Ієрархія граматик Хомського. Операції над мовами. [1,6,9].



Практичне заняття 6. Побудова граматик для простих мов. – 2 год.

1. Опитування та обговорення лекційного матеріалу.

2. Побудова граматик для фрагментів мов програмування. Побудова граматик для різних формальних мов та доведення їх правильності.

Завдання для самостійної роботи (4 год.)

Побудова граматик для різних мов та доведення їх правильності.[1, 6].



Лекція 10. Автоматні формалізми сприйняття мов. – 2 год.

Машини Тьюрінга, Лінійно-обмежені автомати, магазинні автомати, скінченні автомати. Еквівалентністі класів автоматів та породжуючих граматик [1,3,6,9].



Практичне заняття 7. Автомати та граматики. – 2 год.

1. Опитування та обговорення лекційного матеріалу.

2. Побудова автоматів для фрагментів мов програмування. [1,3,6].

Завдання для самостійної роботи (4 год.)

Властивості автоматів різних класів. Побудова автоматів для фрагментів мов програмування. [1,3, 6].



Лекція 11. Контекстно-вільні граматики і мови та їх властивості. – 2 год.

Особливості породження слів в контекстно-вільних граматиках. Рекурсивні нетермінали. Замкненість/незамкненість мов відносно основних операцій [1,3,6].



Завдання для самостійної роботи (2 год.)

Доведення властивостей замкненості контекстно-вільних мов. [1,2,6].



Лекція 12. Нормальні форми контекстно-вільних граматик. – 2 год.

Еквівалентні перетворення граматик, зведені граматики, граматики у нормальній формі Хомського, у нормальній формі Грейбах.[1,3,6].



Практичне заняття 8. Властивості контекстно-вільних граматик та мов. Нормальні форми граматик. – 2 год.

1. Опитування та обговорення лекційного матеріалу.

2. Доведення властивостей замкненості контекстно-вільних мов. Побудова нормальних форм та доведення коректності зведень граматик до нормальних форм. [1,3,6].

Завдання для самостійної роботи (2 год.)

Доведення коректності зведень граматик до нормальних форм. [1,2,6].



Лекція 13. Рівняння в алгебрах формальних мов. – 2 год.

Рівняння в алгебрах формальних мов. Побудова розв’язків рівнянь. Доведення еквівалентності в породженні мов граматиками та рівняннями. [1,3].



Практичне заняття 9. Побудова розв’язків рівнянь в алгебра мов. – 2 год.

1. Опитування та обговорення лекційного матеріалу.

2. Побудова розв’язків рекурсивних рівнянь в алгебра мов. [1].

Завдання для самостійної роботи (2 год.)

Побудова розв’язків рівнянь в алгебрах мов. [1,3,6]



Лекція 14. Розв’язні та нерозв’язні проблеми теорії формальних мов. – 2 год.

Масові проблеми, їх алгоритмічна розв’язність. Розв’язні проблеми. Нерозв’язні проблеми.



Завдання для самостійної роботи (2 год.)

Дослідження розв’язності проблем різних типів.[1,3,6]

Модульна контрольна робота 2 [1,3].– 4 год.

Типове завдання модульної контрольної роботи №2

Побудуйте граматики, які породжують мови

а) {an*nn1};

б) {ww{a, b, с}*, |w|a=|w|b=|w|c };

в) { www{a, b}};

г) {ambnambnm1, n1}.

Доведіть правильність побудованих граматик. Якщо граматика не є контекстно вільною, доведіть, що контекстно-вільної граматика для вибраної мови не існує.

Контрольні запитання до змістового модуля 2.


  1. Як визначається синтаксичний аспект мов?

  2. Як формулюється принцип відокремлення і єдності синтаксичного та семантичного аспектів.

  3. Охарактеризуйте основні моделі формальних мов.

  4. Якими методами подається синтаксис мов програмування?

  5. Що таке БНФ?

  6. Які є модифікації БНФ?

  7. Що таке формальна мова?

  8. Визначте основні поняття теорії формальних мов.

  9. Що таке породжуючи граматика?

  10. Розкрийте інтенсіональні та екстенсіональні аспекти визначення породжуючих граматик.

  11. Дайте визначення виводу в граматиці та мови, породженою граматикою.

  12. Яким чином доводиться правильність граматики для породження певної мови?

  13. Як визначається ієрархія Хомського?

  14. Дайте визначення загально-контекстних граматик.

  15. Які алгебраїчні операції задані для формальних мов?

  16. Які типи автоматів використовують для подання синтаксису мов?

  17. Що таке контекстно-вільні граматики?

  18. Які властивості контекстно-вільних граматик?

  19. Відносно яких операцій клас контекстно-вільних мов є замкненим?

  20. Відносно яких операцій клас контекстно-вільних мов не є замкненим?

  21. Дайте визначення різним нормальним формам контекстно-вільних граматик.

  22. Сформулюйте розв’язні проблеми для контекстно-вільних граматик.

  23. Сформулюйте нерозв’язні проблеми для контекстно-вільних граматик.

  24. Як визначається розв’язок системи рівнянь в алгебрах формальних мов?

Рекомендована література: [1,3,6,9].

Змістовий модуль 3. Семантика


Лекція 15. Композиційна семантика. Функціональна семантика. – 2 год.

Принципи функціональної та композиційної семантики. Композиції як логічні засоби конструювання програм. [1,2,4,5,7].



Практичне заняття 10. Функціональна та композиційна семантика для збагачень мови SIPL. – 2 год.

1. Опитування та обговорення лекційного матеріалу.

2. Побудова семантичних термів для програм збагаченої мови SIPL [1].

Завдання для самостійної роботи (4 год.)

Методи збагачення мов програмування та їх формалізація в композиційній семантиці. [1,4].



Лекція 16. Натуральна семантика – 2 год.

Визначення натуральної семантики мови SIPL. Побудова виведень в натуральній семантиці. [1].



Практичне заняття 11. Натуральна семантика для збагачень мови SIPL. – 2 год.

1. Опитування та обговорення лекційного матеріалу.

2. Побудова правил для натуральної семантики програм збагаченої мови SIPL [1].

Завдання для самостійної роботи (4 год.)

Побудова збагачень мови SIPL та визначення їх в натуральній семантиці. Побудова виводів застосування програм [1].



Лекція 17. Взаємозв’язок семантик. – 2 год.

Доведення еквівалентності композиційної та натуральної семантики [1].



Завдання для самостійної роботи (4 год.)

Побудова збагачень мови SIPL та визначення їх в різних семантиках. [1].



Лекція 18. Рекурсія в мовах програмування. Повні впорядковані множини. – 2 год.

Рекурсивні визначення. Повні впорядковані множини та їх властивості. [1, 9].

Практичне заняття 12. Повні впорядковані множини та їх властивості. – 2 год.

1. Опитування та обговорення лекційного матеріалу.

2. Доведення лем про повні впорядковані множини [1].

Завдання для самостійної роботи (4 год.)

Побудова рекурсивних програм. Дослідження властивостей повних впорядковані множин. [1,9].



Лекція 19. Теореми про найменшу нерухому точку. Застосування теорії найменшої нерухомої точки. – 2 год.

Неперервні оператори, їх властивості. Теореми Кнастера-Тарського, про структуру нерухомих точок, про неперервність оператора найменшої нерухомої точки. Неперервність програмних композицій. [1].



Практичне заняття 13. Теореми про найменшу нерухому точку. – 2 год.

1. Опитування та обговорення лекційного матеріалу.

2. Доведення лем та теорем про найменшу нерухому точку. [1].

Завдання для самостійної роботи (4 год.)

Неперервні оператори, побудова нерухомих точок. [1].



Лекція 20. Аналіз рекурсивних програм. – 2 год.

Апроксимації нерухомих точок, доведення властивостей рекурсивних програм. [1, 9].



Завдання для самостійної роботи (4 год.)

Доведення властивостей рекурсивних програм мови SIPL [1].



Лекція 21. Денотаційна семантика. – 2 год.

Принципи побудови денотаційної семантики. Приклади денотаційної семантики програм. [1, 4].



Практичне заняття 14. Побудова денотаційної семантики програм. – 2 год.

1. Опитування та обговорення лекційного матеріалу.

2. Розвязання задач на побудову денотаційної семантики програм [1].

Завдання для самостійної роботи (4 год.)

Побудова денотаційної семантики для розширень мови SIPL [1].



Лекція 22. Аксіоматична семантика. – 2 год.

Метод Флойда-Хоара доведення властивостей програм. Аксіоматична семантика мови SIPL. [1].



Практичне заняття 15. Аксіоматична семантика. – 2 год.

1. Опитування та обговорення лекційного матеріалу.

2. Доведення коректності програм в аксіоматичній семантиці [1].

Завдання для самостійної роботи (4 год.)

Побудова аксіоматичної семантики для розширень мови SIPL [1,7].



Лекція 23. Абстрактні типи даних. – 2 год.

Визначення абстрактних типів даних. Властивості абстрактних типів даних. Приклади.[1, 4,7,9].



Завдання для самостійної роботи (2 год.)

Дослідження спеціальних абстрактних типів даних. [1].



Лекція 24. Принципи іменування та номінативні дані. – 2 год.

Принципи іменування. Номінативні дані. Дані мов програмування як конкретизації номінативних даних. [1].



Практичне заняття 16. Дані в мовах програмування. – 2 год.

1. Опитування та обговорення лекційного матеріалу.

2. Формалізація даних мов програмування як абстрактних типів даних та як номінативних даних. [1].

Завдання для самостійної роботи (4 год.)

Побудова спеціальних номінативних даних.[1].



Лекція 25. Сучасні методи розробки програм та їх формалізація. – 2 год.

Композиційні методи розробки програм. Методи VDM, RAISE, B, Z. [1,5,13].



Практичне заняття 17. Методи розробки програм. – 2 год.

1. Опитування та обговорення лекційного матеріалу.

2. Розробка програм в RAISE, B, Z. [1, 5, 13].

Завдання для самостійної роботи (4 год.)

Розробка програмних систем в RAISE, B, Z та доведення їх властивостей [1, 13].



Лекція 26. Методи семантичного аналізу програм. – 1 год.

Уточнення даних та їх інформаційних зв’язків. Приклади семантичного аналізу програм [1,13].



Завдання для самостійної роботи (2 год.)

Основні методи семантичного аналізу програм [1,7,13]. Доведення еквівалентності перетворень даних та програм [6, 13].


Завдання для самостійної роботи (2 год.)

Розробка простих програмних систем в RAISE, B, Z та доведення їх семантичних властивостей [1,7,13].


Типове завдання модульної контрольної роботи №3

Розробити програмну систему (банкомат, е-магазин, телефонна система, ліфт, мікрохвильова піч, кавовий автомат) та верифікувати її властивості.



Модульна контрольна робота 3.– 5 год. [1,13].

Контрольні запитання до змістового модуля 3.

  1. Визначення семантики.

  2. Сформулюйте принципи функціональної семантики.

  3. Сформулюйте принципи композиційної семантики.

  4. Сформулюйте принципи натуральної семантики.

  5. Як розуміється еквівалентність композиційної та натуральної семантик?

  6. Що таке рекурсивні визначення?

  7. Як визначаються повні впорядковані множини?

  8. Які властивості мають повні впорядковані множини?

  9. Що таке неперервний оператор?

  10. Як визначаються нерухомі точки оператора?

  11. Сформулюйте теорему Кнастера-Тарського.

  12. Яку структуру має множина нерухомих точок неперервного оператора?

  13. Як визначається семантика рекурсивних програм?

  14. Як можна доводити властивості рекурсивних програм?

  15. Сформулюйте принципи денотаційної семантики.

  16. Сформулюйте принципи аксіоматичної семантики.

  17. Як доводиться коректність програм в аксіоматичній семантиці?

  18. Сформулюйте визначення абстрактних типів даних.

  19. Сформулюйте принципи іменування.

  20. Що таке номінативні дані?

  21. Визначте різні типи структур даних як конкретизацій номінативних даних.

  22. Сформулюйте принципи абстрактних типів даних.

  23. Наведіть приклади абстрактних типів даних.

  24. Сформулюйте принципи побудови мови VDM.

  25. Сформулюйте принципи побудови мови RAISE.

  26. Сформулюйте принципи побудови мови B.

  27. Сформулюйте принципи побудови мови Z.

  28. Що таке уточнення даних?

  29. Як доводяться семантичні властивості програм?

  30. Які властивості досліджуються при семантичному аналізі програм?

Рекомендована література: [1, 2, 4, 5, 7, 8, 13]

Питання до іспиту

  1. Основні поняття програмування та відношення між ними

  2. Основні програмні поняття та відношення між ними

  3. Сутнісні та семіотичні аспекти програм

  4. Програмні системи та рівні їх абстракції

  5. Номінативні дані. Структури даних мов програмування як конкретизації номінативних даних

  6. Основні композиції програм

  7. Методи подання синтаксису мов програмування

  8. Формальні граматики та мови (визначення та класифікація)

  9. Визначення та властивості -областей

  10. Визначення та властивості неперервних відображень

  11. Теореми про найменшу нерухому точку (Кнастер-Тарський-Кліні)

  12. Теорема про неперервність оператора нерухомої точки

  13. Системи рівнянь в формальних мовах

  14. Композиційна семантика мов програмування

  15. Натуральна семантика мов програмування

  16. Денотаційна семантика мов програмування

  17. Функціональне програмування

  18. Аксіоматична семантика

  19. Формальні методи розробки програм.

  20. Розробка систем в RAISE, та доведення їх семантичних властивостей.

  21. Розробка систем в B та доведення їх семантичних властивостей.

  22. Розробка систем в Z та доведення їх семантичних властивостей.

Рекомендована література

Основна

  1. М.С. Нікітченко. Курс лекцій з теорії програмування. Електронний посібник. – Київ, 2008.

  2. И.А. Басараб, Н.С.Никитченко, В.Н. Редько. Композиционные базы данных. - К., Либідь, 1992.– 182 с.

  3. Дж. Хопкрофт, Р. Мотвани, Д. Ульман. Введение в теорию автоматов, языков и вычислений.– М.: Вильямс, 2002.– 528 с.

  4. С. Лавров. Программирование. Математические основы, средства, теория.– СПб.: БХВ-Петербург, 2001.– 320 с.

  5. В.М. Глушков, Г.Е. Цейтлин, Е.Л. Ющенко. Алгебра. Языки. Программирование.– К.: Наукова думка, 1974.– 328 с.

  6. М. Гросс, А. Лантен. Теория формальных грамматик.– М.: Мир, 1971.–294 с.

  7. Э. Дейкстра. Дисциплина программирования. - М., Мир, 1976.

  8. Д. Грис. Наука программирования. - М., Мир, 1982.

Додаткова

  1. Капітонова Ю.В., Кривий С.Л., Летичевський О.А. та ін. Основи дискретної математики. – К., 2002.

  2. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М., 1983.

  3. Мальцев А.И. Алгебраические системы. – М.: Наука, 1970.

  4. Нікітченко М.С., Шкільняк С.С. Математична логіка та теорія алгоритмів: підручник. – К., 2008.– 528 с.

  5. The RAISE specification language. Prentice Hall Int.– 1992.– 397 p.





База даних захищена авторським правом ©lecture.in.ua 2016
звернутися до адміністрації

    Головна сторінка