Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте www.za4et.net.ru

Математика Математика

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

Коврик для запекания, силиконовый "Пекарь".
Коврик "Пекарь", сделанный из силикона, поможет Вам готовить вкусную и красивую выпечку. Благодаря материалу коврика, выпечка не
202 руб
Раздел: Коврики силиконовые для выпечки
Гуашь "Классика", 12 цветов.
Гуашевые краски изготавливаются на основе натуральных компонентов и высококачестсвенных пигментов с добавлением консервантов, не
170 руб
Раздел: 7 и более цветов
Фонарь садовый «Тюльпан».
Дачные фонари на солнечных батареях были сделаны с использованием технологии аккумулирования солнечной энергии. Уличные светильники для
106 руб
Раздел: Уличное освещение

Содержание. Постановка задачи. Построение модели. Описание алгоритма Доказательство правильности алгоритма Блок-схема алгоритма Описание переменных и программа Расчёт вычислительной сложности Тестирование Список литературы Постановка задачи. Перечислить все способы расстановки ферзей на шахматной доске на , при которых они не бьют друг друга. Построение модели. Очевидно, на каждой из горизонталей должно стоять по ферзю. Будем называть k-позицией (для k = 0, 1,., ) произвольную расстановку k ферзей на k нижних горизонталях (ферзи могут бить друг друга). Нарисуем "дерево позиций": его корнем будет единственная 0-позиция, а из каждой k-позиции выходит стрелок вверх в (k 1)-позиции. Эти позиций отличаются положением ферзя на (k 1)-ой горизонтали. Будем считать, что расположение их на рисунке соответствует положению этого ферзя: левее та позиция, в которой ферзь расположен левее. Дерево позиций для = 2 Данное дерево представлено только для наглядности и простоты представления для =2. Среди позиций этого дерева нам надо отобрать те -позиции, в которых ферзи не бьют друг друга. Программа будет "обходить дерево" и искать их. Чтобы не делать лишней работы, заметим вот что: если в какой-то k-позиции ферзи бьют друг друга, то ставить дальнейших ферзей смысла нет. Поэтому, обнаружив это, мы будем прекращать построение дерева в этом направлении. Точнее, назовем k-позицию допустимой, если после удаления верхнего ферзя оставшиеся не бьют друг друга. Наша программа будет рассматривать только допустимые позиции. Описание алгоритма. Разобьем задачу на две части: (1) обход произвольного дерева и (2) реализацию дерева допустимых позиций. Сформулируем задачу обхода произвольного дерева. Будем считать, что у нас имеется Робот, который в каждый момент находится в одной из вершин дерева. Он умеет выполнять команды: вверх налево (идти по самой левой из выходящих вверх стрелок) вправо (перейти в соседнюю справа вершину) вниз (спуститься вниз на один уровень) вверх налево вправо вниз и проверки, соответствующие возможности выполнить каждую из команд, называемые "есть сверху", "есть справа", "есть снизу" (последняя истинна всюду, кроме корня). Обратите внимание, что команда "вправо" позволяет перейти лишь к "родному брату", но не к "двоюродному". Будем считать, что у Робота есть команда "обработать" и что его задача - обработать все листья (вершины, из которых нет стрелок вверх, то есть где условие "есть сверху" ложно). Для нашей шахматной задачи команде обработать будет соответствовать проверка и печать позиции ферзей. Доказательство правильности приводимой далее программы использует такие определения. Пусть фиксировано положение Робота в одной из вершин дерева. Тогда все листья дерева разбиваются на три категории: над Роботом, левее Робота и правее Робота. (Путь из корня в лист может проходить через вершину с Роботом, сворачивать влево, не доходя до нее и сворачивать вправо, не доходя до нее.) Через (ОЛ) обозначим условие "обработаны все листья левее Робота", а через (ОЛН) - условие "обработаны все листья левее и над Роботом". Нам понадобится такая процедура: procedure вверх до упора и обработать {дано: (ОЛ), надо: (ОЛН)} begi {инвариант: ОЛ} while есть сверху do begi вверх налево e d {ОЛ, Робот в листе} обработать; {ОЛН} e d; Основной алгоритм: дано: Робот в корне, листья не обработаны надо: Робот в корне, листья обработаны {ОЛ} вверх до упора и обработать {инвариант: ОЛН} while есть снизу do begi if есть справа he begi {ОЛН, есть справа} вправо; {ОЛ} вверх до упора и обработать; e d else begi {ОЛН, не есть справа, есть снизу} вниз; e d; e d; {ОЛН, Робот в корне => все листья обработаны} Осталось воспользоваться следующими свойствами команд Робота (сверху записаны условия, в которых выполняется команда, снизу - утверждения о результате ее выполнения): {ОЛ, не есть сверху} обработать {ОЛН} {ОЛ} вверх налево {ОЛ} {есть справа, ОЛН} вправо {ОЛ} {не есть справа, ОЛН} вниз{ОЛН} Теперь решим задачу об обходе дерева, если мы хотим, чтобы обрабатывались все вершины (не только листья).

Решение. Пусть x - некоторая вершина. Тогда любая вершина y относится к одной из четырех категорий. Рассмотрим путь из корня в y. Он может: а) быть частью пути из корня в x (y ниже x); б) свернуть налево с пути в x (y левее x); в) пройти через x (y над x); г) свернуть направо с пути в x (y правее x); В частности, сама вершина x относится к категории в). Условия теперь будут такими: (ОНЛ) обработаны все вершины ниже и левее; (ОНЛН) обработаны все вершины ниже, левее и над. Вот как будет выглядеть программа: procedure вверх до упора и обработать {дано: (ОНЛ), надо: (ОНЛН)} begi {инвариант: ОНЛ} while есть сверху do begi обработать вверх налево e d {ОНЛ, Робот в листе} обработать; {ОНЛН} e d; Основной алгоритм: дано: Робот в корне, ничего не обработано надо: Робот в корне, все вершины обработаны {ОНЛ} вверх до упора и обработать {инвариант: ОНЛН} while есть снизу do begi if есть справа he begi {ОНЛН, есть справа} вправо; {ОНЛ} вверх до упора и обработать; e d else begi {ОЛН, не есть справа, есть снизу} вниз; e d; e d; {ОНЛН, Робот в корне => все вершины обработаны} Приведенная только что программа обрабатывает вершину до того, как обработан любой из ее потомков. Теперь изменим ее, чтобы каждая вершина, не являющаяся листом, обрабатывалась дважды: один раз до, а другой раз после всех своих потомков. Листья по-прежнему обрабатываются по разу: Под "обработано ниже и левее" будем понимать "ниже обработано по разу, слева обработано полностью (листья по разу, остальные по два)". Под "обработано ниже, левее и над" будем понимать "ниже обработано по разу, левее и над - полностью". Программа будет такой: procedure вверх до упора и обработать {дано: (ОНЛ), надо: (ОНЛН)} begi {инвариант: ОНЛ} while есть сверху do begi обработать вверх налево e d {ОНЛ, Робот в листе} обработать; {ОНЛН} e d; Основной алгоритм: дано: Робот в корне, ничего не обработано надо: Робот в корне, все вершины обработаны {ОНЛ} вверх до упора и обработать {инвариант: ОНЛН} while есть снизу do begi if есть справа he begi {ОНЛН, есть справа} вправо; {ОНЛ} вверх до упора и обработать; e d else begi {ОЛН, не есть справа, есть снизу} вниз; обработать; e d; e d; {ОНЛН, Робот в корне => все вершины обработаны полностью} Доказательство правильности алгоритма. Докажем, что приведенная программа завершает работу (на любом конечном дереве). Доказательство. Процедура вверх налево завершает работу (высота Робота не может увеличиваться бесконечно). Если программа работает бесконечно, то, поскольку листья не обрабатываются повторно, начиная с некоторого момента ни один лист не обрабатывается. А это возможно, только если Робот все время спускается вниз. Противоречие. Блок-схема алгоритма. Описание переменных и программа. Теперь реализуем операции с деревом позиций. Позицию будем представлять с помощью переменной k: 0. (число ферзей) и массива c: array - координаты ферзя на i-ой горизонтали; при i > k значение c роли не играет). Предполагается, что все позиции допустимы (если убрать верхнего ферзя, остальные не бьют друг друга). program quee s; co s = .; var k: 0. ; c: array of 1.

; procedure begi work; {начать работу} begi k := 0; e d; fu c io da ger: boolea ; {верхний ферзь под боем} var b: boolea ; i: i eger; begi if k &l ;= 1 he begi da ger := false; e d else begi b := false; i := 1; {b &l ;=> верхний ферзь под боем ферзей с номерами &l ; i} while i &l ;> k do begi b := b or (c)=abs(i-k)); {диагональ} i := i 1; e d; da ger := b; e d; e d; fu c io is up: boolea {есть сверху} begi is up := (k &l ; ) a d o da ger; e d; fu c io is righ : boolea {есть справа} begi is righ := (k > 0) a d (c &l ; ); e d; {возможна ошибка: при k=0 не определено c} fu c io is dow : boolea {есть снизу} begi is up := (k > 0); e d; procedure up; {вверх налево} begi {k &l ; } k := k 1; c := 1; e d; procedure righ ; {вправо} begi {k > 0, c 1; e d; procedure dow ; {вниз} begi {k > 0} k := k - 1; e d; procedure work; {обработать} var i: i eger; begi if (k = ) a d o da ger he begi for i := 1 o do begi wri e ('&l ;', i, ',' , c, '> '); e d; wri el ; e d; e d; procedure UW; {вверх до упора и обработать} begi while is up do begi up; e d work; e d; begi begi work; UW; while is dow do begi if is righ he begi righ ; UW; e d else begi dow ; e d; e d; e d. Расчёт вычислительной сложности. Емкостная сложность: В программе используется одномерный массив размерности , поэтому объём входа и объём выхода совпадают и равны . Количество пременных равно 3(i,b,k) 1(co s ), т.е. объём промежуточных данных равен 4. С( )= 4 Временная сложность: Если рассматривать обработку каждого листа, без проверки на пути к нему, то временная сложность ( ) = 0 1 2 3 . Но в случае, когда каждая вершина проверяется, временная сложность ( ) = o( 0 1 2 3 ). И это тем вернее, чем больше . Данный вывод получен на основе приведённых ниже статистических данных: 1 2 3 4 5 6 7 Общее кол-во листьев 2 7 40 341 3906 55987 960800 Кол-во вершин построенного дерева. 2 3 4 17 54 153 552 Время построения(сек) &l ;0.01 &l ;0.01 &l ;0.01 &l ;0.01 &l ;0.01 &l ;0.01 &l ;0.01   8 9 10 11 12 13 Общее кол-во листьев Кол-во вершин построенного дерева. 2057 8394 35539 166926 856189 4674890 Время построения(сек) &l ;0.01 0.21 1.20 6.48 37.12 231.29 Тестирование. Построенная по описанному алгоритму программа при различных выдаёт следующие данные: =4 &l ;1,2>&l ;2,4>&l ;3,1>&l ;4,3> &l ;1,3>&l ;2,1>&l ;3,4>&l ;4,2> Т.е. количество расстановок равно 2. Ниже приведена таблица зависимости от количества решений (R). = 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 “Mas er of U iverci y” в файле she .rar в файловой области “Bardak” (тел. 43-27-03; время работы 21.00 – 7.00; F адрес – 2:5090/58).

Читатель может опробовать себя в качестве перцептрона. 167 См. А.PМоль, Теория информации и эстетическое восприятие, изд-во «Мир», 1966. 168 См. А.PЧерч, Введение в математическую логику, т. 1, ИЛ, 1960. Введение. 169 См., например, М.PЛифшиц и Л.PРейнхарт, Кризис безобразия, изд-во «Искусство», 1968, стр. 2. 170 Русский перевод выпущен в 1934 г. изд-вом АН СССР. 171 Д.PБом, Квантовая теория, Физматгиз, 1961. 172 О святая простота! (лат.) 173 Заметим, что употребляемые здесь Лемом термины «прагматик», «прагматический» не следует смешивать ни с «прагматикой» в семиотике, ни с «прагматизмом» как философским направлением. Эти слова с греческим корнем удобны, и поэтому им приходится нести на себе большую нагрузку. 174 Б.PРассел, История западной философии, ИЛ, 1959, стр. 624-625. 175 Почти дословная формулировка дана, скажем, в книге W.PJamеs, Pragmatism, N.Y., 1963, стр. 98. 176 См. книгу В.PЛеви, Охота за мыслью, изд-во «Молодая гвардия», 1967. 177 Ф.PКрик, К расшифровке генетического кода, сб. «Живая клетка», ИЛ, 1962. 178 П.PА.PЖоголев, Н.PП.PТрифонов, Курс программирования, изд-во «Наука», 1967, стр. 352. 179 См., например, сб. «Вычислительные машины и мышление», изд-во «Мир», 1967, и М.PМ.PБотвинник, Алгоритм игры в шахматы, изд-во «Наука», 1968. 180 Op. cit, стр. 723-724. 181 Н.PП.PДубинин, Молекулярная генетика и действие излучения на наследственность, Атомиздат, 1963, стр. 160. 182 П.PФресс, Ж.PПиаже, Экспериментальная психология, изд-во «Прогресс», 1966. 183 М.PЕ.PЛобатев, Генетика, Изд. Ленингр. университета 1967. стр. 714 и сл.

1. Организация и организационная теория (по книге Дафта Р. "Организации")

2. Психология азартных игр

3. История азартных игр

4. Зависимость от азартных игр, гэмблинг-зависимость

5. Теория химического строения органических соединений. Электронная природа химических связей. Предпосылки теории строения. Теория химического строения. Изомерия

6. Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)
7. Теория игр и принятие решений
8. Теория графов. Методические указания по подготовке к контрольным работам по дисциплине «Дискретная математика»

9. Методичка для курсового проектирования по ПТЦА (прикладная теория цифровых автоматов)

10. Задачи и методы теории знания

11. Предмет экономической теории. Методы экономического анализа

12. Вычисление интеграла методом Ньютона-Котеса (теория и программа на Паскале)

13. Роль теории дифференциальных уравнений в современной математике и ее приложениях

14. Элементы дифференциального и интегрального исчисления в книге П. Я. Гамалеи "Вышняя теория морского искусства"

15. Возможности использования элементов теории вероятностей и статистики на уроках математики в начальной школе

16. Теория взаимодействий: общие закономерности взаимодействий участников соревнований в единоборствах и спортивных играх

Табурет "Плетенка" складной (большой).
Табурет, сделанный из пластмассы высокого качества. Ширина: 310 мм. Длина: 270 мм. Высота: 445 мм. Размеры сидения: длина - 230 мм, ширина
450 руб
Раздел: Стульчики
Шкатулка-фолиант "Книга Соломона", 21x13x5 см.
Шкатулка-фолиант выполнена в виде старой книги. Обложка шкатулки выполнена из кожзаменителя. Такая шкатулка послужит оригинальным, а
677 руб
Раздел: Шкатулки сувенирные
Кресло детское мягкое "Мяу-Мяу".
Кресло-игрушка "Мяу-Мяу" (Кошечка) - яркое и оригинальное кресло для детской комнаты, выполненное с использованием вышивальной
1442 руб
Раздел: Качели, кресла-качалки, шезлонги

17. Предмет и метод экономической теории

18. Использование теории игр в практике управления

19. Предмет, задачи и методы теории перевода

20. Шпаргалки з курсу Теорія і методіка журналістської творчості ГЕК

21. Метод АВИ в математической теории переноса вредных веществ в гетерогенных средах

22. Предмет и метод теории государства и права
23. Применение методов математической статистики и теории вероятностей в задачах теоретической лингвистики при анализе устной и звучащей речи на русском и английском языках
24. Теория игр

25. Математические методы в теории принятия решений

26. Теория игр. Корпоративные игры

27. Риск и теория игр

28. Теория игр

29. Формы и методы материального стимулирования труда в рыночных условиях. Теория и практический опыт

30. Предмет, объекты и методы политической психологии, соотношение теории и практики

31. Общие основы теории и методики спортивных игр

32. Методы познания экономической теории

Рюкзак детский, 30x24x10 см.
Рюкзак детский с вместительным основным отделением и дополнительными карманами. Лямки регулируются. Размер: 30х24х10 см. Материал:
419 руб
Раздел: Без наполнения
Ходунки-каталка "Happy Time ".
Ходунки-каталка Happy Time–специально разработаны для мылышей от 6 месяцев до 3 лет специально для того, чтобы помочь малышу сделать свои
2760 руб
Раздел: Ходунки
Лестница-стремянка, 4 ступени, стальная.
Нескользящие пластиковые коврики. Размер ступеньки: 30x20 см. Материал: сталь. Высота на уровне верхней ступени: 91 см. Количество
2071 руб
Раздел: Лестницы

33. Модель олигополии в контексте теории игр

34. Предмет, функції і методи економічної теорії

35. Практическое применение теории игр

36. Теории и гипотезы о Луне

37. Происхождение человека. Эволюция человека. Теории и гипотезы

38. Теории зарождения жизни на Земле
39. Теория Дарвина
40. Антропогенез: эволюционная теория происхождения человека

41. Бюджетный дефицит и государственный долг: теория проблемы и ее проявление в российской экономике

42. Шпаргалки для госэкзамена по теории государства и права

43. Теория социальной пассионарности Л. Н. Гумилева

44. Противоречивость "норманнской теории" происхождения государства у славян

45. Норманнская теория происхождения русской государственности ее апологеты и критики

46. Шпаргалка по общей теории права

47. Теория государства и права как наука и учебная дисциплина

48. Генезис (развитие) теории правового государства с древнейших времен и по наши дни

Электроминикар Tokids "Лев", цвет желтый.
Помимо того, что каталка может развивать моторные функции, научиться управлять своим собственным маленьким автомобильчиком, она также
1261 руб
Раздел: Электромобили
Карандаши цветные "Color'Peps", треугольный корпус, 36 цветов.
Карандаши цветные из американской липы, треугольные, ударопрочный грифель. В наборе: 36 цветов.
668 руб
Раздел: Более 24 цветов
Таблетки бесфосфатные для посудомоечных машин "Vaily", 30 штук.
Экологически безопасные для Вас и Вашего дома. Подходят для детской посуды. Специальная формула на основе органических компонентов. Не
430 руб
Раздел: Для посудомоечных машин

49. Теории государства и права (Шпаргалка)

50. Теория государства и права

51. Теория государства и права

52. Теория государства и права (Шпаргалка)

53. Теория разделения властей

54. Экзаменационные вопросы к государственному экзамену по теории государства и права
55. Определения (Теория государства и право)
56. Предмет теории государства и права

57. Шпоры к ГОСам (теория государства и права)

58. Шпаргалки по теории государства и права

59. Теория государства и права (шпаргалки для госэкзамена)

60. Теория государства и права (ТГП) в таблице

61. Теория государства и права (шпаргалки)

62. Теория и методика преподавания классического танца

63. Антропогенез: эволюционная теория происхождения человека

64. Проблемы теории культуры в отечественной философии (А. Ф. Лосев, М. К. Мамардашвили)

Рюкзак школьный "Pixie Crew" с силиконовой панелью для картинок (Тролли).
Повседневные вещи кажутся скучными и однотонными, а тебе хочется выглядеть стильно и быть не как все? "Pixie Crew" сделает твою
2082 руб
Раздел: Без наполнения
Копилка-раскраска "Сова в шляпе".
Набор для творчества. Копилка-раскраска. Пластиковая копилка легкая, приятная на ощупь, не бьется при падении и ее легко раскрашивать. В
324 руб
Раздел: Копилки
Набор кукол "Шарлотта Земляничка" (с одеждой).
Игровой набор "Шарлотта Земляничка" состоит из четырех мини-кукол высотой 8 см и массы полезных аксессуаров. Благодаря
1599 руб
Раздел: Шарлотта Земляничка

65. Шпоры по Поэтике или теории литературы

66. Теория и методика русского языка (экзаменационные билеты)

67. Норманнская теория происхождения государства у славян и ее роль в российской истории

68. Краткий конспект лекций по Теории тестирования аппаратных и программных средств

69. Теория системного управления

70. Постановка лабораторной работы по теории графов
71. Теория многозадачности и многопоточности
72. Лекции по теории проектирования баз данных (БД)

73. Компьютерный файлово-загрузочный полиморфный стелс-вирус ONEHALF 3544, особенности алгоритма и методы борьбы с ним

74. Теории управления

75. Терминология теории систем. Классификация систем. Закономерности систем

76. Лабораторная работа №5 по "Основам теории систем" (Транспортные задачи линейного программирования)

77. Лабораторная работа №3 по "Основам теории систем" (Теория двойственности в задачах линейного программирования)

78. Достаточно общая теория управления (Расовые доктрины в России: их возможности и целесообразность следования им в исторической перспективе)

79. Теория систем автоматического регулирования

80. Теория устойчивости

Магнитный держатель для ножей, 40 см.
Магнитный настенный держатель для ножей и других металлических кухонных инструментов. В комплекте шурупы для крепежа. Длина: 40 см.
335 руб
Раздел: Подставки для ножей
Похвальный лист, с пометкой "Министерство образования и науки Российской Федерации", 200 штук.
Формат: А4. Ориентация: горизонтальная. Бумага: мелованная матовая, плотностью 140 г/м2. В упаковке: 200 штук.
1024 руб
Раздел: Похвальные листы
Сменный фильтр "Барьер-6" (2 штуки).
Сменная кассета Барьер-6 «для жесткой воды» благодаря повышенному содержанию ионообменной смолы более эффективно снижает
461 руб
Раздел: Фильтры для воды

81. Теория вероятностей и случайных процессов

82. Теория графов и её применение

83. Методы обучения математике в 10 -11 класах

84. Теория статистики (Станкин)

85. Шпоры по теории вероятности

86. Теория неявных функций и ее приложения
87. Теория криминологии
88. Обратная сила закона. Теория и практика применения на примере преступлений против собственности

89. Суть теории биосферы В.И. Вернадского

90. Теории обучения в высшей школе

91. Психологические теории эмоций

92. Теория и методика воспитания (шпаргалка)

93. Концепция разделения властей: теория и опыт, история и современность

94. Теория олигархицации политических партий

95. Теория политики в работе Шапиро

96. Теории происхождения государства

Сменная кассета "Барьер 7", для воды с повышенным содержанием железа, для всех типов фильтров "Барьер", 2.
Кокосовый активированный уголь очищает от активного хлора, органических загрязнений и т.д. Обработка активированного угля серебром
551 руб
Раздел: Фильтры для воды
Дневник школьный "Розовая такса".
Формат: А5. Количество листов: 48. Внутренний блок: офсет 70 г/м2. Тип крепления: книжное (прошивка). Твердый переплет из искусственной
338 руб
Раздел: Для младших классов
Карандаши полимерные "Elios", 24 цвета.
Карандаши полимерные. В наборе: 24 цвета.
339 руб
Раздел: 13-24 цвета

97. Изучение теории и технологии выплавки шарикоподшипниковой стали марки ШХ4

98. Электромагнитная теория света

99. Теория Э.Фрома - опыт анализа и применения при наблюдении бытия


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.