Вопросы для экзамена

1.Делимость целых чисел. НОД, НОК и их свойства. Простые числа. Решето Эратосфена. Алгоритмы факторизации (метод пробных делителей и метод Ферма).

2.Алгоритм Евклида, бинарный алгоритм. Линейное представление НОД.

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

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

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

6.Диофантовы уравнения.

7.Арифметика и свойства сравнений.

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

9.Быстрое возведение числа в степень в кольце ZM.

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

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

12.Циклическая атака на RSA.

13.Китайская теорема об остатках.

14.Размещения и сочетания. Бином Ньютона.

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

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

17.Лексикографический и антилексикографический порядок. Генерация k - элементных под• множеств

18.Перечислительная комбинаторика. Код Грея. Перечисление перестановок.

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

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

21.Машинное представление графов. Поиск в глубину и поиск в ширину в графе.

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

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

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

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

26.Двудольные графы. Теорема Кенига. Определение двудольности графа.

27.Планарность. Теорема Эйлера. Гомеоморфизм графов. Теорема Понтрягина-Куратовско• го.

1

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

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

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

31.Свойства бинарных отношений. Способы задания. Отношение порядка. Алгоритм топо• логической сортировки.

32.Транзитивное замыкание бинарного отношения. Алгоритм Уоршелла.

Задачи для экзамена

1.Линейное представление НОД.

2.Разложение иррациональности в цепную дробь с заданной точностью ǫ.

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

4.Алгоритм RSA - кодирования.

5.Алгоритм Хаффмена.

6.Принцип включения-исключения.

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

8.Построение эйлеровой цепи в графе.

9.Построение минимального остового дерева нагруженного графа.

10.Построение главных циклов и коциклов графа.

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

12.Исследование бинарного отношения.

13.Алгоритм Уоршелла.

Литература

1.Поздняков С. Н., Рыбин C. В. Дискретная математика. М.: Издательский центр ”Ака• демия“, 2008.

2.Виноградов И. М. Основы арифметики. М.: Наука, 1972.

3.Кнут Д. Искусство программирования для ЭВМ : В 3т. Т.2. М.: Мир, 1977.

4.Фудзисава Т., Касами Т. Математика для радиоинженеров. М.: Радио и связь, 1984.

5.Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986.

6.Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988.

2

7.Липский В. Комбинаторика для программистов. М.: Мир, 1988.

8.Дж. Дэвенпорт, И.Сирэ, Э.Турнье. Компьютерная алгебра. М.: 1991.

9.Нефедов В. Н., Осипова В. А. Курс дискретной математики. М.: Изд-во МАИ, 1992.

10.Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1997.

11.Харари Ф. Теория графов. М.: Мир, 1998.

12.Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.

М.: Мир, 1998.

13.Введение в криптографию/Под общ. ред. В. В. Ященко. М.: MЦНMО, 1998.

14.Романовский И. В. Дискретный анализ. СПб.: Невский диалект, 1999.

15.Новиков Ф. А. Дискретная математика для программистов. СПб.: Питер, 2002.

Учебные пособия

1.Малов С. Ю., Поздняков С.Н., Рыбин С.В. Основы дискретной математики. СПбГЭТУ, 2002.

2.Поздняков С.Н., Рыбин С.В. Компьютерная математика. СПбГЭТУ, 2005.

3.Поздняков С.Н., Рыбин С.В. Введение в дискретную математику. СПбГЭТУ, 2006.

3