Пошук навчальних матеріалів по назві і опису в нашій базі:

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




138.6 Kb.
НазваМетодичні вказівки до виконання контрольної роботи 3 дисципліни "теорія програмування" для студентів заочної форми навчання
Дата конвертації10.11.2012
Розмір138.6 Kb.
ТипМетодичні вказівки
Зміст
1 Загальні вказівки
2 Завдання для контрольних робіт
Stats -> s ; stats | s .
A має кути – 60, 60, 60,трикутник B
A має кути – 60, 60, 60;трикутник B
A має кути – 60, 60, 60;трикутник B
3 Приклади виконання завдань
B має кути – 20, 80, 80.Правило: трикутник
Список літератури
Методичні вказівки
Міністерство освіти і науки України

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


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

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

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.

Схожі:

Методичні вказівки до виконання контрольної роботи 3 дисципліни \"теорія програмування\" для студентів заочної форми навчання iconМетодичні вказівки І контрольні завдання з англійської мови для студентів 1 курсу заочної форми навчання
Виконання контрольної роботи з дисципліни «Англійська мова (за професійним спрямуванням)» студентами заочної форми навчання є складовою...
Методичні вказівки до виконання контрольної роботи 3 дисципліни \"теорія програмування\" для студентів заочної форми навчання iconМетодичні вказівки до виконання контрольної роботи Електричне коло постійного струму
Програма, методичні вказівки та завдання до контрольної роботи №1 з дисципліни "Основи теорії електричних кіл" для студентів спеціальності...
Методичні вказівки до виконання контрольної роботи 3 дисципліни \"теорія програмування\" для студентів заочної форми навчання iconМетодичні вказівки до виконання контрольної роботи для студентів спеціальності
Основи управління якістю. Програма курсу та методичні вказівки до виконання контрольної роботи для студентів спеціальності „Автомобілі...
Методичні вказівки до виконання контрольної роботи 3 дисципліни \"теорія програмування\" для студентів заочної форми навчання iconМетодичні вказівки щодо виконання контрольних робіт студентами заочної форми навчання
Виконання контрольної роботи з курсу “Контролінг” є важливим етапом засвоєння положень дисципліни студентами заочної форми навчання....
Методичні вказівки до виконання контрольної роботи 3 дисципліни \"теорія програмування\" для студентів заочної форми навчання iconМетодичні вказівки щодо виконання контрольних робіт з навчальної дисципліни "Організація роботи з кадрами " для студентів заочної формИ навчання
Методичні вказівки щодо виконання контрольних робіт з навчальної дисципліни “Організація роботи з кадрами ” для студентів заочної...
Методичні вказівки до виконання контрольної роботи 3 дисципліни \"теорія програмування\" для студентів заочної форми навчання iconМетодичні вказівки до виконання контрольних робіт з дисципліни „ Теорія систем та математичне моделювання для студентів заочної форми навчання напряму «Інформатика»
Методичні вказівки до виконання контрольних робіт з дисципліни „ Теорія систем та математичне моделювання ” /Укладач Л. Д. Назаренко....
Методичні вказівки до виконання контрольної роботи 3 дисципліни \"теорія програмування\" для студентів заочної форми навчання iconЗавдання для контрольної роботи для студентів заочної форми навчання з дисципліни «Промисловий маркетинг»
Виконання студентами, контрольної роботи, як складової частини навчального процесу, передбачено їх навчальними планами
Методичні вказівки до виконання контрольної роботи 3 дисципліни \"теорія програмування\" для студентів заочної форми навчання iconМетодичні вказівки до виконання контрольної роботи з курсу культурології для студентів заочної форми навчання всіх спеціальностей
Розповсюдження і тиражування без офіційного дозволу Дніпродзержинського державного технічного університету заборонено
Методичні вказівки до виконання контрольної роботи 3 дисципліни \"теорія програмування\" для студентів заочної форми навчання iconМетодичні вказівки щодо виконання контрольної роботи та самостійної роботи студентів по темі «системи диференціальних рівнянь»
М вища математика. Методичні вказівки щодо виконання контрольної роботи та самостійної роботи студентів по темі «Системи диференціальних...
Методичні вказівки до виконання контрольної роботи 3 дисципліни \"теорія програмування\" для студентів заочної форми навчання iconМетодичні вказівки до виконання та оформлення курсової роботи для студентів всіх форм навчання
Методичні вказівки до виконання та оформлення курсової роботи для студентів усіх форм навчання з дисципліни “Програмування”/Укладачі:...
Додайте кнопку на своєму сайті:
ua.convdocs.org


База даних захищена авторським правом ©ua.convdocs.org 2014
звернутися до адміністрації
ua.convdocs.org
Реферати
Автореферати
Методички
Документи
Випадковий документ

опубликовать
Головна сторінка