Задачи о маршрутах: эйлеровы и гамильтоновы маршруты, обходы графов, нахождение кратчайших путей.
Деревья: эквивалентные признаки, определяющие дерево. Бинарные деревья, способы нумерации вершин дерева, связь нумераций с вычислением арифметических выражений. Каркасные деревья, задача о минимальном соединении.
Хроматическое число графа, алгоритм построения правильной раскраски в минимальное число цветов, «проблема четырёх красок».
Двудольные графы. Признак двудольности. Паросочетания в двудольном графе, «задача о назначении».
Задачи на ориентированных графах: задача о максимальном потоке, применение графов для анализа программ.
Анализ связности графов. Нахождение сильно связанных компонентов.
Тема 5. Алгебра логики и элементы теории формальных систем.
Функции и операции. Свойства операций: ассоциативность, коммутативность, дистрибутивность. Понятие единичного элемента. Группа, кольцо, поле – определения и примеры: кольцо целых чисел, кольцо полиномов, кольцо вычетов, поле действительных чисел, поле комплексных чисел. Понятие о конечных полях.
Отношения на множествах: определение, виды отношений, примеры. Бинарные отношения и их свойства. Основные виды бинарных отношений: эквивалентность, порядок (строгий, нестрогий, частичный, линейный). Решетка: определение и примеры.
Функции алгебры логики. Таблица истинности. Представление функций формулами. Двойственные функции. Булева алгебра. Эквивалентные преобразования формул. Конъюнктивная и дизъюнктивная нормальные формы. Алгоритмы преобразования произвольной формулы в совершенные нормальные формы. Основные замкнутые классы логических функций. Функционально полные системы, критерии функциональной полноты.
Язык логики предикатов. Преобразования формул логики предикатов. Предваренные нормальные формы.
Понятие формальной теории (логического исчисления). Аксиомы и правила вывода. Исчисление высказываний. Исчисление предикатов. Свойства формальных теорий: полнота, непротиворечивость, разрешимость. Практическая значимость построения и изучения формальных теорий.
Тема 6. Основы теории алгоритмов.
Предпосылки развития теории алгоритмов. Понятие алгоритма. Общие требования к алгоритмам. Способы формального подхода к изучению алгоритмов.
Машина Тьюринга (МТ) как пример формальной модели алгоритма. Примеры записи алгоритмов на МТ. Универсальная МТ. Проблема остановки МТ как пример алгоритмически неразрешимой задачи.
Обзор других моделей алгоритмов, инвариантность понятия алгоритмически разрешимых задач по отношению к разным моделям. Понятие недетерминированной машины Тьюринга.
Понятие полиномиально вычислимых задач. Классы сложности Р и NP.
Тема 7. Введение в анализ алгоритмов
Понятие вычислительной сложности алгоритмов. Необходимость применения быстрых алгоритмов. Сложность алгоритма. Рост функций и О-символика. Анализ алгоритмов.
Тема 8. Простейшие методы сортировки массива
Задача сортировки массива. Устойчивость сортировки. Сложность сортировки. Метод прямого выбора. Пузырьковая сортировка. Сортировка вставками. Оценка сложности простейших методов сортировки. Исследование сложности простейших методов сортировки в зависимости от упорядоченности исходного массива.
Тема 9. Теоретико-числовые алгоритмы
Простые числа. Проверка числа на простоту. Тест на основе малой теоремы Ферма. Решето Эратосфена. Основная теорема арифметики. Разложение числа на простые множители. Функция Эйлера. Наибольший общий делитель. Простейший алгоритм и алгоритм Евклида для нахождения наибольшего общего делителя. Сравнение сложности этих алгоритмов. Наименьшее общее кратное. Его связь с наибольшим общим делителем.
Тема 10. Рекурсивные алгоритмы
Рекурсия. Элементарные рекурсивные алгоритмы: вычисление факториала, чисел Фибоначчи и наибольшего общего делителя. Стратегия «разделяй и властвуй». Быстрые методы сортировки, основанные на данной стратегии: сортировка слиянием и быстрая сортировка методом Хоара.
Задача поиска в массиве. Последовательный поиск. Двоичный поиск в отсортированном массиве. Сравнение сложности последовательного поиска и двоичного. Достоинства и недостатки этих двух методов поиска.
Тема 12. Динамические структуры данных
Стек и очередь. Реализация стека и очереди на основе массива. Функции для работы с очередью: insert, remove, first, isEmpty. Функции для работы со стеком: push, pop, last (top), isEmpty. Дерево двоичного поиска. Высота дерева. Обход дерева. Хеш-таблица. Коллизии и методы их разрешения: метод цепочек и метод открытой адресации.
Тема 13. Вычислительные алгоритмы
Умножение матрицы на матрицу и матрицы на столбец. Решение уравнения методом деления отрезка пополам. Численное интегрирование. Метод прямоугольников, метод трапеций и метод Симпсона. Погрешность вычислительного алгоритма. Оценка погрешностей изученных методов.
РАЗДЕЛ 3. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
3.1. Примерные темы курсовых работ
1. Сортировка методом вставок;
2. Шейкерная сортировка;
3. Пирамидальная сортировка;
4. Сортировка методом Шелла;
5. Сортировка слиянием;
6. Быстрая сортировка методом Хоара;
7. Двоичный поиск в массиве;
8. Дерево двоичного поиска;
9. Хеш-таблица (метод открытой адресации);
10. Хеш-таблица (метод цепочек);
11. Код Хаффмана;
12. Код Шеннона-Фано;
13. Задача о ранце;
14. Задача о ханойских башнях;
15. Вычисление интеграла методом прямоугольников;
16. Вычисление интеграла методом трапеций;
17. Вычисление интеграла методом Симпсона;
18. Решение уравнения методом деления отрезка пополам;
19. Алгоритм Дейкстры;
20. Тест Ферма для проверки числа на простоту;
21. Тест Миллера-Рабина для проверки числа на простоту;
22. Алгоритм Рабина-Карпа для поиска подстрок;
23. Алгоритм быстрого возведения в степень;
24. Обобщенный алгоритм Евклида;
25. Вычисление инверсий с помощью обобщенного алгоритма Евклида;
26. Реализация стека на основе указателей;
27. Реализация очереди на основе указателей;
28. Поиск цикла в связном списке;
29. Поиск гамильтонова цикла в графе;
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.