Модель обчислення — Вікіпедія

Ця стаття містить правописні, лексичні, граматичні, стилістичні або інші мовні помилки, які треба виправити. Ви можете допомогти вдосконалити цю статтю, погодивши її із чинними мовними стандартами. (лютий 2018)

Модель обчислення
Досліджується в	теоретична інформатика
Представляє	розрахунок
Модель обчислення у Вікісховищі

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

Моделі[ред. | ред. код]

Деякі приклади моделей обчислення:

• Машина Тюрінга
• Скінченні автомати
• Рекурсивні функції
• Лямбда-числення
• Комбінаторна логіка
• Клітинний автомат
• Абстрактні переписні системи^[en]
• Взаємодія мереж^[en]
• Мережа процесів Кана

Застосування[ред. | ред. код]

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

У розробці, керованій моделями^[en], модель розрахунку пояснює, що поведінка всієї системи є результатом поведінки кожного з її компонентів.

Ключовий момент, про який часто забувають, полягає в тому, що зазначені нижні межі для задач часто ставляться для моделі обчислення, яка більш обмежена, ніж набір операцій, які можна використовувати на практиці. Тому можуть існувати алгоритми, які будуть працювати швидше, ніж можна буде вважати можливим.^[1]

Категорії[ред. | ред. код]

Існує безліч моделей обчислень, що відрізняються в наборі допустимих операцій та вартістю їх обчислень. Їх можна розділити на такі загальні категорії як автомат та їй еквівалентні (наприклад, Лямбда-числення еквівалентне машини Тюрінга). Вони використовуються в доведеннях обчислюваності та верхньої межі обчислювальної складності алгоритмів. Також існують моделі дерева рішень, що використовуються у доведеннях нижніх меж обчислюваної складності алгоритмічних задач.

Див. також[ред. | ред. код]

• Стек-машина^[en] (0-операндна машина)
• Акумулятор (процесор) (1-операндна машина)
• Регістрові машини (2, 3, … операндна машина)
• RAM-машина
• Cell-probe модель^[en]

Список літератури[ред. | ред. код]

Додаткові джерела[ред. | ред. код]

• Fernández, Maribel (2009). Models of Computation: An Introduction to Computability Theory. Undergraduate Topics in Computer Science. Springer. ISBN 978-1-84882-433-1.
• Savage, John E. (1998). Models Of Computation: Exploring the Power of Computing. Архів оригіналу за 12 жовтня 2016. Процитовано 19 грудня 2017.

Це незавершена стаття з інформатики. Ви можете допомогти проєкту, виправивши або дописавши її.