ене пропозицію включається до групи і переходимо до п.V9. p> (Vк) Кінець.
5. Порівняльний аналіз формальних алгоритмів докази по Вонг і методу пропорційної резолюції
Для порівняльної оцінки логічної складності алгоритмів пропонується використовувати кількісну міру у вигляді повної ентропії (алгоритмічної міри кількості інформації з Колмагороу) двійковій послідовності
I A (k, s) = n * H (k, s) (1)
де H (k, s) = - (log + log + + log) (2)
або H (k, s) = - (log + 2 * log) (3) - загальне число входів безумовних і умовних операторів
змістовного алгоритму (граф - схема)
k - число входів безумовних операторів
s1 - число В«одиничнихВ» виходів умовних операторів
s0 - число В«нульовихВ» виходів умовних операторів
s - число умовних операторів (s = s1 = s0)
У формулі (1) IK (k, s) = - n (log), біт - частка логічної складності алгоритму по безумовним операторам
IS (k, s) = - n (2 * log), біт - частка логічної складності алгоритму по умовних операторам.
Формула (1) являє собою абсолютну логічну складність алгоритму, виміряну в двійкових одиницях (бітах).
Для порівняльної оцінки складності двох альтернативних алгоритмів можна використовувати формулу
a = (4)
де I (k, s) Ві I (k, s).
Чисельне значення a дозволяє прийняти рішення про вибір алгоритму для реалізації програми:
алгоритм, який характеризується меншим значенням повної ентропії I (k, s) приймається для написання робочої програми.
Висновок
У цій роботі були розглянуті різні методи доказів теорем числення висловів, це аналітичні (прямий доказ істинності теорем і доказ істинності теорем від протилежного) і формальні (доведення теорем методом Вонга і доказ теорем методом пропозіціональной резолюції). До кожного з методів давалися словесні (змістовні) алгоритми, блок-схема, за алгоритмом, а також був проведений порівняльний аналіз обох методів. При розробці робочої програми я зіткнувся з проблемою вибору алгоритму, тому що необхідно було вибрати найбільш ефективний з двох алгоритмів (алгоритм Вонга або алгоритм методу пропозіціональной резолюції). Але, провівши порівняльний аналіз алгоритмів, я прийшов до висновку, що, найбільш ефективним методом для написання програми є метод резолюції. p align="justify"> Для методу пропозіціональной резолюції наводиться програма і результати виконання програми для курсового завдання.
У ході виконання курсової роботи я отримав практичний досвід і вивчив алго...
