Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Основные понятия и свойства алгоритма).pdf

- Параметрически-зависимые по трудоемкости алгоритмы

Это алгоритмы, трудоемкость которых определяется не размерностью входа (как правило, для этой группы размерность входа обычно фиксирована), а конкретными значениями обрабатываемых слов памяти:

(D) = (,…,) = (,…,), m =< n

Примерами алгоритмов с параметрически-зависимой трудоемкостью являются алгоритмы вычисления стандартных функций с заданной точностью путем вычисления соответствующих степенных рядов. Очевидно, что такие алгоритмы, имея на входе два числовых значения – аргумент функции и точность выполняют существенно зависящее от значений количество операций.

а) Вычисление последовательным умножением (x, k) = (k).

б) Вычисление = (/n!), с точностью до = (x, )

- Количественно-параметрические по трудоемкости алгоритмы

Однако в большинстве практических случаев функция трудоемкости зависит как от количества данных на входе, так и от значений входных данных, в этом случае:

(D) = (||D||, ,…,) = (N, ,…,)

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

- Порядково-зависимые по трудоемкости алгоритмы

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

Пусть множество D состоит из элементов (,…,), и ||D||=N,

Определим = {(,…,)}-множество всех упорядоченных N-ок из ,…,, отметим, что ||=n!.

Если (i) (j), где i, j є , то алгоритм будем называть порядково-зависимым по трудоемкости.

Примерами таких алгоритмов могут служить ряд алгоритмов сортировки, алгоритмы поиска минимума и максимума в массиве. Рассмотрим более подробно алгоритм поиска максимума в массиве S, содержащим n элементов:

Глава 3. Примеры использования алгоритмов

1. Алгоритмы в реальной жизни:

Алгоритм поглощения таблетки:

1) начало;

2) беру таблетку;

3) кладу в рот;

4) делаю глоток воды;

5) глотаю таблетку;

6) конец.

Алгоритм кипячения воды:

1) Налить в чайник воду.

2) Зажечь спичку.

3) Открыть кран газовой горелки.

4) Поднести спичку к горелке.

5) Поставить чайник на плиту.

6) Ждать, пока вода закипит.

7) Выключить газ.

2. Алгоритмы в литературе:

У лукоморья дуб зеленый;
Златая цепь на дубе том:
И днем и ночью кот ученый
Все ходит по цепи кругом:
Идет направо – песнь заводит,
Налево – сказку говорит,
Там чудеса: там леший бродит,
Русалка на ветвях сидит…

А. С. Пушкин

3. Алгоритмы в информатике:

Линейные алгоритмы

«Сбор в школу».

1. Просыпаемся

2. Умываемся.

3. Чистим зубы.

4. Делаем зарядку.

5. Одеваемся.

6. Кушаем.

7. Обуваемся и идем в школу.

8. Конец алгоритма.

Циклические алгоритмы

Если ряд чисел от 1 до 100. Нам необходимо найти все простые числа, то есть те, которые делятся на единицу и себя. Назовем алгоритм «Простые числа»

Проверяем, меньше ли оно 100.

Берем число 8.

7. Проверяем, простое ли оно.

6. Проверяем, меньше ли оно 100.

5. Берем число 2.

4. Если условие выполняется, записываем его.

3. Если да, проверяем простое ли это число.

2. Проверяем, меньше ли оно 100.

1. Берем число 1.

1

Берем число 9.

Нет, пропускаем его.

Проверяем, простое ли число.

Таким образом, перебираем все числа, до 100. Как видите, шаги 1 – 4 будут повторяться некоторое число раз.

1

Разветвляющиеся алгоритмы

Переход дороги пешеходом:

.

1. Подходим к светофору

2. Смотрим на сигнал светофора.

3. Он должен быть зеленым (это условие).

4. Если условие выполняется, мы переходим дорогу.

4.1 Если нет – ждем, пока загорится зеленый.

4.2 Переходим дорогу.

5. Конец алгоритма

4. Алгоритмы в математике:

Квадратное уравнение:

Начало алгоритма

Если дискриминант <0, то действительных решений нет.

Если =0, то одно решение.

Если >0, то два разных корня.

Если дискриминант <0, то действительных решений нет

Если =0, то одно решение

Если >0, то два разных корня

Заключение

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

«Используемые в настоящее время объемы массивов данных достигают размеров, которые еще десятилетие назад казались почти невероятными. Чем большими становятся объемы перерабатываемых данных, тем актуальнее становится задача оптимизации используемых алгоритмов, в том числе и сортировки. В то же время по-прежнему важными остаются задачи, не требующие повышения скорости алгоритмов. Например, для образовательных целей часто более важной является их простота»,
цитата Дупленко А.Г. (Сравнительный анализ алгоритмов сортировки данных в массивах // Молодой учёный – 2013 - №8 – с. 50-53.).

Список использованных источников