Деревья

Линейные массивы можно также использовать для компактного представления деревьев определенного вида.Пусть Т-дерево с М вершинами , в котором вершины помечены целыми числами 1,2,... , М. Говорят,что дерево Т рекурсивно помечено( или рекурсивное), если каждая вершина с меткой больше 1 смежа ровно с одной вершиной , у которого метка имеет меньшее зна чение. На рис. 13. Приведены примеры рекурсивного дерева Т₁ и нерекурсивного дерева Т₂

На примере линейного массива ДЕРЕВО показано ,как комактно можно представить рекурсивное дерево Т₁; ДЕРЕВО (I)=J обозначает , что вершина I смежна вершине J.

1 2 3 4 5 6 7 8 9 10

0 1 1 1 2 4 5 4 5 1

TREE

Методы разработки алгоритмов

Существует три основных метода разработки алгоритмов:

1) частных целей

2) подъема

3) отрабатывания назад

Метод частных целей

Метод частных целей основан на сведении трудной задачи к последовательности простых задач. Но и как большинство других методов его не всегда легко перенести на конкретную задачу.

Осмысленный выбор более простых задач: дело искусства, а не интуиции.

Более того, не существует общего набора правил для определения класса задач, которые можно решить с помощью такого подхода.

Метод подъема

Алгоритм начинается с принятия начального предположения или вычисления начального значения задачи. Затем переходим от начального значения к лучшему. Когда алгоритм достигает точки из которой нельзя перейти, он останавливается.

Метод отработки назад

Метод обработки назад начинается с цели (решения) и движемся обратно к начальной постановки задачи. Затем, если действия обратимы, движемся обратно от постановки к решению.

Пример:

Подойдем к задаче с помощью метода отрабатывания назад. На основании этого метода мы задаемся целью (вопросом): с какого расстояния мы можем пересечь пустыню имея запас горючего точно для k баков.

k=1,2,3…n пока не найдем такое целое n, что позволяет пройти весь путь 1000км.

Мы поставим частную цель, так как не смогли сразу решить исходную задачу. Мы не задаем вопрос: сколько топлива на всю дистанцию? Вместо этого, мы задаемся вопросом: какое расстояние можно проехать на заданном топливе.

На первый вопрос ответить можно лишь тогда , когда ответ на второй вопрос будет не меньше 1000л.

Эвристики (гипотезы)

Эврист алгоритм определяющийся, как алгоритм со следующими свойствами:

1) обычно находит хорошие, но не обязательно оптимальные решения

2) его можно быстрее и проще реализовать, чем любой известный точный алгоритм

3) не существует задачи, которой нельзя описать эвристическим алгоритмом.

(многие основаны на методе частных целей и методе подъема)

Общий подход к построению эвристического алгоритма заключается в перечислении требований к общему решению и разделяется на два класса:

1) легко удовлетворять

2) не так легко удовлетворять

1) должны быть удовлетворены

2) те, по отношению к которым можно пойти на компромисс

Цель: Создать алгоритм, удовлетворяющий первые требования, но не обязательно вторые.

Пример:

13- оптимальных проходов 14-оптимальных проходов

В этом алгоритме реализована идея подъема, однако задача сведена к набору частных целей: найти на каждом шаге самый «дешевый» город.

Оптимальное решение имеет два свойства:

1) состоит из множества ребер, вместе представляющих тур (5 ребер)

(его гарантируем)

2) Стоимость никакого Другова не будет меньше заданного (идем на компромисс)

Программирование с отходом назад

Организованный исчерпывающий поиск, который часто позволяет избежать исследование всех возможностей. Он удобен для решения задач, требующих проверки потенциально большого конечного числа решений.

Решение:

Мы промоделируем каждую возможную комбинацию из N ( 0 и 1 на i-м месте)

1, если вкл. и 0, если выкл.

Моделируем с помощью второго дерева.

Рекурсия

В математике и программировании это метод определения или выражения функции или процедуры для решения задачи посредством той же функции или процедуры.

Рекуррентные соотношения - это соотношения, которые выражают значение функции при помощи других значений, вычисленных для меньших аргументов.

Для вычисления нужно произвести рекурсивное обращение и вычислить , сделать N- рекурсивных обращений.

Принято говорить, что глубина рекурсии, требуемая для вычисления , равна N.

В машинных программах глубина рекурсии соответствует самой длинной последовательности обращений к процедуре требуемой для вычисления функции. Поэтому, глубина рекурсии – мера вычислительной сложности, рекурсивно определенной функции.

Глубина рекурсии ряда Фибоначчи равна (N-3)

Функция может быть дважды рекурсивна, если сама функция и один из ее аргументов определены через самих себя.

Пример: функция Аккермана.

Массив:

int a [10] char char a [10] [10]

Алгоритмы машины и математики

Не существует алгоритма сортировки, который был бы.

Эффективность зависит от:

1) какое число сортируемых элементов

2) все ли они могут быть помещены доступную оперативную память

3) до какой степени они отсортированы

4) какой диапазон сортируемых элементов

5) какова длина, сложность и требования к памяти алгоритма сортировки

6) предполагается ли добавление или исключение

Сортировка

Сортировка стала важным предметом вычислительной математики в основном потому, что она отнимает значительную часть времени работы ЭВМ. Осознание того, что 25% всего времени вычислений расходуется на сортировку данных , придает особое значение эффективным алгоритмам сортировки.

К сожалению ,нет алгоритма сортировки, который был бы наилучшим в любом случае. Трудно даже решить, какой алгоритм будет лучшим в данной ситуации, так как эффективность алгоритма сортировки может зависеть от множества факторов, например от того ,(1) каково число сортируемых элементов; (2) все ли элементы могут быть помещены в доступную оперативную память;(3) до какой степени элементы уже отсортированы; (4) каковы диапазон и распределение значений сортируемых элементов ; (5) записаны ли элементы на диске, магнитной ленте или перфокартах; (6) каковы длина , сложность и требования к памяти алгоритма сортировки ; (7) предполагается ли , что элементы будут периодически исключаться или добавляться ;(8) можно ли элементы сравнивать параллельно.

Очевидно, что с отсортированными данными работать легче , чем с произвольно расположенными. Когда элементы отсортированы, их проще найти (как в телефонном справочнике), обновить , исключить, включить и слить воедино. На отсортированных данных легче определить, имеются ли пропущенные элементы (как в колоде игральных карт) , и удостовериться , что все элементы были проверены. Легче также найти общие элементы двух множеств , если они оба отсортированы. Сортировка применяется при трансляции программ , когда составляются таблицы символов ; она также является важным средством для ускорения работы практически любого алгоритма , в котором часто нужно обращаться к определенным элементам.

Обычно сортируемые элементы представляют собой записи данных определенного вида. Каждая запись имеет поле ключа и поле информации . Поле ключа содержит положительное число ,обычно целое, и записи упорядочиваются по значению ключа.

В этом разделе мы рассматриваем два из наиболее эффективных алгоритмов сортировки , быстрой сортировки и сортировки пирамидой (QUICKSORT и HEAPSORT) , и устанавливаем теоретически неулучшаемые границы для всех алгоритмов сортировки с помощью сравнений. В других разделах обсуждаются еще два алгоритма сортировки : сортировка простыми включениями (SIS) и параллельная сортировка (PARSORT).