рефераты

Рефераты

рефераты   Главная
рефераты   Краткое содержание
      произведений
рефераты   Архитектура
рефераты   Астрономия
рефераты   Банковское дело
      и кредитование
рефераты   Безопасность
      жизнедеятельности
рефераты   Биографии
рефераты   Биология
рефераты   Биржевое дело
рефераты   Бухгалтерия и аудит
рефераты   Военное дело
рефераты   География
рефераты   Геодезия
рефераты   Геология
рефераты   Гражданская оборона
рефераты   Животные
рефераты   Здоровье
рефераты   Земельное право
рефераты   Иностранные языки
      лингвистика
рефераты   Искусство
рефераты   Историческая личность
рефераты   История
рефераты   История отечественного
      государства и права
рефераты   История политичиских
      учений
рефераты   История техники
рефераты   Компьютерные сети
рефераты   Компьютеры ЭВМ
рефераты   Криминалистика и
      криминология
рефераты   Культурология
рефераты   Литература
рефераты   Литература языковедение
рефераты   Маркетинг товароведение
      реклама
рефераты   Математика
рефераты   Материаловедение
рефераты   Медицина
рефераты   Медицина здоровье отдых
рефераты   Менеджмент (теория
      управления и организации)
рефераты   Металлургия
рефераты   Москвоведение
рефераты   Музыка
рефераты   Наука и техника
рефераты   Нотариат
рефераты   Общениеэтика семья брак
рефераты   Педагогика
рефераты   Право
рефераты   Программирование
      базы данных
рефераты   Программное обеспечение
рефераты   Промышленность
      сельское хозяйство
рефераты   Психология
рефераты   Радиоэлектроника
      компьютеры
      и перифирийные устройства
рефераты   Реклама
рефераты   Религия
рефераты   Сексология
рефераты   Социология
рефераты   Теория государства и права
рефераты   Технология
рефераты   Физика
рефераты   Физкультура и спорт
рефераты   Философия
рефераты   Финансовое право
рефераты   Химия - рефераты
рефераты   Хозяйственное право
рефераты   Ценный бумаги
рефераты   Экологическое право
рефераты   Экология
рефераты   Экономика
рефераты   Экономика
      предпринимательство
рефераты   Юридическая психология

 
 
 

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


Математическая логика и теория алгоритмов
Содержание.
Постановка задачи.
Построение модели.
Описание алгоритма
Доказательство правильности алгоритма
Блок-схема алгоритма
Описание переменных и программа
Расчёт вычислительной сложности
Тестирование
Список литературы
Постановка задачи.
Перечислить все способы расстановки 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; {ОЛН, Робот в корне => все листья обработаны}
Осталось воспользоваться следующими свойствами команд Робота (сверху записаны условия, в которых выполняется команда, снизу - утверждения о результате ее выполнения):
{ОЛ, не есть_сверху} обработать {ОЛН}
{ОЛ} вверх_налево {ОЛ}
{есть_справа, ОЛН} вправо {ОЛ}
{не есть_справа, ОЛН} вниз{ОЛН}
Теперь решим задачу об обходе дерева, если мы хотим, чтобы обрабатывались все вершины (не только листья).
Решение. Пусть 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; {ОНЛН, Робот в корне => все вершины обработаны}
Приведенная только что программа обрабатывает вершину до того, как обработан любой из ее потомков. Теперь изменим ее, чтобы каждая вершина, не являющаяся листом, обрабатывалась дважды: один раз до, а другой раз после всех своих потомков. Листья по-прежнему обрабатываются по разу:
Под "обработано ниже и левее" будем понимать "ниже обработано по разу, слева обработано полностью (листья по разу, остальные по два)". Под "обработано ниже, левее и над" будем понимать "ниже обработано по разу, левее и над - полностью".
Программа будет такой:
procedure вверх_до_упора_и_обработать {дано: (ОНЛ), надо: (ОНЛН)} begin {инвариант: ОНЛ} while есть_сверху do begin обработать вверх_налево end {ОНЛ, Робот в листе} обработать; {ОНЛН} end;
Основной алгоритм: дано: Робот в корне, ничего не обработано надо: Робот в корне, все вершины обработаны {ОНЛ} вверх_до_упора_и_обработать {инвариант: ОНЛН} while есть_снизу do begin if есть_справа then begin {ОНЛН, есть справа} вправо; {ОНЛ} вверх_до_упора_и_обработать; end else begin {ОЛН, не есть_справа, есть_снизу} вниз; обработать; end; end; {ОНЛН, Робот в корне => все вершины обработаны полностью}
Доказательство правильности алгоритма.
Докажем
, что приведенная программа завершает работу (на любом конечном дереве).
Доказательство
. Процедура вверх_налево завершает работу (высота Робота не может увеличиваться бесконечно). Если программа работает бесконечно, то, поскольку листья не обрабатываются повторно, начиная с некоторого момента ни один лист не обрабатывается. А это возможно, только если Робот все время спускается вниз. Противоречие.
Блок-схема алгоритма.
Описание переменных и программа.
Теперь реализуем операции с деревом позиций. Позицию будем представлять с помощью переменной k: 0..n (число ферзей) и массива c: array [1..n] of 1..n (c [i] - координаты ферзя на i-ой горизонтали; при i > k значение c [i] роли не играет). Предполагается, что все позиции допустимы (если убрать верхнего ферзя, остальные не бьют друг друга).
program queens; const n = ...; var k: 0..n; c: array [1..n] of 1..n; procedure begin_work; {начать работу} begin k := 0; end; function danger: boolean; {верхний ферзь под боем} var b: boolean; i: integer; begin if k <= 1 then begin danger := false; end else begin b := false; i := 1; {b <=> верхний ферзь под боем ферзей с номерами < i} while i <> k do begin b := b or (c[i]=c[k]) {вертикаль} or (abs(c[i]-c[k])=abs(i-k)); {диагональ} i := i+ 1; end; danger := b; end; end; function is_up: boolean {есть_сверху} begin is_up := (k < n) and not danger; end; function is_right: boolean {есть_справа} begin is_right := (k > 0) and (c[k] < n); end; {возможна ошибка: при k=0 не определено c[k]} function is_down: boolean {есть_снизу} begin is_up := (k > 0); end; procedure up; {вверх_налево} begin {k < n} k := k + 1; c [k] := 1; end; procedure right; {вправо} begin {k > 0, c[k] < n} c [k] := c [k] + 1; end; procedure down; {вниз} begin {k > 0} k := k - 1; end; procedure work; {обработать} var i: integer; begin if (k = n) and not danger then begin for i := 1 to n do begin write ('<', i, ',' , c[i], '> '); end; writeln; end; end; procedure UW; {вверх_до_упора_и_обработать} begin while is_up do begin up; end work; end; begin begin_work; UW; while is_down do begin if is_right then begin right; UW; end else begin down; end; end; end.
Расчёт вычислительной сложности.
Емкостная сложность:
В программе используется одномерный массив размерности n, поэтому объём входа и объём выхода совпадают и равны n. Количество пременных равно 3(i,b,k) + 1(const n), т.е. объём промежуточных данных равен 4.
С(n)=n+4
Временная сложность:
Если рассматривать обработку каждого листа, без проверки на пути к нему, то временная сложность T(n) = n
0
+n
1
+n
2
+n
3
+…+n
n .
Но в случае, когда каждая вершина проверяется, временная сложность T(n) = o(n
0
+n
1
+n
2
+n
3
+…+n
n
). И это тем вернее, чем больше 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
Тестирование.
Построенная по описанному алгоритму программа при различных 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
Cписок литературы.
Кузнецов О.П. Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.
Евстигнеев В.А. Применение теории графов в программировании. – М.:Наука, 1984.
Основной алгоритм находился на BBS “Master of Univercity” в файле shen.rar в файловой области “Bardak” (тел. 43-27-03; время работы 21.00 – 7.00; FTN адрес – 2:5090/58).
Применение компьютеров для доказательств теорем математической логики. Реферат математика на шахматной доске Красноярск Россия Красноярске. Реферат про тафтологию по теории алгоритмов и матиматической логике. Реферат по дискретной математике на тему математическая логика. Реферат на тему разработка математической модели в виде графов. Математическая логика и теория алгоритмов решенные задачи. Математическая логика и теория алгоритмов темы рефератов. Реферат об алгоритмах в элементах математической логики. Листьев Теория вероятностей и математическая статистика. Реферат на тему существование алгоритмов в математике. Реферат на тему основы теории информации и алгоритмов. Реферат математическая логика и теория алгоритмов. Полная логическая характеристика понятия адвокат. Полная логическая характеристика хороший адвокат. Математическая логика и теория алгоритмов задачи.

© 2011 Рефераты