Файл: Понятие алгоритма, свойства алгоритма, способы представления алгоритма.pdf

Алгоритмы

Что такое алгоритм?

Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий.
Типичный пример: рецепт приготовления блюда. В отличие от алгоритма для компьютера, рецепт подразумевает некоторую свободу действий и пространство для импровизации. Компьютерный алгоритм должен быть четко описан и четко выполнен.

Программа ≠ алгоритм.
Программа существует и выполняется в компьютере и может использовать алгоритмы для реального решения задач.
Алгоритм – абстрактное понятие, описание идеи (вроде математической теории).
Нас интересует не сложность конкретной задачи, а рост сложности. Как сильно увеличится количество работы с увеличением входных данных?
Пример линейного роста: красить стену. В два раза больше площади – в два раза больше времени потребуется.
Пример нелинейного роста: поиск фамилии в телефонном справочнике. Если увеличить справочник в два раза, то время поиска не увеличится в два раза (если мы используем не глупый метод поиска от начала до конца).

Немного истории

825 г., Абу Абдуллах Мухаммед ибн Муса аль- Хорезми, ученый из Хорезма. Слово “алгоритм” скорее всего произошло от его фамилии. 1834 г., Аналитическая машина Чарльза Бэббиджа. По задумке автора является программируемым устройством для решения целого класса вычислительных задач. Ада Лавлейс описала первые программы для аналитической машины. Графиня Лавлейс считается первым в мире программистом.

Пример алгоритма: умножение сложением

a x b = a + a + a ... + a (b раз)

Абстракция – важное понятие в программировании и информатике. Алгоритм можно

рассматривать как абстрактную коробку, которая принимает данные, производит какие-то операции и “возвращает” результат.

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

Основными свойствами алгоритмов являются:

• детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;
• результативность. Указывает на наличие таких исходных данных, для которых реализуемый по заданному алгоритму вычислительный процесс должен через конечное число шагов остановиться и выдать искомый результат;
• массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа;
• дискретность. Означает расчлененность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем (компьютером) не вызывает сомнений;
• конечность. Каждое из действий и весь алгоритм в целом обязательно завершаются.