Программа лекций по курсу «Дискретная математика»
| Вид материала | Программа |
СодержаниеОсновные задачи по курсу «Дискретная математика» Литература по курсу «Дискретная математика» |
- Рабочая программа дисциплины (модуля) Дискретная математика, 101.32kb.
- Рабочая программа учебной дисциплины «Дискретная математика» Направление подготовки, 139.29kb.
- Примерная программа наименование дисциплины «Дискретная математика» Рекомендуется для, 135.29kb.
- Джеймс А. Дискретная математика и комбинаторика [Текст] / Джеймс А. Андерсон, 42.79kb.
- Темы курсовой работы по дисциплине "дискретная математика" (Приложение к рабочей программе, 128.96kb.
- Учебная программа для специальности: (рабочий вариант) 1-310301-02 Математика (научно-педагогическая, 120.64kb.
- Аннотация программы учебной дисциплины «Дискретная математика и математическая логика, 55.65kb.
- Рабочая программа Наименование дисциплины дискретная математика по направлению подготовки, 201.9kb.
- В. М. Фомичёв дискретная математика и криптология курс лекций, 410.4kb.
- Методические указания к выполнению курсовой работы по дисциплине " Дискретная математика", 254.75kb.
Программа лекций по курсу «Дискретная математика»
Кафедра ВМ-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.