Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов

Алгоритмы и анализ сложности Часть 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 с.)
	Алгоритм. Свойства алгоритмов. Виды алгоритмов. Формы записи алгоритмов Научить записывать алгоритм, определять наличие алгоритмов в школьных предметах: биология, математика, русский язык		Анализ характеристик алгоритмов сжатия изображений на основе иерархического...
	Список литературы по «Теории алгоритмов» Основная Игошин В. И. Задачи и упражнения по математической логике и теории алгоритмов: учеб пособие для студ высш учеб заведений. – М.: Академия,...		Экзаменационные билеты и ответы для подготовки к итоговой аттестации... Понятие алгоритма. Свойства алгоритма. Исполнители алгоритмов (назначение, среда, режим работы, система команд). Компьютер как формальный...
	Программа «Logic» поддерживает четыре темы: вычисление логических... С. В. Русакова и предназначен для изучения темы «Логические основы работы эвм». Он может быть использован преподавателями информатики...		Учебно-методический комплекс по дисциплине теория алгоритмов Курс "Теория алгоритмов" рассчитан на один семестр и призван упрочить фундамент специальной подготовки будущих педагогов, способствовать...
	Учебно-методический комплекс по дисциплине теория алгоритмов Курс "Теория алгоритмов" рассчитан на один семестр и призван упрочить фундамент специальной подготовки будущих педагогов, способствовать...		«Построение индивидуальной траектории развития ребенка» Сборник научно-методических и инструктивных материалов «Построение индивидуальной траектории развития ребенка» – Караганда: рио карагандинского...