Міністерство освіти і науки, молоді та спорту України Національний університет “Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 2 на тему: " Програмування машин Поста " з дисципліни: " AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ " Вибір індивідуального завдання: DN = 17 A2 = №(m) = 109 № V=(17+109)%25+1=2 Львів – 2013 1.Мета роботи Вивчити принципи роботи машин Поста, набути практичних навичок програмування машин Поста. Постановка задачі Загальна частина Розробити алгоритм розв'язання задачі згідно з індивідуальним завданням. Скласти програму для машини Поста. Відлагодження і тестування програми провести в середовищі емулятора мишини Поста. Записати в середовищі емулятора в поле "Условие задачи" варіант і умову індивідуального завдання. В поле "Комментарий" записати коротке пояснення дій, які реалізуються у відповідних станах МП. Визначити часову (T), місткісну (M) та програмну (P) складності алгоритму, представленого у вигляді програми для МП. Індивідуальне завдання На стрічці задана послідовність з одного або більше масивів різної довжини. При цьому кожні два сусідніх масиви відокремлені один від одного однією порожньою коміркою. Заповнити всі порожні комірки між масивами мітками. В початковому стані каретка знаходиться над крайньою лівою міткою масиву. Словесний опис алгоритму  Рухаємо каретку вправо перевіряєм доки не находимо порожню комірку. Потім перевіряємо чи наступний елемент масив. Якщо так, то заповнюєм порожню комірку масивом, інакше завершуємо програму. Алгоритм у вигляді програми для МТ >2 Рух каретки вправо  ? 3,1 Перевіряємо чи є масив. Якщо так,тоді рухаємось вправо  3. > 4 Рух каретки вправо  4. ? 5,6 Перевіряємо чи є масив,якщо порожня комірка тоді завершуємо виконання програми  5. ! Закінчення  6. < 7 Рух каретки вліво  7. V 1 Заповнюємо порожні комірки між масивами   Результати роботи програми 5.1 Початковий стан МП
5.2 Кінцевий стан МП
6. Ефективність алгоритму 6.1 Часова складність Кількість виконаних тактів дорівнює 30 , тобто часова складність T= 30 . 6.2 Місткісна складність В процесі роботи використовуються комірки стрічки з номерами від 0 до 6, тобто місткісна складність М=7. 6.3 Програмна складність Табличне представлення МП містить 7 заповнених рядків, отже програмна складність цієї МП дорівнює Р=7. Висновок У цій лабораторній роботі я вивчив принципи роботи машин Поста та набув практичних навичок програмування машин Поста.