Программа лекций по курсу «Дискретная математика»

Вид материалаПрограмма

Содержание


Основные задачи по курсу «Дискретная математика»
Литература по курсу «Дискретная математика»
Подобный материал:
Программа лекций по курсу «Дискретная математика»

Кафедра ВМ-2, весенний семестр 2003 г. Лектор С.В.Рыбин

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

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

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

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

5. Наилучшие приближения цепными дробями.

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

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

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

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

10. Метод безключевого чтения RSA (циклическая атака).

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

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

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

14. Китайская теорема об остатках для многочленов. Интерполяционная формула Лагранжа.

15. Интерполяционная формула Ньютона. Остаток интерполирования.

16. Приближенная интерполяция (Метод наименьших квадратов).

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

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

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

20. Числа Стирлинга первого и второго рода и их свойства.

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

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

23. Элементарная теория вероятностей: основные определения, условные вероятности и формула Байеса.

24. Случайные величины. Математическое ожидание и дисперсия.

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

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

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

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

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

30. Эйлеровы цепи в графе.

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

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

33. Двудольные графы.

34. Ориентированные графы. Основные понятия.
^

Основные задачи по курсу «Дискретная математика»


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

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

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

4. Решение сравнений первой степени.

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

6. Интерполяционные формулы Лагранжа и Ньютона.

7. Размещения и сочетания.

8. Рекуррентные уравнения с постоянными коэффициентами.

Дополнительные задачи по курсу «Дискретная математика»


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

2. Теорема Эйлера-Ферма.

3. Приближенная интерполяция (Метод наименьших квадратов).

4. Полиномиальное кодирование. Код Шеннона-Фэно и алгоритм Хаффмана.

5. Графы: каркасы, главные циклы и коциклы, эйлеровы пути.
^

Литература по курсу «Дискретная математика»


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

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

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

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

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

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

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

8. Ф.А.Новиков, Дискретная математика для программистов, С.-Петербург, 2001.

9. И.В.Романовский, Дискретный Анализ, С.-Петербург, 1999.

10. М.Сибуя, Т.Ямомото, Алгоритмы обработки данных, Москва, 1986.

11. Введение в криптографию, под общей ред. В.В.Ященко, Москва, 1998.