УДК 372.8

ЭФФЕКТИВНОСТЬ АЛГОРИТМОВ НА УРОКАХ ИНФОРМАТИКИ

Лялин Андрей Васильевич
Вятский государственный университет
преподаватель кафедры фундаментальной информатики и прикладной математики, магистрант кафедры прикладной информатики

Аннотация
Авторы школьных учебников по информатике только упоминают об эффективности алгоритмов и довольно поздно, в параграфах о поиске и сортировке. Но эту важную тему можно рассмотреть намного раньше. В статье мы предлагаем один из способов сделать это.

Ключевые слова: информатика, решение задач, эффективность алгоритмов


THE EFFICIENCY OF ALGORITHMS AT THE LESSONS OF INFORMATICS

Lialin Andrei Vasilievich
Vyatka State University
lecturer of fundamental informatics and applied mathematics department, master's degree student of applied informatics department

Abstract
The authors of school informatics textbooks only mention the efficiency of algorithms and rather late, in paragraphs about searching and sorting. But this important topic can be learned much earlier. In the paper we suggest one way to do it.

Keywords: efficiency of algorithms, informatics, problem solving


Библиографическая ссылка на статью:
Лялин А.В. Эффективность алгоритмов на уроках информатики // Современная педагогика. 2016. № 11 [Электронный ресурс]. URL: http://pedagogika.snauka.ru/2016/11/6313 (дата обращения: 27.05.2017).

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

Дональд Кнут [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. Кнут Д.  Искусство программирования. Том 1. Основные алгоритмы. – М.: «Вильямс», 2006.
  2. Кормен, Т.  Лейзерсон Ч., Ривест Р. Алгоритмы:  построение  и  анализ. – М.: МЦНМО, 1999.
  3. Вирт Н. Преподавание информатики: потерянная дорога // Международная конференция по преподаванию информатики ITiCSE г. Аархус (Дания),24 июня2002 г.[Электронный ресурс]. URL: http://www.inr.ac.ru/~info21/texts/2002-06-Aarhus/ru.htm (дата обращения: 30.11.2016).
  4. Бентли Дж. Жемчужины программирования. – СПб.: Питер, 2002.
  5. Джонсон Дж. К. Индивидуализация обучения // Новые ценности образования: Десять концепций и эссе / Ред. Н.Б. Крылова. – М.: Инноватор, 1996. С.97–103.


Все статьи автора «Лялин Андрей Васильевич»


© Если вы обнаружили нарушение авторских или смежных прав, пожалуйста, незамедлительно сообщите нам об этом по электронной почте или через форму обратной связи.

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

Вы должны авторизоваться, чтобы оставить комментарий.

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться: