Міністерство освіти І науки України

національний університет “Львівська політехніка”

Кафедра ЕОМ

Програмування машин Тьюрінга

Методичні вказівки

До лабораторної роботи № 1

з дисципліни

" AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ"

для студентів напряму

6.050102 “Комп’ютерна інженерія”

Затверджено

на засідання кафедри

“Електронні обчислювальні машини”.

Протокол № __ від ________ 2012 р. р.

Львів – 2012

Методичні вказівки до комплексу лабораторних робіт з дисципліни "Алгоритми та методи обчислень" для підготовки студентів напряму 6.050102 “Комп’ютерна інженерія” / Укл. Т.А.Матвейчук – Львів: Видавництво НУ “Львівська політехніка”, 2012 – 22 с.

Укладач: Матвейчук Т.А., ст. викладач каф.ЕОМ

Відповідальний

за випуск: Мельник А.О., д-р техн. наук, проф.

Рецензенти: Мороз І.В., ст. викладач каф.ЕОМ

Юрчак І.Ю., доцент кафедри САПР, к.т.н.

1. Мета роботи

Вивчити принципи роботи машин Тюринга, набути практичних навичок програмування машин Тьюрінга.

2. Теоретичні відомості

Теорія алгоритмів - одне з основних понять математики та інформатики. Навіть походження самого терміна «алгоритм» пов'язане з математикою. Відомо, що основна особливість всіх обчислювальних машин полягає в тому, що в основі їх роботи лежить програмний принцип управління. Це означає, що для вирішення як найпростішого, так і найскладнішого завдання користувачеві необхідно використовувати перелік інструкцій або команд, дотримуючись яких крок за кроком комп'ютер видасть необхідний результат. Таким чином, для того, щоб вирішувати завдання на комп'ютері, його необхідно спочатку алгоритмізувати. Саме алгоритмічний принцип і лежить в основі роботи всіх комп'ютерів.

2.1. Поняття алгоритму

В старому трактуванні алгоритм - це точний набір інструкцій, що описують послідовність дій деякого виконавця для досягнення результату, Розв'язок деякого завдання за кінцевий час. У зв'язку з розвитком паралельності в роботі комп'ютерів слово «послідовність» стали заміняти більше загальним словом «порядок». Це пов'язане з тим, що якісь дії алгоритму повинні бути виконані тільки один за одним, але якісь можуть бути й незалежними.

Поняття алгоритму необов'язково відноситься до комп'ютерних програм, так, наприклад, чітко описаний рецепт готування блюда також є алгоритмом, у такому випадку виконавцем є людина. Однак найчастіше як виконавець виступає комп'ютер.

Єдиного «істинного» визначення поняття «алгоритм» немає.

«Алгоритм - це всяка система обчислень, що виконуються по строго визначеним правилам, які після певного числа кроків свідомо приводять до Розв'язок поставленого завдання.» (А. Колмогоров)

«Алгоритм - це точне розпорядження, яке визначає обчислювальний процес, що йде від варійованих вихідних даних до шуканого результату.» (А. Марков)

«Алгоритм - строго детермінована послідовність дій, що описує процес перетворення об'єкта з початкового стану в кінцеве, записана за допомогою зрозумілих виконавцеві команд.» (М. Угринович)

«Алгоритм - це послідовність дій, спрямованих на одержання певного результату за кінцеве число кроків.» (ROXANstudio)

«Алгоритм є формалізована послідовність дій (подій). Алгоритм може бути записаний словами і зображений схематично. Практично будь-яка невипадкова повторювана дія піддається опису через алгоритм.» ([grey_olli])

«Алгоритм - однозначно, доступно і коротко описана послідовність процедур для відтворення процесу з обумовленим завданням алгоритму результатом при заданих початкових умовах. Універсальність (або спеціалізація) алгоритму визначається застосовністю і надійністю даного алгоритму для Розв'язок нестандартних завдань.»