Анализ эффективности алгоритмов

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ  ИНСТИТУТ

1. Кафедра прикладной информатики

 

 

КУРСОВАЯ РАБОТА

 

по дисциплине «Теоретические основы информатики»

 

 

на тему

«Анализ эффективности алгоритмов»

 

Вариант № 11

 

 

 

 

2. Исполнитель:

3. Шнейдер Яков Александрович

«Бизнес - информатика»

Курс 1

Группа: вечерняя

№ зачетной книжки: 11улд12311

 

Руководитель:

Никифорова С.В.

 

 

 

 

Владимир

2012 

 

Содержание

Введение 3

Теоретическая часть 4

1. Измерение эффективности алгоритмов 4
2. О-сложность алгоритмов 7

Практическая часть 14

Задание 1 14

Задание 2 16

Задание 3 20

Задание 4 21

Заключение 25

Список использованной литературы 26

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Цель исследования: Выявить и систематизировать материалы по теме: «Анализ эффективности алгоритмов».

Задачи Исследования:

• Изучить литературу по теме исследования;
• Систематизировать теоретический материал;
• Выполнить практическую часть, состоящую их 4-х заданий.

    Задание 1. Расчет информационной емкости документов предметной          области.

    Задание 2. Построение инфологических моделей предметной области.

     Задание 3. Формирование информационных запросов к реляционной базе данных с помощью операций реляционной алгебры.

     Задание 4. Применение методов поиска и сортировки данных.

 

 

 

 

 

 

 

 

 

 

 

 

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Измерение эффективности  алгоритмов

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

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

Выбирая алгоритм, оцените  его эффективность.

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

Сравнение эффективности  алгоритмов должно быть сосредоточено  на их существенных различиях.

Анализ алгоритмов (analysis с algorithms) - это область компьютерных наук изучающая способы сравнения  эффективности разных методов решения задач. В этом определении использован термин "метод решения задачи", а не "программа". Следует подчеркнуть, что анализ алгоритмов, как правило, исследует существенные различия эффективности, которые обусловлены собственно методами решения задач, а не остроумными программистскими трюками. Изощренные приемы кодирования, позволяющие снизить стоимость вычислений, чаще всего снижают читабельность программы, тем самым повышая затраты на ее сопровождение и модификацию. Сравнение алгоритмов должно быть сосредоточено на их существенных различиях, поскольку именно их эффективность является основным фактором, определяющим общую стоимость решения, если два алгоритма выполняются несколько часов, а разница между временем их выполнения составляет несколько секунд, их эффективность одинакова.

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

Как сравнить быстродействие двух алгоритмов, решающих одну и ту же зав дачу? Для этого их можно  запрограммировать на языке C++ и  запустить обе программы. У этого  подхода есть три существенных недостатка.

Три недостатка подхода, основанного на сравнении  программ

1. Как запрограммированы  алгоритмы?

Допустим, алгоритм А1 выполняется  быстрее, чем алгоритм А2. Это может  быть связано с тем, что программа, реализующая алгоритм ai, просто лучше  написана. Следовательно, сравнивая время выполнения программ, мы на самом деле сравниваем реализации алгоритмов, а не сами алгоритмы. Реализации алгоритмов сравнивать бессмысленно, поскольку они очень сильно зависят от стиля программирования и не позволяют определить, какой из алгоритмов эффективнее.

2. На каком компьютере  должны выполняться программы?

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

3. Какие данные вводятся  в программы?

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

Анализ алгоритма не должен зависеть от конкретных реализаций, компьютеров и данных.

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

Основной способ оценки эффективности алгоритма - подсчет  его операций.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

O-сложность алгоритмов

O(1) 
Большинство операций в программе выполняются только раз или только несколько раз. Алгоритмами константной сложности. Любой алгоритм, всегда требующий независимо от размера данных одного и того же времени, имеет константную сложность.

О(N) 
Время работы программы линейно обычно когда каждый элемент входных данных требуется обработать лишь линейное число раз.

О(N2), О(N3), О(Nа) 
Полиномиальная сложность. О(N2)-квадратичная сложность, О(N3)- кубическая сложность

О(Log(N)) 
Когда время работы программы логарифмическое, программа начинает работать намного медленнее с увеличением N. Такое время работы встречается обычно в программах, которые делят большую проблему в маленькие и решают их по отдельности.

O(N*log( N)) 
Такое время работы имеют те алгоритмы, которые делят большую проблему в маленькие, а затем, решив их, соединяют их решения.

O(2N) 
Экспоненциальная сложность. Такие алгоритмы чаще всего возникают в результате подхода именуемого метод грубой силы.

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

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

Определение сложности  алгоритма в основном сводится к анализу циклов и рекурсивных вызовов.

Например, рассмотрим алгоритм обработки элементов массива. 
For i:=1 to N do 
Begin 
... 
End;

Сложность этого алгоритма O(N), т.к. тело цикла выполняется N раз, и сложность тела цикла равна O(1).

Если один цикл вложен в другой и оба цикла зависят от размера одной и той же переменной, то вся конструкция характеризуется квадратичной сложностью. 
For i:=1 to N do 
For j:=1 to N do  
Begin 
... 
End; 
Сложность этой программы О(N2).

Давайте оценим сложность  программы "Тройки Пифагора"

Существуют два способа  анализа сложности алгоритма: восходящий (от внутренних управляющих структур к внешним) и нисходящий (от внешних  и внутренним).

O(H)=O(1)+O(1)+O(1)=O(1); 
O(I)=O(N)*(O(F)+O(J))=O(N)*O(доминанты условия)=О(N); 
O(G)=O(N)*(O(C)+O(I)+O(K))=O(N)*(O(1)+O(N)+O(1))=O(N2); 
O(E)=O(N)*(O(B)+O(G)+O(L))=O(N)* O(N2)= O(N3); 
O(D)=O(A)+O(E)=O(1)+ O(N3)= O(N3)

Сложность данного алгоритма O(N3).

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

Эта информация может  использоваться программистом для  построения более эффективной программы  следующим образом. Прежде всего  можно попытаться сократить глубину  вложенности повторений. Затем следует рассмотреть возможность сокращения количества операторов в циклах с наибольшей глубиной вложенности. Если 90% времени выполнения составляет выполнение внутренних циклов, то 30%-ное сокращение этих небольших секций приводит к 90%*30%=27%-му снижению времени выполнения всей программы.

Это наиболее простой  пример.

Анализом эффективности  алгоритмов занимается отдельный раздел математики и найти наиболее оптимальную  функцию бывает не так - то и просто.

Оценим алгоритм бинарного поиска в массиве - дихотомию.

Суть алгоритма: идем к середине массива и ищем соответствие ключа значению срединного элемента. Если нам не удается найти соответствия, мы смотрим на относительный размер ключа и значение срединного элемента и затем перемещаемся в нижнюю или верхнюю половину списка. В этой половине снова ищем середину и опять сравниваем с ключом. Если не получается, снова делим на половину текущий интервал.

function search(low, high, key: integer): integer; 
var 
mid, data: integer; 
begin 
while low<=high do 
begin 
mid:=(low+high) div 2; 
data:=a[mid]; 
if key=data then 
search:=mid 
else 
if key < data then 
high:=mid-1 
else 
low:=mid+1; 
end; 
search:=-1; 
end;

Решение:

Первая итерация цикла имеет  дело со всем списком. Каждая последующая  итерация делит пополам размер подсписка. Так, размерами списка для алгоритма являются

n n/21 n/22 n/23 n/24 ... n/2m

В конце концов будет такое целое m, что

n/2m<2 или n<2m+1

Так как m - это первое целое, для  которого n/2m<2, то должно быть верно

n/2m-1>=2 или 2m=<n

Из этого следует, что  
2m=<n<2m+1 
Возьмем логарифм каждой части неравенства и получим 
m=<log2n=x<m+1 
Значение m - это наибольшее целое, которое =<х. 
Итак, O(log2n).

Обычно решаемая задача имеет естественный "размер" (обычно количество данных ею обрабатываемых) которое мы называем N. В конечном итоге нам бы хотелось получить выражение для времени, необходимого программе для обработки данных размера N, как функцию от N. Обычно на интересует средний случай - ожидаемое время работы программы на "типичных" входных данных, и худший случай - ожидаемое время работы программы на самых плохих входных данных.

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

Несколько важных причин такого рода анализа: 
1. Программы, написанные на языке высокого уровня, транслируются в машинные коды, и понять сколько времени потребуется для выполнения того или иного оператора может быть трудно. 
2. Многие программы очень чувствительны к входным данным, и их эффективность может очень сильно от них зависеть. Средний случай может оказаться математической фикцией не связанной с теми данными на которых программа используется, а худший случай маловероятен.

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

O-анализ сложности  получил широкое распространение  во многих практических приложениях.  Тем не менее необходимо четко  понимать его ограниченность.

К основным недостаткам подхода  можно отнести следующие: 
1) для сложных алгоритмов получение O-оценок, как правило, либо очень трудоемко, либо практически невозможно, 
2) часто трудно определить сложность "в среднем", 
3) O-оценки слишком грубые для отображения более тонких отличий алгоритмов, 
4) O-анализ дает слишком мало информации (или вовсе ее не дает) для анализа поведения алгоритмов при обработке небольших объемов данных.

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

Еще одна сложность - определение "среднего случая". Обычно сделать это достаточно трудно из-за невозможности предсказания условий работы алгоритма. Иногда алгоритм используется как фрагмент большой, сложной программы. Иногда эффективность работы аппаратуры и/или операционной системы, или некоторой компоненты компилятора существенно влияет на сложность алгоритма. Часто один и тот же алгоритм может использоваться в множестве различных приложений.

Из-за трудностей, связанных  с проведением анализа временной сложности алгоритма "в среднем", часто приходится довольствоваться оценками для худшего и лучшего случаев. Эти оценки по сути определяют нижнюю и верхнюю границы сложности "в среднем". Собственно, если не удается провести анализ сложности алгоритма "в среднем", остается следовать одному из законов Мерфи, согласно которому оценка, полученная для наихудшего случая, может служить хорошей аппроксимацией сложности "в среднем".

Возможно, основным недостатком O-функций является их черезмерная  грубость. Если алгоритм А выполняет некоторую задачу за 0.001*N с, в то время как для ее же решения с помощью алгоритма В требуется 1000*N с, то В в миллион раз быстрее, чем А. Тем не менее А и В имеют одну и ту же временную сложность O(N).

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

О пространственной сложности  как объеме памяти, необходимой для  выполнения программы, уже упоминалось  ранее.

При анализе интеллектуальной сложности алгоритма исследуется понятность алгоритмов и сложность их разработки.

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

Алгоритм быстрой сортировки характеризуется также и большей  интеллектуальной сложностью по сравнению  с алгоритмом сортировки вставками. Если предложить сотне людей отсортировать  последовательность объектов, то вероятнее всего, большинство из них используют алгоритм сортировки выборками. Маловероятно также, что кто-то из них воспользуется быстрой сортировкой. Причины большей интеллектуальной и пространственной сложности быстрой сортировки очевидны: алгоритм рекурсивный, его достаточно трудно описать, алгоритм длиннее (имеется в виду текст программы), чем более простые алгоритмы сортировки.

 

Практическая  часть

ВАРИАНТ 11

Задание 1

Пронумеруем реквизиты  каждого документа (Р1, Р2, Р3, Р4, Р5, P6) и установим их значность. Результаты представлены в соответствующих таблицах:

Таблица 1 – Список филиалов сбербанка

№ реквизита	Р1	Р2	P3
Наименование  реквизита	Номер филиала	Адрес	Телефон
Значность реквизита	2	25	11
Значение  реквизита	22	Улица Малахова дом 22	22-22-22
	23	Улица Хмелева дом 33	33-33-33
	24	Улица Маннаного дом 44	44-44-44
	25	Улица Чингисса дом  77	77-77-77

Таблица 2 – Справочник плательщиков

№ реквизита	Р1	Р2	Р3	Р4
Наименование  реквизита	Код плательщика	ФИО плательщика	Домашний адрес	Номера счетов для  оплаты за
				воду	газ	отопление	эл.энергию
Значность реквизита	4	30	25	4	4	4	4
Значение  реквизита	1242	Капустин  А.А	Ул.Зелёная	4201	4202	4203	4204
	1333	Шевчук Б.А	Ул.Красная	3371	3372	3373	3374
	1242	Лапшин М.Ю	Ул. Чаева	2356	2357	2358	2359

 

Таблица 3 – Список услуг

№ реквизита	P1	Р2
Наименование  реквизита	№  п/п	Название  услуги
Значность реквизита	2	15
Значение  реквизита	1	Водоснабжение
	2	Электроэнергия
	3	Отопление
	4	Газоснабжение

Таблица 4 – Квитанция об оплате услуг

№ реквизита	Р1	Р2	Р3	Р4	Р5	Р6	Р7	Р8
Наименование  реквизита	Номер филиала Сбербанка	Дата оплаты	ФИО клиента	Домашний адрес клиента	Название коммунальной услуги	Номер счета	Месяц, за который производится оплата	Сумма оплаты
Значность реквизита	2	10	30	25	4	4	2	10
Значение  реквизита	24	02.02.2011		ул. Зеленая 48 кв. 64	водоснабжение	4201	01

Определим среднюю информационную емкость документа (среднее количество символов в документе) по формуле:

, где

q_ij– количество символов в j-ом реквизите i-ого документа,

                      k_i – число строк в i-ом документе,

                      m – количество реквизитов в документе,

                      n – количество рассматриваемых документов.

 

Q = ( 2*4+2*25+2*11  +  3*4+3*30+3*25+3*4+3*4+3*4+3*4  +  4*2+4*15  +  2+10+30+25+4+4+2+10  ) / 4 =   115 символов.

 

Задание 2

 На основе анализа  информационных процессов, происходящих  в ПрО, выделить объекты ПрО  и их атрибуты, выявить  связи  (отношения) между объектами. Построить  инфологическую модель ПрО в  виде ER – диаграммы (модель «объекты – связи»).

Объекты ПрО представлены в виде таблиц 1-4,  атрибуты объектов – наименования столбцов таблиц. Инфологическая модель ПрО в виде ER – диаграммы представлена на рисунке1.

 

 1

 1

1 1

 1 

 

 м

 

                                                                               

                                                                                                                                                                                                            

                                                                                                                                               

                                                                   м                                          

 

 

 

 

Рисунок1 – ER – диаграмма ПрО «Товары»

Описание структуры атрибутов

Описание атрибутов, таблицы, Квитанция оплаты услуг представлено на рисунке 2.

 

Рисунок 2 – Атрибуты таблицы квитанция оплаты услуг

Описание атрибутов, таблицы, Список услуг представлено на  рисунке 3.

 

Рисунок 3 – Атрибуты таблицы список услуг

  Описание атрибутов, таблицы, Список филиалов Сбербанка представлено на рисунке 3.

 

Рисунок 3 – Атрибуты таблицы список филиалов Сбербанка

Описание атрибутов, таблицы, Справочник плательщиков представлено на рисунке 3.

 

Рисунок 5 – Атрибуты таблицы справочник плательщиков

3. Свойства отношений между объектами описать в виде следующей таблицы:

Свойства отношений  между оьъектами ПрО

№ п/п	Название отношения	Объекты, связанные отношением		Тип отношения
		название объекта 1	название объекта 2
1	Содержат	Список филиалов	Список услуг	функциональные
2	Предъявляет	Плательщик	Справочник плательщика	временные
3	Получает	Плательщик	Квитанция	временные
4	Выбирает	Плательщик	Список филиалов	временные

 

4. Инфологическую модель  ПрО в виде ER – диаграммы отобразить в среде реляционной БД (РБД) в виде совокупности схем отношений с указанием ключевых атрибутов:

Список филиалов Сбербанка (Номер филиала, Адрес, Телефон)

Справочник плательщика (Код плательщика, ФИО плательщика, Домашний адрес, Вода, Газ, Электроэнергия)

Список услуг (№ подпункта, название услуги)

Квитанция об оплате услуг (Номер филиала сбербанка, Дата оплаты, ФИО клиента, Домашний адрес клиента, Название коммунальной услуги, Номер счёта, Месяц за который производится оплата, Сумма платежа).

5. Для реляционной  инфологической модели БД построить  даталогичекую модель БД в  виде взимосвязанных файлов. Представить  графически формат каждой реляционной таблицы и связи между ними (рисунок 6).

 

Рисунок 6 – Схема данных

 

 

 

 

 

 

 

 

 

 

 

 

Задание 3

Предусматривается, что  к создаваемой реляционной БД будут осуществляться запросы следующего содержания (конкретные значения в  запросах могут меняться в зависимости от содержания полей записей):

а)    представить информацию о клиентах, проживающих по ул. Зелёной;

б)   вывести дату оплаты, а также адресы, телефон  кассы, в которой клиент Шевчук Б.А. уплатил за газ за январь текущего года;

в)   во вновь созданную  таблицу архив перенести информацию об оплате электроэнергии за январь месяц  текущего года.

Запрос клиентов проживающих  по улице Зелёной представлен  на рисунке 8.

 

Рисунок 8 – Запрос клиентов проживающих по ул.Зелёной

Запрос даты оплаты Шевчуком за газ за январь текущего года представлен на рисунке 9.

Рисунок 9 – Запрос даты оплаты за январь

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

Рисунок 10 – Архив оплаты

Данные запросы реализованы  в реляционной СУБД Microsoft Access.

 

Задание 4

1. Выполнить сортировку  реквизита методом турниров, простых вставок, пузырька.  

 

Код плательщика

1380

2341

1012

2643

2154

2425

1826

1117

1158

1429

1340