37. Дерево прийняття рішень

Кореневі дерева можна застос. для розв‘яз. рішешень. Для цього використ. дерево прийняття рішень. В такому дереві кожна внутрішня вершина V перевір. умовою. Прийняття рішення за допомогою такого дерева полягає у побуд. Простого шляху від кореня вершини до листка. Знач. умови задає ребро яке буду додано в шлях після верш. Кінцева вершина буде відповід. прийняттям рішень.

38. Бектрекінг

Пошук з поверненням — загальний алгоритм для знаходження всіх (або деяких) розв'язків деякої обчислювальної задачі, який покроково будує кандидатів на розв'язок, і відкидає кожного неповного кандидата С («вертається») як тільки визначає, що С не може буди доповненим до вірного розв'язку.

39. Каркаси

Каркасом або з‘єдн. деревом графа називається його підграф якийявляє собою дерево та містить всі вершини графа. Нехай граф А має Н вершин та М ребер. Число &(А) = м–n+1 назив. цикломатичним числом графа. Воно являється числовою характ. зв‘язн. графа.

Для дерева &(G) = 0. Алгоритм який полягає у вилученні ребер із простих циклів неефективний для дії ПК реалізацій. А ефективний буде побудування каркаса, тобто послідовний добір ребер у каркас.

40. Автомати

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

Автомат – це схематизований алгоритм.

Використовуючи автомати можна моделювати багато машин, включаючи компоненти ПК.

Вхідну стрічку можна розглядати як лінійну послідовність клітинок кожна з яких містить точно один вхідний символ зі скінченною вхідною алфавіту.

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

Автомат який ніколи не переміщує голівку вліво назив одностороннім.

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

Память автомата – це структура в якій записуються, зберігаються і зчитуються додаткові дані, що використовуються автоматом при роботі.

Керуючий пристрій складається зі скінченною множиною станів.

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

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