Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Міністерство освіти і науки, молоді та спорту України
Черкаський державний технологічний університет
Факультет інформаційних технологій і систем
Кафедра комп’ютерних технологій
Дисципліна:
Теорія алгоритмів
З В І Т
з лабораторної роботи № 3-4
Тема: “ ЗАГАЛЬНА СХЕМА ПОБУДОВИ АЛГОРИТМІЧНИХ СИСТЕМ.
студента 3-го курсу спеціальності «ІТПС - 1233»
Глизя Євгенія Олександровича
_________________ ______________
(Дата) (Підпис студента)
Оцінка __________________
Перевірено ______________
(Дата)
Викладач ________________ / Триус Ю.В./
(Підпис) (Прізвище та ініціали)
Черкаси – 2012 р.
Завдання до лабораторної роботи:
1. Нехай і задано схему нормального алгоритму
Побудувати блок-схему та граф-схему дії даного алгоритму і знайти результат перетворення заданих слів:
а) X=abba;
б) X=bbaabb;
в) X=aa.
Результат виконання:
Блок схема :
Граф схема:
3. Побудувати схему алгоритму, який незастосовний до будь-якого слова в будь-якому алфавіті.
4. Побудувати схему алгоритму, який застосований до будь-якого слова в будь-якому алфавіті.
5. В алфавіті U={|} побудувати схему нормального алгоритму для знаходження суми скінченного числа натуральних чисел. Вхідне слово X подавати у вигляді: ||||+||||||+||.
6. Нехай задано два слова X і Y в алфавіті . В розширеному алфавіті побудувати нормальний алгоритм, який слово виду перетворює в слово X, тобто
.
Цей алгоритм називається алгоритмом відсікання правої частини слова.
7. В алфавіті задане деяке натуральне число X. Побудувати схему нормального алгоритму такого, що
.
Подати його у вигляді блок-схеми та граф-схеми і виконати при , .
8. Побудувати схему нормального алгоритму для знаходження значення булевого виразу, який містить константи 0 і 1, символи операцій заперечення (), кон’юнкція (), диз’юнкція (), імплікація (->) і еквіваленція (<->) при цьому для зазначення порядку виконання операцій можна застосовувати круглі дужки. Наприклад, вхідним словом для алгоритму може бути вираз (01) (11)->(0<->1).
Завдання для самостійного виконання:
1.1. Аналогічно до задачі 6 побудувати схему алгоритму відсікання лівої частини слова.
1.2. Побудувати схему нормального алгоритму подвоєння слів в алфавіті .
1.3. Побудувати схему нормального алгоритму подвоєння слів в алфавіті .
1.4. В алфавіті задане деяке натуральне число X. Побудувати схему нормального алгоритму такого, що
.
Подати його у вигляді блок-схеми та граф-схеми і виконати при , .
1.5. В алфавіті задано деяке натуральне число X. Сконструювати нормальні алгоритми А такі, що
а);
б).
Побудувати їх блок-схеми та граф-схеми.
1.6. Задана схема нормального алгоритму B є початком схеми нормального алгоритму для знаходження добутку двох натуральних чисел в алфавіті . Побудувати схему алгоритму A, яка є продовженням схеми В, таку, що з’єднання алгоритмів В і А буде схемою нормального алгоритму для знаходження добутку двох натуральних чисел в алфавіті U. Вхідне слово X подавати у вигляді .
.
Індивідуальне завдання №2 Варіант №2
1. Скласти схему нормального алгоритму у відповідному алфавіті, який перевертає задане слово, побудувати блок-схему та граф-схему алгоритму і реалізувати його у середовищі AlgoMachines:
Слово – Computer
2. В алфавіті задано деяке натуральне число X у десятковій системі числення. Скласти нормальний алгоритм А такий, що для вхідного слова виду Х+N (або Х-N) обчислює відповідне значення виразу: