Эффективность алгоритмов – ключевая тема информатики, о чём говорят многие ведущие специалисты в этой области. Процитируем некоторых из них.
Дональд Кнут [1]: «На практике нам нужны не просто алгоритмы, а хорошие алгоритмы в широком смысле этого слова… Часто решить одну и ту же проблему можно с помощью нескольких алгоритмов и нужно выбрать наилучший из них».
Томас Кормен, Чарльз Лейзерсон и Рональд Ривест [2]: «Поскольку один из критериев разработки алгоритмов – их эффективность, описание всех алгоритмов включает в себя тщательный анализ времени их работы. Алгоритмы, разработанные для решения одной и то же задачи, часто очень сильно различаются по эффективности. Эти различия могут быть намного значительнее, чем те, что вызваны применением неодинакового аппаратного и программного обеспечения».
Никлаус Вирт [3]: «Требуется гораздо больше таланта, проницательности и времени, чтобы спроектировать экономную, простую и эффективную систему, нежели сложную и громоздкую».
Джон Бентли [4]: «Лень – двигатель прогресса. Хорошие программисты всегда немножко ленивы. Они сидят и ждут озарения, вместо того, чтобы воплощать в жизнь первую пришедшую им в голову идею».
Действительно, если есть алгоритм для некоторой задачи по информатике, то на этом работа не заканчивается, а только начинается. Программист стремится улучшить своё решение или найти новое. Математик, например, тоже ищет более простое доказательство теоремы. Но оно уже не будет таким же достижением, как первое. Чаще всего, когда теорема доказана, он ставит точку.
Важность понятия сложности или эффективности алгоритмов подчёркивается не только ведущими специалистами в информатике, но и авторами Федерального государственного образовательного стандарта среднего (полного) общего образования. Овладение этим понятием – одно из «требований к предметным результатам» по информатике.
Не смотря на это, в школьных учебниках оно только упоминается и довольно поздно, в параграфах о поиске и сортировке.
Однако познакомить школьников с темой эффективности алгоритмов можно намного раньше, ещё до изучения основ программирования.
Один из способов сделать это – использовать задачи на ручное выполнение алгоритма, с помощью ручки и бумаги.
Мы включаем в такие задачи два пункта. В первом пункте исходные данные небольшие и его легко решить простым перебором вариантов. Во втором пункте исходные данные значительно больше и переборное решение не срабатывает. Оно занимает слишком много времени. Школьники «вынуждены» придумывать новый алгоритм и на личном опыте, в сравнении, понимают, насколько важна эффективность алгоритмов.
Таким образом, учитель достигает максимального результата в обучении предмету, так как «ученики осознают и удерживают в памяти:
• 10% того, что читают,
• 26% того, что слышат,
• 30% того, что видят,
• 50% того, что видят и слышат,
• 70% того, что обсуждают с другими,
• 80% того, что основано на личном опыте» [5].
Приведём примеры подобных задач.
Пример 1. Кнопки. Отличник стоит перед лестницей, которая ведёт домой. Он умеет шагать на следующую ступеньку или через одну. Но местный хулиган раскидал везде большие канцелярские кнопки.
В строке записано, сколько их попало на каждую ступеньку. Отличник хочет подняться на последнюю, наступив на минимальное число кнопок. Чему оно равно?
a) 2, 1, 4, 2, 3, 1.
b) 1, 2, 3, 4, 1, 4, 2, 3, 1, 5, 4, 2.
Пример 2. Треугольники. Вы купили «Конструктор». Он состоит из палочек разной длины, которые лежат по возрастанию длин. В инструкции к нему сказано, что из любых трёх можно составить треугольник.
В строке записано, какой длины каждая палочка. Верна ли инструкция?
a) 10, 12, 17, 23, 35.
b) 9, 15, 16, 18, 19, 21, 22, 24, 30, 31, 33.
Библиографический список
- Кнут Д. Искусство программирования. Том 1. Основные алгоритмы. – М.: «Вильямс», 2006.
- Кормен, Т. Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 1999.
- Вирт Н. Преподавание информатики: потерянная дорога // Международная конференция по преподаванию информатики ITiCSE г. Аархус (Дания),24 июня2002 г.[Электронный ресурс]. URL: http://www.inr.ac.ru/~info21/texts/2002-06-Aarhus/ru.htm (дата обращения: 30.11.2016).
- Бентли Дж. Жемчужины программирования. – СПб.: Питер, 2002.
- Джонсон Дж. К. Индивидуализация обучения // Новые ценности образования: Десять концепций и эссе / Ред. Н.Б. Крылова. – М.: Инноватор, 1996. С.97–103.