 |
- ⒶⒸКосовская Т.М. Алгоритмы и анализ их сложности. [Pdf-Fax- 2.5M] Учебное пособие. Учебное издание. Автор: Татьяна Матвеевна Косовская. Обложка: С.С. Сизиумов, фотобанк «Лори».
(Москва: ООО Компания «Ай Пи Ар Медиа», 2023. - Санкт-Петербургский государственный университет)
Скан: ???, OCR, обработка, формат Pdf-Fax: звездочет, 2024
- СОДЕРЖАНИЕ:
Введение (6).
Глава 1. ПРОСТЕЙШИЕ ДИСКРЕТНЫЕ АЛГОРИТМЫ И ОЦЕНКИ ЧИСЛА ИХ ШАГОВ (8).
1.1. Различие между числом шагов алгоритма
и вычислительной сложностью алгоритма (8).
1.2. Метод Гаусса для матриц с целыми коэффициентами. Анализ роста коэффициентов (10).
1.3. Арифметика многоразрядных чисел (15).
1.3.1. Представление неотрицательного многоразрядного числа как числа в системе счисления по заданному модулю (15).
1.3.2. Запись многоразрядного числа из файла. Оценка числа шагов (16).
1.3.3. Вывод многоразрядного числа в файл. Оценка числа шагов (18).
1.3.4. Сложение двух неотрицательных многоразрядных чисел. Оценка числа шагов (19).
1.3.5. Предикаты равенства и неравенств многоразрядных чисел. Оценка числа шагов (19).
1.3.6. Вычитание двух положительных многоразрядных чисел. Оценка числа шагов (20).
1.3.7. Умножение многоразрядного числа на макроцифру. Оценка числа шагов (21).
1.3.8. Умножение многоразрядных чисел. Оценка числа шагов (22).
1.3.9. Деление многоразрядных чисел. Оценка числа шагов (23).
1.4. Сортировки и оценки числа шагов (26).
1.4.1. «Пузырек» (27).
1.4.2. Сортировка слияниями фон Неймана (28).
1.4.3. Сортировка подсчетом (29).
Глава 2. АЛГОРИТМЫ НА ГРАФАХ (30).
2.1. Различные способы представления графа в компьютере и оценки числа шагов решения простейших задач (30).
2.1.1. Матрица смежности (31).
2.1.2. Списки смежности (32).
2.1.3. Матрица инцидентности (32).
2.1.4. Массивы V и E (33).
2.2. Оценки числа шагов некоторых стандартных алгоритмов (34).
2.2.1. Алгоритм Дейкстры поиска кратчайшего пути во взвешенном ориентированном графе. Оценки числа шагов (34).
2.2.2. Алгоритм Р. Прима нахождения остова минимального веса. Оценки числа шагов (35).
2.2.3. Нахождение Гамильтонова цикла. Оценки числа шагов (36).
2.2.4. Связь между понятиями «независимое множество», «вершинное покрытие» и «КЛИКА» (36).
2.2.5. Алгоритм построения максимальной клики (37).
Глава 3. ТЕОРИЯ АЛГОРИТМОВ (39).
3.1. Интуитивное понятие алгоритма и необходимость введения его точного математического понятия (39).
3.2. Представление о рекурсивных функциях. Тезис Черча (41).
3.3. Машины Тьюринга. Тезис Тьюринга - Черча (43).
3.3.1. Примеры программ машин Тьюринга (45).
3.3.2. Теорема о композиции машин Тьюринга (48).
3.3.3. Многоленточные машины Тьюринга (50).
3.3.4. Теорема о числе шагов машины Тьюринга, моделирующей работу многоленточной машины Тьюринга (55).
3.3.5. Многоголовчатые машины Тьюринга (56).
3.3.6. Недетерминированные машины Тьюринга (57).
3.3.7. Теорема о числе шагов машины Тьюринга, моделирующей работу недетерминированной машины Тьюринга (58).
3.4. Нормальные алгоритмы Маркова (59).
3.5. Конструктивные объекты (63).
3.6. Различие между математическими понятиями алгоритма и программами (65).
3.7. Теоремы о невозможности построения алгоритма (69).
3.7.1. Код алгоритма. Применимость алгоритма к данным. Универсальный алгоритм (69).
3.7.2. Теоремы о несуществовании алгоритма (70).
3.8. Массовые проблемы. Алгоритмическая разрешимость и неразрешимость (71).
Глава 4. ТЕОРИЯ СЛОЖНОСТИ АЛГОРИТМОВ (76).
4.1. Задачи, приводящие к понятию вычислительной сложности алгоритма (76).
4.2. Временная и емкостная (зональная) сложности алгоритма (79).
4.3. Время реализации алгоритмов с различной временной сложностью (80).
Глава 5. КЛАССЫ СЛОЖНОСТИ АЛГОРИТМОВ (83).
5.1. Классы Р, NP и P-SPACE. Соотношения между этими классами (83).
5.2. Полиномиальная сводимость и полиномиальная эквивалентность (85).
5.3. NP-полные задачи (87).
5.4. Задача ВЫПОЛНИМОСТЬ (ВЫП). Теорема Кука (88).
5.5. Основные NP-полные задачи (90).
5.6. Методы доказательства NP-полноты (92).
5.7. Метод сужения доказательства NP-полноты (97).
5.8. Анализ подзадач (98).
5.9. Задачи с числовыми параметрами. Псевдополиномиальные задачи (99).
5.10. «Похожие» задачи с разной вычислительной сложностью (102).
5.11. Задачи с числовыми параметрами и сильная NP-полнота (104).
Список литературы (109).
ИЗ ИЗДАНИЯ: В учебном пособии излагаются некоторые аспекты вычислительной сложности при работе с целыми числами и графами, а также описаны основные понятия теории алгоритмов и некоторые классы сложности алгоритмов. Приводятся алгоритмы работы с «длинными» целыми числами, которые не помещаются в одну ячейку компьютера, доказываются оценки числа шагов работы этих алгоритмов. Анализируется число шагов решения некоторых задач на графах при разных способах их задания. Отдельная глава посвящена описанию трех математических понятий алгоритма: рекурсивных функций, машин Тьюринга и их модификаций, нормальных алгоритмов Маркова. Доказываются теоремы о невозможности построения некоторых алгоритмов и об алгоритмической неразрешимости некоторых массовых проблем. Изложены основные понятия вычислительной сложности алгоритмов, даны сведения о современном делении алгоритмов на классы сложности.
Подготовлено с учетом требований Федерального государственного образовательного стандарта высшего образования.
Учебное пособие предназначено для студентов, обучающихся по направлениям подготовки, связанным с технологиями программирования и искусственным интеллектом, и изучающих дисциплины «Теория алгоритмов», «Теория вычислительной сложности алгоритмов», «Анализ алгоритмов». |
 |
