- •Содержание
- •Введение.
- •1. Основы анализа алгоритмов
- •1.1. Сравнительные оценки алгоритмов
- •1.2. Элементарные операции в формальной системе
- •1.3. Классы входных данных
- •1.4. Классификация алгоритмов по виду функции трудоемкости
- •1.5. Классификация скоростей роста. Асимптотический анализ функций
- •2. Оценка о (о большое)
- •3. Оценка (Омега)
- •1.6. Эффективность рекурсивных алгоритмов
- •1. Оценка (тета)
- •1.7. Анализ программ
- •1.8. Вопросы для самоконтроля
- •Классификация алгоритмов по виду функции трудоемкости.
- •2. Алгоритмы поиска и выборки
- •2.1. Последовательный поиск
- •2.2. Двоичный поиск
- •2.3. Задача выборки
- •2.4. Вопросы для самоконтроля
- •3.Алгоритмы сортировки
- •3.1. Сортировка трех чисел по месту
- •3.2. Сортировка вставками
- •3.3. Пузырьковая сортировка
- •3.4. Сортировка Шелла.
- •3.5. Корневая сортировка
- •3.6. Сортировка методом индексов
- •3.7. Быстрая сортировка (алгоритм Хоара)
- •3.8. Вопросы для самоконтроля
- •Сортировка Шелла.
- •Сортировка методом индексов.
- •4. Алгоритмы на графах
- •4.1. Основные понятия теории графов
- •4.2. Структуры данных для представления графов
- •4.3. Алгоритмы обхода вершин графа
- •4.3.1. Обход в глубину
- •4.3.2. Обход в ширину
- •4.4. Поиск остовного дерева минимального веса
- •4.4.1. Алгоритм Дейкстры – Прима
- •4.4.2. Алгоритм Крускала
- •4.5. Алгоритм поиска кратчайшего пути
- •4.6. Вопросы для самоконтроля
- •Структуры данных для представления графов.
- •5. Численные методы
- •5.1. Вычисление значений многочленов
- •5.2. Умножение матриц
- •5.2.1 Стандартный алгоритм умножения матриц
- •5.2.2. Умножение матриц по Винограду
- •5.2.3. Умножение матриц по Штрассену
- •5.3. Вопросы для самоконтроля
- •Стандартный алгоритм умножения матриц.
- •6. Алгоритмы сравнения с образцами
- •6.1. Сравнение строк
- •6.2. Алгоритм Кнута – Морриса – Пратта
- •6.3. Алгоритм Бойера - Мура
- •6.4. Вопросы для самоконтроля
- •7. Вычислительная геометрия
- •7.1. Основные понятия
- •7.2. Векторное произведение векторов
- •7.2.1. Ориентированная площадь треугольника
- •7 .3. Задача о выпуклой оболочке
- •7.3.1. Алгоритм Грэхема
- •7.3.2. Алгоритм Джарвиса
- •7.3.3. Рекурсивный алгоритм
- •7.4. Вопросы для самоконтроля
- •8. Задачи класса np
- •8.1. Примеры np-полных задач
- •8.1.1. Задача о коммивояжере
- •8.1.2. Задача о раскраске графа
- •8.1.3. Раскладка по ящикам
- •8.1.4 Упаковка рюкзака
- •8.1.5. Задача о суммах элементов подмножества
- •8.1.6. Задача о планировании работ
- •8.2. Приближенные эвристические решения nр-полных задач.
- •8.2.1. Жадные приближенные алгоритмы
- •8.2.2. Приближения в задаче коммивояжера
- •8.2.3. Приближения в задаче о раскладке по ящикам
- •8.2.4. Приближения в задаче об упаковке рюкзака
- •8.3. Вопросы для самопроверки
- •Приближения в задаче об упаковке рюкзака.
- •9. Динамическое программирование
- •Часть1--------------------
- •10. Метод ветвей и границ
- •Вопросы к зачету
- •Классификация алгоритмов по виду функции трудоемкости.
- •Приближения в задаче об упаковке рюкзака.
- •Динамическое программирование
- •Метод ветвей и границ. Литература
Вопросы к зачету
Понятие трудоемкости алгоритма в формальном базисе.
Обобщенный критерий оценки качества алгоритма.
Система обозначений в анализе алгоритмов - худший, лучший и средний случаи.
Классификация алгоритмов по виду функции трудоемкости.
Примеры количественных и параметрически–зависимых алгоритмов.
Обозначения в асимптотическом анализе функций.
Трудоемкость рекурсивных алгоритмов.
Алгоритм последовательного поиска. Оценка худшего, лучшего и среднего случая.
Алгоритм двоичного поиска. Оценка среднего случая.
Выборка k-го по величине значения.
Рекурсивный алгоритм выборки k-го по величине значения.
Алгоритмы сортировки 3-х чисел.
Сортировка вставками. Оценка наихудшего и среднего случая.
Пузырьковая сортировка. Оценка наихудшего случая.
Сортировка Шелла.
Корневая сортировка: достоинства и недостатки.
Сортировка методом индексов.
Быстрая сортировка. Анализ наихудшего случая.
Структуры данных для представления графов.
Алгоритмы обхода графа в глубину; в ширину.
Поиск минимального остовного дерева методом Дейкстры-Прима.
Поиск минимального остовного дерева методом Крускала.
Поиск кратчайшего пути.
Вычисление значений многочленов стандартным способом.
Вычисление значений многочленов по схеме Горнера.
Стандартный алгоритм умножения матриц.
Особенности умножения матриц по Винограду.
Основная идея алгоритма Штрассена для умножения матриц.
Варианты представления точки на плоскости.
Понятие ориентированной площади.
Определение выпуклости многоугольника.
Построение выпуклой оболочки алгоритмом Грэхема.
Построение выпуклой оболочки алгоритмом Джарвиса.
Рекурсивный алгоритм построения выпуклой оболочки.
Определение классов Р, NP, NP–полных классов задач.
Примеры NP–полных задач.
Эвристические алгоритмы раскладки по ящикам.
Приближения в задаче об упаковке рюкзака.
Динамическое программирование
Метод ветвей и границ. Литература
Т.Кормен, Ч. Лейзерсон, Р.Ривест. Алгоритмы: построение и анализ. - М.: МЦИМО, 1999.- 960с.
Дж. Макконнелл. Анализ алгоритмов. Вводный курс. - М.: Техносфера, 2002. –304с.
С.Гудман, С.Хидетниеми Введение в разработку и анализ алгоритмов. – М.: Мир, 1981. – 368с.
Альфред Вахо, Джон Хопкрофт, Джеффри Д. Ульман. Структуры данных и алгоритмы .: Пер. с англ. : М.: Издательский дом «Вильямс», 2003. – 384с.
Окулов С.М. Программирование в алгоритмах. - М.: Бином. Лаборатория знаний, 2002. –341 с.
Беллман Р., Дрейфус Р. Прикладные задачи динамического программирования: Пер. с англ. – М.: Наука, 1965– 457 с.