Реферат: Моделі і методи прийняття рішень
Q=(q1 , q2 , …, q5 ),
де q0 - початковий стан;
q1 - стан помилки;
q2 - кількість нулів непарна, а одиниць – парна;
q3 – кількість нулів і одиниць непарна;
q4 – кількість нулів і одиниць парна;
q5 – кількість нулів парна, а одиниць – непарна;
Згідно з умовою задачі F=<q2 >
Функції переходів визначаються так:
| q0 #→q1 | q0 0→q2 | q3 0→q5 |
| q1 →q1 | q0 1→q5 | q3 1→q2 |
| q2 →q1 | q1 0→q1 | q4 0→q2 |
| q3 →q1 | q1 1→q1 | q4 1→q5 |
| q4 →q1 | q2 0→q4 | q5 0→q3 |
| q5 →q1 | q2 1→q3 | q5 1→q4 |
Автомати зручно задавати таблично:
| # | 0 | 1 |
← |
| q0 | q1 | q2 | q5 |
| q1 | q1 | q1 | q1 |
| q2 | q1 | q4 | q3 |
| q3 | q1 | q5 | q2 |
| q4 | q1 | q2 | q5 |
| q5 | q1 | q3 | q4 |
Рис.1. Табличне задання автомата
Рядки таблиці позначаються станами множини Q, а стовпці – символами вхідного алфавіту. Символ ←позначає заключні допустимі стани.
Графічний опис автомата полягає у побудові графа, де вершини qi і qj з’єднуються дугою a якщо виконується команда qi a→qj . Заключні допустимі вершини позначаються подвійним колом.
Рис.2. Графічне задання автомата
Спеціальним типом автомата є машина Тьюринга. Універсальна машина Тьюринга може обчислити будь-який інтуїтивний алгоритм.
3. Складність алгоритмів
Універсальним обчислювальним пристроєм називатимемо пристрій, на якому можна промоделювати роботу машини Тьюринга.
Машини Тьюринга дозволяють обчислювати тільки рекурсивні функції.
Частково рекурсивні функції – визначена не при всіх значеннях аргумента.
Теза Тьюринга: Клас функцій, частково обчислюваних за Тьюрингом, збігається з класом частково рекурсивних функцій.
Теза Чорча: клас частково рекурсивних функцій збігається з класом частково обчислюваних функцій.
Теза Чорча еквівалентна тезі Тьюринга.
Моделі РАМ і РАСП
Машина Тьюринга дуже незручна для програмування через послідовний доступ до комірок пам’яті (стрічка), неструктурованість записів на стрічці (потрібно використовувати розподільники), відсутні основні арифметичні операції та ін.
Модель РАМ – довільний доступ до пам’яті, одна стрічка – для читання, друга – для запису.
РАСП – програма перебуває в регістрах і може сама себе змінювати.
Під складністю алгоритму розуміється часова оцінка його роботи або ємність необхідної пам’яті.
Апріорний аналіз алгоритму – теоретично, тестування – практична перевірка.