2k4s_DM_Task_List

МАТЕРИАЛЫ для СТУДЕНТОВ ЗАОЧНОГО ОТДЕЛЕНИЯ СПбГЭТУ (ЛЭТИ)

Курс ”Дискретная математика“

Кафедра ВМ-2 Курс 2 Семестр 4

Санкт-Петербург 2014

1Программа курса

1.1Арифметика целых чисел

1.Делимость целых чисел. НОД. Простые числа. Разложение числа на простые.

2.Алгоритм Евклида и его анализ, бинарный алгоритм.

3.Расширенный алгоритм Евклида.

4.Цепные дроби. Разложение иррациональности в цепную дробь.

5.Классы вычетов по данному модулю. Китайская теорема об остатках.

6.Функция Эйлера и ее свойства. Теорема Эйлера-Ферма.

7.Быстрое возведение числа в степень в кольце Z/(m).

8.Применение теоремы Эйлера в криптографии. Система шифрования RSA. Электронная подпись.

9.Схема Горнера. Алгоритм Евклида для многочленов.

1.2Комбинаторика и производящие функции

1.Размещения и сочетания без повторений. Бином Ньютона.

2.Размещения и сочетания с повторениями.

3.Кодирование с исправлением ошибок. Граница Хемминга. Код Шеннона-Фэно и алгоритм Хаффмена.

4.Лексикографический и антилексикографический порядок.

5.Нумерация перестановок.

6.Разбиения чисел.

7.Принцип включения - исключения и его применения.

8.Рекуррентные уравнения. Производящие функции. Числа Фибоначчи.

1.3Теория графов

1.Машинное представление графов.

2.Поиск в глубину и поиск в ширину в графе.

3.Связность. Эйлеровы цепи в графе. Алгоритм Флёри.

4.Деревья, каркасы. Алгоритм построения каркаса.

5.Главные циклы и коциклы.

2

6.Минимальные остовые деревья нагруженных графов. Алгоритмы Краскала и

Прима.

7.Паросочетания в двудольных графах. Построение наибольшего паросочетания. Задача о назначении.

8.Метод ветвей и границ.

9.Задача нахождения кратчайших путей в графе. Алгоритмы Форда-Беллмана, Дейкстры и Флойда.

10.Планарность. Гомеоморфизм графов.

11.Раскраска графов.

2Контрольные работы

2.1Первый вариант

√

1.Представить 377 в виде периодической цепной дроби и вычислить с точно• стью до ε = 10−5.

2.Найти остаток от деления 251927 на 84.

3.Найти наименьшее натуральное число x, удовлетворяющее условиям:

x ≡ 12 MOD 27, x ≡ 36 MOD 37, x ≡ 6 MOD 22, x ≡ 9 MOD 13.

4.Пусть m = 35 и e = 7 открытая часть ключа RSA. Найти закрытую часть

ключа d.

√√

5.Сколько целых слагаемых содержит бином ( 3 5 + 5 7)65

6.Пусть имеется 6 кодовых символов: D, E, N, T, S, U с частотами появления (см. табл. 2.1):

D	E	N	T	S	U
20	21	15	17	18	9

Таблица 2.1. Частоты появления кодовых символов.

C помощью алгоритма Хаффмена построить код Шеннона-Фэно для текстового со• общения S T U D E N T (большему слову приписываем справа 1, а меньшему – 0).

7. Найти решение однородного рекуррентного уравнения с граничными условия•

ми:

3fn+2 − 8fn+1 + 4fn = 0, f0 = 2, f1 = 2.

8. Используя граф на рис. 2.1 (источник вершина A), проиллюстрировать ал• горитм просмотра вершин графа и построения остовного дерева:

(a) в глубину;

3

(b)в ширину.

Врешении указать порядок просмотра вершин графа, динамику изменения состояния стека и очереди, маркировку вершин. Решение проиллюстрировать рисунком.

HIJKGFED@ABCONML

HIJKONML

HIJKONML

HIJKONML

A

F

H

B

HIJKONML

ONMLHIJK

WVUTPQRS

HIJKONML

J

L

M

K

ONMLHIJK

HIJKONML

HIJKONML

ONMLHIJK

G

D

I

K

Рис. 2.1.

9. Построить Эйлеров путь в графе, заданном своей матрицей смежности (см. табл. 2.2):

	v1	v2	v3	v4	v5	v6	v7
v1	0	1	0	1	1	1	0
v2	1	0	1	1	1	0	0
v3	0	1	0	0	1	0	0
v4	1	1	0	0	1	1	0
v5	1	1	1	1	0	1	1
v6	1	0	0	1	1	0	1
v7	0	0	0	0	1	1	0

Таблица 2.2. Матрица смежности графа.

10. Найти незамкнутый маршрут минимальной длины методом ветвей и границ для графа на рис. 2.2. Представить частичные решения (в форме остовных деревьев) и их расширения.

HIJKONML

B

a(5)

b(4)

ONMLHIJK

HIJKONML

A

c(1)

C

g(2)

d(6)

D

q(3)

E

r(5)

F

ONMLHIJK

HIJKONML

ONMLHIJK

h(5)

k(1)

m(6)

n(3)

HIJKONML

HIJKONML

G

p(4)

H

Рис. 2.2.

4

11. Граф задан матрицей смежности (см. табл. 2.3):

	v1	v2	v3	v4	v5	v6	v7	v8
v1	0	1	0	1	1	0	0	0
v2	1	0	1	0	1	0	0	0
v3	0	1	0	1	1	0	0	0
v4	1	0	1	0	1	0	0	0
v5	1	1	1	1	0	0	0	0
v6	0	0	0	0	0	0	1	1
v7	0	0	0	0	0	1	0	1
v8	0	0	0	0	0	1	1	0

Таблица 2.3. Матрица смежности графа.

Напишите линейную систему уравнений для индикаторов ребер этого графа и решите ее. Проиллюстрируйте результаты решения на графе. Сформулируйте теорему о числе независимых циклов графа и проиллюстрируйте ее на примере данного графа. Проил• люстрируйте алгоритм нахождения базиса пространства циклов графа.

12.Нарисуйте двудольный граф по следующим данным. Множество вершин левой части L = {2, 6, 7, 8, 9, 10}, множество вершин правой части R = {1, 2, 3, 4, 5, 6}. Множе• ство ребер определяется делимостью числа из левой части на число из правой. Напри• мер, вершина 10 левой части соединяется с вершинами 1, 2, 5 правой части. Определите наибольшее паросочетание для данного графа. Проиллюстрируйте промежуточные ша• ги алгоритма.

13.Алгоритмом Флойда построить матрицу кратчайших расстояний между па• рами вершин указанного на рис. 2.3 графа и соответствующую матрицу ссылок. В решении представить все матрицы, соответствующие последовательному расширению множества промежуточных вершин.

a(5)

HIJKONML

g(6)

HIJKONML ll b(14)

A

**

nn

B

c(11)

d(8)

e(9)

f(6)

h(7)

••

HIJKONML

♦♦HIJKONML

C

tsts

**

3D3

77

YY

k(6)

♦♦

♦♦♦

m(2)

n(3)♦

♦♦♦♦♦♦

♦

HIJKONML mm

l(7)

♦

p(8)

''

♦

E

Рис. 2.3.

14. Алгоритмом Дейкстры определить кратчайшие пути от вершины M до осталь• ных вершин графа на рис. 2.4. Построить дерево кратчайших путей. В решении пред•

5

ставить значения промежуточных пометок вершин.

A

a(2)

F

b(2)

H

c(3)

B

GFED@ABC

GFED@ABC

GFED@ABC

GFED@ABC

e(8)

h(5)

d(3)

f(3)

g(1)

k(4)

l(3)

L

m(2)

n(4)

J

M

K

89:;?>=<

@ABCGFED

GFED@ABC?>=<89:;

@ABCGFED

w(9)

t(2)

r(9)

s(4)

u(5)

D

v(7)

G

x(5)

I

y(6)

K

GFED@ABC

@ABCGFED

89:;?>=<

GFED@ABC

Рис. 2.4.

2.2Второй вариант

√

1.Представить 126 в виде периодической цепной дроби и вычислить с точно• стью до ε = 10−5.

2.Найти остаток от деления 231129 на 45.

3.Найти наименьшее натуральное число x, удовлетворяющее условиям:

x ≡ 6 MOD 13, x ≡ 33 MOD 37, x ≡ 19 MOD 23, x ≡ 14 MOD 36.

4.Пусть m = 35 и e = 5 открытая часть ключа RSA. Найти закрытую часть

ключа d.

√√

5.Сколько целых слагаемых содержит бином ( 5 5 + 3 7)70

6.Пусть имеется 6 кодовых символов: A, C, E, H, R, T с частотами появления (см. табл. 2.4):

A	C	E	H	R	T
25	9	21	22	6	17

Таблица 2.4. Частоты появления кодовых символов.

C помощью алгоритма Хаффмена построить код Шеннона-Фэно для текстового со• общения T E A C H E R (большему слову приписываем справа 1, а меньшему – 0).

7. Найти решение однородного рекуррентного уравнения с граничными условия•

ми:

2fn+2 + 5fn+1 − 3fn = 0, f0 = 0, f1 = 7.

8. Используя граф на рис. 2.5 (источник вершина F ), проиллюстрировать ал• горитм просмотра вершин графа и построения остовного дерева:

(a)в глубину;

(b)в ширину.

6

В решении указать порядок просмотра вершин графа, динамику изменения состояния стека и очереди, маркировку вершин. Решение проиллюстрировать рисунком.

HIJKONML

HIJKGFED@ABCONML

HIJKONML

HIJKONML

A

F

H

B

HIJKONML

ONMLHIJK

WVUTPQRS

HIJKONML

J

L

M

K

ONMLHIJK

HIJKONML

HIJKONML

ONMLHIJK

D

G

I

K

Рис. 2.5.

9. Построить Эйлеров путь в графе, заданном своей матрицей смежности (см. табл. 2.5):

	v1	v2	v3	v4	v5	v6	v7	v8	v9
v1	0	1	1	0	0	0	0	0	0
v2	1	0	1	0	0	0	1	1	0
v3	1	1	0	1	1	0	0	0	0
v4	0	0	1	0	1	0	0	0	0
v5	0	0	1	1	0	1	0	1	0
v6	0	0	0	0	1	0	1	1	1
v7	0	1	0	0	0	1	0	1	1
v8	0	1	0	0	1	1	1	0	0
v9	0	0	0	0	0	1	1	0	0

Таблица 2.5. Матрица смежности графа.

10. Найти незамкнутый маршрут минимальной длины методом ветвей и границ для графа на рис. 2.6. Представить частичные решения (в форме остовных деревьев) и их расширения.

HIJKONML

B

a(5)

b(4)

ONMLHIJK

c(1)

HIJKONML

A

C

g(2)

d(6)

e(2)

f(4)

D

q(3)

E

F

HIJKONML

HIJKONML

HIJKONML

h(5)

k(1)

n(3)

G

p(4)

H

HIJKONML

HIJKONML

Рис. 2.6.

7

11. Граф задан матрицей смежности (см. табл. 2.6):

	v1	v2	v3	v4	v5	v6	v7	v8
v1	0	1	1	1	0	0	0	0
v2	1	0	1	0	1	0	0	0
v3	1	1	0	1	1	0	0	0
v4	1	0	1	0	0	0	0	0
v5	0	1	1	0	0	0	0	0
v6	0	0	0	0	0	0	1	1
v7	0	0	0	0	0	1	0	1
v8	0	0	0	0	0	1	1	0

Таблица 2.6. Матрица смежности графа.

Напишите линейную систему уравнений для индикаторов ребер этого графа и решите ее. Проиллюстрируйте результаты решения на графе. Сформулируйте теорему о числе независимых циклов графа и проиллюстрируйте ее на примере данного графа. Проил• люстрируйте алгоритм нахождения базиса пространства циклов графа.

12.Нарисуйте двудольный граф по следующим данным. Множество вершин левой части L = {3, 6, 7, 8, 9, 10}, множество вершин правой части R = {1, 2, 3, 4, 5, 6}. Множе• ство ребер определяется делимостью числа из левой части на число из правой. Напри• мер, вершина 10 левой части соединяется с вершинами 1, 2, 5 правой части. Определите наибольшее паросочетание для данного графа. Проиллюстрируйте промежуточные ша• ги алгоритма.

13.Алгоритмом Флойда построить матрицу кратчайших расстояний между па• рами вершин указанного на рис. 2.7 графа и соответствующую матрицу ссылок. В решении представить все матрицы, соответствующие последовательному расширению множества промежуточных вершин.

a(5)

HIJKONML

g(6)

HIJKONML ll b(4)

A

**

nn

B

c(1)

d(8)

e(9)

f(6)

h(7)

••

HIJKONML

♦♦HIJKONML

C

tsts

**

3D3

77

YY

k(6)

♦♦

♦

♦

♦

m(12)

♦

n(13)

l(7)

''

♦♦♦♦♦♦♦♦ p(8)

HIJKONML mm

E

Рис. 2.7.

14. Алгоритмом Дейкстры определить кратчайшие пути от вершины J до осталь• ных вершин графа на рис. 2.8. Построить дерево кратчайших путей. В решении пред•

8

ставить значения промежуточных пометок вершин.

A

a(2)

F

b(2)

H

c(3)

B

@ABCGFED

GFED@ABC

GFED@ABC

GFED@ABC

e(8)

h(5)

d(3)

f(3)

g(1)

k(4)

l(3)

L

n(4)

J

M

K

HIJKGFED@ABCONML

GFED@ABC

GFED@ABC

@ABCGFED

w(9)

t(2)

p(5)

r(9)

s(4)

u(5)

v(7)

x(5)

I

y(6)

D

G

K

@ABCGFED

@ABCGFED

HIJKONML

GFED@ABC

Рис. 2.8.

3Экзаменационные вопросы

1.НОД, НОК и их свойства. Простые числа. Решето Эратосфена.

2.Разложение числа на простые (метод пробных делителей и метод Ферма).

3.Алгоритм Евклида и его анализ, бинарный алгоритм. Линейное представление

НОД.

4.Обобщенный алгоритм Евклида.

5.Цепные дроби. Разложение числа в цепную дробь.

6.Свойства и вычисление подходящих дробей.

7.Бесконечная цепная дробь. Разложение иррациональности в цепную дробь.

8.Решение диофантовых уравнений.

9.Классы вычетов по данному модулю. Арифметика и свойства сравнений.

10.Функция Эйлера и ее свойства. Теорема Эйлера-Ферма.

11.Быстрое возведение числа в степень в кольце Z/(m).

12.Применение теоремы Эйлера в криптографии. Система шифрования RSA.

13.Электронная подпись. Электронные деньги.

14.Сравнения первой степени. Китайская теорема об остатках.

15.Многочлены. Основные операции и свойства. Схема Горнера.

16.Алгоритм Евклида для многочленов. Линейное представление НОД.

17.Размещения и сочетания. Бином Ньютона и его комбинаторное использование.

18.Кодирование с исправлением ошибок. Граница Хемминга.

9

19.Код Шеннона-Фэно и алгоритм Хаффмена.

20.Лексикографический и антилексикографический порядок.

21.Нумерация перестановок.

22.Разбиения чисел.

23.Принцип включения - исключения и его применения.

24.Рекуррентные уравнения. Производящие функции. Числа Фибоначчи.

25.Решение однородного линейного рекуррентного уравнения. Частные решения.

26.Решение неоднородного линейного рекуррентного уравнения.

27.Машинное представление графов.

28.Поиск в глубину и поиск в ширину в графе.

29.Простейшие определения и свойства графов. Связность.

30.Эйлеровы цепи в графе. Алгоритм Флёри.

31.Деревья, каркасы. Алгоритм построения каркаса.

32.Минимальные остовые деревья нагруженных графов. Алгоритмы Прима и Краскала.

33.Главные циклы и коциклы. Граница и кограница.

34.Двудольные графы. Паросочетания в двудольных графах.

35.Построение наибольшего паросочетания.

36.Задача о назначениях.

37.Кратчайшие пути в графе. Алгоритм Форда–Беллмана.

38.Алгоритм Форда–Беллмана для нахождения дерева кратчайших путей

39.Алгоритм Дейкстры.

40.Алгоритм Флойда.

41.Планарность. Теорема Эйлера. Гомеоморфизм графов.

42.Раскраска графов.

10