Пять важных особенностей алгоритма

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

Интерпретация

Информация и представление

Информация и ее представление

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

В информатике информация понимается как абстрактное значение выражений, графических изображений, указаний (операторов) и высказываний.

В связи с информацией различают:

· ее представление или изображение (внешняя форма);

· ее значение (собственно «абстрактная» информация);

· ее отношение к реальному миру (связь абстрактной информации с действительностью).

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

Внешнюю форму изображения называют представлением (конкретная форма сообщения).

Виды представлений:

· условные знаки («сигналы»),

· произносимые слова («акустическое представление»),

· рисунки (графическое представление, «пиктограммы», «иконки»),

· последовательность символов («слова», «текст»), и т.д.

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

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

Под алгоритмом понимается способ преобразования представления информации. Слово algorithm произошло от имени аль-Хорезми - автора известного арабского учебника по математике.

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

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

· Конечность (финитность). Алгоритм должен всегда заканчиваться после конечного числа шагов.

· Определенность. Каждый шаг алгоритма должен быть точно определен.

· Ввод. Алгоритм имеет некоторое (быть может, равное нулю) число входных данных, т.е. величин, заданных ему до начала работы.

· Вывод. Алгоритм имеет одну или несколько выходных величин, т.е. величин, имеющих вполне определенное отношение ко входным данным.

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

Алгоритм должен быть практичным и хорошим с эстетической точки зрения.

Для алгоритмов важно различать следующие аспекты:

· постановку задачи, которая должна быть разрешена с помощью алгоритма;

· специфичный способ, каким решается задача, при этом для алгоритма различают:

a. элементарные шаги обработки, которые имеются в распоряжении;

b. описание выбора отдельных подлежащих выполнению шагов.

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

Примеры «почти» алгоритмов − медицинский и кулинарный рецепты.

Примеры неформальных описаний алгоритмов

1. Арифметические операции над десятичными числами.

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

2. Алгоритм Евклида для вычисления наибольшего делителя (НОД).

Постановка задачи. Пусть даны два положительных целых числа a и b, надо найти наибольший общий делитель НОД(a, b) чисел a и b.

2а. Первая версия алгоритма:

· если a = b, то справедливо НОД(a, b)= a;

· если a < b, то применяем алгоритм НОД к числам a и b - a;

· если b < a, то применяем алгоритм НОД к числам a - b и b.

Используется математическое свойство:

для любых положительных целых чисел x и y если x < y, то НОД(x, y)=НОД(y - x, x).

2б. Вторая версия алгоритма:

1. если a < b, то меняем местами значения (так, чтобы стало a ≥ b);

2. делим a на b, пусть r - остаток от деления (имеем a ≥ b > r ≥0);

3. если r =0, то b - выход;

4. положить (заменить) a на b, b на r и вернуться к шагу 2.

3. Сортировка колоды карт.

Постановка задачи. Имеется колода карт. Пусть на каждой карте зафиксировано одно натуральное число (ради простоты будем считать, что все числа попарно различны). Требуется отсортировать, т.е. упорядочить, колоду карт так, чтобы зафиксированные на картах числа образовывали монотонную (возрастающую или убывающую) последовательность.

3а. Сортировка путем предсортировки и слияния.

Заданная колода x сортируется с помощью следующего предписания:

· если x пуста или содержит одну карту, то x отсортирована;

· если x содержит более одной карты, то x разделить на две непустые колоды; отсортировать каждую из них и затем слить (объединить) эти колоды в одну отсортированную колоду.

3б. Сортировка путем вставок.

Заданная колода сортируется по убыванию с помощью следующего алгоритма, который в соответствующее место отсортированной колоды y вставляет по очереди карты, выбираемые из неотсортированной колоды x (процесс начинается с пустой колоды y).

· Если колода x пуста, то y - искомая отсортированная колода;

· если x непуста, то из x берется любая карта и вставляется в подходящее место колоды y так, чтобы в результате колода y осталась отсортированной.

Этот алгоритм применяется к уменьшающейся колоде x и увеличивающейся колоде y.

3в. Сортировка путем выбора.

Заданная колода x сортируется по убыванию по следующему алгоритму, который последовательно выбирает из x «наибольшую» карту и добавляет ее в конец колоды y (процесс начинается с пустой колоды y).

Пусть даны две колоды x и y. Пусть колода y отсортирована по убыванию, и пусть все карты из y больше любых карт из x. Колода x всортировывается в y по следующему предписанию:

· если x пуста, то y - искомая отсортированная колода;

· если x непуста, то из x выбирается «наибольшая» карта и добавляется в конец y.

Алгоритм применяется к уменьшающейся колоде x и увеличивающейся колоде у.

3г. Сортировка путем перестановки.

Заданная колода x сортируется по следующему алгоритму:

· если x содержит две соседние карты, нарушающие требуемое упорядочение, то эти карты меняются местами, после чего к полученной колоде применяется этот же алгоритм;

· если в x не встречается ни одной неупорядоченной пары соседних карт, то колода x отсортирована и тем самым является искомой колодой.

4. Алгоритм вычисления дроби (a+b)/(a-b).

Сначала вычисляем (используя алгоритмы сложения и вычитания) значения выражений a + b и a-b (все равно, последовательно или одновременно), а потом образуем частное от деления полученных результатов (используя алгоритм деления).

5. Алгоритм, распознающий, можно ли получить последовательность знаков a из последовательности знаков b посредством вычеркивания некоторых знаков.

Если a - пустая последовательность знаков, то ответом будет «да». В противном случае нужно посмотреть, не пуста ли последовательность b. Если это так, то ответом будет «нет». Иначе нужно сравнить первый знак последовательности a с первым знаком последовательности b. Если они совпадают, то надо снова применить тот же алгоритм к остатку последовательности a и остатку последовательности b. В противном случае нужно снова применить тот же алгоритм к исходной последовательности a и остатку последовательности b.

Этот алгоритм выдает двузначный результат, − «да» или «нет», т.е. он является алгоритмом распознавания свойства «быть частью данной последовательности знаков».

Хотя описание алгоритма конечно и постоянно, количество фактически выполняемых тактов - величина переменная. Это оказывается возможным благодаря итерации (алгоритмы 2б, 3б, 3в, 3г) или рекурсии (алгоритмы 2а, 3а, 5). При словесном описании итерацию часто записывают в следующей форме «Пока выполнено определенное условие, повторяй». Рекурсия - это когда поставленная задача решается с помощью решения той же самой задачи, но с несколько измененными (более простыми) параметрами.

Классические элементы описания алгоритмов

· выполнение элементарных шагов;

· разветвление по условию;

· повторение и рекурсия.

Дата добавления: 2014-01-15