Ответы на экзаменационные вопросы. Введение
Скачать 389.99 Kb.
|
5.4. Переход к временным оценкам Сравнение двух алгоритмов по их функции трудоемкости вносит некоторую ошибку в получаемые результаты. Основной причиной этой ошибки является различная частотная встречаемость элементарных операций, порождаемая разными алгоритмами и различие во временах выполнения элементарных операций на реальном процессоре. Таким образом, возникает задача перехода от функции трудоемкости к оценке времени работы алгоритма на конкретном процессоре: Дано: FA(DA) - трудоёмкость алгоритма требуется определить время работы программной реализации алгоритма – TA(DA). На пути построения временных оценок мы сталкиваемся с целым набором различных проблем. Укажем основные:
Попытки различного подхода к учету этих факторов привели к появлению разнообразных методик перехода к временным оценкам. 1) Пооперационный анализ Идея пооперационного анализа состоит в получении пооперационной функции трудоемкости для каждой из используемых алгоритмом элементарных операций с учетом типов данных. Следующим шагом является экспериментальное определение среднего времени выполнения данной элементарной операции на конкретной вычислительной машине. Ожидаемое время выполнения рассчитывается как сумма произведений пооперационной трудоемкости на средние времена операций: TA(N) = å Faопi(N) * `t опi 2) Метод Гиббсона Метод предполагает проведение совокупного анализа по трудоемкости и переход к временным оценкам на основе принадлежности решаемой задачи к одному из следующих типов:
Далее на основе анализа множества реальных программ для решения соответствующих типов задач определяется частотная встречаемость операций, создаются соответствующие тестовые программы, и определяется среднее время на операцию в данном типе задач –`t тип задачи. На основе полученной информации оценивается общее время работы алгоритма в виде: TA(N) = FA(N) *`t тип задачи 3) Метод прямого определения среднего времени В этом методе так же проводится совокупный анализ по трудоемкости – определяется FA(N), после чего на основе прямого эксперимента для различных значений Nэ определяется среднее время работы данной программы Tэ и на основе известной функции трудоемкости рассчитывается среднее время на обобщенную элементарную операцию, порождаемое данным алгоритмом, компилятором и компьютером – `tа. Эти данные могут быть (в предположении об устойчивости среднего времени по N) интерполированы или экстраполированы на другие значения размерности задачи следующим образом: `tа= Tэ(Nэ) / FA(Nэ), T(N) = `tа * FA(N). 5.5. Сложностные классы задачТеоретический предел трудоемкости задачиРассматривая некоторую алгоритмически разрешимую задачу, и анализируя один из алгоритмов ее решения, мы можем получить оценку трудоемкости этого алгоритма в худшем случае – ¦ˆA(DA)=O(g(DA)). Такие же оценки мы можем получить и для других известных алгоритмов решения данной задачи. Рассматривая задачу с этой точки зрения, возникает резонный вопрос: какова оценка сложности самого «быстрого» алгоритма решения данной задачи в худшем случае? Очевидно, что это оценка самой задачи, а не какого либо алгоритма ее решения. Таким образом, мы приходим к определению понятия функционального теоретического нижнего предела трудоемкости задачи в худшем случае: Fthlim= min { (Fa^ (D)) } Если мы можем на основе теоретических рассуждений доказать существование и получить оценивающую функцию, то мы можем утверждать, что любой алгоритм, решающий данную задачу работает не быстрее, чем с оценкой Fthlim в худшем случае: Fa^ (D) = (Fthlim) Приведем ряд примеров: 1) Задача поиска максимума в массиве A=(a1,…,an) – для этой задачи, очевидно должны быть просмотрены все элементы, и Fthlim=Q (n). 2) Задача умножения матриц - для этой задачи можно сделать предположение, что необходимо выполнить некоторые арифметические операции со всеми исходными данными, что приводит нас к оценке Fthlim=Q (n2). С началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на ее размерность. Какие задачи могут быть решены на ЭВМ за реальное время? Ответ на этот вопрос был дан в работах Кобмена (Alan Cobham, 1964), и Эдмнодса (Jack Edmonds, 1965), где были введены сложностные классы задач. Класс P (задачи с полиномиальной сложностью) Задача называется полиномиальной, т.е. относится к классу P, если существует константа k и алгоритм, решающий задачу с Fa(n)=O(nk), где n - длина входа алгоритма в битах n = |D| . Задачи класса P – это интуитивно, задачи, решаемые за реальное время. Отметим следующие преимущества алгоритмов из этого класса:
Таким образом, задачи класса P есть уточнение определения «практически разрешимой» задачи. Класс NP (полиномиально проверяемые задачи) Представим себе, что некоторый алгоритм получает решение некоторой задачи – соответствует ли полученный ответ поставленной задаче, и насколько быстро мы можем проверить его правильность? Содержательно задача относится к классу NP, если ее решение некоторым алгоритмом может быть быстро (полиномиально) проверено. Проблема P = NPПосле введения в теорию алгоритмов понятий сложностных классов Эдмондсом (Edmonds, 1965) была поставлена основная проблема теории сложности – P = NP? Словесная формулировка проблемы имеет вид: можно ли все задачи, решение которых проверяется с полиномиальной сложностью, решить за полиномиальное время? Очевидно, что любая задача, принадлежащая классу P, принадлежит и классу NP, т.к. она может быть полиномиально проверена – задача проверки решения может состоять просто в повторном решении задачи. На сегодня отсутствуют теоретические доказательства как совпадения этих классов (P=NP), так и их несовпадения. Предположение состоит в том, что класс P является собственным подмножеством класса NP, т.е. NP \ P не пусто. Класс NPC (NP – полные задачи)Понятие NP – полноты основывается на понятии сводимости одной задачи к другой. Сводимость может быть представлена следующим образом: если мы имеем задачу 1 и решающий эту задачу алгоритм, выдающий правильный ответ для всех индивидуальных задач, составляющих задачу, а для задачи 2 алгоритм решения неизвестен, то если мы можем переформулировать (свести) задачу 2 в терминах задачи 1, то мы решаем задачу 2. Таким образом, если задача 1 задана множеством индивидуальных задач DA1, а задача 2 – множеством DA2 , и существует функция fs (алгоритм), сводящая конкретную постановку задачи 2 (dА2) к конкретной постановке задачи 1(dА1): fs(d(2)Î DA2) = d(1)Î DA1, то задача 2 сводима к задаче 1. Если при этом FA (fs) = O(nk), т.е. алгоритм сведения принадлежит классу P, то говорят, что задача 1 полиномиально сводится к задаче 2. Принято говорить, что задача задается некоторым языком, тогда если задача 1 задана языком L1, а задача 2 – языком L2, то полиномиальная сводимость обозначается следующим образом: L2 £ p L1. Определение класса NPC (NP-complete) или класса NP-полных задач требует выполнения следующих двух условий: во-первых, задача должна принадлежать классу NP (L Î NP), и, во-вторых, к ней полиномиально должны сводиться все задачи из класса NP (Lx £ P L, для каждого Lx Î NP). Для класса NPC доказана следующая теорема: Если существует задача, принадлежащая классу NPC, для которой существует полиномиальный алгоритм решения (F = O(nk)), то класс P совпадает с классом NP, т.е. P=NP. Схема доказательства состоит в сведении любой задачи из NP к данной задаче из класса NPC с полиномиальной трудоемкостью и решении этой задачи за полиномиальное время (по условию теоремы). В настоящее время доказано существование сотен NP– полных задач, но ни для одной из них пока не удалось найти полиномиального алгоритма решения. В настоящее время исследователи предполагают следующее соотношение классов, показанное на рис. – P ¹ NP, то есть NP \ P ¹ 0, и задачи из класса NPC не могут быть решены (сегодня) с полиномиальной трудоемкостью. 5.6. П  остроение эффективных алгоритмов. Метод декомпозиции Рассмотрим один из методов, применяемых для снижения сложности алгоритмов. Пусть необходимо решить индивидуальную задачу размером N. Попробуем разбить эту задачу на подзадачи меньшего размера. Если разбивать некуда, то решаем задачу минимального размера очевидным способом. Разработаем процедуру, позволяющую решить исходную задачу размером N, используя решения подзадач меньшего размера. Подзадачи будем решать аналогичным способом. Описанный подход называется методом декомпозиции. С его помощью можно получить эффективные алгоритмы решения многих массовых проблем. Пример. Поиск минимального и максимального элемента массива. Вход: Натуральное число N, массив X[1..N]. Выход: Xmax, Xmin - соответственно максимальный и минимальный элемент массива X. Очевидно, что за размер задачи можно принять число N - количество элементов массива X. Будем считать характерной операцией операцию сравнения двух чисел. Первый вариант решения. Будем просматривать массив слева направо, сравнивая каждый элемент массива с наименьшим и наибольшим значением, при необходимости обновляя наименьший и наибольший элемент. Запишем алгоритм строго. (int, int) minmax (int N, array [1...N] of int X) { int MIN, MAX; MIN = X(1); MAX = X(1); for I = 2 to N { if (MIN < X(I)) MIN = X(I); if (MAX > X(I)) MAX = X(I); } return(MIN,MAX); } Сложность этого алгоритма: T(N)=2*N-2 Второй вариант решения. Применим метод декомпозиции. Если массив состоит из двух элементов, то находим максимальный и минимальный элемент этого массива простым сравнением этих двух чисел. Если в массиве больше двух элементов, то: разделим массив пополам, найдем максимальный и минимальный элементы в каждой половине. Сравнив два найденных максимальных элемента, найдем максимальный элемент массива. Сравнив два найденных минимальных элемента, найдем минимальный элемент массива. Искать максимальный и минимальный элементы в половинах будем тем же способом. Запишем алгоритм строго. (int, int) MINMAX (int N, array [1...N] of int X) { int MIN1, MIN2, MAX1, MAX2, MIN, MAX; array [1...N/2+1] of int A, B; if (N == 1) return(X[1],X[2]); else if (N == 2) { if (X[1] < X[2]) return(X[1],X[2]); else return(X[2],X[1]); } else { A[1...N/2]=X[1...N/2]; B[1...N-N/2]=X[N/2+1...N]; (MIN1,MAX1)=MINMAX(N/2, A); (MIN2,MAX2)=MINMAX(N-N/2, B); if (MIN1 < MIN2) MIN = MIN1; else MIN = MIN2; if (MAX1 < MAX2) MAX = MAX2; else MAX = MAX1; return(MIN,MAX); } } Вычислим сложность приведенного алгоритма. Пусть n=2**k k=1 (n=2): T(2)=1; k=2 (n=4): T(4)=(1*2)+2=4; k=3 (n=8): T(8)=((1*2)+2)*2+2=10; . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . k=r (n=2r): T(2r)=(…((1*2)+2)*2+2…)*2+2=2r-1+2r-1+2r-2+2r-3+…+2 Перед нами сумма геометрической прогрессии. Сумма членов геометрической прогрессии: S=a0-an/1-q=(2r-2)/(2-1)=2r-2 T(2r)=2r+2r-1-2 Но r=log2n, следовательно T(n)=n+n/2-2=3n/2-2. Очевидно, что сложность второго алгоритма меньше, чем сложность первого алгоритма. При помощи метода декомпозиции получен более эффективный алгоритм. |
Похожие:
 | Ответы на экзаменационные вопросы по истории. Вопросы и ответы на экзаменационные вопросы по истории. | | Экзаменационные вопросы по культурологии А. П. Позднякова. Ботаника, Зоология, Анатомия, Общая биология конспекты уроков, лабораторные, контрольные работы, интересные статьи,... |
| Экзаменационные вопросы с ответами по физкультуре Вопросы и ответы к теоретической части экзамена по физкультуре | | Ответы на экзаменационные вопросы по литературе для 9 класса Вопросы из вариантов I и II (общеобразовательная школа, 31 и 21 билет соответственно; "старые", "Вестник образования" №4 февраль... |
| Экзаменационные билеты для 9кл. (2006) и примерные ответы по билетам... Биология урок, тест, ответы, билеты, биология человека, общая биология, егэ 2006, школа, олимпиада, тестирование биология, экзамен,... |  | Экзаменационные вопросы по бжд для студентов специальности 110203.... Экзаменационные вопросы по бжд для студентов специальности 190603. 65 – «Сервис транспортных и технологических машин и оборудования... |
| Экзаменационные вопросы по нормальной физиологии Содержит ответы на 143 экзаменационных вопроса по охране труда, а также курсы лекций по охране труда | | Экзаменационные вопросы по истории и философии науки Курс «История и философия науки» Программы курса и экзаменационные вопросы по первым двум частям курса представлены ниже |
| Экзаменационные билеты по истории России (9 класс) Девятиклассники!... Билет № Вопрос Древняя Русь в IX – начале XII в.: возникновение государства, древнерусские князья и их деятельность | | Экзаменационные вопросы интернет-курсов интуит (intuit): 192. Введение... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования |
| Экзаменационные вопросы интернет-курсов интуит (intuit): Введение... Анооспо «Оренбургский колледж менеджмента, туризма и гостиничного сервиса» (техникум) | | Экзаменационные билеты для 9кл. (2006) и примерные ответы по билетам... А. П. Позднякова. Ботаника, Зоология, Анатомия, Общая биология конспекты уроков, лабораторные, контрольные работы, интересные статьи,... |
| Экзаменационные билеты для 9кл. (2006) и примерные ответы по билетам... А. П. Позднякова. Ботаника, Зоология, Анатомия, Общая биология конспекты уроков, лабораторные, контрольные работы, интересные статьи,... | | Содержание введение Глава I. Из истории создания религиозных учебных заведений А. П. Позднякова. Ботаника, Зоология, Анатомия, Общая биология конспекты уроков, лабораторные, контрольные работы, интересные статьи,... |
| Экзаменационные билеты по литературе для 9 класса Билет №1 «Слово о полку Игореве» На этапе окончания основной школы девятиклассники, выбравшие экзамен по литературе, сдают его, как правило, в устной форме (собеседование,... | | Ответы на экзаменационные вопросы интернет-курсов интуит (intuit): 138. Микроэкономика фирмы Администрация региона Х ввела запрет на вывоз бананов со своей территории (бананы – главный продукт потребления жителей региона).... |
