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

Математическая логика и теория алгоритмовСодержание. 1. Постановказадачи. 2. Построениемодели. 3. Описаниеалгоритма4. Доказательствоправильности алгоритма 5. Блок-схемаалгоритма6. Описаниепеременных и программа7. Расч твычислительной сложности8. Тестирование9. Перечислитьвсе способы расстановки n ферзей на шахматной

доске n на n, при которых они небьют друг друга. Построение модели. Очевидно, на каждой из nгоризонталей должно стоять по ферзю. Будем называть k-позицией для k 0, 1 n произвольную расстановку k ферзей на k нижних горизонталях ферзимогут бить друг друга . Нарисуем дерево позиций его корнем будетединственная 0-позиция, а из каждой k-позиции выходит n стрелок вверх в k 1 -позиции. Эти n позиций отличаются положением ферзя на k 1 -ой горизонтали.

Будем считать, что расположение их на рисункесоответствует положению этого ферзя левее та позиция, в которой ферзьрасположен левее.Дерево позиций для n 2Данное дерево представлено только для наглядности ипростоты представления для n 2.Среди позиций этого дерева намнадо отобрать те n-позиции, в которых ферзи не бьют друг друга. Программа будет обходить дерево и искать их.Чтобы не делать лишней работы, заметим вот что если в какой-то k-позиции ферзибьют друг друга, то ставить

дальнейших ферзей смысла нет. Поэтому, обнаруживэто, мы будем прекращать построение дерева в этом направлении.Точнее, назовем k-позициюдопустимой, если после удаления верхнего ферзя оставшиеся не бьют друг друга.Наша программа будет рассматривать только допустимые позиции. Описание алгоритма.Разобьемзадачу на две части 1 обход произвольного дерева и 2 реализацию деревадопустимых позиций.Сформулируем задачуобхода произвольного дерева.

Будем считать, что у нас имеется Робот, который вкаждый момент находится в одной из вершин дерева. Он умеет выполнять команды вверх налево идти по самойлевой из выходящих вверх стрелок вправо перейти в соседнюю справа вершину вниз спуститься вниз на один уровень вверх налевовправовнизи проверки, соответствующиевозможности выполнить каждую из команд, называемые есть сверху , есть справа , есть снизу последняя истинна всюду, кроме корня . Обратитевнимание, что команда вправо позволяет перейти лишь к родномубрату , но не к

двоюродному .Будем считать, что у Робота естькоманда обработать и что его задача - обработать все листья вершины, из которых нет стрелок вверх, то есть где условие есть сверху ложно . Для нашей шахматной задачи команде обработать будет соответствовать проверка ипечать позиции ферзей.Доказательство правильностиприводимой далее программы использует такие определения. Пусть фиксированоположение Робота в одной из вершин дерева.

Тогда все листья дерева разбиваютсяна три категории над Роботом, левееРобота и правее Робота. Путь из корня в лист может проходить через вершину сРоботом, сворачивать влево, не доходя донее и сворачивать вправо, не доходя до нее. Через ОЛ обозначим условие обработаны все листья левее Робота , а через ОЛН - условие обработаны все листья левее и над

Роботом .Нам понадобится такая процедура procedureвверх до упора и обработать дано ОЛ ,надо ОЛН begin инвариант ОЛ whileесть сверху do begin вверх налево end ОЛ, Робот влисте обработать ОЛН end Основной алгоритм дано Робот в корне, листья не обработанынадо Робот в корне, листья обработаны ОЛ вверх до упора и обработать инвариант ОЛН while есть снизуdo begin if есть справаthen begin

ОЛН, есть справа вправо ОЛ вверх до упора и обработать end else begin ОЛН, неесть справа, есть снизу вниз end end ОЛН, Робот вкорне gt все листья обработаны Осталось воспользоватьсяследующими свойствами команд Робота сверху записаны условия, в которыхвыполняется команда, снизу - утверждения о результате ее выполнения 1 ОЛ, не есть сверху обработать ОЛН 2 ОЛ вверх налево

ОЛ 3 есть справа, ОЛН вправо ОЛ 4 не есть справа, ОЛН вниз ОЛН Теперь решим задачу об обходедерева, если мы хотим, чтобы обрабатывались все вершины не только листья .Решение. Пусть x - некотораявершина. Тогда любая вершина y относитсяк одной из четырех категорий. Рассмотрим путь из корня в y. Он может а быть частью пути из корня в x y ниже x б свернуть налево с пути в x yлевее x в пройти через x y над x г свернуть направо с пути в x y правее x

В частности, сама вершина xотносится к категории в . Условия теперь будут такими ОНЛ обработаны все вершиныниже и левее ОНЛН обработаны все вершиныниже, левее и над.Вот как будет выглядетьпрограмма procedureвверх до упора и обработать дано ОНЛ ,надо ОНЛН begin инвариант ОНЛ whileесть сверху do begin обработать вверх налево end ОНЛ, Робот влисте обработать ОНЛН end Основной алгоритм дано

Робот вкорне, ничего не обработано надо Робот вкорне, все вершины обработаны ОНЛ вверх до упора и обработать инвариант ОНЛН while есть снизуdo begin if есть справаthen begin ОНЛН, есть справа вправо ОНЛ вверх до упора и обработать end else begin ОЛН, неесть справа, есть снизу вниз end end ОНЛН, Робот вкорне gt все вершины обработаны Приведенная толькочто программа обрабатывает вершину до того, как обработан любой из ее потомков.

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

ОНЛ ,надо ОНЛН begin инвариант ОНЛ whileесть сверху do begin обработать вверх налево end ОНЛ, Робот влисте обработать ОНЛН end Основной алгоритм дано Робот вкорне, ничего не обработано надо Робот вкорне, все вершины обработаны ОНЛ вверх до упора и обработать инвариант ОНЛН while есть снизуdo begin if есть справаthen begin ОНЛН, есть справа вправо ОНЛ вверх до упора и обработать end else begin

ОЛН, неесть справа, есть снизу вниз обработать end end ОНЛН, Робот вкорне gt все вершины обработаны полностью Доказательство правильностиалгоритма.Докажем, что приведенная программазавершает работу на любом конечном дереве .Доказательство. Процедура вверх налевозавершает работу высота Робота не можетувеличиваться бесконечно . Если программа работает бесконечно, то, посколькулистья не

обрабатываются повторно, начиная с некоторого момента ни один лист необрабатывается. А это возможно, толькоесли Робот все время спускается вниз. Противоречие. Блок-схема алгоритма. Описание переменных и программа.Теперь реализуем операции сдеревом позиций. Позицию будем представлять с помощью переменной k 0 n число ферзей и массива c array 1 n of1 n c i - координаты ферзя на i-ой горизонтали при i gt k значение c

i роли не играет . Предполагается, что все позиции допустимы если убратьверхнего ферзя, остальные не бьют друг друга . program queens const n var k 0 n c array 1 n of 1 n procedurebegin work начать работу begin k 0 end functiondanger boolean верхний ферзь под боем var b boolean i integer begin if k lt 1then begin danger false end elsebegin b false i 1 b lt gt верхний ферзь под боем ферзей с номерами lt i while i lt gt k do begin b bor c i c k вертикаль or abs c i -c k abs i-k диагональ i i 1 end danger b end

end functionis up boolean есть сверху begin is up k lt n and not danger end functionis right boolean есть справа begin is right k gt 0 and c k lt n end возможнаошибка при k 0 не определено c k functionis down boolean есть снизу begin is up k gt 0 end procedure up вверх налево begin k lt n k k 1 c k 1 end procedureright вправо begin k gt 0, c k lt n c k c k 1 end proceduredown вниз begin k gt 0 k k - 1 end procedurework обработать var i integer begin if k n and not danger then begin for i 1to n do

begin write lt , i, , , c i , gt end writeln end end procedure UW вверх до упора и обработать begin while is updo begin up end work end begin begin work UW while is downdo begin if is rightthen begin right UW end elsebegin down end end end.Расч т вычислительной сложности.Емкостная сложность В программе используетсяодномерный массив размерности n, поэтому объ м входа и объ

м выхода совпадают иравны n. Количество пременных равно 3 i,b,k 1 const n , т.е. объ мпромежуточных данных равен 4.С n n 4Временная сложность Еслирассматривать обработку каждого листа, без проверки на пути к нему, товременная сложность T n n0 n1 n2 n3 nn. Но вслучае, когда каждая вершина проверяется, временная сложность T n o n0 n1 n2 n3 nn .И это тем вернее, чем больше n.

Данный вывод получен на основе привед нных нижестатистических данных 1 2 3 4 5 6 7 Общее кол-во листьев 2 7 40 341 3906 55987 960800 Кол-во вершин построенного дерева. 2 3 4 17 54 153 552 Время построения сек lt 0.01 lt 0.01 lt 0.01 lt 0.01 lt 0.01 lt 0.01 lt 0.01 8 9 10 11 12 13 Общее кол-во листьев Кол-во вершин построенного дерева. 2057 8394 35539 166926 856189 4674890 Время построения сек lt 0.01 0.21 1.20 6.48 37.12 231.29

Тестирование.Построенная по описанному алгоритмупрограмма при различных n выда т следующие данные n 4Т.е. количество расстановокравно 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 Cписок литературы.1 КузнецовО.П. Адельсон-Вельский Г.М. Дискретная математика для инженера. М. Энергоатомиздат,

1988.2 ЕвстигнеевВ.А. Применение теории графов в программировании. М. Наука, 1984.3 Основнойалгоритм находился на BBS Master of Univercity в файле shen.rar в файловойобласти Bardak тел. 43-27-03 время работы 21.00 7.00 FTN адрес 2 5090 58 .