Реферат: Математическая логика и теория алгоритмов - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

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

Банк рефератов / Математика

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 141 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

10 Математическая логика и теория алгоритмов Содержание. 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; ОЛН , Робот в корне => все листья обработаны Осталось восп ользоваться следующими свойствами команд Робота (сверху записаны условия , в которых выпол няется команда , снизу - утверждения о результат е ее выполнения ): (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; ОНЛН , Робот в корне => все вершины обработаны Приведенная только что программа обрабатывает вершину до того , как обработ ан любой из ее потомков . Теперь изменим ее , чтоб ы каждая вершина , не являюща яся листом , обрабатывалась дважды : один раз до , а другой раз после всех своих п отомков . Листья по-прежнему обрабатываются по разу : Под "обработано ниже и левее " будем понимать "ниже обработано по разу , слева обработано полностью (листья по разу , остальные по два )". Под "обработано ниже , левее и над " будем понимать "ниже обработано по разу , левее и над - полностью ". Программа будет такой : 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писок литературы. 1) Кузнецов О.П . Адельсон-Вельский Г.М . Дискретная математика для инженера . – М .: Энергоатомиздат , 1988. 2) Евстигнеев В.А . Приме нение теории графов в программировании . – М .:Наука , 1984. 3) Основной алгоритм н аходился на BBS “ Master of Univercity” в файле shen.rar в файловой области “ Bardak ” (тел . 43-27-03; время работы 21.00 – 7.00; FTN адрес – 2:5090/58).
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Решил вставать до 8. Сегодня, например, встал в 7:92.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по математике "Математическая логика и теория алгоритмов", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru