Лекция 1.

1.Понятие алгоритма. Характеристики алгоритма.

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

Первые алгоритмы – алгоритмы выполнения арифметических операций над числами, они были сформулированы узбекским математиком в 9 веке н.э. (из местечка Хорезми) по имени Аль Хорезми, от его имени в латинской транскрипции и произошел термин «алгоритм».

Пример алгоритма.

Алгоритм Умножение вещественного А на целое N , (N≥0):M=A*N

1 шаг i=0

2 шаг p=0

3 шаг если А=0 или N=0, то перейти к шагу 7

4 шаг p=p+A

5 шаг i=i+1

6 шаг если i<N, то перейти к шагу 4

7 шаг M=p

8 Шаг Конец

Разработка алгоритма. Основные этапы.

1.Определить множество входных данных алгоритма – ВХОД АЛГОРИТМА и множество выходных данных алгоритма – ВЫХОД АЛГОРИТМА.

2. Формируется интуитивная идея связи ВХОД – ВЫХОД.

3. Идея оформляется в виде последовательности инструкций – описание алгоритма.

Свойства алгоритма.

1.Как правило, у алгоритма есть вход.

2. Как правило, у алгоритма есть выход.

3.Определённость инструкций, они должны быть понятны исполнителю и допускать однозначную трактовку. В предложении 3 «или» надо трактовать как в формальной логике.

4. Выполнимость инструкций. Инструкцию исполнитель длжен выполнить за конечное время. Кнут в книге «Искусство программирования» так определяет выполнимость инструкции: если человек, вооружившись карандашом и бумагой, сможет выполнить все операции, включенные в инструкцию , пусть даже за сколь угодно большое время.

Это не означает простоту инструкции! Например, инструкция “положить Х значение, равное наибольшему вещественному числу, меньшему 1” невыполнима.

5.Конечность алгоритма (свойство алгоритма). Пример бесконечного алгоритма:

1шаг. i=0

2шаг. i=i+1

3шаг. Перейти к шагу 2.

Доказательство конечности алгоритма, пусть не очень строгое, лучше, чем отсутствие его.

6. Массовость алгоритма. Означает применимость его для различных вариантов данных, т.е. дать возможность решать целую группу задач.

Характеристики алгоритмов

Решение задачи будет более эффективным, если выбран эффективный алгоритм. Как его выбрать? Как сравнить два алгоритма? Как оценить качество алгоритма? Существует много критериев. Современный способ оценки алгоритма использует такой критерий:

Критерий качества алгоритма – нас будет интересовать порядок роста необходимых для решения задачи времени и емкости памяти при увеличении количества входных данных.

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

Например, есть n чисел: x₁, x₂,…x_n. Найти max(x₁, x₂,…x_n). Есть 2 алгоритма:

1.А1: Запоминаем r=x₁. Каждое из оставшихся чисел сравниваем с r. Если число больше r, его запоминаем в r. Затраченное время T(n)=C1*n.

2.А2: Cортируем числа по убыванию и выбираем первое. Затраченное время T(n)=C2*n².

С ростом n в 10 раз временные затраты А1 вырастут в 10раз, а в А2 – в 100 раз, т.е. А1 лучше.

Определение: Время Т, затраченное алгоритмом, как функция от размера задачи n называется временн'ой сложностью алгоритма и обозначается Т(n). Аналогично определяется емкостная сложность: количество емкости памяти, затраченное алгоритмом, как функция от размера задачи n называется емкостной сложностью алгоритма и обозначается Е(n).

Если алгоритм обрабатывает вход размера n за время Т(n)=C*f(n), то говорят,что временная сложность этого алгоритма порядка О(f(n)),т.е. временная сложность А1 порядка О(n),а А2 – порядка О(n²).

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