На протяжении всей жизни, в учебе, на работе или в быту человек сталкивается с необходимостью решения огромного количества задач.
Для решения любой задачи надо знать, что дано и что следует получить. Для получения результатов необходимо знать способ решения задачи, т. е. располагать алгоритмом.
Алгоритм — это точная конечная система предписаний, определяющая содержание и порядок действий исполнителя над некоторыми объектами для получения искомого результата.
Исполнитель алгоритма — это субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нем перечень действий.
Исполнители бывают неформальными и формальными.
В информатике рассматривают только формальных исполнителей, которые не понимают и не могут понять смысл даваемых команд.
К этому типу относятся все технические устройства, в том числе и компьютер.
Свойства алгоритма
- Дискретность — алгоритм состоит из отдельных команд, каждая из которых выполняется за конечное число шагов.
- Детерминированность (или определенность) — при каждом запуске алгоритма с одними и теми же исходными данными должен быть получен один и тот же результат.
- Понятность — алгоритм содержит только те команды, которые входят в систему команд исполнителя, для которого он предназначен.
- Конечность (или результативность) — для корректного набора данных алгоритм должен завершиться через конечное время с вполне определенным результатом. При этом результатом может быть и сообщение о том, что задача не имеет решений.
- Массовость — алгоритм предназначен для решения не одной частной задачи, а для некоторого класса задач.
Способы записи алгоритмов
Алгоритмы можно записывать разными способами:
- на естественном языке;
- графически в виде блок-схем;
- в виде программы на каком-либо языке программирования.
Если задача имеет алгоритмическое решение вообще, то можно придумать множество алгоритмов ее решения. Критерием выбора наилучшего алгоритма является сложность алгоритма — количество элементарных действий, которые выполняет исполнитель при решении задачи, пользуясь данным алгоритмом.
Сложность алгоритма принято обозначать O(n) (читается «О большое от эн»).
Сложность алгоритма выражают в виде функции от объема входных данных.
Лучшим считается алгоритм, имеющий наименьшую сложность.
Примеры алгоритмов:
1. Уходя, гасите свет. Это алгоритм?
И постоянно добавляя и конкретизируя данное предложение, мы приходим к выводу – нет.
А как будет звучать эта фраза, чтобы её мог выполнить любой:
Уходя из помещения последним, если свет горел, выключи его. -Алгоритм
2. А вот пример из книги о вкусной и здоровой пище.
Пример приготовления теста
1. взять 200 г маргарина, пол стакана воды, 3 стакана муки
2. растопить маргарин
3. влить воду
4. всыпать муку
5. перемешать, чтобы не было комков
6. положить в холод на 30 минут
Исходные данные: 200 г маргарина, пол стакана воды, 3 стакана муки
Результат: тесто.
В этом алгоритме действия шли один за другим, мы их даже нумеровали, чтобы выполнить последовательно.
Алгоритм такого вида называется линейным в словесной форме, но могут быть линейные алгоритмы и в графической форме:
Но линейные алгоритмы встречаются в этой жизни очень редко.
Часто возникает условие, которое надо либо выполнять, либо нет.
Порядок выполнения действий будет зависеть от выполнения некоторого условия. И появляется еще одна графическая структура.
Алгоритмы с такой структурой называются разветвляющимися.
Разветвляющимся называется алгоритм, в котором порядок выполнения действий зависит от выполнения некоторого условия.