Алгоритмы и их свойства
💻 Информатика · 9 класс
Алгоритм и его свойства
Алгоритм — это точное и понятное предписание исполнителю выполнить конечную последовательность действий, ведущую от исходных данных к нужному результату. Рецепт блюда, инструкция по сборке шкафа, правило умножения столбиком — всё это алгоритмы. В информатике алгоритм составляют так, чтобы его мог выполнить формальный исполнитель: компьютер, робот или человек, действующий «не задумываясь».
Основные свойства алгоритма
Чтобы предписание считалось алгоритмом, оно должно обладать пятью свойствами.
| Свойство | Что означает | Если нарушено |
|---|---|---|
| Дискретность | Действие разбито на отдельные шаги, выполняемые по очереди | Шаги сливаются, исполнитель не знает, что делать |
| Понятность | Каждая команда входит в систему команд исполнителя | Исполнитель встречает незнакомую команду и останавливается |
| Определённость (точность) | Каждый шаг трактуется однозначно | Появляется выбор «как понимать» — разные результаты |
| Результативность (конечность) | Алгоритм завершается за конечное число шагов с ответом | Зацикливание, ответа нет |
| Массовость | Применим к классу однотипных задач, а не к одной | Решает лишь один частный случай |
Способы записи алгоритмов
- Словесный — обычный текст по шагам. Прост, но допускает неоднозначность.
- Блок-схема — графические блоки: овал (начало/конец), прямоугольник (действие), ромб (условие).
- Псевдокод и школьный алгоритмический язык — компактная запись, близкая к программе.
- Программа — запись на языке программирования, понятная компьютеру.
Пример: алгоритм нахождения наибольшего из двух чисел
ввести a, b
если a > b
то вывести a
иначе вывести b
конец
Здесь видны все свойства: шаги отделены (дискретность), команды понятны исполнителю, условие однозначно, число шагов конечно, а работает алгоритм для любых чисел.
Эффективность алгоритмов
Одну задачу можно решить разными алгоритмами, и они не равноценны. Эффективность оценивают по двум ресурсам: времени (число действий) и памяти (объём хранимых данных). Чем меньше операций при росте объёма данных, тем алгоритм быстрее. Например, чтобы найти число в неупорядоченном списке, придётся перебрать все элементы; а в упорядоченном — хватит деления пополам, что намного быстрее.
Частые ошибки. Путают алгоритм и программу: программа — лишь одна из форм записи алгоритма. Забывают про конечность — пишут цикл без условия выхода. Считают «понятным» то, что ясно человеку, но не входит в систему команд исполнителя.
Кратко о главном
- Алгоритм — конечная последовательность точных команд для исполнителя.
- Пять свойств: дискретность, понятность, определённость, результативность, массовость.
- Записать алгоритм можно словами, блок-схемой, псевдокодом или программой.
- Эффективность измеряют по затратам времени и памяти.
- Для одной задачи бывают разные алгоритмы — выбирают более быстрый и экономный.