Бінарна алгебраїчна операція
Химия

Математична логіка та теорія алгоритмів


Математична логіка та теорія алгоритмів

Завантажити реферат: Математична логіка та теорія алгоритмів

Зміст реферату

1. Постановка задачі.
2. Побудова моделі.
3. Опис алгоритму
4. Доказ правильності алгоритму
5. Блок-схема алгоритму
6. Опис змінних та програма
7. Розрахунок обчислювальної складності
Тестування
Список літератури

1. Постановка задачі

Перерахувати всі способи розміщення n ферзей на шахівниці n на n, при яких вони не б’ють один одного

2. Побудова моделі

Вочевидь, кожної з n горизонталей має стояти по ферзю. Будемо називати k-позицією (для k = 0, 1,…,n) довільне розміщення k ферзей на k нижніх горизонталях (ферзі можуть бити один одного). Намалюємо «дерево позицій»: його коренем буде єдина 0-позиція, а з кожної k-позиції виходить n стрілок вгору (k+1)-позиції. Ці n позицій відрізняються положенням ферзя на (k+1)-ой горизонталі. Вважатимемо, що розташування їх на малюнку відповідає положенню цього ферзя: лівіше та позиція, в якій ферзь розташований лівіше

Дерево позицій для n = 2

Дане дерево представлене тільки для наочності та простоти уявлення для n=2

Серед позицій цього дерева нам треба відібрати ті n-позиції, у яких ферзі не б’ють одна одну. Програма «обходитиме дерево» і шукатиме їх. Щоб не робити зайвої роботи, зауважимо ось що: якщо в якійсь k-позиції ферзі б’ють один одного, то ставити подальші ферзи немає сенсу. Тому, виявивши це, ми припинятимемо побудову дерева в цьому напрямку

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

3. Опис алгоритму

Розіб’ємо завдання на дві частини: (1) обхід довільного дерева та (2) реалізацію дерева допустимих позицій

Сформулюємо завдання обходу довільного дерева. Вважатимемо, що у нас є Робот, який у кожен момент знаходиться в одній з вершин дерева. Він уміє виконувати команди:

вгору_ наліво (йти по самій лівій з стрілок, що виходять вгору)

праворуч (перейти в сусідню праворуч вершину)

вниз (спуститися вниз на один рівень)

вгору_ліворуч

праворуч

вниз

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

Будемо вважати, що робота має команду «обробити» і що його завдання — обробити все листя (вершини, з яких немає стрілок вгору, тобто де умова «є_зверху» хибна). Для нашого шахового завдання команді обробити відповідатиме перевірка та друк позиції ферзей

Доказ правильності програми, що наводиться далі, використовує такі визначення. Нехай фіксоване становище Робота в одній із вершин дерева. Тоді все листя дерева розбивається на три категорії: над Роботом, ліворуч Робота і правіше Робота. (Шлях з кореня в лист може проходити через вершину з Роботом, згортати вліво, не доходячи до неї і згортати вправо, не доходячи до неї.) Через (ОЛ) позначимо умову «оброблено все листя лівіше Робота», а через (ОЛН) — умова «оброблено все листя лівіше і над Роботом»

Залишилося скористатися такими властивостями команд Робота (зверху записані умови, в яких виконується команда, знизу — твердження про результат виконання):

{ОЛ, немає_зверху} обробити {ОЛН}

{ОЛ} вгору_наліво {ОЛ}

{є_право, ОЛН} праворуч {ОЛ}

{не є_право, ОЛН} вниз{ОЛН}

Тепер розв’яжемо завдання про обхід дерева, якщо ми хочемо, щоб оброблялися всі вершини (не тільки листя)

Рішення. Нехай x – певна вершина. Тоді будь-яка вершина y належить до однієї із чотирьох категорій. Розглянемо шлях із кореня у y. Він може:

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

Під «оброблено нижче і лівіше» розумітимемо «нижче оброблено по разу, зліва оброблено повністю (листя по разу, решта по два)». Під «оброблено нижче, ліворуч і над» будемо розуміти «нижче оброблено по разу, ліворуч і над — повністю»

4. Доказ правильності алгоритму

Доведемо, що наведена програма завершує роботу (на будь-якому кінцевому дереві)

Доказ . Процедура вверх_налево завершує роботу (висота робота не може збільшуватися нескінченно). Якщо програма працює нескінченно, то оскільки листя не обробляються повторно, починаючи з деякого моменту жоден лист не обробляється. А це можливо тільки якщо Робот весь час спускається вниз. Протиріччя

5. Блок-схема алгоритму

Опис змінних та програма

Тепер реалізуємо операції із деревом позицій. Позицію представлятимемо за допомогою змінної k: 0..n (число ферзей) та масиву c: array
[1..n] of 1..n (c [i] — координати ферзя на І-ій горизонталі; при i > k значення c [i] ролі не грає). Передбачається, що всі позиції допустимі (якщо прибрати верхнього ферзя, інші не б’ють одна одну)

6. Розрахунок обчислювальної складності

Ємнісна складність:

У програмі використовується одномірний масив розмірності n, тому обсяг входу та обсяг виходу збігаються і дорівнюють n. Кількість премних дорівнює 3(i,b,k) + 1(const n), тобто. обсяг проміжних даних дорівнює 4

З(n)=n+4

Тимчасова складність:

Якщо розглядати обробку кожного листа, без перевірки на шляху до нього, то тимчасова складність T(n) = n 0 +n 1 +n 2 +n 3 +…+nn

Але якщо кожна вершина перевіряється, тимчасова складність T(n) = o(n 0 +n 1 +n 2 +n 3 +…+nn ). І це тим вірніше, що більше n. Цей висновок отримано на основі наведених нижче статистичних даних:

1

2

3

4

5

6

7

Загальна кількість листя

2

7

40

341

3906

55987

960800

Кількість вершин побудованого дерева.

2

3

4

17

54

153

552

Час побудови (сек)

<0.01

<0.01

<0.01

<0.01

<0.01

<0.01

<0.01

8

9

10

11

12

13

Загальна кількість листя

Кількість вершин побудованого дерева.

2057

8394

35539

166926

856189

4674890

Час побудови (сек)

<0.01

0.21

1.20

6.48

37.12

231.29

7. Тестування

Побудована за описаним алгоритмом програма за різних n видає такі дані:

n=4

<1,2><2,4><3,1><4,3>

<1,3><2,1><3,4><4,2>

Тобто. кількість розстановок дорівнює 2. Нижче наведено таблицю залежно від n кількості рішень (R)

n =

1

2

3

4

5

6

7

8

9

10

11

12

13

R=

1

0

0

2

10

4

40

92

352

724

2680

14200

73712

Список літератури

  1. Кузнєцов О.П. Адельсон-Вельський Г.М. Дискретна математика інженера. — М.: Вища школа, 1988.
  2. Євстігнєєв В.А. Застосування теорії графів у програмуванні. — М.: Наука, 1984.
  3. Основний алгоритм знаходився на BBS “Master of Univercity” у файлі shen.rar у файловій області “Bardak” (тел. 43-27-03; час роботи 21.00 – 7.00; FTN адреса – 2:5090/58).

© Реферат плюс



Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *