AOP_Tom1 (1021736), страница 153
Текст из файла (страница 153)
1. 1-3). 9. (а) Да. (Ь) Да, если рассматривается биологическое отцовство (или материнство), и нет, если допускается юридическое отцовство (или материнство) (когда, например, дочь может выйти замуж за своего отца, совсем как в песне "1'гн Му Окп Сга2пра"), (с) Нет (-1 < 1 и 1 ч — 1). (Й) Следует надеяться, что это так, ибо в противном случае возможно существование циклической цепочки доказательств. (е) 1 с 3 и 3 < 1. (1) Это утверждение не однозначно.
Если предположить, что вызываемые у подпрограммы зависят от подпрограмлб которые вызвали у, то люжно прийти к выводу о том, что условие транзитивности не всегда выполняется. (Например, общая подпрограмма ввода-вывода может вызывать различные процедуры обработки для каждого имеющегося устройства ввода-вывода, но не все эти процедуры обработки обычно необходимы для функционирования какой-то одной программы. Эта проблема часто является причиной ошибок во многих системах автоматического программирования.) 10. Для ()) существует три случая: т = у; х с у и у = 2; х с у и у с 2.
А для (н) — два случая: х = у; х ,"4 у. Решение очевидно для каждого из них, как и для (ш). 11. "Перемножьте" приведенные ниже комбинации, которые в итоге дадут 52 решения: 13749(25 + 52)85 + (1379 + 1397 + 1937 + 9137)(4258 + 4528 + 2458 + 5428 -~- 2548 + 5248 + 2584+ 5284)б+ (1392-'г 1932+ 1923+ 9123+ 9132+ 9213)7(458+ 548+ 584)б. 12. Рассмотрил2 еле,тующие примеры. (а) Расположим (в любом порядке) все множества из ?г элементов до всех множеств с Ь+ 1 элементами, 0 < 6 < и. (Ь) Представим подмножество последовательностью нулей и единиц, которая указывает, какой элемент находится в множестве.
Это позволит установить соответствие между всеми подмножествами и целыми числами от О до 2" — 1, которые записаны в двоичной системе счисления. Порядок соответствия и является топологической последовательностью. 13. Дж. Ша и Д. И. Кляйтман (Пгзсгеге Магй.
83 (1987), 271-278) доказали, что это количество не превышает П" („") " . Оно больше очевидной нижней границы П~ (")' = 2" ~ аой О 2" О 2 ~ + ~ Р на множитель 2 т~ы2, причем предполагается, что нижняя оценка ближе к истине. 14. Если а2 аэ... а„и Ьг62... ܄— две допустимые топологические сортировки, то предположим, что 7' — такое минимальное значение, при котором а, Р' Ь„тогда аь = Ь, и а, = Ьы для некоторого Ь,т > 7.
Теперь Ь, Я о, поскольку ?г > 7, а а, Я Ьм так как т > 7. Следовательно, (гг) не выполняется. И наоборот, если существует только одна топологическая сортировка а2 аг .. а„, условие а, "с а ~.1 должно выполняться для некоторого 1 < 7' < и, так как в противном случае а, и аг ы можно поменять местами. Исходя из вышесказанного н условия транзитивиости, получим (гг). Замечание. Приведенное ниже альтернативное доказательство подходит и к бесконечным множествам. (а) Каждое частичное упорядочение может быть расп2ирено до линейного упорядочения. Например, для некоторых двух элементов с отношениями хо тГ уо и уэ я то можно создать другое частичное упорядочение по правилу кк .С у, если х С хо и уо < у". Последнее упорядочение "включает" первое из двух упорядочений и то < уо.
Теперь для завершения доказательства применим обычным способом лемму Церна или трансфинитную индукцию, (Ь) Очевидно, что линейное упорядочение не может быть расширено до любого другого линейного упорядочения, (с) Частичное упорядочение, которое имеет несравнимые элементы тэ и уэ, как и в (а), может быть расширено до двух линейных упорядочений, в которых хо < Мо и уо < хо соответственно, а потому существует по крайней леере два линейных упорядочения. 16.
Если Я являетея конечным множеством, можно перечислить все отношения а < 6 дамного частичного упорядочения. Удаляя последовательно по одному все отношения, которые следуют из других, получим неприводиллое множество. Задача теперь заключается в том, чтобы доказать единственность такого множества независимо от порядка удаления избыточных отношений. Если существует два таких неизбыточных множества [Г и 1'', в которых отношение а < 6 присутствует в [7, но не в р, то существует Й+ 1 отношений а < сс м < сс < 6 в множестве р для некоторого Ь > 1.
Однако в таком случае из множества [Г можно вывести отношения а < с~ и сл с Ь без использования отношения а < Ь (так как 6 Я с~ и с~ Я а), поахал~у отношение а м Ь является избыточным в лсножестве [7. Такой результат не верен для бесконечмых множеств Я. Существует ме более одного неизбыточного мможестяа отношений. Наприл~ер, если множество 5 включает целые числа плюс элемент сю, а отношения и < и + 1 и и м оо определемы для всех и, то не существует ни одного нензбыточного множества отношений, которые характеризуют это частичное упорядочение. 16.
Пусть хр,хрл...хр„ — топологическая сортировка множества о. Тогда для строк и столбцов следует применить перестановку Р~рл...рл. 17. Если Ь на шаге Т4 увеличивается от 1 до и,то получим 1932745860. Если Ь на шаге Т4 улсемьшается от и до 1, как в программе Т, то получим 9123745860. 18.
Они связывают элементы списка в рассортированном порядке, ОЫМК[0] — первый, ОЫМК[ОЫМК[0]] — второй и т. д.; ОЫМК[последний] = О. 19. В некоторых случаях это может привести к ошибке. Например, если в очереди содержится только один элемент на шаге Т5, то модифицированный метод может установить Р = О (опустошая таким образом очередь), но другие элементы люгут быть помещены в очередь на шаге Тб. Следовательно, в предлагаемой модификации этого алгоритма на шаге Тб необходимо включить проверку условия Р = О. 20. Действительно, стек можно было бм использовать следующим образом. (Шаг Т7 исключается.) Т4.
Установить Т +- О. Для 1 < й < и, если СООМТ[6] равно нулю, выполнить следующие действия; установить БЫМК [6] +- Т, Т +- Ь. (БЫМК [й] = ОЫМК [6].) Тб. Вывести значение Т. Если Т = О, перейти к шагу ТБ, в противном случае установить М +- Й вЂ” 1, Р +- ТОР [Т] . Т е- Б1 1МК [Т] ТБ. То же, что и прежде, но перейти к шагу ТЬ, а не к шагу Т7. Когда СООМТ [КОС(Р) ] улсеньшится до нуля, установить Б(1МК [БОС(Р)] +- Т и Т +- БОС(Р) .
21. Повторяющиеся отношения могут лишь мемного замедлить выполнение алгоритма и увеличить размер выделяемого в пуле пространства. Отношение 7' < 7' будет рассматриваться как заллкмутая петля (или цикл) (т. е. на соответствующей схеме это будет выглядеть, как выходящая из квадратика направленная на него же стрелка), которая нарушает частичное упорядочение. 22, Для создания "отказоустойчивой" программы следует: (а) проверить, что 0 < и < некоторое ллаксимальное значение, (Ь) проверить, что для каждого отношения 7 < Й выполняются условия 0 < 7',Ь < и, (с) убедиться в толб что количество отношений не переполняет область пула. 23.
В конце шага Т5 добавьте ТОР[К] +- Л. (Затем всегда следует устанавливать ТОР Ш, ..., ТОР [и] для указания на все еще неотмененные отношения.) На шаге ТБ, если М > О, п>А>1 п>А>1 Верно ли, что ТОР Ы = О? печатать МООР ОЕТЕСТЕО 1М 1МРУТс и установить ЦПМК[?с] с- О для 1 < Й < и. Кроме того, необходимо добавить следуюп1ие шаги. Т9. Для 1 < А < и установить Р с- ТОР[?с], ТОР[А] +- 0 и выполнить шаг Т10 (Это позволит установить указатель ОПЕК[1] на один из предшественников объекта 1 для каждого еще невыведенного 1.) Затем перейти к шагу Т11. Т10.
Если Р Рс Л, установить ОПЕК [БОС (Р) 3 с — /с, Р +- МЕХТ(Р) и повторить этот шаг. Т11. Найти ?с с ЦПМК [А] Ф О. Т12. Установить ТОР[93 +- 1 и (с +- ОПЕК[А]. Теперь, если ТОРЫ ж О, повторить этот шаг. Т13. (Найдено начало петли.) Печатать значение )с, установить ТОР[А] с — О, А с- ЦПМКЫ и, если ТОРЫ = 1,повторить этот шаг. Т14. Напечатать значение )с (начвло и конец петли) и прекратить выполнение. (Замечание.
Петля распечатывается в обратном порядке; чтобы распечатать ее в прялюм порядке, алгоритм, подобный описанному в упр. 7, следует вставить между шагами Т12 и Т13.) $ 24. В код програлсмы следует вставить следующие три новые строки. 08а РНХМТЕН ЕЦУ 16 Ца БТБ МО бба БТХ Х, 1(ТОР) ТОР[Р] с в Л. Строки 74-75 следует заменить приведенными ниже строками. 74 162 ООМЕ 78 ОУТ ПМЕ1(РН1МТЕН) Печать сообщения о наличии петли. 7б ЕОб МО 77 БТХ Х,б(ЦПМК) ЦПМК[)с] +- О.
78 ОЕСВ 1 79 16Р с-2 80 ООб МО 81 Т9 102 Х,б(ТОР) Р +- ТОР[А]. 88 БТХ Х,б(ТОР) ТОР[?с] +- О. 88 122 Т9А Верно ли,что Р = Л? Ц Т10 Ю1 0,2(БУС) гП +- БУС(Р). 88 БТБ Х, 1(Ц11МК) ЦПМК [гП3 +- lс. 88 1.02 0,2(МЕХТ) Р +- МЕХТ(Р). 87 12Р Т10 Верно ли,что Р Рс Л? 88 Т9А ОЕС6 1 8У 16Р Т9 Уб Т11 1МСб 1 91 ООА Х,б(ЦПМК) 98 )АХ с-2 Найти такое А, для которого ЦПМК [А] ф О.
У8 Т12 БТб Х,б(ТОР) ТОР[)с] с- й. У4 106 Х,б(ЦПМК) )с+- ЦПМКЫ. 98 ).01 Х,б(ТОР) Уб 112 Т12 97 Т13 ЕМТА 0,6 98 СНАМ Преобразовать число А и символ, 99 1ВУБ *(РН1МТЕН) 100 БТХ ЧА(ЛЕ Печатать. 101 ОУТ 1.1МЕ2(РНХМТЕН) Остановиться, если ТОР [к) = 0 ТОР[И < — О, А+- Ц1.1МК[1с). 103 112 РОМЕ 103 БТК Х,б(ТОР) 104 006 Х.б(ЦПМК) 100 101 Х,б(ТОРУ 100 ЗНР Т13 107 ПМЕ1 АЕР 100Р Строка заголовка. 108 АЬР ОЕТЕС 100 А1.Р ТЕО 1 110 ААР М 1МР 111 А1.Р ОТ: 11е ПМЕ2 АЕР Последующие строки. 113 РАУЛЕ ЕЦО ПМЕ2+3 114 ОВ10 ПМЕ2+24 110 РОМЕ НЕТ Конец вычислений. 110 Х ЕМО ТОРБОКТ 1 Замечание. Если отношения 9 < 1 и 6 < 9 добавить к исходным данным (18), то эта программа наилет петлю и напечатает ее в виде 9, 6, 8, 5, 9.
26. Одно из решений может включать две следующие стадии. Стадия 1. (Таблица К используется, как последовательный стек, по мере того как применяются обозначения В = 1 или 2 для каждой используемой подпрограммы.) АО. Для 1 < 1 < М установить В(К [1) ) +- В(К [1) ) + 2, если В(К [1) ) < О. А1. Если М = О, перейти к стадии 2; в противном случае установить Р ь — Х[М) и уменьшить М на 1. А2. Если (В(Р) ( = 1, перейти к шагу А1; в противном случае установить Р +- Р + 1. АЗ. Если В(БОВ1(Р) ) < О, установить М +- М+ 1, В(3081(Р) ) С- В(БОВ1(Р) ) + 2, Х[М) +- БОВ1(Р) . Если 3082(Р) ф 0 и В(БОВ2(Р) ) < О, выполнить аналогичные действия с БОВ2(Р).
Перейти к шагу А2. $ Стадия Я, (Проход по таблице и перераспределение пал~яти.) В1. Установить Р +- Р1КБТ. В2. Если Р = Л, установить М + — М + 1, ВАЗЕ(100 (Х [М) ) ) +- М1 ОС, БОВИ ОС (Х [М) ) ) +- О и завершить выполнение алгоритма. ВЗ. Если В(Р) > О, установить М+-М+ 1, ВАЗЕ(100(Х[М) ) ) <-МАОС, БОВ(100(Х[М) )) +-Р, МЫ)С ь — МЬОС+ БРАСЕ(Р). В4. Установить Р +- ПМК(Р) и вернуться к шагу В2.
! 27. Читателю предлагается самостоятельно изучить приведенный ниже код. 1Н В БРАСЕ 11МК БОВ1 БОВ2 ВАЗЕ БОВ АО ЕЦО 0:1 ЕЦО 2:3 ЕЦО 4:б ЕЦО 2:3 ЕЦО 4:Б ЕЦО 0:3 ЕЦО 4:Б 102 М 122 В1 103 1.2 ьОА 0,3(В) 1АР ььЗ 1МСА 2 БТА 0,3(В) ВЕС 2 12Р 101 А1 112 002 ОЕС1 А2 ЕОА ВЕСА 1АК 1МС2 АЗ АОЗ СОА )АР ТМС1 1 1В 81 Х,1 1 0,2(1:1) 1 А1 1 0,2(БОВ1) 0,3(В) 9Р 1 1ИСА 2 В1 ЕМТ2 Г1НБТ БТА 0,3(В) 1ОА МЕСС БТЗ 1,1 )МР 1Г 9Н 103 0,2(БОВ2) ВЗ 101 0.2(В) 332 А2 )ХМР В4 10А 0,3(В) 1МС1 1 )АР А2 БТ2 1,1(БОВ) 1МС1 1 ° АРО 0,2(БРАСЕ) 1МСА 2 1В БТА К+1,1(ВАЗЕ) БТА 0,3(В) В4 102 0,2((.1ИК) БТЗ 1,1 В2 32МК ВЗ Л(Р А2 БТ2 Хэ1,1(БОВ) $ 28. Предложим здесь лишь несколько комментариев, имеющих отношение к "военной игре".
Пусть А — игрок с тремя фишками, которые расположены в узлах А13, а В— другой игрок. В этой игре А должен "захватить" В, но если В сможет дважды вызвать повторение одного и того же состояния, он выиграет. Однако для того, чтобы не хранить сведения обо всей предыстории игры в виде набора всех состояний, глелует изменить алгоритм. Отметим состояния 157 — 4, 789 — В и 359-б, в которых очередь следующего хода принадлежит игроку В, как "проигрышные" и применим предложенный алгоритм. Теперь основная выигрышная стратегия для игрока А заключается в перемещении только в проигрышные для В состояния.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
