моделі обчислень

У цьому розділі розглянемо різні способи представлення обчислень (обробки даних) у вигляді моделей; ці способи пов'язані з різною природою обчислень.

Модель - математична абстракція для класу об'єктів (процесів), в якій виділяються істотні властивості класу і відкидаються несуттєві; чим грубіше модель, тим ширше клас. Добре сформульована модель володіє ясним фізичним змістом і адекватна (відповідає, відповідає вимогам точності) даного класу. Наприклад, в планетарної моделі небесні тіла представляються у вигляді матеріальних точок, які не мають розмірів, але мають конкретну масу; ця модель дозволяє досить точно прогнозувати, наприклад, місячні затемнення.

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

Для обчислень в широкому сенсі побудовані різноманітні моделі, що враховують характер обчислень (чисельні, логічні, символьні), розрядність чисел (бітові або байтові), сталість довжини оброблюваних слів в ЕОМ і т. Д.

Нижче розглядаються 2 моделі обчислень у вузькому сенсі:

а також 2 моделі дискретної переробки інформації - автомати і машини Тьюринга.

Логічні алгоритми містять інструкції, що відносяться не до чисел, а до об'єктів будь-якої природи. Прикладами логічних алгоритмів можуть служити алгоритм пошуку шляху в лабіринті, ігрові алгоритми, алгоритм перемикання світлофора і т. Д. Моделлю логічних обчислень є асоціативні обчислення.

Чисельні алгоритми зводять рішення поставленого завдання до арифметичних дій над числами. Приклад - алгоритм Евкліда для знаходження найбільшого загального дільника двох заданих позитивних чисел. До чисельних алгоритмах зводиться вирішення багатьох завдань: обчислення коренів алгебраїчних рівнянь, рішення систем рівнянь, чисельне інтегрування і т. П. Моделлю таких обчислень є рекурсивні функції.

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

Автоматна модель з розширеними можливостями - машина Тьюринга - дозволяє не тільки реалізувати різні обчислення і перетворення інформації, а й перевірити існування алгоритму для даного класу задач.