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

ЗМІСТ

                                                                             C.

1 ЗАГАЛЬНІ ВКАЗІВКИ  .  .  .  .  .  .  . .  .  .  .  .  .  .  .  .  .   4

2 ЗАВДАННЯ ДЛЯ КОНТРОЛЬНИХ РОБІТ.  .  .  .  .  .    5

3 ПРИКЛАДИ ВИКОНАННЯ ЗАВДАНЬ.  .  .  .  .  .  .  .  15

СПИСОК ЛІТЕРАТУРИ   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 22

1 ЗАГАЛЬНІ ВКАЗІВКИ

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

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

Контрольна робота виконується після проведення всіх лекцій і лабораторних робіт.

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

Після отримання рецензії студент повинен виправити помилки, вказані викладачем.

            Для допомоги у виконанні контрольної роботи найбільш доцільно використовувати конспект лекцій дистанційного курсу з  дисципліни “Теорія програмування”.

2 ЗАВДАННЯ ДЛЯ КОНТРОЛЬНИХ РОБІТ

Варіант 1

            Завдання 1 Написати регулярний вираз для мови, яка являє собою множину ланцюжків у алфавіті {a,b,c}, що містять хоча б один символ a і хоча б один символ b.

Завдання 2 За регулярним виразом (a|b)^* методом Томпсона побудувати ε-недетермінований автомат.

Завдання 3    Методом побудови підмножин перетворити

 ε - недетермінований автомат із завдання 2 в детермінований автомат. Результатом повинна бути діаграма переходів для відповідного детермінованого автомата.

Завдання 4  Написати граматику,   яка для алфавіту {0,1} генерує всі рядки, включаючи порожній.

Завдання 5 Мовою функціонального програмування описати і застосувати функцію, що обчислює один з коренів квадратного рівняння.

Завдання 6  Мовою логічного програмування написати програму з такими фактами, правилами і цілями:

Факти: a  - син b;

 b - син c.

Правило: x - онук z, якщо x - син y і y – син z.

Ціль: чи є a онуком c ?

Завдання 7 Написати найслабкішу передумову для послідовності операторів

y := 3*x + 1;

                        x := y + 3,

якщо постумовою Q останнього оператора є { x < 10 }.

Варіант 2

            Завдання 1 Написати регулярний вираз для мови, яка являє собою множину ланцюжків з 0 і 1, у яких четвертий від правого краю символ дорівнює 1.

Завдання 2 За регулярним виразом (a|b)^*a методом Томпсона побудувати ε- недетермінований автомат.

Завдання 3 Методом побудови підмножин перетворити ε- недетермінований автомат з завдання 2 у детермінований автомат. Результатом повинна бути діаграма переходів для відповідного детермінованого автомата.

Завдання 4  Є граматика з продукціями

 S  ->  if E then S else S | if E then S | Other .

Показати, що ланцюжок

             if E then if E then Other else Other

має два лівих породження.

Завдання 5 Мовою функціонального програмування описати і застосувати функцію, що обчислює відстань від довільної точки на площині до точки з координатами (1,2).

Завдання 6  Мовою логічного програмування написати програму з такими фактами, правилами і цілями:

Факт: a  - чоловік b.

Правило: x - дружина y, якщо y – чоловік x.

Ціль: чи є b  дружиною a ?

Завдання 7 Написати найслабкішу передумову для послідовності операторів

y := 5*x – 2;

                        x := y – 6,

якщо постумовою Q останнього оператора є { x < 2 }.

 Варіант 3

            Завдання 1 Написати регулярний вираз для мови, яка являє собою множину ланцюжків з 0 і 1, що містять не більш однієї пари послідовних одиниць.