Скачать 0.72 Mb.
|
Алгоритмы и анализ сложности Часть 1 1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир,1979. 2. Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1990. 3. Гудман С., Хидетмиеми С. Введение в разработку и анализ алгоритмов. – М.: Мир, 1981. – 368 с. 4. Дейкстра Э. Дисциплина программирования. – М.: Мир, 1978. – 275 c. 5. Ершов А.П. Теоретическое программирование. – М.: Наука, 1977. 6. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. – М.: Мир, 1978. 7. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2001. 8. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. 9. Рейнгольд Э., Нивергельд Ю., Део Н. Комбинаторные алгоритмы. Теория и практика.– М.: Мир,1980. – 476 с. Методы анализа алгоритмов Алгоритм Свойства алгоритма: - дискретность - сходимость (конечность) - определенность (детерминированность) - массовость Вход и выход алгоритма Алгоритмическая система Частичные и конечные алгоритмы, общие требования Модель вычислений – однопроцессорная машина с произвольным доступом Элементарные шаги ЭШ для языка высокого уровня Другие вычислительные схемы Временная сложность (трудоемкость) Длина входа ![]() ![]() Асимптотическая трудоемкость при ![]() ![]() ![]() ![]() ![]() ![]() ![]() Типичные случаи для оценок трудоемкости: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() для случаев ![]() ![]() ![]() ![]() ![]() Соотношения для трудоемкостей: ![]() ![]() ![]() ![]() Формула Стирлинга для больших ![]() ![]() ![]() Важность снижения порядка трудоемкости. Пример с увеличением мощности компьютера в 1000 раз. Случаи ограниченных значений ![]() Трудоемкость в наихудшем ![]() ![]() Трудоемкость в среднем: для генеральной совокупности всех случаев ![]() с вероятностями ![]() ![]() ![]() Экспериментальное исследование сложности алгоритмов Емкостная сложность ![]() Эффективные алгоритмы Оптимальное решение, асимптотическая оптимальность Практическая эффективность Оценка нижней границы трудоемкости Алгоритмы, основанные на сравнениях (древовидные) Множество возможных решений ![]() Первое сравнение приводит к разделению всего множества решений на два подмножества и выбору одного из них. После 2 сравнений мы потенциально можем проверить ![]() ![]() ![]() Наша цель – выйти на одно из ![]() Гарантированно сделать это за ![]() ![]() ![]() это минимальная гарантированная трудоемкость в наихудшем для алгоритмов, основанных на сравнениях Примеры для поиска в неупорядоченном и упорядоченном массиве ![]() ![]() Для дихотомического поиска: в общем случае ![]() ![]() ![]() причем ![]() => требуется не более ![]() трудоемкость в наихудшем (и наилучшем): ![]() Минимальная гарантированная трудоемкость в наихудшем для задачи поиска, основанного на сравнениях: ![]() ![]() Трудоемкость в наихудшем будет минимальной, если каждое текущее множество решений всегда делится на подмножества, мощности которых отличаются на ![]() Рекуррентные и рекурсивные алгоритмы ![]() ![]() ![]() Рекуррентное представление сортировки прямым выбором Рекурсивные объекты и определения Рекурсивные алгоритмы: конечность, глубина рекурсии, емкостная сложность, когда нужно использовать Рекуррентные соотношения для определения трудоемкости Примеры для сортировок и поиска Переход к асимптотическим оценкам 1-я теорема о временной сложности алгоритмов Пусть ![]() Тогда: 1. ![]() ![]() 2. ![]() ![]() ![]() Доказательство: ![]() 1. При ![]() ![]() ![]() 2. Если ![]() ![]() ![]() ![]() Случай ![]() Примеры Числа Фибоначчи: ![]() Итеративный: ![]() ![]() Рекурсивный: ![]() ![]() 2-я теорема о временной сложности алгоритмов Пусть ![]() Тогда: 1. ![]() ![]() 2. ![]() ![]() 3. ![]() ![]() Доказательство для случая ![]() ![]() где ![]() 1. Если ![]() ![]() ![]() 2. Если ![]() ![]() 3. Если ![]() ![]() ![]() ![]() ![]() ![]() Случай ![]() Часто используемые идеи построения алгоритмов: «Разделяй и властвуй» Балансировка Сортировка Общая задача: - дан массив значений ![]() - необходимо найти такую перестановку ![]() ![]() ![]() ![]() Структура сортируемых информационных объектов: ключевые и информационные поля Цель сортировки – создание структуры для быстрого поиска Ключи в составе объектов или наборы пар <ключ><ссылка (указатель) на объект> ^ Инверсия элементов: ![]() ![]() Прямая и косвенная сортировка ![]() ![]() ![]() => ![]() => минимальная гарантированная трудоемкость в наихудшем для сортировки, основанной на сравнениях: ![]() ^ Серия – упорядоченная последовательность эл-тов массива Идея алгоритма Исходный массив A, рабочий массив D. void merge_sort(int b, int e) { int c = (b + e) / 2; if (c > b) merge_sort(b, c); if (e > c+1) merge_sort(c+1, e); слияние_серий(b, c, e); // из A в D копирование_элементов(b, e); // из D в A } Глубина рекурсии = ![]() ![]() |
![]() | Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1: Синтаксический анализ. М.: Мир, 1978. 612 с | ![]() | Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции М.: Мир, 1978 2 тома, (612 с., 487 с.) |
![]() | Научить записывать алгоритм, определять наличие алгоритмов в школьных предметах: биология, математика, русский язык | ![]() | |
![]() | Игошин В. И. Задачи и упражнения по математической логике и теории алгоритмов: учеб пособие для студ высш учеб заведений. – М.: Академия,... | ![]() | Понятие алгоритма. Свойства алгоритма. Исполнители алгоритмов (назначение, среда, режим работы, система команд). Компьютер как формальный... |
![]() | С. В. Русакова и предназначен для изучения темы «Логические основы работы эвм». Он может быть использован преподавателями информатики... | ![]() | Курс "Теория алгоритмов" рассчитан на один семестр и призван упрочить фундамент специальной подготовки будущих педагогов, способствовать... |
![]() | Курс "Теория алгоритмов" рассчитан на один семестр и призван упрочить фундамент специальной подготовки будущих педагогов, способствовать... | ![]() | Сборник научно-методических и инструктивных материалов «Построение индивидуальной траектории развития ребенка» – Караганда: рио карагандинского... |