Машина тьюринга
Завдання 16.1
1. Оцінити складність алгоритму обробки двовимірного масиву, розробленого при виконанні Лабораторної роботи 15.1
O(n^2)
2. Оцінити час, необхідний для вирішення завдання у всіх можливих випадках.
O(n)
3. Оцінити об'єм необхідної пам'яті у всіх можливих випадках.
4*n^2
4. Здійснити поопераційний аналіз алгоритму обробки масиву, розробленого при виконанні Лабораторної роботи 15.1
Введення розмір матриці
Заповнення елементами масив
Перебір рядків та стовпчиків
Виведення результатів на екран
5. Запропонувати способи покращення розробленого алгоритму.
Зменшити перебір елементі шляхом зміни циклів
6. Кількісно оцінити запропоноване покращення алгоритму обробки двовимірного масиву, розробленого при виконанні Лабораторної роботи 15.1
O(n*log(n))
Завдання 16.2
- текст завдання відповідно до свого варіанту;
Розробити машини Тюрінга відповідно до наведеного в варіанті завдання.
Скласти множину тестів для перевірки функціональної повноти розробленої МТ.
Визначити вхідний алфавіт та множину станів розробленої машини Тюрінга,
Здійснити перевірку правильності роботи машини Тюрінга та скласти протокол роботи машини Тюринга при виконанні тестових прикладів (в протоколі роботи машини Тюринга визначається, яку саме команду виконує, в якому стані знаходиться та який вигляд має проміжне слово машини Тюринга на кожному кроці роботи).
Варіант до завдання:
