Дисципліни “теорія програмування” icon

Дисципліни “теорія програмування”




Скачати 138.67 Kb.
НазваДисципліни “теорія програмування”
Дата04.07.2012
Розмір138.67 Kb.
ТипДокументи

Міністерство освіти і науки України

Сумський державний університет


МЕТОДИЧНІ ВКАЗІВКИ

ДО ВИКОНАННЯ КОНТРОЛЬНОЇ РОБОТИ

3 ДИСЦИПЛІНИ “ТЕОРІЯ ПРОГРАМУВАННЯ”

ДЛЯ СТУДЕНТІВ ЗАОЧНОЇ ФОРМИ НАВЧАННЯ

напряму 0802


Суми

Вид-во СумДУ

2008

Методичні вказівки до виконання контрольної роботи з дисципліни “Теорія програмування” /Укладач М.С.Бабій. – Суми: Вид-во СумДУ, 2008. – 23с.


Кафедра інформатики

ЗМІСТ


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, що містять не більш однієї пари послідовних одиниць.


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


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


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

PROGRAM -> begin DECS ; STATS end

DECS -> D ; DECS | D

^ STATS -> S ; STATS | S .

Написати ліве породження для

begin D ; D ; S ; S end


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


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

Факти: a – позитивне;

b – негативне.

Правило: добуток xy позитивний, якщо x і y – обоє позитивні або обоє негативні.

Ціль: чи є ab позитивним ?


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

y := 4*x – 5;

x :=2* y – 11,

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


Варіант 4


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


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


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


Завдання 4 Побудувати контекстно-вільну граматику, що генерує множину ланцюжків { 0n1n | n ? 1}.


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


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

Правило: добуток xy позитивний, якщо x>0, y>0 або x<0, y<0.

Ціль: чи є добуток (-1) і (-5) позитивним ?


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

y := 2*x + 1;

x := y – 4,

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


Варіант 5


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


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


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


Завдання 4 Подана граматика породжує мову регулярного вираження { 0*1(0|1)* }:

S –> A1B , A –> 0A | ? , B –> 0B | 1B | ?.

Записати ліве і праве породження для ланцюжка 00101.


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


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

Факти: a – поле класу c ;

b – метод класу d .

Правило: x – є членом класу y, якщо x – поле y або x – метод y.

Ціль: чи є a членом класу d ?


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

y := 4*x – 15;

x := y,

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


Варіант 6


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


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


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


Завдання 4 Подана граматика породжує мову регулярного виразу {0*1(0|1)* }:

S –> A1B , A –> 0A | ? , B –> 0B | 1B | ?.

Записати ліве і праве породження для ланцюжка 1001.


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


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

Факти: трикутник ^ A має кути – 60, 60, 60,

трикутник B має кути – 45, 45, 90.

Правило: трикутник є рівнобедреним, якщо два його кути однакові.

Ціль: чи є трикутники A і B рівнобедреними ?


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

y := x + 4;

x := y – 4,

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


Варіант 7


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


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


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


Завдання 4 Подана граматика породжує мову регулярного виразу { 0*1(0|1)* }:

S –> A1B , A –> 0A | ? , B –> 0B | 1B | ?.

Записати ліве і праве породження для ланцюжка 00011.


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


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

Факти: трикутник ^ A має кути – 60, 60, 60;

трикутник B має кути – 45, 45, 90.

Правило: трикутник є прямокутним, якщо один з його кутів дорівнює 90 градусам.

Ціль: чи є трикутники A і B прямокутними ?


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

y := x + 9;

x := y + 8,

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


Варіант 8


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


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


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


Завдання 4 Подана граматика породжує мову регулярного виразу { 0*1(0|1)* }:

S –> A1B , A –> 0A| ? , B –> 0B|1B| ?.

Записати ліве і праве породження для ланцюжка 00010.


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


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

Факти: трикутник ^ A має кути – 60, 60, 60;

трикутник B має кути – 45, 45, 90.

Правило: трикутник є рівностороннім, якщо всі кути рівні.

Ціль: чи є трикутники A і B рівносторонніми ?


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

y := x – 2;

x :=4*y + 3,

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

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


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


Клас регулярних виразів визначається такими правилами:

1 є регулярним виразом.

2 Якщо а А, то а – регулярний вираз.

3 Якщо w – регулярний вираз, то w* і (w) – регулярні вирази.

  1. Якщо w1 і w2 – регулярні вирази, то w1w2, w1|w2 – регулярні вирази. У виразі w1w2 використовується операція конкатенації, у виразі w1|w2 – операція об'єднання.


Потрібний вираз може бути представлений, наприклад, у такій формі:

( (a|b|c)a(a||b|c)b(a|b|c) ) | ( (a|b|c)b(a||b|c)a(a|b|c) ) .


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


Розбираємо регулярний вираз r на складові підвирази. Для кожного базового символу з r, що є або символом алфавіту, або , будуємо базові недетерміновані автомати.



Потім відповідно до структури r комбінуємо базові недетерміновані автомати, поки не одержимо автомат для усього виразу.

Позначимо недетермінований автомат для s через N(s), а недетермінований автомат для t через N(t).

Тоді правила комбінування можна зобразити так:

а) для s|t


?




б) для st





в) для s*



Комбінуючи дані елементи, одержимо схему для виразу (a|b)*a.




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


Метод побудови підмножин полягає в наступному.

Спочатку будується ?-замикання для вихідного стану 0. У замикання входять усі стани, що досяжні з вихідного по переходах . Для даної схеми


-close{0}= {0,1,2,4,7},

З підмножини A по символу a можна перейти до підмножини {3,8}. Замиканням підмножини {3,8} буде підмножина {1,2,3,4,6,7,8}, яку позначимо буквою B.

Відповідно по символу b з підмножини A можна перейти до підмножини {5}, замиканням якої буде підмножина {1,2,4,5,6,7}. Позначимо це замикання буквою С.

Далі виконуємо ті самі переходи вже для підмножин B і C. Процес завершується, коли будуть вичерпані всі підмножини.

Результуюча таблиця переходів для даної схеми буде мати вигляд





a

b

A

B

C

B

B

C

C

B

C


Відповідна діаграма переходів має вигляд





Завдання 4 Побудувати контекстно-вільну граматику, що генерує множину ланцюжків { 0n1n | n ? 1}.


Граматика визначається як четвірка компонентів (VT, VN, P, S).

Тут:

VT – алфавіт термінальних символів або терміналів;

VN – алфавіт нетермінальних символів або нетерміналів, VT VN= ;

P – множина продукцій (або правил) вигляду , складається з одного або більше символів V, — з нуля або більше символів V, де V= VT VN ;

S – стартовий символ (або аксіома).


Прикладом контекстно-вільної граматики для даного завдання може бути граматика

( {0, 1}, {S}, P, S )

з набором продукцій: S –> 01; S –> 0S1.


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


Запис даної функції мовою Лісп може мати вигляд


( defun S ( R ) (* 3.14 R R) ) ,


а її застосування для радіуса R=5

( S 5 ) .


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

Факти: трикутник A має кути – 30, 60, 90,

трикутник ^ B має кути – 20, 80, 80.

Правило: трикутник є рівнобедреним, якщо два його кути однакові.

Ціль: чи є трикутники A і B рівнобедреними ?


Запис правил і фактів мовою Пролог може мати вигляд


predicates

tre (symbol, integer, integer, integer)

rb (symbol)

clauses

tre (a, 30, 60, 90).

tre (b, 20, 80, 80).

rb (V) :- tre (V, X, Y, _), X=Y .

rb (V) :- tre (V, _, Y, Z), Y=Z .

rb (V) :- tre (V, X, _, Z), X=Z .


Цілі записуються у вигляді rb(a), rb(b).


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

y := x + 9;

x := y + 8,

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


Для послідовності операторів


{P1} S1 {P2},

{P2} S2 {P3}

правило виведення буде таким:


.

Кожний з операторів є оператором присвоювання вигляду х = Е або y = Е, правило виведення для якого має вигляд відповідно Р=Qx=E або Р=Qy=E. Іншими словами, передумова Р обчислюється як умова Q , в якій всі x або y заміняють виразом Е.

Таким чином, передумовою другого оператора буде

{y<–7}, а першого – {x < –16}.


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


Основна література


  1. Ахо А. и др. Компиляторы. Принципы, технологии, инструменты. – М.: Вильямс, 2001. – 768с.

  2. Глушков В.М. и др. Алгебра. Языки. Программирование. – К: Наукова думка, 1989. –376c.

  3. Жуков Д. Доказательство правильности программ. – Файл.

  4. Люгер Д. Искусственный интеллект. – М.: Вильямс, 2003. – 864с

  5. Себеста М. Основные концепции языков программирования. – М.: Вильямс, 2001. – 672с.

  6. Хантер Р. Основные концепции компиляторов. – М.: Вильямс,2002. – 256с.

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


Додаткова література


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

9 Дейкстра Э. Дисциплина программирования. – М.: Мир,

1978.


Електронні видання


  1. Конспект лекцій дистанційного курсу з дисципліни “Теорія програмування”.


Навчальне видання


^ МЕТОДИЧНІ ВКАЗІВКИ

ДО ВИКОНАНЯ КОНТРОЛЬНОЇ РОБОТИ

3 ДИСЦИПЛІНИ “ТЕОРІЯ ПРОГРАМУВАННЯ”

ДЛЯ СТУДЕНТІВ ЗАОЧНОЇ ФОРМИ НАВЧАННЯ

напряму 0802


Відповідальний за випуск О.П. Чекалов

Редактор Н.А Гавриленко

Комп’ютерне верстання


Підп. до друку поз.

Формат 60х84/16. Папір офс. Гарнітура Times New Roman Cyr. Друк офс.

Ум. друк. арк. 1,39 Обл.-вид. арк. 0,93

Тираж 50 пр. Собівартість вид.

Зам. №


Видавництво СумДУ при Сумському державному університеті

40007, м. Суми, вул. Р.-Корсакова,2

Свідоцтво про внесення суб”єкта видавничої справи до Державного реєстру

ДК № 3062 від 17.12.2007.

Надруковано у друкарні СумДУ

40007, Суми, вул. Р.-Корсакова,2.

Схожі:

Дисципліни “теорія програмування” iconМетодичні вказівки до виконання контрольної роботи 3 дисципліни "теорія програмування" для студентів заочної форми навчання
Методичні вказівки до виконання контрольної роботи з дисципліни “Теорія програмування” /Укладач М. С. Бабій. – Суми: Вид-во СумДУ,...
Дисципліни “теорія програмування” iconМетодичні вказівки до виконання контрольної роботи 3 дисципліни "теорія програмування" для студентів заочної форми навчання
Методичні вказівки до виконання контрольної роботи з дисципліни “Теорія програмування” /Укладач М. С. Бабій. – Суми: Вид-во СумДУ,...
Дисципліни “теорія програмування” iconЗатверджую Ректор О. Л. Голубенко 2012 р. Пояснювальна записка
Програма розроблена на основі навчальної програми з дисциплін: «Програмування», «Прикладна теорія цифрових автоматів», «Системне...
Дисципліни “теорія програмування” iconПояснювальна записка щодо проведення фахового вступного випробування для осіб
Програма розроблена на основі навчальної програми з дисциплін: «Програмування», «Прикладна теорія цифрових автоматів», «Системне...
Дисципліни “теорія програмування” iconКоркуна олеся євстахіївна korkuna Olesia Evstakhiivna
Викладає дисципліни: «Вища математика», «Теорія ймовірності та математична статистика», «Математичне програмування»
Дисципліни “теорія програмування” iconПояснювальна записка щодо проведення фахового вступного випробування для осіб, які вступають на навчання за освітньо-професійними програмами
Програма розроблена на основі навчальної програми з дисциплін: «Програмування», «Прикладна теорія цифрових автоматів», «Системне...
Дисципліни “теорія програмування” iconМ.І. Самойленко, Г. В. Білогурова, В. П. Протопопова методичні вказівки до виконання практичних, гозрахунково-графічних та самостійних робіт з дисципліни „Вища та прикладна математика: Теорія ймовірностей та математична статистика;
Вища та прикладна математика: Теорія ймовірностей та математична статистика; Математичне програмування”
Дисципліни “теорія програмування” iconНазва модуля: Основи цифрових систем керування електромеханічними системами Код модуля
Обчислювальна техніка, алгоритмічні мови та програмування, теорія автоматичного керування, теорія електроприводу
Дисципліни “теорія програмування” iconПитання на іспит з дисципліни «Математичне програмування та дослідження операцій»
Загальна математична модель лінійного програмування. Форми запису задач лп. Геометрична інтерпретація злп
Дисципліни “теорія програмування” iconПитання на іспит з дисципліни «Математичне програмування та дослідження операцій»
Загальна математична модель лінійного програмування. Форми запису задач лп. Геометрична інтерпретація злп
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи