Математические методы исследования алгоритмического и программного обеспечения

1 Введение 5

2 Методическое указания

по организации

практических занятий 7

2.1 Практическое занятие 1 Комбинаторные задачи . . . . . . . 7

2.1.1 Метод математической индукции . . . . . . . . . . . . . 7

2.1.2 Множества . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.1.3 Отображения . . . . . . . . . . . . . . . . . . . . . . . . 9

2.1.4 Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2 Практическое занятие 2. Задачи по теории алгоритмов . . . 12

2.3 Практическое занятие 3. Задачи по теории алгоритмов . . . 13

2.4 Практическое занятие 4. Асимптотические методы решения

рекуhрентных соотношений на основе основной теоремы о ре-

ккурентных соотношениях . . . . . . . . . . . . . . . . . . . . 14

2.5 Практическое занятие 5. Метод Акрра-Бази . . . . . . . . . 15

2.6 Практическое занятие 6. Решение рекуррентных соотношений методом производящих функций . . . . . . . . . . . . . . 17

2.7 Практическое занятие 7. Получение явного выражения на

основе композиции производящих функций . . . . . . . . . . . 18

2.7.1 Пример 1 . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.7.2 Пример 2 . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.8 Практическое занятие 8. Решение рекуррентных уравнений

на основе уравнений вида T(x) = xR(T(x)) . . . . . . . . . . . 20

2.9 Практическое занятие 9. Решение рекуррентных уравнений

на основе функциональных уравнений вида R(T(x)) = F(x) . 23

2.9.1 Пример 1 . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.9.2 Пример 2 . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.10 Практическое занятие 10. Решение задач теории графов . . 28

2.11 Практическое занятие 11. Решение задач теории графов . . 29

2.12 Практическое занятие 12.Решение задач теории графов . . . 30

3

2.13 Практическое занятие 13. Решение задач теории синтаксического анализа: вывод цепочки, определение типа грамматики,

построение грамматик . . . . . . . . . . . . . . . . . . . . . . . 30

2.14 Практическое занятие 14. Решение задач теории синтаксического анализа: эквивалентные преобразования, построение син-

таксических деревьев нисходящими и восходящими методами 32

2.15 Практическое занятие 15. Решение задач теории синтаксиче-

ского анализ: построение грамматики для проблемно-ориентированного

языка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.16 Практическое занятие 16. Одноканальные СМО . . . . . . . 34

2.17 Практическое занятие 17. Многоканальные СМО . . . . . . 35

2.18 Практическое занятие ќ18. Многоканальные СМО . . . . . . 35

3 Методические указания

по организации

самостоятельной работы 36

3.1 Проработка лекционного материала . . . . . . . . . . . . . . . 36

3.2 Самостоятельное изучение тем теоретической части курса . . 37

3.2.1 Алгебра . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.2.2 Основы криптографии . . . . . . . . . . . . . . . . . . . 37

3.2.3 Сети Петри . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.2.4 Задачи и методы машинного обучения . . . . . . . . . . 41

А Онлайн энциклопедия целых последовательностей . . . . . . . 43

Б Коэффициенты степеней полиномов и рациональных произво-

дящих функций . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

В Коэффициенты степеней производящих функций логарифма

и функций заданных радикалами . . . . . . . . . . . . . . . . 45