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






НазваниеАхо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов
страница1/5
Дата публикации10.02.2015
Размер0.72 Mb.
ТипДокументы
top-bal.ru > Информатика > Документы
  1   2   3   4   5
Алгоритмы и анализ сложности

Часть 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   2   3   4   5

Добавить документ в свой блог или на сайт

Похожие:

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов iconЛитература Ахо А., Ульман Дж. Теория синтаксического анализа, перевода...
Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1: Синтаксический анализ. М.: Мир, 1978. 612 с

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов iconАхо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции
Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции М.: Мир, 1978 2 тома, (612 с., 487 с.)

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов iconАлгоритм. Свойства алгоритмов. Виды алгоритмов. Формы записи алгоритмов
Научить записывать алгоритм, определять наличие алгоритмов в школьных предметах: биология, математика, русский язык

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

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов iconСписок литературы по «Теории алгоритмов» Основная
Игошин В. И. Задачи и упражнения по математической логике и теории алгоритмов: учеб пособие для студ высш учеб заведений. – М.: Академия,...

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов iconЭкзаменационные билеты и ответы для подготовки к итоговой аттестации...
Понятие алгоритма. Свойства алгоритма. Исполнители алгоритмов (назначение, среда, режим работы, система команд). Компьютер как формальный...

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов iconПрограмма «Logic» поддерживает четыре темы: вычисление логических...
С. В. Русакова и предназначен для изучения темы «Логические основы работы эвм». Он может быть использован преподавателями информатики...

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов iconУчебно-методический комплекс по дисциплине теория алгоритмов
Курс "Теория алгоритмов" рассчитан на один семестр и призван упрочить фундамент специальной подготовки будущих педагогов, способствовать...

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов iconУчебно-методический комплекс по дисциплине теория алгоритмов
Курс "Теория алгоритмов" рассчитан на один семестр и призван упрочить фундамент специальной подготовки будущих педагогов, способствовать...

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов icon«Построение индивидуальной траектории развития ребенка»
Сборник научно-методических и инструктивных материалов «Построение индивидуальной траектории развития ребенка» – Караганда: рио карагандинского...



Школьные материалы


При копировании материала укажите ссылку © 2015
контакты
top-bal.ru

Поиск