http://www.informatik.kz

Реферат по информатике

Тема: "Анализ алгоритмов".


Понятие алгоритма

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

Определение 1. Алгоритм (алгорифм) – точное предписание, которое задает вычислительный процесс, начинающийся с произвольного исходного данного и направленный на получение полностью определенного этим исходным данным результата. (Математическая энециклопедия)
 

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

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

 

Купить за СМС "Анализ алгоритмов"   Цена: 150 тг.= 1 у.е.


Назад


Rambler's Top100       Каталог Интернет ресурсов. Казахстанский интернет.   Resurs.kz: сайты Казахстана и раскрутка сайта