Разработка системы задач (алгоритмы-программы) по дискретной математике

| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: новшество, поняття реферат
| Добавил(а) на сайт: Офелия.

Общая схема
Даны N упорядоченных множеств U1 U2,..., Un (N - известно), и требуется построить вектор А=(а1 а2, ..., аn), где a1?U1, a2?U2, ..., an?Un, удовлетворяющий заданному множеству условий и ограничений.
В алгоритме перебора вектор А строится покомпонентно слева

направо. Предположим, что уже найдены значения первых (к-1)

компонент, A=(a1, a2, ..., a(k-1)), ?, ..., ?), тогда заданное множество

условий ограничивает выбор следующей компоненты аk некоторым

множеством SkCUk. Если Sk[ ] (пустое), мы вправе выбрать в

качестве ак наименьший элемент Sk и перейти к выбору ^/^ "^выборы п«я»,
(к+1) компоненты и так далее. Однако /[ + Д Jfcv при данном а, если условия условия а,, ^иаз таковы, что Sk оказалось пустым, то мы возвращаемся к выбору
(к-1) компоненты, отбрасываем а(k-1) и выбираем в качестве нового a(k-1) тот элемент S(k-i), который непосредственно следует за только что отброшенным. Может оказаться, что для нового a(k-1) условия задачи допускают непустое Sk, и тогда мы пытаемся снова выбрать элемент ак. Если невозможно выбрать a(k-1), мы возвращаемся еще на шаг назад и выбираем новый элемент а(к-2) и так далее.

Графическое изображение - дерево поиска. Корень дерева (0 уровень) есть пустой вектор. Его сыновья суть множество кандидатов для выбора а1 и, в общем случае, узлы k-го уровня являются кандидатами на выбор ак при условии, что а1, а2, ..., a(k-1) выбраны так, как указывают предки этих узлов. Вопрос о том, имеет ли задача решение, равносилен вопросу, являются ли какие-нибудь узлы дерева решениями. Разыскивая все решения, мы хотим получить все такие узлы.
Рекурсивная схема реализации алгоритма, procedure Backtrack(Beктop,i); begin if then else begin ; for a?Si do Васкtrаск(вектор| | a,i+l); end; end;
Оценка временной сложности алгоритма. Данная схема реализации перебора приводит к экспоненциальным алгоритмам. Действительно, Пусть все решения имеют длину N, тогда исследовать требуется порядка | Si| *| S2| *...*| SN| узлов дерева. Если значение S; ограничено некоторой константой С, то получаем порядка CN узлов.

Поиск данных.

Логарифмический(бинарный) поиск

Логарифмический (бинарный или метод деления пополам) поиск данных применим к сортированному множеству элементов а1 < а2 < ... < ап, размещение которого выполнено на смежной памяти. Для большей эффективности поиска элементов надо, чтобы пути доступа к ним стали более короткими, чем просто последовательный перебор. Наиболее очевидный метод: начать поиск со среднего элемента, т.е. выполнить сравнение с элементом а. Результат сравнения позволит определить, в какой половине последовательности а{, а2,..., а, 1+„ ,,..., ап продолжить поиск, применяя к ней ту же процедуру, и т.д. Основная идея бинарного поиска довольно проста, однако «для многих хороших программистов не одна попытка написать правильную программу закончилась неудачей». Чтобы досконально разобраться в алгоритме, лучше всего представить данные ах < а2 < ... < ап в виде двоичного дерева сравнений, которое отвечает бинарному поиску.
Двоичное дерево называется деревом сравнений , если для любой его вершины
(корня дерева или корня поддерева) выполняется условие:

{Вершины левого поддерева}