Эффективность алгоритмов
презентация к уроку по информатике и икт (11 класс)

Слайд 1

Слайд 2

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

Слайд 3

Что такое алгоритм? Требования для понятия АЛГОРИТМ: 1. Любой алгоритм применяется к исходным данным и выдает результат. 2. Данные для своего размещения требуют память. 3. Алгоритм состоит из отдельных элементарных шагов (действий). 4. Последовательность шагов алгоритма детерминирована. 5. Каждый алгоритм должен быть результативным, т.е. после конечного числа шагов выдавать результат. 6. Следует различать: - описание алгоритма (инструкцию или программу); - механизм реализации алгоритма (устройство); - процесс реализации алгоритма. 3

Слайд 4

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

Слайд 5

Принципы и способы разработки алгоритма Системный подход – использование методов декомпозиции (нисходящее проектирование сверху-вниз ) и синтеза (программирование снизу-вверх). Методы дедукции Методы индукции: методы частных целей, подъема, отрабатывания назад и т.п. Структурное программирование: композиция, альтернатива, итерация. 5

Слайд 6

Свойства алгоритма Алгоритм – система формальных правил, четко и однозначно определяющая процесс решения поставленной задачи в виде конечной последовательности действий или операций. 6

Слайд 7

Эффективность алгоритма Эффективность программы имеет следующие составляющие: 1. Интеллектуальная сложность 2. Пространственная эффективность (память): определяется объемом необходимой памяти для выполнения программы. 3. Временная эффективность сложность - быстродействие алгоритма. Временем работы алгоритма называется количество выполненных элементарных операций T . Элементарные операции: запись значений в ячейку памяти, сравнение двух значений, арифметические операции и т.д. Функция T ( n) – Временная сложность алгоритма. 7

Слайд 8

Эффективность алгоритма Примеры целтаб A[1:n] 1. Вычислить сумму первых трех элементов массива (при n≥3) . Sum:=A[1]+A[2]+A[3] Алгоритм включает 2 операции сложения и 1 операцию записи в память. Его сложность T(n)=3 . 2 . Вычислить сумму значений всех элементов массива Sum:=0 нц для i от 1 до n Sum:= Sum + A[ i ] кц Алгоритм включает n операций сложения и n+1 операцию записи в память. Его сложность T(n)=n+n+1=2n+1. 8

Слайд 9

Эффективность алгоритма Точное количество элементарных операций, затраченных для решения конкретной задачи, зависит от размера входных данных и от самих входных данных. Понятие временной сложности алгоритма рассматривают в наилучшем, наихудшем м среднем случаях. На практике основное внимание уделяется анализу работы алгоритма в наихудшем состоянии, так как: 1. Время работы в наихудшем случае – это верхний предел этой величины для любых входных данных. 2. В некоторых алгоритмах наихудший случай встречается достаточно часто. 3. Характер поведения «усредненного» времени часто не лучше поведения времени работы наихудшего случая. При анализе сложности алгоритма оценивают поведение функции f(n) в пределе n →∞ , т.е. скорость роста времени работы алгоритма с увеличением размера входных данных. Т.е. оценивается асимптотическая сложность алгоритма . 9

Слайд 10

ПРАКТИЧЕСКАЯ РАБОТА № 1 Цель работы: Выполнить анализ эмпирической эффективности (практической сложности) методов поиска: последовательного, быстрого последовательного, бинарного. Методические указания по выполнению работы Для выполнения работы необходимо: 1. Выполнить программную реализацию алгоритмов поиска. 3. Сгенерировать исходные последовательности в зависимости от заданного размера выборки. − для генерации исходной числовой последовательности можно использовать датчик случайных чисел. – для чистоты эксперимента данные должны быть из одной сгенерированной выборки. 4. Выполнить эксперименты, в ходе которых определить время работы каждого алгоритма в зависимости от размера выборки, используя функцию time (). 10

Слайд 11

ПРАКТИЧЕСКАЯ РАБОТА № 1 Таблица 1 – Результаты удачного поиска Таблица 2 – Результаты неудачного поиска 11 Объем выборки Значение для поиска Время, сек При последовательном поиске При быстром последовательном поиске При бинарном поиске 5 10 100 250 500 600 700 800 900 Объем выборки Значение для поиска Время, сек При последовательном поиске При быстром последовательном поиске При бинарном поиске 5 10 100 250 500 600 700 800 900

Слайд 12

ПРАКТИЧЕСКАЯ РАБОТА № 1 5. Построить график зависимости времени работы алгоритма от размера выборки. 6. Выполнить анализ методов и определить самый эффективный метод в смысле быстродействия. 12

Слайд 13

ПРАКТИЧЕСКАЯ РАБОТА № 1 ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК 13

Слайд 14

ПРАКТИЧЕСКАЯ РАБОТА № 1 ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК 14 !

Слайд 15

ПРАКТИЧЕСКАЯ РАБОТА № 1 БЫСТРЫЙ ПОИСК 15 N

Слайд 16

ПРАКТИЧЕСКАЯ РАБОТА № 1 БИНАРНЫЙ ПОИСК 16