Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 31
Текст из файла (страница 31)
Он показывает нам, что при определении множеств нужно быть очень осторожным. Иначе в своей математической системе мы можем получить внутреннее противоречие. Особое внимание следует обращать на то, чтобы множества не становились "слишком большими". ПРИМЕР 4.68. (Парадокс Рассела) Пусть 5 — множество всех множеств. Пусть Иг = (х: х ф х). Пустое множество принадлежит Иг, т.к, оно не принадлежит самому себе.
На самом деле, большинство известных нам множеств принадлежит И'. Однако, о не принадлежит И', т.к. о 6 о. А вот принадлежит ли множеству И' само И'? Если Иг 6 И', то оно принадлежит множеству всех множеств, которые сами себе не принадлежат. Следовательно, И' ф И'. Однако, если предположить, что Иг ф Иг, то И' принадлежит множеству всех множеств, которые не принадлежат сами себе. Но таким множеством является И', так что Иг 6 И'. В любом случае мы приходим к противоречию.
° УПРАЖНЕНИЯ 1. Пусть о = (1,2,3,4,5,6) и ф — инъективная функция из о в его булеан Р(Б), определенная следующим образом: ф(1) = (1,2,3,4), ф(2) = (1, 4), ф(3) = (2, 3, 4), ф(4) = О, РДЗДЕЛ 4.5. Мощность (продолжение) 183 ф(5) = (1,2,3,4,5,6), ф(6) = (1,3,6). Опишите множество, отсутствие отображения на которое гарантирует нам теорема 4.66. 2. Пусть Я = (1,2,3,4,5,6) и ф — инъективная функция из Я в его булеан Р(Я), определенная следующим образом: ф(1) = (2,3,4), ф(2) = (1,4), ф(3) = (2,4), ф(4) = И, ф(5) = (1,2,3,4,6), ф(6) = (1,3). Опишите множество, отсутствие отображения на которое гарантирует нам теорема 4.66.
3. Пусть о = (1,2,3,4,5,6) и ф — инъективная функция из Я в его булеан Р(Б), определенная следующим образом: ф(1) = (1,2,3,4), ф(2) = (1,2,4), ф(3) = (2,3,4,5), ф(4) = (4), ф(5) = (1,2,3,4,5,6), ф(6) = (1, 3, 6) . Опишите множество, отсутствие отображения на которое гарантирует нам теорема 4.66.
4. Докажите, что множество неотрицательных рациональных чисел счетно. 5. Докажите, что множество рациональных чисел счетно. 6. Пусть Я = (а+ 51: а, 5 е Я), где г = ~/ — Т. Докажите, что Я счетно. 7. Докажите, что множество всех полиномов 5-ой степени с целыми коэффициентами счетно. 8. Докажите, что множество всех полиномов степени не выше и с целыми коэффициентами является счетным. РАЗДЕЛ 5.1. Циклы и алгоритмы для матриц 185 Выполнив процесс для г = к, нужно положить г = 6+ 1 и повторять процесс до тех пор, пока не выполним его для г = и. Таким образом, для того чтобы вычислить сумму Я = );,", р(г), мы должны: Положить Я = О; Цикл погот1доп: Заменить значение 5 на Я+ р(г); Конец цикла.
В итоге получим значение Я, равное 2,',". , р(г). ПРИМЕР 5.1. Вычислить М = г". Положить М = 1; Цикл по г от 1 до и: Заменить значение М на М*г; Конец цикла. ПРИМЕР 5.2. Вычислить р(а), где р(х) — полинам, используя схему Горнера. Сначала заметим, что а4х + азх + азх~ + агх + ао = х(х(х(агх + аз) + аз) + аг) + ао . Используя этот факт, построим алгоритм вычисления Я = р(а), где р(х) = а„х" + а„гх" + +азх +агх+ао. Алгоритм имеет вид: Положить Я = а„; Цикл по гот 1 доп: Заменить Я на аЯ+ а„;; Конец цикла.
ОПРЕДЕЛЕНИЕ 5.3. Даны частичные упорядочения, <, и <з, упорядочение <з называется топологической сортировкой упорядочения <з, если «а является полным упорядочением, и всякий раз, когда а <г 6, тогда а <з 6. Опишем достаточно простой алгоритм нахождения топологической сортировки для упорядочения <г на множестве Я. Он состоит в следующем: мы находим произвольный минимальный элемент частичного упорядочения и объявляем его минимальным элементом полного упорядочения; затем выбираем другой минимальный элемент и объявляем его следующим элементом в полном упорядочении и т.д. Это действие повторяется, пока все элементы множества не будут выбраны. Мы всегда выбираем минимальный элемент, поэтому если в исходном упорядочении а < 6, то это соотношение будет иметь место и в новом упорядочении, так как а будет выбрано первым.
Теперь опишем алгоритм формально: Процедура ТС(Я, <т): Выбрать минимальный элемент г из (Я, <г); Удалить з из 5; Выполнять следующие шаги до тех пор, пока Я не пусто; Выбрать минимальный элемент г из (Я, <г) и удалить его; Положить г <~ г; Переименовать г в г; Конец процедуры. 186 ГЛАВА 5. Алеоритмы и рекурсия А11 А12 .
А1р А21 А22 Азр Ае1 А~2 . Акр — матрица размера п х р, и в в в В21 В22 . В2иъ Вр Вр ..  — матрица размера р х т, то произведение матриц А и В, обозначаемое через АВ, есть матрица С = [С1 ] размера и х т, где С,у — точечное произведение г-ой строки матрицы А и 2-ого столбца матрицы В. То есть, в,, В, В21 А,ьВьу . С, =[А11 Ага Аю ... А1р] ° Вр, Если А = [А, ] — матрица размера т х и, то произведение этой матрицы на скаляр а есть матрица [В11] = а[А„] (см.
главу 4). Алгоритм нахождения этого произведения можно описать следующим образом: Процедура Скаляр(а, А, тп, 22): Цикл по 1 от 1 до гп: Цикл по 2' от 1 до ги В, =аА, Конец цикла; Конец цикла; Конец процедуры. Имя этой процедуры состоит из собственного имени "Скаляр" и входных данных, каковыми являются скалярная величина а и матрица А размера пт х и. Если А = [А; ] и В = [В;у] — матрицы размера т х и, то сумма А + В, определенная в главе 4, есть матрица С = [С, ] размера гп хи, где С, = Аеу+В,, Алгоритм нахождения суммы двух матриц А и В размера гп х и может быть описан следующим образом: Процедура Сложение матриц(А, В, 222, 22); ц Цикл по 2 от 1 до ги С11 = А1 + В1; Конец цикла; Конец цикла; Конец процедуры. Напомним, что если ртсадЕЛ 5.
7. циклы и алгоритмы для матриц 187 ° УПРАЖНЕНИЯ Опишите алгоритм нахождения транспонироаанной матрицы. Вычислите: 3 4] 2 — 2 3] 1 3 [4 3 — 5 О) — 5 2 ] г)[ — 4 3 — 5 О) д) (-4) 2 4 2[- 3) 3[ 2 4) 3. Пусть А = — 2 4 3] Вычислите: а) А' б) 44с в) А'А. 4. Пусть А= 4 5 ~ и В= ~ 2 3 . Вычислите: 1 21 ~ 4 1 б) ВА; в) АВс. г) АсВ ж)А — В; з)  — А; и) 5А; д) (АВ)', к) 2 — ЗА. а) АВ; е) Вс 4с. Опишем алгоритм умножения матриц А и В размера и х р и р х т. Процедура Умножение матриц(А, В, т,, р, и): Цикл по 2 от 1 до т: Цикл по 1' от 1 до и: Су=о; Цикл по )с от 1 до р: Значение Су заменить на С; + АсьВь,, Конец цикла; Конец цикла; Конец цикла; Конец процедуры.
188 ГЛАВА д Алгоритмы и рекурсия 5. Пусть А =, ~ и В = 1 0 — 5 ( Вычислите: а) АВ; б) ВА; в) А', г) В', АсВс. е) (ВА)'. 6. Постройте алгоритм нахождения наибольшего элемента последовательности. 7. Постройте алгоритм нахождения наименьшего элемента последовательности. 8. Постройте алгоритм нахождения наименьшего и наибольшего элементов последовательности. 9.
Постройте алгоритм для проверки, является ли матрица А симметричной. 10. Постройте алгоритм для проверки рефлексивности отношения, используя его матричное представление. 11. Постройте алгоритм нахождения среднего арифметического для и чисел. 12. Напишите алгоритм сложения двух целых чисел. 13. Напишите алгоритм вычитания двух целых чисел.
14. Напишите алгоритм умножения двух целых чисел. 15. Напишите алгоритм деления одного целого числа на другое целое число. то, тем самым, функция определена для всех целых чисел, больших а. Вероятно, правильнее говорить не о рекурсивной функции, а о функции, допускающей рекурсивное определение, поскольку многие функции могут быть заданы как рекурсивно, так и непосредственно. Заметим, что такая форма рекурсивного определения применима лишь к функциям, заданным на множестве неотрицательных целых чисел.
В дальнейшем мы рассмотрим возможность рекурсивного определения для более широкого класса функций. Кроме того, заметим, что возможность рекурсивного определения функции не всегда очевидна. Например, рассмотрим функцию, заданную как Может показаться, что такое определение соответствует приведенным выше пунктам (а) и (б) и задает рекурсивную функцию на множестве неотрицательных це- 5.2. РЕКУРСИВНЫЕ ФУНКЦИИ И АЛГОРИТМЫ Непосредственное задание функции при помощи формулы, как правило, является предпочтительным. Однако, иногда функцию бывает удобно или даже необходимо задавать при помощи так называемого "рекурсивного метода". Из принципа индукции следует, что если а) функция задана для некоторого данного начального значения а (обычно 0 или 1), и б) когда функция задана для некоторого значения к, большего а, она задана также для значения й+ 1, РАЗДЕЛ 5.2.
Рекурсивные функции и елгоратмы 189 лых чисел. Мы видим, однако, что 1(1) = 2, 1(2) = 1, 1(3) = -', а значение Г"(4) не определено, т.к. запись Я)1 не имеет смысла. Аналогично, если алгоритм может быть выполнен для фиксированного значения а и если из выполнимости алгоритма для значения 1с, большего а, следует выполнимость алгоритма для значения Й+ 1, то такой алгоритм выполним для всех значений и > а. Для начала рассмотрим несколько примеров рекурсивных функций. Рассмотрим функцию г(п) = а", определенную на множестве неотрицательных целых чисел.
Ее можно задать как произведение и чисел, каждое из которых равно а. Функция допускает также и рекурсивное определение, а именно: У(О) =1; ((1+ 1) = а 1(/с). ПРИМЕР 5.4. Рассмотрим функцию 1" (п) = и1, называемую "факториалом". Эту функцию легко выразить посредством соотношения и1=1.2 3.. и. Но компьютеру, выполняющему вычисления, невозможно объяснить, что означает троеточие. Однако мы можем составить процедуру, или алгоритм непосредственного вычисления и!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
