Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 2 «Програмування машин Поста» з дисципліни: “ Aлгоритми та методи обчислень” Варіант: ( 8 + 117 ) % 25 + 1 = 1 Львів 2012 Мета роботи Вивчити принципи роботи машин Поста, набути практичних навичок програмування машин Поста. 2. Постановка задачі: 2.1 Загальна частина: Розробити алгоритм розв'язання задачі згідно з індивідуальним завданням. Скласти програму для машини Поста. Відлагодження і тестування програми провести в середовищі емулятора мишини Поста. Записати в середовищі емулятора в поле "Условие задачи" варіант і умову індивідуального завдання. В поле "Комментарий" записати коротке пояснення дій, які реалізуються у відповідних станах МП. Визначити часову (T), місткісну (M) та програмну (P) складності алгоритму, представленого у вигляді програми для МП. 2.2 Індивідуальне завдання: На стрічці заданий масив міток. Збільшити довжину масиву на 2 мітки. В початковому стані каретка знаходиться або зліва від масиву, або над однією з міток масиву. 3. Словесний опис алгоритму: Для реалізація алгоритму потрібно так, щоб МП спочатку знайшла кінець числа, а далі добавила дві мітки. 4. Алгоритм у вигляді програми для МП 1. => 2 Шукає кінець числа  2.? 3,1 Якщо знайде, то  3. V 4 Ставить дві мітки(збільшить число на 2)  4. =>5   5. V 6   6. ! кінець   5. Результати виконання програми 5.1. Початковий стан МП
5.2. Кінцевий стан МП
n = 6 6. Складність алгоритму 6.1. Часова складність Запустивши покроково (F8) програму на виконання можна порахувати, що кількість виконаних тактів дорівнює 16, тобто часова складність T=11 6.2. Місткісна складність У процесі роботи я використовую комірки стрічки з номерами 0, 1, 2, 3, тобто міст кісна складність М=4 6.3. Програмна складність Табличне представлення МТ містить 6 команд, отже програмна складність даної МП дорівнює Р=6. Висновки Сьогодні я вивчив принципи роботи машин Поста, набув практичних навичок у програмуванні машин Поста.