Материал: LS-Sb89586
МИНОБРНАУКИ РОССИИ
–––––––––––––––––––––––––––––––––––
Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»
–––––––––––––––––––––––––––––––––––
ДИСКРЕТНАЯ МАТЕМАТИКА
Методические указания по решению задач
Санкт-Петербург Издательство СПбГЭТУ «ЛЭТИ»
2013
УДК 519.1 (077)
Дискретная математика: Методические указания по решению задач / сост.: С. Г. Иванов, Н. Н. Сосновский. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2013. 32 с.
Содержат краткие теоретические материалы и примеры решения задач по основам теории целых чисел, комбинаторике, булевым функциям.
Предназначены для студентов очного и заочного отделений, изучающих курс дискретной математики, и соответствуют стандартной программе этого курса.
Утверждено редакционно-издательским советом университета
вкачестве методических указаний
©СПбГЭТУ «ЛЭТИ», 2013
2
1. ОСНОВЫ ТЕОРИИ ЦЕЛЫХ ЧИСЕЛ
1.1. Деление с остатком
Определение: a, b Z, b > 0.
Разделить a на b с остатком – значит найти такие числа p и q, чтобы a = bq + r, при этом 0 ≤ r < b.
Примеры:
1.25 = 4 6 + 1.
2.–25 = (–5) 6 + 5.
Докажем единственность деления с остатком.
В самом деле, если a bq1 r1 bq2 r2, тогда b q1 q2 r2 r1.
Если левая часть не равна 0, то ее модуль не меньше b, поскольку умножаем b на ненулевое целое число. С другой стороны, оба остатка меньше b, поэтому модуль разности в правой части меньше b.
Противоречие!
Поэтому левая часть равна 0, и два представления совпали.
1.2. Делимость
Говорят, что a b (a делится на b) или b | a (b делит a), если существует q такое, что a = bq.
Свойства делимости:
1.a | b и b | c a | c.
2.a | b и a | c a | (b c).
3.a | b и a | c a | (b kc), k Z.
1.3.Наибольший общий делитель и наименьшее общее кратное
Определение. Пусть a1, ...,an – набор целых чисел. Тогда:
d – наибольший общий делитель набора a1, ...,an , если d – наибольшее натуральное число, на которое делятся все a1, ...,an ;
m – наименьшее общее кратное набора a1, ...,an , если m – наименьшее натуральное число, которое делится на все a1, ...,an .
3
1.4. Алгоритм Евклида
Пример. НОД (72, 96) = НОД (72, 96 – 72) = НОД (72, 24) = 24.
Идея вычисления наибольшего общего делителя в том, что некоторые числа заменяем их линейными комбинациями таким образом, что числа уменьшаются, а наибольший общий делитель остается прежним.
Приведем более строгое описание работы алгоритма.
Теорема. Множество общих делителей не меняется при элементарных преобразованиях набора a1, ...,an , то есть при замене ai числом ai qak .
Всамом деле, если некоторое число d было общим делителем набора
a1, ...,an , то все линейные комбинации этих чисел, в том числе ai qak , де-
лятся на d.
Аналогично, если число d1 является общим делителем для набора, в котором провели замену, то оно является делителем qak , а следовательно, и делителем ai . Значит, это число является делителем исходного набора.
Пример:
276 = 84 3 + 24;
84 = 24 3 + 12;
24 = 12 2; НОД (276, 84) = НОД (84, 24) = НОД (12, 24) = НОД (12, 0) = 12.
Общая формула алгоритма для двух чисел: a bq1 r1;
b r1q2 r2 ; r1 r2q3 r3 ;
r2 r3q4 r4 ;
…
В конце концов остаток при делении окажется равен нулю, поскольку остатки уменьшаются с каждым шагом, и все они положительные:
rk 1 rk qk 1 rk 1; rk rk 1qk 2.
Тогда НОД (a, b) = rk 1 (то есть наибольший общий делитель равен по-
следнему ненулевому остатку).
Алгоритм Евклида относится к так называемым быстрым алгоритмам, поскольку на каждом шаге остаток уменьшается по крайней мере в 2 раза,
4
поэтому за сравнительно небольшое количество шагов алгоритм заканчивает работу.
Для трех чисел вычисление наибольшего общего делителя может быть, например, таким:
НОД (65, 182, 130) = НОД (65, 182, 0) = НОД (65, 52, 0) = НОД (13, 0, 0) = 13.
1.5. Обобщенный алгоритм Евклида
Линейное представление наибольшего общего делителя
Если d = НОД (a, b), то существуют такие целые числа x и y, что d = ax + by. Выведем общий метод вычисления линейного представления НОД.
a bq1 r1; b r1q2 r2 ; r1 r2q3 r3 ;
r2 r3q4 r4 ;
…
rk 2 rk 1qk rk ; rk 1 rk qk 1 rk 1;
rk rk 1qk 2.
Отсюда получаем:
rk 1 rk 1 rk qk 1. |
|
То есть rk 1 = НОД (a, b) выражен через два предыдущих остатка: rk и |
rk 1. |
Далее, воспользовавшись тем, что rk rk 2 rk 1qk , выразим rk 1 |
в виде |
rk 1 rk 1 rk qk 1 rk 1 rk 2 rk 1qk qk 1. |
(1.1) |
В этом случае получим линейное представление rk 1 = НОД (a, b) через
остатки rk 1 и rk 2 .
Затем выразим rk 1 через остатки rk 2 и rk 3 , и, подставив полученное представление в формулу (1.1), получим представление НОД (a, b) через остатки rk 2 и rk 3 . Продолжим процесс до тех пор, пока не получим линейное
представление НОД (a, b) через a и b.
Для трѐх и более чисел вычисление наибольшего общего делителя осуществляется последовательной заменой пар чисел исходного набора их НОД:
НОД (65, 182, 130) = НОД (НОД(65, 182), 130) = НОД (13, 130) = 13.
5